6

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?

  • 3
    Wow. What an interesting question. – Kit Z. Fox Mar 22 '13 at 1:03
  • For clarification, you have a million [effectively] random strings and you want some way to say which are more similar to English than others? Or are you trying to identify which strings contain English words? – acattle Mar 22 '13 at 1:23
  • @acattle I have 1 million strings, maybe 5 of those strings contain meaningful English words and the rest are just a jumble of incoherent letters. I need some way of extracting those 5 strings by identifying which contain actual English words. – StuR Mar 22 '13 at 10:49
4

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).

| improve this answer | |
  • That patent uses candidate words to test for word boundaries, so it is in effect just a dictionary search. Katz's back-off model is very interesting however, and is along the lines of what I feel I need to implement. – StuR Mar 22 '13 at 11:53
  • @StuR I've been having a think. A dictionary search, while not exactly efficient, might not be too impossible. If you can binary-search the dictionary then it's O(n*lg(m)*p) where n is the length of the strings, m is the number of words in the dictionary, and p is the number of strings you're checking. Using a probabilistic model will be at least O(n*p). – acattle Mar 22 '13 at 13:01
  • Well I tried it with a dictionary of ~17,000 words (disregarding words of length < 2), 17 billion iterations. But my little MacBook wasn't up to the challenge and I gave up after 5 hours! It may well be the most accurate method though. – StuR Mar 22 '13 at 15:05
  • 2
    If you pour the dictionary into a trie structure, it will speed up each search tremendously. en.wikipedia.org/wiki/Trie – sea-rob Mar 22 '13 at 15:17
  • @StuR What programming language are you using? You might check into the D programming language. How far did you get in 5 hours? – Mark D May 30 '13 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.