Any computer science geeks?

[dsr at tao.merseine.nu (dsr at tao.merseine.nu)]

On Thu, May 18, 2006 at 09:06:01AM -0400, markw at mohawksoft.com wrote:
> While I like to think I'm no slouch in this department, I'd like to see if
> anyone has a better idea:
> 
> You have two strings and you want to quantify how similar they are.
> 
> "Tom Lehrer - The Was The Year That Was" and "That Was The Year That Was -
> Tom Lehrer"
> 
> (2) Levenshtein Distance is an N^2 algorithm and, well, yuck.
> 
> Anyone have any ideas? I currently using an n^2 algorithm that scans
> through both strings and used run length matching, but if you know of
> something better, I'd love to hear it.

I don't have anything faster, but you could, for example, apply
SOUNDEX to each word, sort the result, and count how many were
the same.

You'll probably want an enhanced SOUNDEX... see
http://www.creativyst.com/Doc/Articles/SoundEx1/SoundEx1.htm

-dsr-