Делаем правильный Did You Mean

Затакт: это мой первый пост, а первый пост как всегда блином :).

Недавно была получена задача модернизировать поиск на сайте, и, так получилось, что надо было сделать функционал «Did You Mean».

Кстати, большое спасибо камраду alexblackalexblack за его статью Яндекс-like поиск своими руками, без неё я был бы как без рук :)

Сейчас я начну перечислять как я всё это делал. PHP, база MySQL, язык сайта — английский.
(правильное решение — в конце :)

0) Создание индексов

Написал маленький скрипт, который бегает по всему контенту сайта (благо он весь в базе) и создаёт таблицу guess_word с полями word — само слово, search_index — индекс слова (soundex или metaphone, в зависимости от настроек) и count — частота встречания слова.

Все слова заранее преобразовывались в lowercase и из них вырезалось всё кроме букв.

1) soudex + частота встречания

Если слово не было найдено, то берём его soudex индекс и ищем в базе обратно сортируя по частоте встречания.
Работает, но плохо. Далеко не всегда самое часто встречающееся слово является правильной подсказкой.

2) soundex + levenshtein

Находим все слова с таким же soundex индексом, далее выбираем из них то, у которого расстояние Левенштейна наименьшее.
Намного лучше, но всё равно есть проблемы. На стандартную опечатку teh находит tea (а не the, ибо расстояние между teh и the больше чем между teh и tea).

3) metaphone

Отказался от metaphone, так как он даёт худшие результаты. (Хотя странно, конечно).

4) Рассчитываем правильное расстояние между словами.

Расстояние левенштейна учитывает замены букв, удаления и вставки, но не учитывает обмен местами.

Идея A: считаем сколько разнх букв есть в слове, и прибавляем результат к расстоянию. при этом в расстоянии левенштейна делаем цену за удаление/вставку ниже чем за замену, ибо удаление/вставка уже рассчитана.
Результат A: не то. теперь самым близким к teh оказывается te

Идея B: поиграться с ценами в левенштейне.
Результат B: немного не то что я ожидал. Например, при поднятии цены на замену, алгоритм решает что teh в the выгоднее преобразовать через удаление и вставку. Хорошо, конечно, но не подходит.

Идея C: отказаться от левенштейна в пользу самописной функции.
function words_dist($str_a, $str_b)
{
    if ($str_a == $str_b) return 0;

    // (begin of) считаем количество различных символов. в отличии от btlfsa
    // (смотреть в комментах на php.net/levenshtein) считает разницу в их количестве
    // например btlfsa teh:tehh = 0, words_dist teh:tehh = 1

    $arr_a = array();
    for ($i = 0; $i < strlen($str_a); $i++) {
        $arr_a[$str_a{$i}] = (array_key_exists($str_a{$i}, $arr_a) ? $arr_a[$str_a{$i}] : 0) + 1;
    }

    $arr_b = array();
    for ($i = 0; $i < strlen($str_b); $i++) {
        $arr_b[$str_b{$i}] = (array_key_exists($str_b{$i}, $arr_b) ? $arr_b[$str_b{$i}] : 0) + 1;
    }

    foreach($arr_a as $k=>$v) {
        if (!array_key_exists($k, $arr_b)) $arr_b[$k] = 0;
    }

    $dst = 0;
    foreach ($arr_b as $k=>$v) $dst += abs((array_key_exists($k, $arr_a) ? $arr_a[$k] : 0) - $v);

    // (end of) считаем количество различных символов

    // считаем удаление/добавление символа более дорогостоящей операцией нежели обмен символов местами
    $dst *= 2;

    if (strlen($str_a) < strlen($str_b))
    {
        $l = strlen($str_b)-strlen($str_a);
        for ($i = 0; $i < $l; $i++) $str_a .= ' ';
    }
    elseif (strlen($str_b) < strlen($str_a))
    {
        $l = strlen($str_a)-strlen($str_b);
        for ($i = 0; $i < $l; $i++) $str_b .= ' ';
    }

    // считаем сколько символов не на своём месте
    for ($i = 0; $i < strlen($str_a); $i++) { if ($str_a{$i} != $str_b{$i}) $dst++; }

    return $dst;
}

Ссылка на код без комментов (на всяий случай)

Результат C: работает превосходно. (пока что :), возможно потом найдутся различные неточности)

5) Исправляем поиск по индексу

soudex индекс далеко не всегда даёт одинаковые индексы для похожих слов. Например, stcok и stages имеют одинаковые индексы, тогда как stcok и stock разные (ещё забавно theaters и tetrachloride).

Идея A: Делить индекс на 2 части (букву и число) и искать от [буква][число-2] до [буква][число+2]
Результат A: Не стал делать, так как подумал что могут ошибиться и в первой букве, а тогда soudex бессилен.

Идея B: добавлять к словам одинаковую первую букву, например 'L'. так как теперь первая буква одинаковая, заносить её в индекс не имеет смысла. $index = substr(soundex('L'.$word), 1);
Результат B: превзошёл мои ожидания. даже не пришлось делать поиск по диапазону (-2… +2).

*) Итоги

a) индексировать soundex-ом
b) перед индексацией добавлять к словам одинаковую первую букву, $index = substr(soundex('L'.$word), 1)
c) из списка возможных слов выбирать самописной функцией, и не использовать расстояние Левенштейна

И ещё в качестве бонуса: сделаем из угаданного слова разукрашку (подсветим красным неправильные буквы). Код достаточно очевидный и объёмный, по-этому просто дам на него ссылку: zame-dev.org/pub/highlight.html

Демонстрация

upd: наверное надо всё таки искать по диапозону, ибо soundex('Lteom') не такой как soundex('Lterm') ( но всё же гораздо ближе, чем soundex('teom') и soundex('term') )