Применение алгоритмов нечеткого поиска в PHP

Вдохновленный топиками о нечетком поиске и фонетических алгоритмах, захотел попытаться реализовать нечто подобное похожее на гугловское «Возможно, вы имели в виду: ...» средствами PHP.

Для исправления опечаток в словах понадобится:
Расстояние Левенштейна (или расстояние Дамерау-Левенштейна — разница будет незначительной) — levenshtein()
Metaphone — metaphone()
Алгоритм Оливера — similar_text()
База русских слов (с падежами, учетом времен и т.д.).

Функция для транслитерации слов:

1. function translitIt($str)
2.   {
3.     $tr = array(
4.         "А"=>"A","Б"=>"B","В"=>"V","Г"=>"G",
5.         "Д"=>"D","Е"=>"E","Ж"=>"J","З"=>"Z","И"=>"I",
6.         "Й"=>"Y","К"=>"K","Л"=>"L","М"=>"M","Н"=>"N",
7.         "О"=>"O","П"=>"P","Р"=>"R","С"=>"S","Т"=>"T",
8.         "У"=>"U","Ф"=>"F","Х"=>"H","Ц"=>"TS","Ч"=>"CH",
9.         "Ш"=>"SH","Щ"=>"SCH","Ъ"=>"","Ы"=>"YI","Ь"=>"",
10.         "Э"=>"E","Ю"=>"YU","Я"=>"YA","а"=>"a","б"=>"b",
11.         "в"=>"v","г"=>"g","д"=>"d","е"=>"e","ж"=>"j",
12.         "з"=>"z","и"=>"i","й"=>"y","к"=>"k","л"=>"l",
13.         "м"=>"m","н"=>"n","о"=>"o","п"=>"p","р"=>"r",
14.         "с"=>"s","т"=>"t","у"=>"u","ф"=>"f","х"=>"h",
15.         "ц"=>"ts","ч"=>"ch","ш"=>"sh","щ"=>"sch","ъ"=>"y",
16.         "ы"=>"yi","ь"=>"'","э"=>"e","ю"=>"yu","я"=>"ya"
17.       );
18.       return strtr($str,$tr);
19.   }

* This source code was highlighted with Source Code Highlighter.

Итак, для начала получим весь словарь из БД и запишем его в массив парами, где ключ — русское слово, значение — транслитерация.

1.   $query = "SELECT ru_words FROM word_list";
2.  
3.   if($stmt = $this->conn->prepare($query))
4.   {
5.     $stmt->execute();
6.     $stmt->bind_result($ru_word);
7.     while($stmt->fetch())
8.     {
9.       $word_translit[$ru_word] = translitIt($ru_word);
10.     }
11.   }

* This source code was highlighted with Source Code Highlighter.

Далее проверяем наше введенное слово на наличие в словаре, если нету — делаем его транслитерацию:

1. if(isset($word_list[$myWord]))
2.       {
3.         $correct[] .= $myWord;
4.       }
5.       else
6.       {
7.   $myWord = $this->translitIt($myWord);

* This source code was highlighted with Source Code Highlighter.

После этого запускаем цикл, который будет выбирать из массива те слова, расстояние Левенштейна между «метафонами» которых не будет превышать половину «метафона» введенного слова (грубо говоря, допускается до половины неправильно написанных согласных букв), потом, среди выбранных вариантов, снова проверяем расстояние, но по всему слову, а не по его «метафону» и подошедшие слова записываем в массив:

1. foreach($word_translit as $n=>$k)
2.     {
3.       if(levenshtein(metaphone($myWord), metaphone($k)) < mb_strlen(metaphone($myWord))/2)
4.       {
5.         if(levenshtein($myWord, $k) < mb_strlen($myWord)/2)
6.         {
7.           $possibleWord[$n] = $k;
8.         }
9.       }
10.     }

* This source code was highlighted with Source Code Highlighter.

Теперь зададим переменные, где расстояние Левенштейна будет равно заведомо большому числу, а «similar text» — заведомо малое число.

1.     $similarity = 0;
2.     $meta_similarity = 0;
3.     $min_levenshtein = 1000;
4.     $meta_min_levenshtein = 1000;

* This source code was highlighted with Source Code Highlighter.

Это нужно для определения максимального значения «подобности» между нашим словом и словами в массиве, а также минимального расстояния Левенштейна. Для начала найдем минимальное расстояние Левенштейна:

1. foreach($possibleWord as $n)
2. {
3.   $min_levenshtein = min($min_levenshtein, levenshtein($n, $myWord));
4. }

* This source code was highlighted with Source Code Highlighter.

И, аналогично, ищем максимальное значение «подобности» для тех слов, в которых расстояние Левенштейна будет минимальным:

1. foreach($possibleWord as $n)
2. {
3.   if(levenshtein($k, $myWord) == $min_levenshtein)
4.   {
5.    $similarity = max($similarity, similar_text($n, $myWord));
6.   }
7. }

* This source code was highlighted with Source Code Highlighter.

Теперь запускаем цикл, который выберет все слова с наименьшим расстоянием Левенштейна и наибольшим значением «подобности» одновременно:

1. foreach($possibleWord as $n=>$k)
2. {
3.   if(levenshtein($k, $myWord) <= $min_levenshtein)
4.   {
5.   if(similar_text($k, $myWord) >= $similarity)
6.   {
7.     $result[$n] = $k;
8.   }
9.   }
10. }

* This source code was highlighted with Source Code Highlighter.

После этого определяем максимальное значение «подобности» между «метафонами» нашего слова и слов в массиве, и минимальное расстояние Левенштейна:

1. foreach($result as $n)
2. {
3.   $meta_min_levenshtein = min($meta_min_levenshtein, levenshtein(metaphone($n), metaphone($myWord)));
4. }
5.  
6. foreach($result as $n)
7. {
8.   if(levenshtein($k, $myWord) == $meta_min_levenshtein)
9.   {
10.    $meta_similarity = max($meta_similarity, similar_text(metaphone($n), metaphone($myWord)));
11.   }
12. }

* This source code was highlighted with Source Code Highlighter.

И получаем окончательный массив, который, в идеале, должен содержать одно слово:

1. foreach($result as $n=>$k)
2. {
3.   if(levenshtein(metaphone($k), metaphone($myWord)) <= $meta_min_levenshtein)
4.   {
5.    if(similar_text(metaphone($k), metaphone($myWord)) >= $meta_similarity)
6.    {
7.    $meta_result[$n] = $k;
8.    }
9.   }
10. }

* This source code was highlighted with Source Code Highlighter.

И возвращаем правильное слово, которое хранится как ключ:

1. return key($meta_result);

* This source code was highlighted with Source Code Highlighter.

Плюс:

Точность определения слова довольно высокая, даже учитывая то, что я использовал словарь на 100 000 слов, который включает только нулевую форму и в списке слишком много слов, которые используются крайне редко (точнее, о которых я впервые слышу). Это, безусловно, портит результат.

Результат:

• халадильнег -> холодильник
• аффтамабэль -> автомобиль
• матоцыгл -> мотоцикл
• вэласэпэд -> велосипед
• аформеть -> оформить
• шына -> шина
• превет -> привет
• Но: пгевед -> перед

Проблему со словами, в которых одинаковое расстояние Левенштейна и значение «подобности» как в чистом слове, так и в его «метафоне», скорее всего, можно решить только добавлением частоты использования слов.

Минус:

Низкое быстродействие:

• Вытянуть из базы 100 000 слов и записать из в массив: 0.322146177292
• Первичный поиск по всему массиву из 100 000 слов: 0.995674848557
• Поиск по массиву из того что осталось с учетом всего слова: 1.97887420654E-5
• Поиск по массиву из того что осталось с учетом «метафонов» слова: 1.81198120117E-5

Тестировалось на: C2D E6550 (2.33GHz), 4Gb (DDR2-800).
Думаю, что это можно частично решить вытаскиванием из базы только тех слов, которые по длине отличаются от введенного на 1-2 символа.

Буду рад услышать от хабрасообщества более рациональные варианты использования фонетических алгоритмов, либо идеи по улучшению данного метода.

Ссылки:

Тут можно скачать весь код в одном классе.
А вот здесь базу русских слов, которую я использовал для тестов.
Благодарим пользователя Karroplan за отличнейшую базу, которая содержит 4 588 867 слов и словоформ.