The new InnoDB full-text search feature in MySQL 5.6 helps in this case.
I use the following query:
SELECT MATCH(column) AGAINST('(word1* word2*) ("word1 word1")' IN BOOLEAN MODE) score, id, column
FROM table
having score>0
ORDER BY score
DESC limit 10;
where ( ) groups words into a subexpression. The first group has like word% meaning; the second looks for exact phrase. The score is returned as float.