Autocomplete или как измерить расстояние Левенштейна

На днях встал вопрос сделать функцию для подсказки завершения слов. Самый простой вариант — сравнивать введенную часть слова с первыми буквами слов из словаря и выдавать все слова, у которых совпадает начало. На маленьких словарях это работает, в целом, неплохо, но люди делают опечатки и хотелось бы предлагать исправленные варианты слов, т. е. нужно выдавать похожие слова. Про меру «похожести» последовательностей 0–1 ещё в 1965 году упомянул советский математик Владимир Иосифович Левенштейн, что позже дало имя расстоянию Левенштейна.

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

Это уже почти то, что нужно, но в расстоянии Левенштейна перестановки не учитываются. На наше счастье товарищ Дамерау (Damerau) не только добавил к указанным операциями ещё одну — перестановку двух соседних символов, но и утверждал, что 80% ошибок при наборе текста дают как раз указанные четыре операции. Расстояние, которое учитывает эти операции назвали, как можно догадаться, расстоянием Дамерау–Левенштейна. Результаты этих работ теперь используются не только в бесполезных спеллчекерах, которые убивают грамотность, но и в исследованиях ДНК.

Мне же эти исследования пригодились для решения поставленной задачи. Ниже показана функция на C++, которая вычисляет расстояние Дамерау–Левенштейна:

int damerauLevenshteinDistance( const std::vector<char>& a, const std::vector<char>& b )
{
    const int a_size = static_cast<int>( a.size() );
    const int b_size = static_cast<int>( b.size() );
    const int INF = a_size + b_size;
    std::vector<std::vector<int> > H( a.size()+2, std::vector<int>( b.size()+2 ) );
    H[0][0] = INF;
    for ( int i = 0; i <= a_size; ++i ) { H[i+1][1] = i; H[i+1][0] = INF; }
    for ( int j = 0; j <= b_size; ++j ) { H[1][j+1] = j; H[0][j+1] = INF; }
    
    const int alphabet_size = std::numeric_limits<char>::max();
    std::vector<char> DA( alphabet_size );
    for ( int d = 0; d < alphabet_size; ++d ) DA[d] = 0;
    for ( int i = 1; i <= a_size; ++i ) {
        size_t DB = 0;
        for ( int j = 1; j <= b_size; ++j ) {
            const int i1 = DA[ b[j-1] ];
            const int j1 = DB;
            const int d = (a[i-1]==b[j-1]) ? 0 : 1;
            if ( d == 0 ) DB = j;
            H[i+1][j+1] = std::min( 
                std::min(H[i][j]+d, H[i+1][j]+1), 
                std::min(H[i][j+1]+1, H[i1][j1] + (i-i1-1) + 1 + (j-j1-1) ) );
        }
        DA[ a[i-1] ] = i;
    }
    return H[a.size()+1][b.size()+1];
}

Тема последних дней — поиск Муаммара Каддафи. Расчет расстояния от этого слова (Gadaffi) до всех слов английского словаря размером 329380 слов занимает порядка 2 секунд на моем домашнем Core2Duo 2.13GHz, т. е. функция работает довольно быстро.

Поскольку в моем словаре слов на несколько порядков меньше и выбирает их пользователь, то моя задача оказалась решена. Однако, существуют и другие варианты хранения словарей, например, префиксное дерево (trie), в котором каждый узел хранит первые буквы строк, потом пары букв и так далее. См. картинку из Википедии:

В таком дереве поиск подходящих окончаний происходит очень быстро. Этот метод также применяется в спелчекерах (например, встречается сотовых телефонах).

Стоит отметить, что автозавершение слов — это встроенная функция Windows и разработчикам предлагаются интерфейсы IAutoComplete и IACList, пользоваться которыми, на первый взгляд, оказалось не очень удобно и они реализуют самый простой вариант автозавершения, что тоже не подходит.

Ссылки по теме:

1. SimMetrics — an open source extensible library of Similarity or Distance Metrics, e.g. Levenshtein Distance, L2 Distance, Cosine Similarity, Jaccard Similarity etc.
   
2. Damerau–Levenshtein distance
   
3. Trie
   
4. GNU Aspell is a Free and Open Source spell checker
   
5. Implementing an autocompleting Combobox
   
6. Using Autocomplete in Windows