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

Прежде всего, я дам вам определение и применение расстояния Левенштейна.

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

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

Алгоритм расстояния Левенштейна использовался в:

Проверка орфографии
Распознавание речи
Анализ ДНК
Обнаружение плагиата



Расстояние Левенштейна
Расстояние Левенштейна (LD) — это мера сходства между двумя строками, которые мы будем называть источником…people.cs.pitt .edu



Как работает расстояние Левенштейна?

В простом случае мы можем посчитать минимальные правки символов в двух словах. Как и в приведенном выше объяснении Википедии, правки определяются либо вставками, удалениями или заменами на один или несколько символов.

пример:

  1. Расстояние Левенштейна между FORM и FORK равно 1. Имеется одна замена M на K.

2. Левенштейн Расстояние между КОТЕНКОМ и СИДЕНИЕМ равно 3, потому что редактируются 3 символа.

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

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

где
a = слово a
b = слово b
a и b — строки или слова, которые мы хотим посчитать расстоянием.
i и j — матричные координаты, которые помогают нам для подсчета правок.
В последней строке уравнения оператор +1 (плюс один) добавляется только тогда, когда i и j не равны тот же персонаж.

Вот шаг для подсчета расстояния.

Прежде всего, создайте матрицу, содержащую такие значения.

А затем мы посчитаем Лев(1,1), который выделен желтым прямоугольником.

  1. поскольку min(1,1)≠0, то мы находим минимум из трех уравнений
  2. lev(0,1) означает, что мы находим значение из строки с индексом 0 и столбца с индексом 1
  3. lev(1,0) означает, что мы находим значение из строки с индексом 1 и столбца с индексом 0
  4. lev(0,0) означает, что мы находим значение из строки с индексом 0 и столбца с индексом 0. Поскольку K не равно S, мы добавляем в уравнение плюс один.
  5. Значение min(2,2,1) равно 1, поэтому мы можем поместить 1 в матрицу выше.

Теперь мы найдем Лева(2,1), который выделен зеленым прямоугольником.

  1. lev(1,1) означает, что мы находим значение из строки с индексом 1 и столбца с индексом 1
  2. lev(2,0) означает, что мы находим значение из строки с индексом 2 и столбца с индексом 0
  3. lev(1,0) означает, что мы находим значение из строки с индексом 1 и столбца с индексом 0. Поскольку I не равно S, мы добавляем в уравнение плюс один.
  4. Значение min(2,3,2) равно 2, поэтому мы можем поместить 2 в матрицу выше.

Ниже приведена полная матрица, если выполнены все шаги.

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

Спасибо!