На хабре было несколько статей на эту тему:
habrahabr.ru/blogs/algorithm/117063/
habrahabr.ru/blogs/algorithm/115147/
habrahabr.ru/blogs/algorithm/114947/
В PHP есть встроенные функции алгоритмов Soundex и Metaphone, но работают ли они с русским языком — не знаю.
