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

Вступление

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

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

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

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

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

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

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

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

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

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

Категория Метод или алгоритм Пакеты Python

Точный поиск Поиск строки Бойера-Мура, поиск строки Рабина-Карпа, поиск Кнута-Морриса-Пратта (KMP), регулярные выражения строка, ре , Адвас Неточный поиск поиск по биграмме, поиск по триграмме, нечеткая логика Нечеткое Фонетические алгоритмы Soundex, Metaphone, Double Metaphone, Caverphone, NYIIS, KÃ¶lner Phonetik, Match Rating codex Адвас , Нечеткое , медуза , фонетика , км / ч Изменения или правки Расстояние Левенштейна, расстояние Хэмминга, расстояние Яро, расстояние Яро-Винклера editdistance , питон- левенштейн, медуза

Таблица 1

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

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

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

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

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

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

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

 test 
 [[ 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.] [ ]

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

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

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

 test 
 [[ 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])

Благодарности

Автор благодарит
Axel Beckert, Mandy Neumeyer, Gerold Rupprecht и Zoleka Hatitongwe за их поддержку при подготовке статьи.