[thelist] Phone Number Word Permutation Algorithm

[Matt Warden]

On Tue, Dec 2, 2008 at 12:55 PM, Fred Jones <fredthejonester at gmail.com> wrote:
>> Sorry, I completely missed the boat on the solution. Here's what you
>> should look into. Convert each word in your English database to its
>> number pad equivalent. Then perform the number search on that column.
>
> I thought about that, but if I use my suggested approach, then the
> varchar comparison is a simple equality comparison and I am uncertain
> if doing a string equality will be significantly faster than a
> numerical one.

Fred, that is likely slightly faster, but this is not really the point
of the suggestion. Let me try to explain.

You have a search key which is a number. For each digit in the number,
there are 3 possible character values. This is the crux of your
problem, because your search space increases dramatically due to this
expansion. You avoid this issue completely by performing a
"compression" on the word list itself, such that this digit->character
expansion of the search key is no longer necessary.

Think of the number of searches you will need to perform if you search
by number strings vs if you search by character strings. For a 7 digit
number, your search space is the following:

1234567
123456
12345
1234
123
234567
23456
2345
234
34567
3456
345
4567
456
567

That's it. That is very manageable and a drop in the pond compared to
the search space if you convert those numbers to all the possible
permutations of character equivalents.

-- 
Matt Warden
Cincinnati, OH, USA
http://mattwarden.com


This email proudly and graciously contributes to entropy.