Common English bigrams / trigrams - recognising that a jumble of letters contain only valid English words

Question

I have a database of one million strings which I want to rank against one another so that I can tell which contain meaningful English words / sentences.

These strings contain no spaces or punctuation. Some contain real English words:

THISISASENTENCETHATCONTAINSENGLISHWORDS

Some are a jumble of random letters:

IHWEIONMSACOMDSCKNENCIJNCDSKMCDJCSJDNJL

Currently I use an updated Mayzner letter frequency list, and I count for occurrences of most common tri/bigrams in the above strings.

["th","he","in","er","an"], // Mayzner most common 2grams
["the","and","ing","ion","tio"] // Mayzner most common 3grams

The first string contains more occurrences of these ngrams, so would rank above the second string in terms of its Englishness.

The above method works OK but I want to improve it.

Here are some of the improvements I've looked into:

• Vowel to consonant ratio.
• Vowel and consonant positions within string.
• Letter positions / relation to one another. e.g. The bigrams: JQ, QG, QK, QY, QZ, WQ, and WZ, should never occur in the English language.
• Dictionary search (i.e. match most commonly used words from an English dictionary)
• E,T,A,O,I,N being the most occurring letters, in this order.

What are the most important factors for determining whether a string contains English words? Maybe it would be a combination of these?

Answer 1

Note: I am a little confused on exactly what the OP means by "similar" and if they want to find English-like strings or actual English strings. I may need to edit my response once they provide clarification

This is the type of feature where the question isn't "how accurate can I make it?" but rather "how good is good enough?" as some of the methods will be easier to implement and more efficient to run than others. Also, there's a very big difference between identifying English-like words and identifying English words so I'm going to break my answer into two parts.

Finding English-like Text

For this purpose, your bigram/trigram probability method is probably satisfactory. If you haven't researched it already, there are plenty of online resources for teaching people how to compute probabilities from bigrams. Here's a set of lecture notes I randomly found on Google. If you find you're getting a lot of strings with a probability of 0 then you should look into using some kind of n-gram smoothing technique but this is probably less important with letter-based n-grams than with word-based n-grams.

However, I see one major problem with using off-the-shelf probabilities, like the Mayzner frequency list you're currently using: n-grams do not cross word boundaries. You correctly say that bigrams like "WZ" never occurs word-internally in English, thus any "WZ" bigram would be assigned a probability of 0 (and thus the probability of the entire string by Naive Bayes). Problem is that there's nothing stopping them from occurring across word boundaries. For example, the sentence "I don't care how Zoe feels" is obviously English but if you remove spaces, punctuation, and capitalize everything you get "IDONTCAREHOWZOEFEELS" which does contain the bigram "WZ".

One possible solution would be to calculate your own probabilities by taking a large corpus of text, like the Brown Corpus, processing the text so that it is a continuous string of capital letters, and then using that to calculate your own probabilities. See here if you need help implementing this.

You also mention about using consonant/vowel ratios and individual letter frequencies to improve your result. You may not realize it but what you're describing is Katz's back-off model which uses trigram, bigram, and unigram probabilities to evaluate text.

Finding Actual English Text

You used the word "rank" in your question so I think these methods may not be what you want since they will tend to return more of a "yes/no" answer than a probability. That isn't to say you can't adapt them to give a probability but it may be difficult.

The first question is do you want to find which strings contain and English word or which string are entirely English. To illustrate the difference, think about which of these two you'd rank higher:

ORANGES
QAPPLEQ

Finding strings which contain an English word is conceptually very easy but requires a lot of time and computing power. You'd simply search for ever word in an English dictionary in every string. One major problem is that there are a lot of English words. If you narrow your search down to the top 3000 or so most common English words then your speed increases but your accuracy drastically decreases. Another problem is that there are single-letter words in English ("a" and "I") that, unless excluded from the word list, would mean the vast majority of strings contain an English word.

If you want to find which strings actually are English then you should focus on identifying word boundaries in text (as opposed to in spoken language). The good news is that there has already been research on on this problem. The bad news is that the existing research generally doesn't focus on English. I have found articles explicitly about identifying word boundaries in Thai text and in Chinese Text. These languages generally do not use white spaces so finding methods to break text into individual words is very important for any kind of computational linguistic analysis. Unfortunately, both these papers seem to use statistical methods so I'm not sure how applicable they are to English text (since the required statistics may not be readily available). You may also want to read this Stackoverflow question about identifying word boundaries in Japanese, but again you have a hard time applying this to your situation.

I have found this patent for identifying word boundaries in continuous text (which is exactly what you'd need) but being a patent, you may need to license this technology before you can be allowed to use it (even for non-commercial uses).