Search for similar strings

Sanjay has asked for the wisdom of the Perl Monks concerning the following question:

Need to search for similar strings in a large text file - detects distortions, e.g. get lists like "New York", "Newyork", "Neww York", "Few York", "Ewe Pork", etc.

Like to get frequencies: "New York" {67}, "Neww York" {12}, ... assuming 67 occurrences of "New York" in the file

Like to get line numbers where occurring: ... "Neww York" {2 - 12,144} ... assuming this string occurring on lines 12 & 144

Handle matches not starting on word boundary: "Anew York" matches "New York". "Anew York" would probably have its own separate list (can we link across lists?)

NOTES:

1. Minimum length of string should be a parameter.

2. How much distortion to tolerate? i.e. depending on distortion accommodated, "hello" may match "goodbye".

3. Probably would have to be broken down into separate scripts!

4. Flexible on output format

Comment on Search for similar strings - to standardise

Replies are listed 'Best First'.
Re: Search for similar strings - to standardise by zentara (Archbishop) on Oct 30, 2009 at 11:46 UTC
maybe off-by-one string comparison is a start I'm not really a human, but I play one on earth. Old Perl Programmer Haiku	[reply]
Re: Search for similar strings - to standardise by planetscape (Chancellor) on Oct 30, 2009 at 16:02 UTC
I would begin by Super Searching for edit distance. word similarity measure and Creating Dictionaries may also be helpful, as may be the work of Ted Pedersen, in particular, his Ngram Statistics Package. HTH, planetscape	[reply]
Re: Search for similar strings - to standardise by Rival (Acolyte) on Oct 30, 2009 at 16:15 UTC
For the string comparison, using the Levenshtein distance is probably your best bet. This is often used in spell-checking to suggest corrections. For implementations, there is a Text::Levenshtein module on CPAN. But also, take a look at this node and this node.	[reply]
Re^2: Search for similar strings - to standardise by educated_foo (Vicar) on Oct 31, 2009 at 03:33 UTC
Edit distance would be useful for comparison, but not so much for clustering strings with their common misspellings. For that, you might try n-grams (mentioned above) or locality-sensitive hashing (basically the same thing, but with gaps).	[reply]
Re: Search for similar strings - to standardise by chaos_cat (Scribe) on Oct 30, 2009 at 13:52 UTC
I haven't used it personally, but it sounds like (ha ha) you could get some mileage out of a soundex (or similar algorithm) match. CPAN turned this up: Text::Soundex You might also want to look into stemming algorithms --cc	[reply]
Re^2: Search for similar strings - to standardise by afoken (Chancellor) on Oct 31, 2009 at 08:10 UTC
Soundex is designed especially for comparing names commonly found in the USA, using mechanics instead of computers. Any other use is at least problematic: It does not work to well with non-english names and words, simply because it groups consonants that share a similar sound IN ENGLISH. In other languages, those consonants often sound completely different. Vowels (except for a possible first one) are completely removed, so soundex removes too much information, especially in non-english languages. And, to make things worse, soundex cuts off after the first few characters. This is fine for english where the most common words and names have just one or two syllables. Other languages have more syllables per word, and so soundex returns just junk. Example: D535 is the soundex code for both "Donaudampfschifffahrtsgesellschaft" (german: Danube steamboat shipping company -- a common stem for ridiculously long compound words) and "Donaudampfschiffkapitän" (german: Danube steamboat capitain), two things that are hardly the same. Of course, this example is made up, but from some tests in old times I know that soundex does not work for german names. It simplyfies wrong and it simplyfies too much for the german language. A second problem for soundex are "s", "sch", "ch", and "sh". Those letter combinations are spoken very differently in german, but soundex treats them all equal. This generates many false positives in german. Both "Schiff" (ship) and "Siff" (slang for dirt) share the same soundex code S100. Another problem occurs with the french language. The last few letters are often silent, but soundex treats them like all other letters. So, "chevaux" (horse power) gets a soundex code of C120, but the "x" is silent, and "au" sounds like "o". So, the soundex code should better be C100 (like "chevo"). A problem shared for several languages including french and german are modified letters, like the german umlauts (äöüÄÖÜ), the german sharp S (ß), accented letters found in several european languages (like à, é, ë, ç), and so on. Soundex is simply not defined for those letters. It depends on the implementation how those letters are treated. They could be removed, they could be replaced by unaccented letters (àéëc => aeec), they could be replaced by replacement sequences (é => ee, ä => e), they could end up unmodified in the soundex code (Kä20). Alexander -- Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". ;-)	[reply]

Back to Seekers of Perl Wisdom