Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.php > #16672

Re: Fuzzy searching inside a MySQL DB

Show key headers only | View raw

Mike Mellen wrote:

> On 3/21/2016 2:09 PM, bit-naughty@hotmail.com wrote:
>> On Friday, March 18, 2016 at 1:57:30 AM UTC+5:30, Mike Mellen wrote:
>>> Would the Soundex() function do what you need?
>>
>> .....sorry, what's Soundex exactly? It definitely *sounds* familiar, I'm
>> sure I've read of it somewhere......?
>
> Soundex is an algorithm that reduces a word or phrase to a string of
> letters and numbers that represent its phonetic sound. Similar sounding
> words (there, their, and they're, for example) all produce the same
> soundex string. mySQL has a soundex() function:
> 
> select last_name,emp_ID from employees where soundex(last_name) =
> soundex(search_string);
> 
> would find all employees whose last names "sound like" the search
> string. For example, entering "Smith" as the search string would match
> Smith, Smithe, Smyth, etc.

Note that Soundex was designed for *English* pronunciation and therefore 
works best with English words (although not-too-bad results with another 
Germanic language, German, have been reported; doubtless due to the 
similarities in *some* words – German is my native language).  In any case, 
it only is designed for *proper* words that can be *pronounced*, not 
something like “sunflow3r” (example from the OP).  I think it is a happy 
coincidence that soundex('sunflow3r') returns 'S514' the same as 
soundex('sunflower').  For example, soundex('sunf10w3r') – a common 
Leetspeak modification – already returns 'S516'.  soundex('$unf10w3r') then 
returns 'U516' because Soundex simply *ignores* the "unpronounceable" “$” 
the same as it *ignored* the “3” in the previous example and in the proper 
word the “e” before the “r” is not emphasized (UK: [ə]; US: [ɚ]).

metaphone() is more accurate for English words than soundex(), but worse 
with other natural languages (which is why there are separate 
implementations of algorithms for Brazilian Portuguese, Spanish, Bangla, 
Amharic, Russian, and German).  And it still would not calculate “sunflow3r” 
as similar to “sunflower” because the former cannot be pronounced similarly 
or at all.  metaphone('sunflow3r') returns 'SNFLR', while 
metaphone('sunflower') returns 'SNFLWR'.

For that kind of comparison, you should use levenshtein() or similar_text() 
instead.


levenshtein() implements the Levenshtein distance algorithm: The L. distance 
between two strings is the minimum number of additions, replacements, or 
deletions that are required to transform the first string into the second 
one.  Thus, the Levenshtein distance between “sunflow3r” and “sunflower” is 
1, and between “sunburn” and “sunflower” is 6:

  0. sunburn
  1. sunfurn     (replacement)
  2. sunflrn     (replacement)
  3. sunflorn    (addition)
  4. sunflowrn   (addition)
  5. sunflowern  (addition)
  6. sunflower   (deletion)

IOW, “sunflow3r” is more similar to “sunflower” than “sunburn” because you 
only need to replace one character to transform the first to the second one.


similar_text() is described, but not well referred to, in the PHP manual.
A summary of the underlying algorithm can be found via

<https://books.google.com/books?id=e7D-mITABmEC&pg=PT501&lpg=PT501&dq=%22ian+oliver%22+%22programming+classics%22+similar_text&source=bl&ots=oavkzNrqVv&sig=1SY1by3i68vvjwo3J-suMv29Af0&hl=hu&ei=jGMfTPKUGN-XOMbWrfsL&sa=X&oi=book_result&ct=result#v=onepage&q=%22ian%20oliver%22%20%22programming%20classics%22%20similar_text&f=false>

(it does not matter if you use books.google.com, .hu, .ch, or whatever) 
which I have found in <http://stackoverflow.com/a/3084791/855543> via a 
Google search for the mentioned book title (so please give that guy an 
upvote, too).

It might be a good idea to run the return values of soundex() or metaphone() 
through levenshtein() or similar_text().  soundex() and metaphone() can only 
give you a canonical representation of the word, while levenshtein() and 
similar_text() can give you a *quantitative* idea *how similar* two strings 
are; in this case then, *how similar* the representations of the words are.  
(The Levensthein distance and Similar Text distance between the 
representations of two exactly similar sounding words is 0.)

  [Note that the functions named above were also listed explicitly in the 
   Study Guide for the Zend PHP 5.3 Certification in the “String functions” 
   section in 2014, and in the Study Guide for the ZCE PHP (5.4) 
   Certification in 2015.  I cannot be sure (because I am not going to buy 
   it), but I think it is likely that they are still listed there in the
   Study Guide for the PHP 5.5-based exam.  So you should know them if you 
   decide to take the exam.]

Also note that the performance of the application is probably improved if 
the comparison algorithm is written in the query language as suggested, if 
necessary as a stored function, instead of in PHP, as then you only have to 
fetch matching records (instead of all of them).  MySQL does not have a 
built-in Levenshtein distance implementation, but this wheel has been 
invented already; STFW.

-- 
PointedEars
Zend Certified PHP Engineer 
<http://www.zend.com/en/yellow-pages/ZEND024953> | Twitter: @PointedEars2
Please do not cc me. / Bitte keine Kopien per E-Mail.

Back to comp.lang.php | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Fuzzy searching inside a MySQL DB bit-naughty@hotmail.com - 2016-03-17 10:16 -0700
  Re: Fuzzy searching inside a MySQL DB Jerry Stuckle <jstucklex@attglobal.net> - 2016-03-17 13:34 -0400
  Re: Fuzzy searching inside a MySQL DB "R.Wieser" <address@not.available> - 2016-03-17 18:37 +0100
  Re: Fuzzy searching inside a MySQL DB Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2016-03-17 14:53 -0400
    Re: Fuzzy searching inside a MySQL DB Dr Eberhard Lisse <nospam@lisse.NA> - 2016-03-22 16:35 +0200
  Re: Fuzzy searching inside a MySQL DB Mike Mellen <mmellen@intellikey.com> - 2016-03-17 16:27 -0400
    Re: Fuzzy searching inside a MySQL DB bit-naughty@hotmail.com - 2016-03-21 11:09 -0700
      Re: Fuzzy searching inside a MySQL DB Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2016-03-21 14:22 -0400
      Re: Fuzzy searching inside a MySQL DB "R.Wieser" <address@not.available> - 2016-03-21 19:24 +0100
      Re: Fuzzy searching inside a MySQL DB Mike Mellen <mmellen@intellikey.com> - 2016-03-21 14:30 -0400
        Re: Fuzzy searching inside a MySQL DB Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-03-21 23:04 +0100
          Re: Fuzzy searching inside a MySQL DB bit-naughty@hotmail.com - 2016-03-22 00:31 -0700
            Re: Fuzzy searching inside a MySQL DB Mike Mellen <mmellen@intellikey.com> - 2016-03-22 10:15 -0400
              Re: Fuzzy searching inside a MySQL DB Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-03-22 21:53 +0100
                Re: Fuzzy searching inside a MySQL DB Mike Mellen <mmellen@intellikey.com> - 2016-03-23 13:26 -0400
                Re: Fuzzy searching inside a MySQL DB bit-naughty@hotmail.com - 2016-03-25 00:03 -0700
                Re: Fuzzy searching inside a MySQL DB Mike Mellen <mmellen@intellikey.com> - 2016-03-25 11:52 -0400
                Re: Fuzzy searching inside a MySQL DB Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-03-25 19:26 +0100
                Re: Fuzzy searching inside a MySQL DB Mike Mellen <mmellen@intellikey.com> - 2016-03-25 15:51 -0400
                Re: Fuzzy searching inside a MySQL DB Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-03-25 21:52 +0100
                Re: Fuzzy searching inside a MySQL DB Jerry Stuckle <jstucklex@attglobal.net> - 2016-03-25 20:20 -0400
                Re: Fuzzy searching inside a MySQL DB Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2016-03-25 12:11 -0400
                Re: Fuzzy searching inside a MySQL DB Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-03-25 08:49 +0100
                Re: Fuzzy searching inside a MySQL DB gordonb.3vp6x@burditt.org (Gordon Burditt) - 2016-03-26 13:44 -0500
                Re: Fuzzy searching inside a MySQL DB bit-naughty@hotmail.com - 2016-03-27 12:42 -0700
                Re: Fuzzy searching inside a MySQL DB Mike Mellen <mmellen@intellikey.com> - 2016-03-28 15:02 -0400
                Re: Fuzzy searching inside a MySQL DB Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-03-28 01:48 +0200
            Re: Fuzzy searching inside a MySQL DB Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-03-22 21:50 +0100

csiph-web