Writing a post search algorithm.

Question

I'm trying to write a free text search algorithm for finding specific posts on a wall (similar kind of wall as Facebook uses). A user is suppose to be able to write some words in a search field and get hits on posts that contain the words; with the best match on top and then other posts in decreasing order according to match score.

I'm using the edit distance (Levenshtein) "e(x, y) = e" to calculate the score for each post when compared to the query word "x" and post word "y" according to: score(x, y) = 2^(2 - e)(1 - min(e, |x|) / |x|), where "|x|" is the number of letters in the query word.

Each word in a post contributes to the total score for that specific post. This approach seems to work well when the posts are of roughly the same size, but sometime certain large posts manages to rack up score solely on having a lot of words in them while in practice not being relevant to the query.

Am I approaching this problem in the wrong way or is there some way to normalize the score that I haven't thought of?

Answer 1

Yes. There are many normalization methods you could use. This is a well-researched field!

Take a look at the vector space model . TDF/IDF could be relevant to what you're doing. It's not strictly related to the method you're using but could give you some normalization leads.

Also note that comparing each post will be O(N) and could get very slow. Instead of string-distance, you may have better results with stemmming. You can then put that into a VSM inverted index.

Many databases (including MySQL and Postgres) have full-text search. That's probably more practical than doing it yourself.