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

Groups > comp.lang.php > #16663 > unrolled thread

Fuzzy searching inside a MySQL DB

Back to article view | Back to comp.lang.php

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#16687

On 3/25/2016 3:51 PM, Mike Mellen wrote:
> On 3/25/2016 2:26 PM, Thomas 'PointedEars' Lahn wrote:
>>
>> You are not paying attention.
>>
>> As I showed, the Soundex strings of “expr1” and “expr2” are identical
>> because *Soundex* *ignores* *non-letters*:
> 
> I am quite familiar with how all of the referenced algorithms work, and
> where they are most useful, having written a number of applications
> involving name/word search.
> 

Don't pay any attention to "Pointed Head".  He is a well-known troll in
several newsgroups, who never has anything original to contribute.

-- 
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================

[toc] | [prev] | [next] | [standalone]

#16683

On Friday March 25 2016 03:03, in comp.lang.php, "bit-naughty@hotmail.com"
<bit-naughty@hotmail.com> wrote:

> On Thursday, March 24, 2016 at 8:35:32 AM UTC+5:30, Mike Mellen wrote:
> 
>> If this description is correct (OP - could you please verify?)
> 
> 
> Yes, it has nothing to do with "leetspeak" - its more like, do you know that
> rap group NWA - that stands for "Niggaz With Attitude" - so what if someone
> searches for .... "Niggers with Attitude".....? They have a song called
> "Fuck Tha Police", so... what if someone searches for "Fuck The Police"....?
> THAT kind of thing......

It looks like even the soundex() function won't satisfy your needs, then, as
soundex() would return different values than you would want:

# mysql> select soundex('niggers'), soundex('niggaz');
# +--------------------+-------------------+
# | soundex('niggers') | soundex('niggaz') |
# +--------------------+-------------------+
# | N262               | N200              | 
# +--------------------+-------------------+
# 1 row in set (0.00 sec)


-- 
Lew Pitcher
"In Skills, We Trust"
PGP public key available upon request

[toc] | [prev] | [next] | [standalone]

#16681

Mike Mellen wrote:

> On 3/22/2016 4:53 PM, Thomas 'PointedEars' Lahn wrote:
>> Mike Mellen wrote:
>>> On 3/22/2016 3:31 AM, bit-naughty@hotmail.com wrote:
>>>> ...sorry, I'm a little confused -  do levenshtein() and  similar_text()
>>>> ship WITH MySQL?
>>> No, but there are PHP levenshtein() and similar_text() functions. There
>>> is a soundex() function in mySQL, which is why I suggested it.
>> AISB, from the OP follows that Soundex is not the correct solution here.
> 
>  From the OP's minimal description, it sounds like he/she wants to
> search an English language  (suggested by word choice and column name)
> database to match user input with possible typos. There is no mention of
> "leetspeak" anywhere.

You are mistaken:

,-<news:f6d322a6-47cc-466e-97a7-03c065bf24ec@googlegroups.com>
| 
| […] if someone types in "sunflower" into the box, I would like it to match 
| "sunflow3r", if it's stored in the DB, say under the field "typeofflower" 
| - what are my options to do this?

-- 
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.

[toc] | [prev] | [next] | [standalone]

#16688

>>> No, but there are PHP levenshtein() and similar_text() functions. There
>>> is a soundex() function in mySQL, which is why I suggested it.
>>
>> AISB, from the OP follows that Soundex is not the correct solution here.
>>
> 
> From the OP's minimal description, it sounds like he/she wants to 
> search an English language  (suggested by word choice and column name) 
> database to match user input with possible typos. There is no mention of 
> "leetspeak" anywhere.

"sunflow3r" is not *clearly* leetspeak; it may be a simple typo made
by a hypothetical user of the OP's web site (*NOT* a typo by the
OP in a post).

What the OP might want is a "finger distance" algorithm of comparing
two words (one correct, the other the way it was typed in).  Look
at a typical keyboard and come up with a "distance" table between
each key and each other key (or at least between the letter keys
and each other key).  The distances will vary a bit depending on
the assumed keyboard type.  Dvorak and USA keyboard layouts are
really different.  As I understand it, USA and keyboards for various
European countries have only a few keys moved around.  Do Chinese and
USA keyboards even have more than a handful of keys in common?
(Space, Enter, and Backspace?)

The "finger distance" between two equal-length words is the sum of
the squares of the distances between corresponding letters.  (This
gives a big penalty for really large distances on one character.)
If the words are not equal length, you may need to come up with a
"distance" for extra or missing characters.  A keyboard looks a bit
like a grid of hexagons, with each letter key having adjacent
characters left, right, up and to the left, up and to the right,
down and to the left, and down and to the right.

Unfortunately, this algorithm, unlike Soundex, needs to compare the
word entered against each word in the database, which does not allow
for a pre-prepared column to match against.  A pre-prepared column
for each word in the database is impractical.

[toc] | [prev] | [next] | [standalone]

#16689

On Sunday, March 27, 2016 at 12:14:59 AM UTC+5:30, Gordon Burditt wrote:

> "sunflow3r" is not *clearly* leetspeak; it may be a simple typo made


....For God's sake, it's a song by a particular singer who spells it like that! For that matter NWA themselves once had an album called "Niggaz4Life", amongst many others who do this type of thing ("Menace II Society" for example)..... IT'S NOT LEETSPEAK!

[toc] | [prev] | [next] | [standalone]

#16693

On 3/27/2016 3:42 PM, bit-naughty@hotmail.com wrote:
> On Sunday, March 27, 2016 at 12:14:59 AM UTC+5:30, Gordon Burditt wrote:
>
>> "sunflow3r" is not *clearly* leetspeak; it may be a simple typo made
>
>
> ....For God's sake, it's a song by a particular singer who spells it like that! For that matter NWA themselves once had an album called "Niggaz4Life", amongst many others who do this type of thing ("Menace II Society" for example)..... IT'S NOT LEETSPEAK!
>

Most of us understand that, and have a rough idea of what your 
application requirements are.  Mr. Lahn appears to be imagining a 
different application.

Anyway, at this point you've been given some suggestions for how to 
proceed. If you wish to supply more information about your application, 
we can possibly offer more help, but this is getting off-topic for a PHP 
newsgroup.

[toc] | [prev] | [next] | [standalone]

#16690

Gordon Burditt wrote:

> "sunflow3r" is not *clearly* leetspeak; it may be a simple typo made
> by a hypothetical user of the OP's web site (*NOT* a typo by the
> OP in a post).

Yes, *that* is a distinct possibility that would explain the *apparent* 
disparity between the OP’s content and the OP’s explanations of it.
If that is the case, my apologies for assuming malice.
 
> What the OP might want is a "finger distance" algorithm of comparing
> two words (one correct, the other the way it was typed in).  Look
> at a typical keyboard and come up with a "distance" table between
> each key and each other key (or at least between the letter keys
> and each other key).  The distances will vary a bit depending on
> the assumed keyboard type.  Dvorak and USA keyboard layouts are
> really different.  As I understand it, USA and keyboards for various
> European countries have only a few keys moved around.

That depends very much on which European country you are talking about.
For example, considering *keys* is not enough, you must consider whole 
keyboard *layouts*, including *keymaps*.

In that regard, even the Standard German and Swiss German keyboard layouts 
are different from each other, even though both are based on QWERTZ.  And 
there is a Swiss French layout as well…

  [Having lived in Switzerland for almost a decade now, I even prefer the 
   Swiss German layout over the Standard German one that I grew up with.  
   (PHP) hacking is actually easier with it; for example, you have the “'”
   and “$” characters available without having to use the Shift key.]

> Do Chinese and USA keyboards even have more than a handful of keys in
> common? (Space, Enter, and Backspace?)

I do not know, but there are always Google and Wikipedia ;-)
 
<https://en.wikipedia.org/wiki/Keyboard_layout#Chinese>

> The "finger distance" between two equal-length words is the sum of
> the squares of the distances between corresponding letters.  (This
> gives a big penalty for really large distances on one character.)
> If the words are not equal length, you may need to come up with a
> "distance" for extra or missing characters.  A keyboard looks a bit
> like a grid of hexagons, with each letter key having adjacent
> characters left, right, up and to the left, up and to the right,
> down and to the left, and down and to the right.

Sounds like a really good idea.
 
> Unfortunately, this algorithm, unlike Soundex, needs to compare the
> word entered against each word in the database, which does not allow
> for a pre-prepared column to match against.  A pre-prepared column
> for each word in the database is impractical.

ACK.  But, in theory, one can have it defined as a stored function that is 
given two “words”, and two layout keys referring a mapping table, and that 
returns the “finger distance”.

-- 
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.

[toc] | [prev] | [next] | [standalone]

#16677

bit-naughty@hotmail.com wrote:

> ...sorry, I'm a little confused -  do levenshtein() and  similar_text()
> ship WITH MySQL?

My article, which you have not quoted at all, ends with:

>> […] MySQL does not have a built-in Levenshtein distance implementation, 
>> but this wheel has been invented already; STFW.

MySQL is *off topic* here.

-- 
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.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.php

csiph-web