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

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

Для исправления опечаток в словах понадобится:
Расстояние Левенштейна (или расстояние Дамерау-Левенштейна — разница будет незначительной) — levenshtein()
Metaphonemetaphone()
Алгоритм Оливера — 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 слов и словоформ.
Поделиться публикацией

Комментарии 22

    +9
    У вас вот этот кусок кода 2 раза подряд в тексте:
    foreach($possibleWord as $n=>$k)
    {
      if(levenshtein($k, $myWord) < $min_levenshtein)
      {
        $min_levenshtein = levenshtein($k, $myWord);
      }
     
      if(levenshtein(metaphone($k), metaphone($myWord)) < $meta_min_levenshtein)
      {
        $meta_min_levenshtein = levenshtein(metaphone($k), metaphone($myWord));
      }
    }
    Исправьте, пожалуйста.

    Кстати, он мог бы быть короче и быстрее:
    foreach($possibleWord as $k)
    {
        $min_levenshtein = min($min_levenshtein, levenshtein($k, $myWord));
        $meta_min_levenshtein = min($meta_min_levenshtein, levenshtein(metaphone($k), metaphone($myWord)));
    }
      0
      Спасибо, переписал немного код.
        +1
        Спасибо за Левенштейна, познавательно.
        Пока пользуюсь в проекте Aspell+tsearch. Aspell'у можно поручить поиск ближайших, работает быстро: 50 результатов в секунду на моем стареньком PPC 1.2GHz 512MB

        aspell.suggest(«превед»)
        => [«перед», «переведи», «переведя», «правде», «пред», «прежде», «краевед», «перевей», «перевес», «перевод», «поревем», «поревет», «приведи», «приведя», «проведи», «проведя», «певец», «правд», «прете», «ревем», «ревет», «Певек», «переда», «передо», «правее», «бревен», «древен», «плевел», «прадед», «правей», «предел», «прелюд», «привес», «привет», «привод», «провод», «предо», «правда», «резеда», «праведный», «пребелый»]
          0
          А постгресовские модули fts и fuzzystrmatch, позволяющие сделать всё тоже самое внутри БД не подошли?
            0
            PostgreSQL никогда не пользовался. Спасибо за подсказку, буду читать о их работе и сравнивать.
            +1
            Может кто и словарик подскажет со всеми формами слов где скачать?
            Вот зачем хранить словарь в базе — не совсем понятно (кроме удобства), можно сгенерировать массивчик для php и заранее инклюдить php-файл с массивом, интересно, насколько быстрее будет.
              0
              Нашел вот это:
              Морфологический словарь на основе словаря Зализняка (MS Access) faqproject.ru/morphological-dictionary-russian-download.html. Правда, за скачивание там денег хотят ($25).
              Нужно ли Вам это, посмотрите там же на скриншоты этого словаря.
              Учтите, кстати, в этом словаре ошибок много.
              0
              Для определения словоформ можно mystem или lemmatizer использовать. А реализовать это лучше в виде модуля php, чтобы всё в память грузить.
                +3
                база русских слов это круто. у меня база со словоформами включает 4.7млн записей (стырено у яндекса, когда-то давно они раздавали сорцы своего сильно обрезаного движка десктопного поиска с включенной базой, не составило труда это оттуда изъять), просто текстовый файл — 85Мб, база с индексами в mysql получается около 250Мб, а если ещё и пару сервисных столбцов засунуть, вдухе ссылки на корень слова и индексы построить по комбинациям — то 600-700мег. так вот, когда вы сделаете
                $query = «SELECT ru_words FROM word_list»;
                а потом ещё и пробежитесь по всему результату запихивая его в массив — тут-то ваш скрипт и помрет, скорее всего :) я уже молчу о
                foreach($word_translit as $n=>$k)

                только кэш, хэш и заранее построеные таблицы
                  0
                  Согласен, такой нагрузки он не выдержит, этот вариант — попытка сделать «чтоб работало» и получить какие-то советы от более опытных специалистов. Скрипт будет переписываться полностью с учетом советов, которые сейчас пишут в комментариях. Если не сложно, выложите пожалуйста куда-то вашу базу.
                  0
                  Предложите что-то лучше. Как по мне очень полезная статья. В 95% скрипт полезен в небольших тематических проектах и служит как эволюция в поиске.
                    0
                    я бы попробовал один из следующих путей:

                    1) Для каждого слова из словаря заранее построить искаженные формы с расстоянием Д-Л не большим какого-нибудь разумного числа, допустим 10. Таким образом составить отдельную таблицу искажений и для них уже найти нормальные слова.
                    Далее, когда пользователь что-то вводит ищем уже в построенной таблице искажений что он там ввел и соотв. номарльную форму. Если же он ввел что-то странное чего у нас ещё нет — упс, надо запустить ваш алгоритм, только найдем какую-нибудь его оптимизированную/распараллеленую форму, есть ссылки в англоязычной вики.

                    2) Использовать не метрику между введеным словом и словом словаря, а что-то где в вычислениях будет присутствовать только введенное слово. Допустим один из фонетических алгоритмов, а для словаря звучания посчитать заранее.

                    3) Проанализировать много текста (ту же библиотеку Мошкова) и найти допустим по 3-5 наиболее используемых слов всех возможных длин слов в словаре (у меня самое длинное слово из 37 букв, что-то там в духе спецстроймонтажпрокладка :) ).
                    Далее делаем таблицу на основе словаря — слово и ещё 5 столбоцов с расстояниями Д-Л или другой метрикой до тех 5и заранее найденых популярных слов.
                    Затем когда пользователь вводит слово, считаем метрику для ввода и популярных слов этой длины +-2, затем из построенной заранее таблицы выбираем слово с минимальной суммой разностей квадратов полученых и сохраненых метрик.
                  0
                  А где буква «ё»? Я что-то ее мельком не нашел, а хром при Ctrl+F ищет в тексте и «е»
                    0
                    Мое упущение, но дописать в массив «Ё»=>«E» не составит труда. Если уже заговорили о транслитерации, то тут больше проблема в том, что одной русской букве может соответствовать до трех лат. Значит, при опечатке в этой букве, расстояние Левенштейна увеличится существенно. Поэтому лучше сделать простую замену букв один к одному, а разницу в количестве компенсировать, например, цифрами.
                    0
                    Так как словарь меняется редко — то его можно один раз подгрузить в расшаренную память, а в самом коде просто на чтение цепляться к этому куску памяти. Вариант несколько непортабельный, но быстрый. Но стаья очень интересная, спасибо!
                      +1
                      Автор, ну есть же на хабре нормальный <source />, зачем использовать левый хайлайтер?
                        0
                        Очень хочется применить что-то подобное в нашем проекте, блин где бы найти highload решение и желательно под ruby? =)
                          +1
                          а яндекс с гуглом на хабре только и умеют пиар-статьи строчить, поделились бы алгоритмами с опенсурс сообществом
                          0
                          $correct[] .= $myWord;
                          что-то тут не так
                            0
                            Все работает. Ошибок не выдает.
                            В чем проявляется «не так»?
                              0
                              Точка перед знаком равенства не имеет смысла, так как дописываем к пустой строке.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое