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

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

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

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

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

  $query = "SELECT ru_words FROM word_list";
 
  if($stmt = $this->conn->prepare($query))
  {
    $stmt->execute();
    $stmt->bind_result($ru_word);
    while($stmt->fetch())
    {
      $word_translit[$ru_word] = translitIt($ru_word);
    }
  }

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

if(isset($word_list[$myWord]))
      {
        $correct[] .= $myWord;
      }
      else
      {
  $myWord = $this->translitIt($myWord);

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

foreach($word_translit as $n=>$k)
    {
      if(levenshtein(metaphone($myWord), metaphone($k)) < mb_strlen(metaphone($myWord))/2)
      {
        if(levenshtein($myWord, $k) < mb_strlen($myWord)/2)
        {
          $possibleWord[$n] = $k;
        }
      }
    }

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

    $similarity = 0;
    $meta_similarity = 0;
    $min_levenshtein = 1000;
    $meta_min_levenshtein = 1000;

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

foreach($possibleWord as $n)
{
  $min_levenshtein = min($min_levenshtein, levenshtein($n, $myWord));
}

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

foreach($possibleWord as $n)
{
  if(levenshtein($k, $myWord) == $min_levenshtein)
  {
   $similarity = max($similarity, similar_text($n, $myWord));
  }
}

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

foreach($possibleWord as $n=>$k)
{
  if(levenshtein($k, $myWord) <= $min_levenshtein)
  {
  if(similar_text($k, $myWord) >= $similarity)
  {
    $result[$n] = $k;
  }
  }
}

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

foreach($result as $n)
{
  $meta_min_levenshtein = min($meta_min_levenshtein, levenshtein(metaphone($n), metaphone($myWord)));
}
 
foreach($result as $n)
{
  if(levenshtein($k, $myWord) == $meta_min_levenshtein)
  {
   $meta_similarity = max($meta_similarity, similar_text(metaphone($n), metaphone($myWord)));
  }
}

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

foreach($result as $n=>$k)
{
  if(levenshtein(metaphone($k), metaphone($myWord)) <= $meta_min_levenshtein)
  {
   if(similar_text(metaphone($k), metaphone($myWord)) >= $meta_similarity)
   {
   $meta_result[$n] = $k;
   }
  }
}

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

return key($meta_result);

Плюс:

Точность определения слова довольно высокая, даже учитывая то, что я использовал словарь на 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 символа.

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

Ссылки:

Тут можно скачать весь код в одном классе.
А вот здесь базу русских слов, которую я использовал для тестов.

Добавлено: 14 Сентября 2013 11:55:18 Добавил: Андрей Ковальчук Нравится 0

Добавить