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

Hi all, I am doing a script to change some values from one database table to another.
My problem is this:

The values that i have to move are _valid_ USA States that people put in the database ( they wrote it from a web page ), but i need to check if the state is valid, a state is valid if it was write correctly, for example
New York or NY

So far i have everything done, but i want to make text match with similar text, so if i have
Ner Yorh, i need it to match with New York, so my question is if there is some module to match _similar text_, something like google does when you put something wrong and it says 'Did you mean: .......'.
Anyone knows a module or something to do this.

___________________________________________
 Optimus magister, bonus liber

Replies are listed 'Best First'.
Re: Match similar text
by Limbic~Region (Chancellor) on Sep 06, 2003 at 23:53 UTC
    shadox,
    Take a look at this node posted yesterday, though Text::Levenshtein is usually the standard answer.

    I would do something like the following:

  • Set a maximum threshold, so if the closest match exceeded this threshold it would be set aside for human interaction
  • Iterate over each state calculating the similarity distance and select the shortest distance
  • Set aside for human interaction any match between two states that was close, perhaps only by a distance of 1
  • Write a log for changes until you feel confident/comfortable it is doing the right thing

    Cheers - L~R

[reply]
      In conjunction w/ that, the person might want to get all distinct mispelled states and update them at once. If his DB is big, say 6mil rows, it'd be 6mil selects, and 1 update for every misspelled row, vs 1 select on a 6 million row table and 1 update for each misspelling.

      Maybe the person already does this, but might as well be obvious :)
      --
      Play that funky music white boy..

[reply]
Re: Match similar text
by Chainsaw (Friar) on Sep 06, 2003 at 23:57 UTC
    An option to do this is to quit all the conflictive's letters and make a match by the result of quit all that conflictive letters from the source and the query.

    Once you do this can make a list of all the possibilities.

    For Example if you want to parse Connecticut will be like

    Query
    Conecticut --> Coecticut

    Source
    Connecticut --> Coecticut

    But be sure to select the right conflictive letters to discriminate. And I'll do the same to the repetitive letters like "nn" in Connecticut or "ss" and "pp" in Mississippi.

    God help me always to see the other face of the coin. And prevent me from accusing of betrayal those who don't think just as I do.
[reply]
Re: Match similar text
by shadox (Priest) on Sep 07, 2003 at 20:55 UTC
    I has been doing some research and benchmarking today and these are my conclusion ( so far ), i did try with 3 difetents methods:

    Chainsaw's
    String::Aprox
    String::Similarity

    My choise at this moment is String::Similarity, why?
    Well first have a look at this benchmark: 
    Benchmark: timing 1000000 iterations of String::Aprox, String::Similar
+ity, Chainsaw...
String::Aprox:  5 wallclock secs ( 3.70 usr +  0.02 sys =  3.72 CPU) @
+ 268889.49/s
(n=1000000)
String::Similarity:  7 wallclock secs ( 7.38 usr +  0.00 sys =  7.38 C
+PU) @ 135593
.22/s (n=1000000)
Chainsaw: 15 wallclock secs (14.16 usr +  0.02 sys = 14.17 CPU) @ 7056
+6.65/
s (n=1000000)

    [download]

    In the benchmark i just called functions which did the basic operation of each solution.
    Even when String::Aprox is fastest it doesn't make all the matchs that String::Similariy does, Chainsaw aproach does well with some matches but it is the slowest and some matches didn't come up
    I just wanted you to know :)
    My answer to my very own question would be:

    Use String::Similarity

    But i will continue testing.....
    ___________________________________________
     Optimus magister, bonus liber
[reply]
[d/l]
Re: Match similar text
by genecutl (Beadle) on Sep 08, 2003 at 20:58 UTC
    Try using soundex. These algorithms simplify words so that differently spelled words that are pronounced similarly will get the same soundex code:

    Text::Soundex
    This module implements the soundex algorithm as described by Donald Knuth in Volume 3 of The Art of Computer Programming. The algorithm is intended to hash words (in particular surnames) into a small space using a simple model which approximates the sound of the word when spoken by an English speaker. Each word is reduced to a four character string, the first character being an upper case letter and the remaining three being digits.

    Text::Metaphone
    Metaphone() is a function whereby a string/word is broken down into a rough approximation of its english phonetic pronunciation. Very similar in concept and purpose to soundex, but much more comprehensive in its approach.

[reply]
Re: Match similar text
by pboin (Deacon) on Sep 08, 2003 at 13:46 UTC
    First thing I'd suggest is to do what you can to stop more bad entries. Make sure to implement validation of one kind or another so this is a one-time problem.

    Then, if it were me (it's not, but play along), I'd follow Sport's suggestion, and do a one-time select on unique state values, then find the mis-spellings you have, and make appropriate update statements.

    It's low-tech, but there's definitely a time and place for that. This should be a one-timer.

[reply]

Back to Seekers of Perl Wisdom