3

Good evening,

I am facing a small problem whilst trying to build a little search algorithm.

I have a database table containing video game names and software names. Now I would like to add new offers by fetching and parsing xml files on other servers. The issue is:

How can I compare the strings for the product name so it works even if the offer name doesn't match the product name stored in my database up to a 100%?

As an example I am currently using this PHP + SQL code to compare the strings:

$query_GID = "select ID,game from gkn_catalog where game like '%$batch_name%' or meta like '%$batch_name%' ";

I am currently using the like operator in conjunction with two wild-cards to compare the offer name (batch_name) with the name in the database (game).

I would like to know how I can improve on this as this method isn't very failsafe or whatever you want to call it, what happens is:

If the database says the game title is:

Deus Ex Human Revolution Missing Link

and the batch_name says:

Deus Ex Human Revolution Missing Link DLC

the result will be empty/wrong/false ... well it won't find the game in my database at all.

Same goes for something like this:

Database = Lego Star Wars The Complete Saga
batch_name = Lego Star Wars : The Complete Saga
Result: False

Is there a better way to do the SQL query?
Or how can I try to get that query working so it can deal with strings that come with special characters (like -minus- & [brackets])
and or characters which aren't included in the names within the database (like DLC, CE...)?

SubZero
  • 113
  • 7

2 Answers2

3

You're looking for fuzzy search algorithms and fuzzy search results. This is a whole field of study. However, there are also some straightforward tutorials to get you started if you take a quick google around.

You might be tempted to try something like PHP's wonderful levenshtein method, which calculates the "closeness" of two strings. However, this would require matching it against every record. If there will be thousands of records, that's out of the question.

MySQL has some matching tools which may help. I see that as I'm writing this, somebody has already mentioned FULLTEXT and MATCH() in the comments. Those are a great way to go.

There are a few other good solutions to look into as well. Storing an index of keywords (with all the articles and helpers like of/the/an/am/is/are/was/of/from removed) and then searching on each word in the search is a simple solution. However, it doesn't produce great results in that the returned values are not weighted well, and it doesn't localize at all.

There are lots of cheap and wonderful third party search tools (Lucene comes to mind) as well that will do most of this work for you. You just call an API and they manage the caching, keywords, indexing, fuzzying, et al for searches.

Here are some SO questions that are related to fuzzy searches, which will help you find more terminology and ideas:

Community
  • 1
  • 1
Kato
  • 40,352
  • 6
  • 119
  • 149
  • Thank you very much for providing so many links to possible solutions, I will make sure to read them all and later on I will decide which one works the best. BTW, may I ask, why do you say that using the levenshtein method against thousands of records would be out of question? I could imagine the usage of this method is quite power demanding, or slow but then, having thousands of records, every method performing such a comparison would be slow and power demanding as well... – SubZero Mar 08 '13 at 22:25
  • Levenshtein via PHP would be slow because retrieving every record in the table in order to perform a comparison is not practical over large data sets. SQL databases do a lot of fancy internals to optimize comparisons and searches (index, index, index) and generally large operations need to be conducted at this level. – Kato Mar 09 '13 at 00:15
1

MySQL queries, as you found out can use the percent character as a joker (%) in conjunction with the LIKE operator.

You have multiple solutions depending on what you want exactly.

  • you can make a fulltext search
  • you can search using language algorithm like soundex
  • you can search by keywords

Remember that you can make a search in multiple passes (search for exact match, then percent on every side, explode in words then insert % between every word, search by keyword, etc.) depending if exact match has priority over close search, etc.

moxy
  • 1,634
  • 1
  • 11
  • 19