Counting English words in a random string

Question

Suppose I have a randomly generated string s=t&^%JHGgfdteam*&HGEdfg, what is the best approach to count the number of English words in that string? (English words as defined in some dictionary file). Obviously brute-force is not a good idea... would a suffix-tri e work? Binary search? Notice that in the case of s, there are two words: "tea" and "team". Any ideas? Regards

Answer 1

I would load the dictionary words in a Trie structure, then read the string from left to right and check if the substrings are in the trie. If they are and there are children, keep going. If they happen to be a leaf or a valid word, add to the occurence count.

In pseudo code:

Trie dict = ... // load dictionary
Dictionary occurences = {}

for i in length(string):
    j = i + 1
    # think of partial as string.Substring(i, j);
    while dict.hasChildren(partial):
        j++ 
        if isWord(partial):
            dict[partial]++

This way you'll guarantee it doesn't miss a match while still looking for all possibilities.

You can limit the minimum length of the valid words by changing what j is initialized to or by rejecting short words in the isWord() method (so a wouldn't be a "valid" word).

Answer 2

The Aho-Corasick string matching algorithm builds the matching structure in time linear in the size of the dictionary and matches patterns at time linear in the size of the input text + number of matches found.