Для оценки похожести двух строк, как правило используют так званую дистанцию редактирования, которая показывает сколько базовых операций нужно сделать чтобы преобразовать одну строку в другую. Базовыми операциями редактирования считаются вставка, удаление и замена символа. Покажем это на примере: чтобы преобразовать строку "сабака" в "собака" нужно выполнить одну операцию замены (символ "а" заменить на "о"), соответственно дистанция редактирования для этих двух строк будет равняться единице.
Вставка Удаление Замена
Рисунок 1. Базовые операции редактирования.
Заметим также, что для преобразования слова "хлеб" в слово "пиво" нужно выполнить четыре замены.
Расстояние Левенштейна (или дистанция редактирования) между строками x и y равняется минимальному количеству базовых операций редактирования, необходимых для преобразования строки "x" в "y". Введем обозначения где lx соответствует длине строки "x", а ly - длине строки "y". Для расчета расстояния Левенштейна используется двухмерная матрица размером (lx+1)*(ly+1). Пример такой матрицы для сравнения слов "природа" "привод" приведен ниже.
| п | р | и | р | о | д | а | ||
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| п | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| р | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| и | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 |
| в | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 |
| о | 5 | 4 | 3 | 2 | 2 | 1 | 2 | 3 |
| д | 6 | 5 | 4 | 3 | 3 | 2 | 1 | 2 |
| Таблица 1 | ||||||||
При оценке похожести этих двух строк нас интересует только последнее полученное значение, которое находиться в правом нижнем углу - это и есть минимальная дистанция редактирования для этих двух слов.
Каждый элемент матрицы отображает минимальное значение среди трех базовых операций редактирования. Т.е. приведенная матрица это конечный результат. Промежуточную матрицу можно увидеть ниже.
| п | р | и | р | о | д | а | ||
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| п | 1 | 2/2/0 | 1/3/2 | 2/4/3 | 3/5/4 | 4/6/5 | 5/7/6 | 6/8/7 |
| р | 2 | 3/1/2 | 2/2/0 | 1/3/2 | 2/4/2 | 3/5/4 | 4/6/5 | 5/7/6 |
| и | 3 | 4/2/3 | 3/1/2 | 2/2/0 | 1/3/2 | 2/4/3 | 3/5/4 | 4/6/5 |
| в | 4 | 5/3/4 | 4/2/3 | 3/1/2 | 2/2/1 | 2/3/2 | 3/4/3 | 4/5/4 |
| о | 5 | 6/4/5 | 5/3/4 | 4/2/3 | 3/2/2 | 3/3/1 | 2/4/3 | 3/5/4 |
| д | 6 | 7/5/6 | 6/4/5 | 5/3/4 | 4/3/3 | 4/2/3 | 3/3/1 | 2/4/3 |
| Таблица 2 | ||||||||
В ячейках находятся значения вида a/d/c, где a - цена вставки, d - цена удаления, c - цена замены. Соответственно оставив среди этих трех значений минимальное, мы и получим таблицу 1.
Иногда полезным может оказаться не только нахождение коэффициента разницы двух строк, но также информация как эти строки могут межу собой сопоставляться. Для примера строки "ABEFDCFCD", "ABCD" можно сопоставить двумя способами
| A | B | E | F | D | C | F | C | D |
| A | B | C | D |
| A | B | E | F | D | C | F | C | D |
| A | B | C | D |
Для нахождения всех возможных способов сопоставления используется матрица полученная в алгоритме Левенштейна. Сам алгоритм нахождения возможных сопоставлений строк можно найти в архиве с исходниками, ссылка на который находиться внизу страницы.
Более расширенным алгоритмом поиска дистанции редактирования, является алгоритм Вагнера-Фишера. В алгоритме Левенштейна все операции редактирования имеют вес равный единице, когда алгоритм Вагнера-Фишера позволяет присвоить разным операциям разный вес, что позволяет сдвинуть оценку похожести двух строк в нужную нам сторону, скажем, увеличить цену для удаления, что приведет к уменьшению оценки разницы слов, если в их преобразованиях необходимо использовать удаление. Кроме того, алгоритм Вагнера-Фишера позволяет устанавливать разный весовой коэффициент для операций редактирования над разными символами. Скажем, уменьшить вес для операции удаления символа "ь" или же установить разный коэффициент для замены символов, что может быть ценным при проверке орфографии в тексте который был набран на клавиатуре (когда ошибка в символах лежащих рядом на клавиатуре будет считаться меньше чем в других случаях) или распознан через OCR систему (когда ошибка будет считаться меньшей если необходимо выполнить замену похожих по начертанию символов).
Исходники (Delphi 7):
Комментариев нет:
Отправить комментарий