Расстояние Левенштейна и сходство текста в Python

Автор оригинала: Frank Hofmann.

Вступление

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

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

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

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

Например, эта технология используется информационно-поисковыми системами, поисковыми системами, системами автоматической индексации, текстовыми сумматорами, системами категоризации, системами проверки на плагиат, системами распознавания речи, рейтинговыми системами, анализом ДНК и алгоритмами профилирования (программы IR/AI для автоматической связи данных между людьми и тем, что они делают).

Методы поиска и сравнения

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

Кроме того, сходство может быть измерено тем, как звучат слова-они звучат одинаково, но написаны по-другому? Переводы с одного алфавита на другой часто дают более одного результата в зависимости от языка, поэтому для поиска родственников по разным написаниям их фамилии и имени был создан алгоритм Soundex, который до сих пор является одним из самых популярных и распространенных на сегодняшний день.

И последнее, но не менее важное: сколько изменений (правок) необходимо, чтобы перейти от одного слова к другому? Чем меньше правок нужно сделать, тем выше уровень сходства. Эта категория сравнения содержит расстояние Левенштейна, на котором мы остановимся более подробно ниже.

В таблице 1 представлен выбор способов поиска и сравнения текстовых данных. Правый столбец таблицы содержит выбор соответствующих модулей Python для выполнения этих задач.

Таблица 1

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

Этот метод был изобретен в 1965 году русским математиком Владимиром Левенштейном (1935-2017). Значение расстояния описывает минимальное количество удалений, вставок или замен, необходимых для преобразования одной строки (источника) в другую (цель). В отличие от расстояния Хэмминга , расстояние Левенштейна работает на струнах с неравной длиной.

Чем больше расстояние Левенштейна, тем больше разница между струнами. Например, от “test” до “test” расстояние Левенштейна равно 0, поскольку исходная и целевая строки идентичны. Никаких преобразований не требуется. Напротив, от “теста” до “команды” расстояние Левенштейна равно 2 – нужно сделать две замены, чтобы превратить “тест” в “команду”.

Вот отличное видео, объясняющее, как работает алгоритм:

Реализация расстояния Левенштейна в Python

Для Python существует довольно много различных реализаций, доступных в Интернете [9,10], а также из различных пакетов Python (см. таблицу выше). Это включает в себя версии, следующие концепции динамического программирования , а также векторизованные версии. Версия, которую мы показываем здесь, является итеративной версией, которая использует пакет NumPy и единственную матрицу для выполнения вычислений. В качестве примера мы хотели бы узнать расстояние редактирования между “тестом” и “текстом”.

Он начинается с пустой матрицы, размер которой равен длине строк. И первая строка, и столбец, начиная с нуля, индексируются все чаще:

         t   e   s   t
  [[ 0.  1.  2.  3.  4.]
 t [ 1.  0.  0.  0.  0.]
 e [ 2.  0.  0.  0.  0.]
 x [ 3.  0.  0.  0.  0.]
 t [ 4.  0.  0.  0.  0.]]

Далее следуют два цикла для сравнения строк по буквам – по строкам и по столбцам. Если две буквы равны, то новое значение в позиции [x, y] является минимальным между значением позиции [x-1, y] + 1 , позицией [x-1, y-1] и позицией [x, y-1] + 1 .

[+0.] [+1.]
[+1.] [   ]

В противном случае это минимум между значением position [x-1, y] + 1 , position [x-1 , y-1] + 1 и position [x, y-1] + 1 . Опять же, это можно визуализировать как подматрицу два на два, где вы вычисляете недостающее значение в правом нижнем углу, как показано ниже:

[+1.] [+1.]
[+1.] [   ]

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

         t   e   s   t
  [[ 0.  1.  2.  3.  4.]
 t [ 1.  0.  1.  2.  3.]
 e [ 2.  1.  0.  1.  2.]
 x [ 3.  2.  1.  1.  2.]
 t [ 4.  3.  2.  1.  1.]]

Расстояние редактирования – это значение в позиции [4, 4] – в правом нижнем углу, которое на самом деле равно 1. Обратите внимание, что эта реализация находится в O(N*M) времени, для N и M длин двух строк. Другие реализации могут выполняться за меньшее время, но более амбициозны для понимания.

Вот соответствующий код для алгоритма расстояния Левенштейна, который я только что описал:

import numpy as np

def levenshtein(seq1, seq2):
    size_x = len(seq1) + 1
    size_y = len(seq2) + 1
    matrix = np.zeros ((size_x, size_y))
    for x in xrange(size_x):
        matrix [x, 0] = x
    for y in xrange(size_y):
        matrix [0, y] = y

    for x in xrange(1, size_x):
        for y in xrange(1, size_y):
            if seq1[x-1] == seq2[y-1]:
                matrix [x,y] = min(
                    matrix[x-1, y] + 1,
                    matrix[x-1, y-1],
                    matrix[x, y-1] + 1
                )
            else:
                matrix [x,y] = min(
                    matrix[x-1,y] + 1,
                    matrix[x-1,y-1] + 1,
                    matrix[x,y-1] + 1
                )
    print (matrix)
    return (matrix[size_x - 1, size_y - 1])

Рекомендации

• [1] Модуль Python re
• [2] Модуль Python Levenshtein
• [[3] Python edit distance module
• [4] Модуль Python advas
• [5] Нечеткий модуль Python
• [6] Модуль Python jellyfish
• [7] Модуль фонетики Python
• [8] Модуль Python kph
• [9] https://www.python-course.eu/levenshtein_distance.php
• [10] https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python

Признание

Автор хотел бы поблагодарить Акселя Бекерта , Мэнди Ноймайер, Герольда Рупрехта и Золеку Хатитонгве за их поддержку при подготовке статьи.