Питон как найти расстояние между подстроками

Rukovodstvo

статьи и идеи для разработчиков программного обеспечения и веб-разработчиков.

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

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

Время чтения: 6 мин.

Вступление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• [1] Модуль Python re
• [2] Модуль Python Левенштейна
• [3] Модуль Python editdistance
• [4] Модуль Python advas
• [5] Нечеткий модуль Python
• [6] Модуль медузы Python
• [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

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

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

Применение библиотеки FuzzyWuzzy для нечёткого сравнения в Python. Расстояние Левенштейна (редакционное расстояние)

Работая над голосовым помощником, который упоминается в предыдущей статье, понял, что просто не могу с вами не поделиться прекраснейшей библиотекой FuzzyWuzzy.

Если коротко, то благодаря ей существует возможность произвести нечёткое сравнение строк без каких-либо страданий.

Первые шаги

Для начала работы необходимо проделать два шага:

/ВАЖНО! Версия Python 2.7 и выше/

Шаг 1. Установка.

Открываем командную строку и вписываем:

Нажимаем Enter.
Далее устанавливаем таким же образом python-Levenshtein для ускорения сопоставления строк в 3-10 раз.

После завершения установки библиотека готова к импортированию.

Шаг 2. Импортирование в проект.

Функционал

1. Самое обычное сравнение:

Если мы изменим пару символов, то на выходе получим другое число.

2. Частичное сравнение

Данный вид сравнения во всей второй строке ищет совпадение с начальной, например:

Но следует помнить про регистр, так как

3. Сравнение по токену

1) Token Sort Ratio

Слова сравниваются друг с другом, независимо от регистра или порядка

2) Token Set Ratio
Это сравнение, в отличие от прошлого, приравнивает строки, если их отличие заключается в повторении слов.

4. Продвинутое обычное сравнение

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

5. Работа со списком

Для сравнения строки со строками из списка используется модуль process

Если необходим только первый в списке, то лучше использовать extractOne

Применение

Как и где применять всё вышеизложенное решать вам, но вот пример из моей курсовой работы:

Давайте пробежимся по коду и поймём что к чему.

Командой os.listdir мы получаем список всех файлов, которые присутствуют в конце указанного пути (в нашем случае на рабочий стол).

Далее идёт сравнение строк списка файлов с именем файла, который назвал пользователь (переменная namerec). Надеюсь, вы обратили внимание, что результатом функции extractOne является кортеж из строки и цифры (индекс сходства)

Исходя из этого, делаем проверку индекса сходства filestart[1] >= 80 ([1], так как в кортеже нумерация с 0, как в массиве) и, если условие верно, то запускаем функцией os.startfile файл с названием filestart[0]. Иначе, если индекс сходства меньше 80 или вылетает ошибка, что файл не найден — сообщаем это пользователю через функцию speak.

Все дороги ведут к матану

Если вам не интересна математика, то можете смело закрывать статью, так как сейчас будет мясо(нет). Сейчас постараюсь кратко и понятно донести смысл расстояния Левенштейна до таких же чайников, как и я.

Расстояние Левенштейна (редакционное расстояние, дистанция редактирования) — метрика, измеряющая разность между двумя последовательностями символов.
У нас есть две строки S1 размером i и S2 размером j
S1=vrhk
S2=rhgr

Существует только 3 операции:

1. Замена: r → v
2. Удаление: -r
3. Подстановка: rVhgr

Откуда в таблице появились 0 и 1? Для превращения пустого символа в пустой символ нам никаких операций проводить не нужно (пишем в таблицу — «0»), а для превращения символа r в пустую строку, необходимо удалить r (одно действие, пишем в таблицу — «1»). С символом v аналогичная ситуация.

Для перехода rh в пустой символ необходимо сначала удалить h, а потом r (используется две операции), следовательно, таблица примет вид:

Теперь рассмотрим ситуацию превращения v в r (отмечена зелёным кругом на таблице).

Существует несколько путей, но мы выбираем наименьший — превращение пустого символа в v.

В ячейку заносим 1. Как так получилось? Мы представляем r как строку, которую нужно превратить в строку v. Перед r существует пустой символ, который мы заменяем на v, получая строку rv. Так как мы проверяем символы справа налево, то v совпадает с v.

Пришло время рассмотреть превращение v в rh

Самый удачный вариант — v мы заменяем на h и всё сводится к задаче превращения r в пустую строку.

Результат заносим в таблицу.

В сравнении vr с r нужно учесть, что последние символы совпадают, а это значит, что задача просто сводится до более простой, без изменения расстояния Левенштейна.

При преобразовании vrh в r достаточно удаления h и эта задача сводится к предыдущей (сравнение vr с r), следовательно расстояние будет равно 2

Как и в случае сравнения vr с r у нас совпадают окончание строк vrh и rh, следовательно, расстояние не изменится.

Заметьте, что vrh и rhg идентичны с нашим предыдущим преобразованием, но с отличием в одну букву, которую просто необходимо убрать, именно из-за этого наше расстояние увеличивается на единицу (обратите внимание на стрелку).

Опираясь на все примеры, описанные выше, мы получаем кратчайшое редакционное расстояние (расстояние Левенштейна) между двумя строками — vrhk и rhgr.

How to extract the substring between two markers?

Let’s say I have a string ‘gfgfdAAA1234ZZZuijjk’ and I want to extract just the ‘1234’ part.

I only know what will be the few characters directly before AAA , and after ZZZ the part I am interested in 1234 .

With sed it is possible to do something like this with a string:

And this will give me 1234 as a result.

How to do the same thing in Python?

22 Answers 22

Using regular expressions — documentation for further reference

Then you can use regexps with the re module as well, if you want, but that’s not necessary in your case.

regular expression

The above as-is will fail with an AttributeError if there are no «AAA» and «ZZZ» in your_text

string methods

The above will return an empty string if either «AAA» or «ZZZ» don’t exist in your_text .

PS Python Challenge?

Surprised that nobody has mentioned this which is my quick version for one-off scripts:

you can do using just one line of code

result will receive list.

You can use re module for that:

In python, extracting substring form string can be done using findall method in regular expression ( re ) module.

With sed it is possible to do something like this with a string:

echo «$STRING» | sed -e «s|.*AAA\(.*\)ZZZ.*|\1|»

And this will give me 1234 as a result.

You could do the same with re.sub function using the same regex.

In basic sed, capturing group are represented by \(..\) , but in python it was represented by (..) .

You can find first substring with this function in your code (by character index). Also, you can find what is after a substring.

Using PyParsing

One liner with Python 3.8 if text is guaranteed to contain the substring:

Just in case somebody will have to do the same thing that I did. I had to extract everything inside parenthesis in a line. For example, if I have a line like ‘US president (Barack Obama) met with . ‘ and I want to get only ‘Barack Obama’ this is solution:

I.e. you need to block parenthesis with slash \ sign. Though it is a problem about more regular expressions that Python.

Also, in some cases you may see ‘r’ symbols before regex definition. If there is no r prefix, you need to use escape characters like in C. Here is more discussion on that.

Как найти подстроки между подстрокой внутри строки питона?

Пусть строка будет «AAAGQWERTYUIOPAGCTHJKLAAAGZXCVBNMAGCT» . Я хочу найти строки между AAAG и AGCT.

Я хотел бы, чтобы результат был [«QWERTYUIOP»,»ZXCVBNM»] , т. [«QWERTYUIOP»,»ZXCVBNM»] Список строк.

Как я могу использовать регулярное выражение или подобные методы для этого?

Я попробовал это

Я хотел вернуть два массива — один с расположением последовательности последовательностей между мотивами, а во-вторых с расположением второго мотива, который даст предыдущие расстояния.