Word Search Algorithm

Sorting networks. Look ''em up (they''re usually hard-coded for numeric sorting though). You can often get better average performance by making guesses on adjacency distribution and searching for letter pairs. Say you wished to search for "DAVE" in the aforementioned matrix, you''d search for adjacent occurences of "DA", "AV" and "VE". Depending on which was found, you''d then search either the preceding on proceding matrix cell for the next letter in the sequence.

For larger matrices and words, you''d want to perform such adjacency searches on letter pairs that statistically show up next to each other more frequently (which could be determined by analyzing a few thousand inputs). You''d isolate occurences of these "high frequency" pairs in words and search for them first, and proceed from there.

This is nothing but a string compare. Boyer/Moore can be used for this.

BTW, it seems like you would want to search for the characters in your string first that would *least* likely occur in the matrix. If you had a 26 entry table that represented each letter in the alphabet, then put in this table the number of times each character occurred in the matrix you could use this to determine if there are characters in your test string that did occur at all in the matrix just by doing an array lookup. If every character in your test string was also in the matrix, then you''d start by using the character that occurred the fewest times in the matrix.

Cool, thanks.

I'll see what I can find on sorting networks and Boyer/Moore.

The brute force method isn't harming performance too bad right now, I was more curious than anything.

I don't expect the matrix to get bigger than 30x30 letters, so even on older machines I doubt the search algorithm will take up much CPU time.


[edited by - caffeine on June 16, 2002 12:59:12 AM]