Fuzzy Searching in PHP: Part 2
Friday, March 7. 2008In part two we looked at how we spider our content and how that content can be stored in way which allows it to be searched. In part 2 I will show you how to actually perform searches on this indexed data.
The basic process can be summarised as follows:
- Get a list of keywords to search for (i.e. the search terms to user inputs)
- Generate the soundex of each keyword
- Select all the rows in the words table (which we can join onto the wordpagelink) which match any of the soundex codes we generated
This will provide us with a very basic list of pages which contain words that match (or sound like) the keywords the user specified.
A More Advanced Search
Although this method does provide us with a fuzzy search it does not give us any degrees of relevancy for each result, so we cannot display the results in any sensible order.
There are several techniques we can use to rank our search results. Firstly, we can use the count field in the wordpagelink to find how many matches are found on each page for each keyword. A large number of matches can increase the relevance.
Another method is to use the levenshtein() function to find the difference between the keywords and the matched words. This is a nice way of combing the speed of the soudex lookup field in our words table with the granularity of the levenshtein difference. Note that the greater the value returned by levenshtein() the less the words match.
It is also possible to alter the weighting of matched keywords based upon where the match occurs in the page content (although this needs to be done during the indexing process). Regular expressions could be used to extract text from headline and title tags. These words are generally more significant and so can be given a higher weighting through the use of the count column; a word found in a h1 or title tag could be given a count of 10, and a word found in a h2 tag could be given a count of 7. You may find it useful to tweak these values for your particular application.
Another interesting method (which I have yet to explore) would be to weight whole pages based upon factors such as traffic, or how many times the page is linked to from other pages in the same site. These options would require more processing during the indexing process, but could ultimately provide very useful results for larger sites.
However, all of these methods need a certain amount of fine-tuning. You will need to play around with the weighing factors until you find you get accurate results, but it should ultimately prove worthwhile. Don’t forgot that that as you increase the number of factors that affect your weightings it will become harder to know exactly which ones to change to get the ideal search results.
Comments
While order could be implemented solely by the admin, we should consider letting the user do his own weighting, too. A user looking for references may want pages by relevance (weighting), while a user tracking down a friend's recommendation may want pages by popularity.
With an additional column in the wordpagelink table, we could also allow users to restrict their searches to entries or comments.
Welcome to port:eightyeight!
Those are some excellent points. More information stored during the spidering process can translate into more flexibility for the user.
As you said, extra columns in the wikiwordslink table could indicate where the match was found, such as body copy, headings, comments, profiles etc. (would just depend on the application).
Alternatively you could have an ENUM field (in MySQL) in the wikiwordslink table which indicates where the match was found, and a unique key across all three columns. This may end up using less space (on the basis that the majority of words will be body copy).
Anyway, I think comes down to a tradeoff between what your users want and what server load you can handle. As always, a middle-ground could be in order
Thanks for commenting!
Adam
As I understand it, soundex wouldn't match 'run' on 'runner' or 'running'. I don't quite understand how you would use levenshtein, but I think it would help in this case?
What do you recommend?
1. http://wiki.musicbrainz.org/DatabaseSchema/SearchTables
Thanks for reading, and I am please you like it!
I think to answer your question fully I would need to spend a little more time reading up on the inner workings of the soundex algorithm - but unfortunately it is coming up to midnight and I need sleep. However, http://en.wikipedia.org/wiki/Soundex looks like a good starting point.
My initial reaction would be to say that you could do a range match against the soundex field. You could code something like "If the first letter of the soundex matches then accept any values within +/- 60[1] of the generated soundex). You could then apply some sort of weighting based on how 'off' the soundex is. You would probably need split the soundex column in the words table into two columns for this to be efficient (on for the letter and one for the number, with an index across both).
I hope this answers your question. Please let me know if you make any progress with this!
Best,
Adam
[1] run = R552, running = R560, runner = R500.
Trackbacks