rrenaud/gibberish-detector

A small program to detect gibberish using a Markov Chain

Overview

A sample program I wrote to detect gibberish. It uses a 2 character markov chain.

http://en.wikipedia.org/wiki/Markov_chain

This is a nice (IMO) answer to this guys question on stackoverflow. http://stackoverflow.com/questions/6297991/is-there-any-way-to-detect-strings-like-putjbtghguhjjjanika/6298040#comment-7360747

Usage

First train the model:

python gib_detect_train.py

Then try it on some sample input

python gib_detect.py

my name is rob and i like to hack True

is this thing working? True

i hope so True

t2 chhsdfitoixcv False

ytjkacvzw False

yutthasxcvqer False

seems okay True

yay! True

How it works

The markov chain first 'trains' or 'studies' a few MB of English text, recording how often characters appear next to each other. Eg, given the text "Rob likes hacking" it sees Ro, ob, o[space], [space]l, ... It just counts these pairs. After it has finished reading through the training data, it normalizes the counts. Then each character has a probability distribution of 27 followup character (26 letters + space) following the given initial.

So then given a string, it measures the probability of generating that string according to the summary by just multiplying out the probabilities of the adjacent pairs of characters in that string. EG, for that "Rob likes hacking" string, it would compute prob['r']['o'] * prob['o']['b'] * prob['b'][' '] ... This probability then measures the amount of 'surprise' assigned to this string according the data the model observed when training. If there is funny business with the input string, it will pass through some pairs with very low counts in the training phase, and hence have low probability/high surprise.

I then look at the amount of surprise per character for a few known good strings, and a few known bad strings, and pick a threshold between the most surprising good string and the least surprising bad string. Then I use that threshold whenever to classify any new piece of text.

Peter Norvig, the director of Research at Google, has this nice talk about "The unreasonable effectiveness of data" here, http://www.youtube.com/watch?v=9vR8Vddf7-s. This insight is really not to try to do something complicated, just write a small program that utilizes a bunch of data and you can do cool things.

gibberish-detector's Issues

Incompatible with Python3

Some of the functions are incompatible with Python3 like xrange.
Probably add python3 compatible files in separate folder in repo

Can I make this model addaptable for words I want by adding text in big.txt ?

It is giving gibberish for word "ok", cn anyone please help me regarding this

Threshold selection

Threshold selection only uses two very small datasets. Is this method too simple? Is there a more appropriate way to select the threshold?

Repetition Detection needed--Vowel/Consonant Algorithm good

I would greatly appreciate it if you could devise some code for the case of "the the the the the the the the the a a a a a" I will send you a small donation if you can effectively solve this problem.

Python -> JavaScript port

Hello 👋
I want to say thanks for the job you did!
I created a line-by-line port of Gibberish-Detector in JavaScript and it is also published in NPM. Would appreciate review or any suggestions. Additionally I'd like to ask if it's possible and appropriate to refer from your README back to my implementation?

log probabilities?

Thanks for your code, I learn a lot, but I have a question, like following.
change

for i, row in enumerate(counts):
        s = float(sum(row))
        for j in xrange(len(row)):
            row[j] = math.log(row[j] / s)

to

for i, row in enumerate(counts):
        s = float(sum(row))
        for j in xrange(len(row)):
            #row[j] = math.log(row[j] / s)
            counts[i][j]=math.log(row[j]/s)

yes?
Thanks again.

Licence missing

Hi!

Is it possible to include a licence for this repository? Without a licence, it defaults to all rights reserved and cannot be incorporated into other software.

Thanks!

big.txt

Thanks for this code.
I'm curious, where does big.txt come from?
Is there a specific set of datasets you combined to get it?

Video link needs an update

Peter's talk can be found at https://youtu.be/yvDCzhbjYWs, the current link doesn't work for me.

Output Gibberish part of Input

Hello, and thank you for writing this fantastic program!

Do you think there could be a way for this program to output parts of the input that are gibberish, while leaving out the parts of the strings that "make sense" based on its model, instead of simply answering "True" or "False"? Or simply highlight the gibberish parts in some way?

If this was made possible, any string could be parsed to have gibberish parts deleted out. Would be a good way to sanitize a lot of file content that's meant for human reading but has junk strings in it for whatever reason.

Thanks again for writing this in the first place. I think you could expand this project to become something majorly useful. Who wouldn't want to be able to detect gibberish in their strings! I would love to contribute to this project, and I have recently started learning Python so hopefully I can someday, but I tried to understand your code and am too much for a noob yet to do it unfortunately.