Calculating probability that a string has been randomized? - Python

Question

this is correlated to a question I asked earlier (question)

I have a list of manually created strings such as:

lucy87

gordan_king

fancy_unicorn77

joplucky_kanga90

base_belong_to_narwhals

and a list of randomized strings:

johnkdf

pancake90kgjd

fancy_jagookfk

manhattanljg

---

What gives away that the last set of strings are randomized is that sequences such as 'kjg', 'jgf', 'lkd', ... .

Any clever way I could separate strings that contain these apparently randomized strings from the crowd?

I guess that this plays a lot on the fact that certain characters are more likely to be placed next to others (e.g. 'co', 'ka', 'ja', ...).

---

Any ideas on this one? Kylotan mentioned Reverend, but I am not sure if it can be used fr such purpose.

Help would be much appreciated!

Answer 1

This is just a thought. I've never tried it myself...

Build a bloom filter from hashing every (overlapping) 4-letter sequence found in a dictionary. Test a string by counting how many 4-letter sequences in the string don't hit the filter. The more misses, the more likely it is that the word contains random junk.

Try tuning the size of the bloom filter and the number of letters per sequence.

Also note (thanks @MihaiD) that you should include a dictionary of names, preferably from multiple languages, in the bloom filter to minimise false positives.

Answer 2

What scores do you get if you run the strings through something like textcat? (I've seen a few different implementations of TextCat; maybe there's a Python one already out there; if not it's not a hard algorithm -- it's the data that's important.)

I'm thinking that if you strip the numbers out, the first set of strings will be closer to the "English" result in TextCat than the ones with random stuff in them.

How much closer and whether you might be able to use the TextCat data -- which is fundamentally based on which letters tend to be next to each other in particular languages -- to "pass" or "fail" a string is going to need some experimentation, though...