4

after i searched i found how to do a fuzzy searching on a string

but i have an array of strings

$search = {"a" => "laptop","b" => "screen" ....}

that i retrieved from the DB MySQL

IS there any php class or function that does fuzzy searching on an array of words

or at least a link with maybe some useful info's

i saw a comment that recommend using PostgreSQL

and it's fuzzy searching capability but

the company had already a MySQL DB

Is there any recommendation ??

2 Answers 2

4

You could do this in MySQL since you already have a MySQL database - How do I do a fuzzy match of company names in MYSQL with PHP for auto-complete? which mentions the MySQL Double Metaphone implementation and has an implementation in SQL for MySQL 5.0+

Edit: Sorry answering here as there is more than could fit in a comment…

Since you've already accepted an answer using PHP Levenshtein function then I suggest you try that approach first. Software is iterative; the PHP array search may be exactly what you want but you have to test and implement it first against your requirements. As I said in your other question a find as you type solution might be the simplest solution here, which simply narrows the product as the user types. There might not be a need to implement any fuzzy searching since you are using the User to do the fuzzy search themselves :-)

For example a user starts typing S, a, m which allows you to narrow the products to those beginning with Sam. So you are always only letting the user select a product you already know is valid.

4
  • those are real people names but i am looking for names like "Samsung" "Nokia" "laptop" "pentuim 4" "ATI radion" and things like that i had a look at the double meta-phone and it sounds like it will produce problems if i used it to match such names
    – Qchmqs
    Aug 1, 2011 at 10:28
  • 1
    Can you add the link to the article that describes these limitations?
    – andyb
    Aug 1, 2011 at 13:29
  • i didn't mentioned that these are limitation but i don't think they will work fine for me am afraid of testing something that may do me more pain
    – Qchmqs
    Aug 1, 2011 at 13:39
  • Edited my answer, since it wouldn't fit in a comment.
    – andyb
    Aug 1, 2011 at 14:37
3

Look at the Levenshtein function

Basically it gives you the difference (in terms of cost) between to strings. I.e. what is the cost to transform string A into string B.

Set yourself a threshold levenshein distance and anything under that for two words mean they're similar.

Also the Bitap algorithm is faster since it can be implemented via bitwise operators, but I believe you will have to implement it yourself, unless there is a PHP lib for it somewhere.

EDIT To use levenshtein method:

The search string is "maptop", and you set your "cost threshold" to say 2. That means you want any words that are two string transform operations away from your search string.

so you loop through your array "A" of strings until

levenshtein ( A[i] , searchString ) <= 2

That will be your match. However you may get more than one word that matches, so it is up to you how you want to handle the extra results.

3
  • in another words i should start write it by my self because it doesn't exist an easy way ?
    – Qchmqs
    Aug 1, 2011 at 10:12
  • And about the database is PostgreSQL Really handle fuzzy searching better than MySQL ?
    – Qchmqs
    Aug 1, 2011 at 10:16
  • i need a recommendation because if that's true i should not waste my time to apply search to PHP arrays while the DB should take care of it
    – Qchmqs
    Aug 1, 2011 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.