Сегодня поговорим о довольно сложной и интересной области программирования — об обработке текста. Так как работа в web — это почти всегда работа с текстом, то эта статья может оказаться вам полезной.

Дело в том, что для компьютера задачи, связанные с текстом, очень сложны. Он создан, чтобы работать с числами, а не с буквами. А понимать смысл слов программы пока еще не научились (на сколько мне известно). Тем не менее, работать с текстами нужно постоянно. И часто встречаются задачки, которые не составляют труда для человека, но могут оказаться довольно сложными для автоматического решения.

Ответтье на вопрос: похожи ли строки "Машка" и "Миша"? На самом деле, для компьютера не важно что вы ответите. Для него весь мир — числа. Поэтому ему не важно похожи ли эти строки. Для него интереснее НА СКОЛЬКО эти строки похожи или не похожи. А вот с этим вопросом не каждый человек сходу справится.

Сегодня я расскажу у метрике Левенштейна, которая позволяет вычислять "расстояние" от одной строки до другой.

Что такое расстояние (метрика) Левенштейна?

В 1965 году советский математик Владимир Иосифович Левенштейн разработал алгоритм, который позволяет оценить на сколько похожа одна строка на другую. Алгоритм Левенштейна позволяет получить именно численную оценку похожести строк.

Основная идея алгоритма состоит в том, чтобы посчитать минимальное количество операций удаления, вставоки и замены, которые нужно сделать над одной из строк, чтобы получить вторую. Допустим, у нас есть слова Машка и Миша. Попробуем преобразовать одно слово в другое, используя только удаление, добавление и замену.

Машка Миша — исходное состояние
Мишка Миша — шаг 1 (замена)
Миша Миша — шаг 2 (удаление)

Нам потребовалось два шага, значит, расстояние Левенштейна от строки Машка до строки Миша равно 2.

Реализация

Как видно, возможность находить расстояние Левенштейна для строк весьма полезна. Его можно использовать для индексации текстов, поиска и других задач.

Когда я попытался найти готовое решение для Perl, я обнаружил модуль Text::Levenshtein. Вы можете скачать его с CPAN и ознакомиться. Я думал, что вот оно, счастье. Но когда я попытался использовать этот модуль, он выдавал не те результаты, которые ожидались. Например, для слов "mama" и "papa" он выдавал результат 3, хотя видно, что в данном случае, метрика равна 2 (замена двух m на p).

В общем, я решил реализовать алгоритм с нуля. И вот что у меня получилось.

sub levenshtein {
    my ($w1, $w2, $t) = @_;
    #если слова равны, возвращаем 0
    if($w1 eq $w2) {return 0}
    #я решил сразу разбить слова на массив букв
    my @w1 = split '', $w1;
    my @w2 = split '', $w2;
    #добавляем в начало каждого слова пустой символ
    #это нужно для построения матрицы
    unshift @w1, "";
    unshift @w2, "";
    #вычисляем длину слов.
    #Не использовал функцию length, потому что
    #она может не правильно работать в разных кодировках   
    my ($n, $m) = ($#w1, $#w2);   
    my @d;
    #формируем матрицу, необходимую для рассчета
    $d[$_][0] =$_ for(0..$n);
    $d[0][$_] = $_ for(0..$m);   
    for(my $i=1; $i<=$n; $i++)    {
        for(my $j=1; $j<=$m; $j++)    {
            my $c = ($w1[$i] eq $w2[$j]) ? 0: 1;
            #присваиваем минимальное из трех возможных значений
            $d[$i][$j] =
            (sort($d[$i-1][$j]+1, $d[$i][$j-1]+1, $d[$i-1][$j-1]+$c))[0];
        }
    }
    return $d[$n][$m];
}

В комментариях говорится о какой-то матрице. Ее можно увидеть, если написать функцию:

sub trace   {
    my $d = shift;
 foreach my $l (@$d) {
    foreach my $r (@$l) {
        print "$r\t";
    }
    print "\n";
 }
}

И использовать ее, например, после заполнения матрицы @d[][].

trace(\@d);

Собственно, матрица, оптимизированная для просмотра выглядит так:

Проставление значений в матрице происходит по следующему алгоритму:

для каждой буквы первого слова
    для каждой буквы второго слова
        присвоить up значение ячейки с текущим номером, но предыдущей строки + 1
        присвоить left значение ячейки, которая предшествует текущей в текущей строке + 1
        Если текущая буква одного слова равна текущей букве другого слова,
            то cost=0,
            иначе cost=1
        присвоить diag значение ячейки в предыдущей строке и в предыдущей ячейке + cost
        присвоить d[i][j] = minimum(up, left, diag)
    конец
конец

Значение в последней(d[m][n], где m и n — длины слов) ячейке матрицы и будет метрикой Левенштейна.

Вообще, все не так сложно. Если вы не поняли алгоритм, написанный выше, то это не страшно. Главное, что вы можете его использовать.

А теперь сюрприз!

Программисты на PHP имеют функцию levenshtein, которая вычисляет дистанцию Левенштейна. Ну что, господа пхп-шники, кто знал об этой функции?;)

Еще по теме можно достать тут: algolist.manual.ru

Страница Владимира Иосифовича

Изучение алгоритмов и нестандартных подходов позволит вам иметь некое конкурентное преимущество. Любой блоггер скажет вам что даже небольшое преимущество может дать большой выигрыш. Так поступают все топовые блоггеры рунета - ищут свои фишки.