Расстояние Левенштейна

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

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

В отличие от расстояния Хэмминга, расстояние Левенштейна можно вычислять и для строк разной длины.

Практический пример

Рассмотрим две строки \( s \) и \( t \):

$$ s = "kitten" $$

$$ t = "sitting" $$

Найдем расстояние Левенштейна между этими словами, то есть минимальное количество вставок, удалений и замен, необходимых для преобразования строки "kitten" в строку "sitting".

1. Замена
   Заменяем \( k \) на \( s \): $$ "kitten" \rightarrow "sitten" $$
2. Замена
   Заменяем \( e \) на \( i \): $$ "sitten" \rightarrow "sittin" $$
3. Вставка
   Добавляем в конец символ \( g \): $$ "sittin" \rightarrow "sitting" $$

Всего требуется выполнить три операции: две замены и одну вставку. Следовательно, расстояние Левенштейна между строками "kitten" и "sitting" равно 3.

Чтобы проследить вычисление шаг за шагом, построим матрицу размером \( (m+1) \times (n+1) \), где \( m \) равно длине строки "kitten" (6), а \( n \) равно длине строки "sitting" (7).

Дополнительная строка и дополнительный столбец позволяют учитывать преобразования из пустой строки и в пустую строку.

Ячейка \( (0, j) \) содержит стоимость преобразования пустой строки в первые \( j \) символов строки "sitting". Поэтому значения в первой строке последовательно увеличиваются от 0 до 7.

Ячейка \( (i, 0) \) содержит стоимость преобразования первых \( i \) символов строки "kitten" в пустую строку. Поэтому значения в первом столбце увеличиваются от 0 до 6.

Для каждой ячейки \( (i, j) \) выбирается минимальная стоимость среди трех возможных операций:

1. удаление символа из строки "kitten", значение верхней ячейки плюс \( 1 \)
2. вставка символа в строку "kitten", значение левой ячейки плюс \( 1 \)
3. замена символа, значение диагональной ячейки. Если символы совпадают, дополнительная стоимость не добавляется.

После этого матрица заполняется последовательно:

Например, при преобразовании пустой строки в "s", "si", "sit" и последующие подстроки стоимость увеличивается на единицу при каждом переходе вправо.

Аналогично, при преобразовании строк "k", "ki", "kit" и последующих подстрок в пустую строку стоимость увеличивается на единицу при каждом переходе вниз.

• Ячейка (1,1) показывает стоимость преобразования "k" в "s". Она равна 1, так как требуется одна замена (k→s).
  
• Ячейка (2,2) показывает стоимость преобразования "ki" в "si". Она остается равной 1, поскольку второй символ совпадает (i).
• Ячейка (3,3) показывает стоимость преобразования "kit" в "sit". Она также равна 1, так как третий символ совпадает (t).
• Ячейка (4,4) показывает стоимость преобразования "kitt" в "sitt". Значение остается равным 1, поскольку четвертый символ также совпадает (t).
• Ячейка (5,5) показывает стоимость преобразования "kitte" в "sitti". Она становится равной 2, так как требуется еще одна замена (e→i).
  
• Ячейка (6,6) показывает стоимость преобразования "kitten" в "sittin". Она остается равной 2, поскольку шестой символ совпадает (n).
• Ячейка (6,7) показывает стоимость преобразования "kitten" в "sitting". Она становится равной 3, так как необходимо добавить символ (g).
  

После заполнения матрицы остается посмотреть на последнюю ячейку.

Правая нижняя ячейка \( (6,7) \) содержит минимальную стоимость преобразования строки "kitten" в строку "sitting". В данном примере она равна 3.

Именно это значение является расстоянием Левенштейна: одна замена (k → s), еще одна замена (e → i) и одна вставка символа (g).

Топология, индуцированная расстоянием Левенштейна

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

1. Неотрицательность. Расстояние Левенштейна между двумя строками \( x \) и \( y \) всегда неотрицательно. При этом \( D_L(x, y) = 0 \) тогда и только тогда, когда \( x = y \). Иными словами, нулевое расстояние имеют только одинаковые строки, поскольку для преобразования строки в саму себя не требуется ни одной операции.
2. Симметричность. Расстояние Левенштейна симметрично, то есть \( D_L(x, y) = D_L(y, x) \). Количество операций, необходимых для преобразования строки \( x \) в строку \( y \), совпадает с количеством операций для обратного преобразования. Это объясняется тем, что каждой операции вставки соответствует операция удаления, а замена символа обратима.
3. Неравенство треугольника. Расстояние Левенштейна удовлетворяет неравенству треугольника: \( D_L(x, z) \leq D_L(x, y) + D_L(y, z) \). Это означает, что кратчайший путь преобразования строки \( x \) в строку \( z \) не может быть длиннее пути через промежуточную строку \( y \). Любое преобразование можно представить как последовательность преобразований из \( x \) в \( y \), а затем из \( y \) в \( z \).

Благодаря этим свойствам расстояние Левенштейна задает на множестве строк метрическое пространство.

Поскольку эта функция расстояния удовлетворяет всем аксиомам метрики, с ее помощью можно определить и топологию, индуцированную данной метрикой.

Пусть задана строка \( x \) и радиус \( r \). Тогда открытый шар с центром в точке \( x \) определяется как множество всех строк \( y \), расстояние Левенштейна до которых меньше \( r \):

$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$

Все открытые множества этой топологии строятся как произвольные объединения таких открытых шаров.

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

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

Практический пример

Рассмотрим множество строк длиной три символа:

$$ X = \{"cat", "bat", "cut"\} $$

Построим базу топологии, используя открытые шары радиуса \( r = 2 \) с центром в каждой строке множества \( X \).

$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$

Поскольку радиус равен \( 2 \), каждый открытый шар содержит все строки, расстояние Левенштейна до которых строго меньше двух. В данном случае это означает, что в шар входят строки, отличающиеся от центральной не более чем одной операцией редактирования.

Примечание. Открытый шар определяется условием «меньше \( r \)», поэтому при \( r = 2 \) имеем: $$ B(x, 2) = \{ y \mid D_L(x, y) < 2 \}. $$ Следовательно, в него входят только строки, расстояние до которых равно 0 или 1. Если же требуется включить и граничные точки, используют замкнутый шар: $$ C(x, 2) = \{ y \mid D_L(x, y) \le 2 \}. $$ В этом случае множество содержит все строки, расстояние до которых не превышает двух операций редактирования.

Теперь найдем открытые шары радиуса \( 2 \) для каждой строки множества \( X \).

1. Открытый шар с центром в строке "cat" $$ B("cat", 2) = \{"cat", "bat", "cut"\} $$ Все три строки находятся на расстоянии меньше двух от строки "cat":
   • "cat" → "cat": 0 операций;
   • "cat" → "bat": одна замена;
   • "cat" → "cut": одна замена.
2. Открытый шар с центром в строке "bat" $$ B("bat", 2) = \{"bat", "cat"\} $$ Строка "cat" отличается от "bat" одной заменой, поэтому принадлежит открытому шару. Расстояние между строками "bat" и "cut" равно двум, поэтому строка "cut" в него уже не входит.
3. Открытый шар с центром в строке "cut" $$ B("cut", 2) = \{"cut", "cat"\} $$ Строка "cat" находится на расстоянии одной замены от строки "cut", тогда как расстояние между строками "cut" и "bat" равно двум. Поэтому строка "bat" не принадлежит этому открытому шару.

Множества \( B("cat", 2) \), \( B("bat", 2) \) и \( B("cut", 2) \) образуют базу топологии, индуцированной расстоянием Левенштейна.

Любое другое открытое множество можно получить как объединение этих открытых шаров.

Например, рассмотрим объединение открытых шаров с центрами в строках "bat" и "cut":

$$ B("bat", 2) \cup B("cut", 2) $$

Поскольку

$$ B("bat", 2) = \{"bat", "cat"\} $$

и

$$ B("cut", 2) = \{"cut", "cat"\} $$

получаем:

$$ B("bat", 2) \cup B("cut", 2) = \{"bat", "cat"\} \cup \{"cut", "cat"\} $$

$$ B("bat", 2) \cup B("cut", 2) = \{"cat", "bat", "cut"\} $$

Следовательно, множество \( \{"cat", "bat", "cut"\} \) также является открытым множеством данной топологии.

Таким образом, расстояние Левенштейна индуцирует на множестве \( X \) метрическую топологию, в которой любое открытое множество получается как объединение открытых шаров базиса.

И так далее.