Расстояние Левенштейна: Всеобъемлющее руководство
Введение
В мире обработки естественного языка (NLP) сравнение и понимание схожести между двумя строками является одной из основных задач. Будь то исправление опечаток, выявление плагиата, сопоставление имен или оценка текста, сгенерированного машиной, способность измерять, насколько «близки» две строки, может значительно повысить эффективность приложений, основанных на языке.
Одной из самых известных и широко используемых метрик сходства строк является расстояние Левенштайна. Этот алгоритм определяет, насколько похожи две строки. Часто называемая расстоянием редактирования, эта операция широко используется в обработке естественного языка (NLP), проверках орфографии, поисковых системах и задачах нечеткого соответствия строк. В этой статье мы глубоко погрузимся в реализацию расстояния Левенштайна на Python, сравнение библиотек, изучение производительности и рассмотрение его интеграции с современными NLP и LLM.
Основные выводы
- Расстояние Левенштейна является фундаментальной метрикой схожести строк, которая вычисляет минимальное количество односимвольных правок (вставок, удалений, замен), необходимых для превращения одной строки в другую.
- Он широко используется в проверках правописания, нечетком поиске, автокоррекции, обнаружении плагиата и биоинформатике.
- Алгоритм использует динамическое программирование, обычно реализуемое с помощью матрицы, что обеспечивает детерминированные и точные результаты.
- Библиотеки Python, такие как
Levenshtein,fuzzywuzzyиdistance, упрощают реализацию для практических задач. - Хотя расстояние Левенштейна является вычислительно затратным и не передает семантическое значение, оно менее идеально для глубоких задач обработки естественного языка, связанных с сравнением полного текста.
- Другие метрики сходства, такие как Джаро-Уинклера, Дамерау-Левенштейна, Жаккара и косинусное сходство, предлагают разные преимущества в зависимости от контекста (например, сопоставление имен, сравнение токенов, семантическое сходство).
Как работает расстояние Левенштейна
Расстояние Левенштейна измеряет минимальное количество односимвольных изменений (вставок, удалений или замен), необходимых для преобразования одной строки в другую. Давайте рассмотрим простое, но полное объяснение расстояния редактирования Левенштейна с использованием примера матрицы и легко понимаемого объяснения:
“книга ” → “назад ”
Давайте :
Строка 1, s1="книга"(длина=4)Строка 2, s2="назад"(длина=4)
Шаг 1: Инициализируйте матрицу
Чтобы представить строки в матрице, мы создадим матрицу 5 X 5 и также включим пустую строку («») по индексу 0.
Инициализация пустой матрицы:
| б | а | с | к | ||
|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | ||
| б | 1 | ||||
| о | 2 | ||||
| о | 3 | ||||
| к | 4 |
Шаг 2: Заполните матрицу
Расстояние Левенштейна между двумя строками i и j (длиной | i | и | j | соответственно) задается как D(i, j), где:
Давайте заполним несколько ключевых ячеек:
Ячейка (1,1): Сравните ‘b’ и ‘b’ → Совпадение
D(1,1)=D(0,0)=0
Ячейка (2,2): Сравнить ‘o’ и ‘a’ → Нет совпадения
D(1,2)=1 (удаление)D(2,1)=2 (вставка)D(1,1)=0 (замена)
D(2,2)=1+min(1,2,0)=1
Ячейка (3,3): Сравните ‘o’ и ‘c’ → Нет совпадения
D(2,3)=2D(3,2)=2D(2,2)=1
D(3,3)=1+min(2,2,1)=2 Продолжайте этот процесс…
Шаг 3: Финальная матрица
| б | а | с | к | ||
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | |
| b | 1 | 0 | 1 | 2 | 3 |
| о | 2 | 1 | 1 | 2 | 3 |
| о | 3 | 2 | 2 | 2 | 3 |
| к | 4 | 3 | 3 | 3 | 2 |
Шаг 4: Итоговый результат
Расстояние Левенштейна D(4,4)=2 Таким образом, требуется 2 операции, чтобы превратить “книга” → “спина”:
- Замените ‘о’ → ‘а’
- Замените ‘о’ → ‘с’
В приведенном выше примере мы вычислили расстояние редактирования и построили матрицу поэтапно. Расстояние Левенштейна определяется с учетом вставок, удалений и замен на каждом шаге, а окончательный результат находится в правом нижнем углу матрицы.
Реализация расстояния Левенштейна на Python (без библиотек)
Вот код на Python, чтобы вычислить и вывести расстояние Левенштейна с матрицей.
def levenshtein_distance(s1, s2): m, n = len(s1), len(s2) dp = [[0 for _ in range(n+1)] for _ in range(m+1)] # Initialize base cases for i in range(m+1): dp[i][0] = i for j in range(n+1): dp[0][j] = j # Fill the matrix for i in range(1, m+1): for j in range(1, n+1): if s1[i-1] == s2[j-1]: cost = 0 else: cost = 1 dp[i][j] = min( dp[i-1][j] + 1, # deletion dp[i][j-1] + 1, # insertion dp[i-1][j-1] + cost # substitution ) # Print the matrix print("Levenshtein Distance Matrix:") print(" ", " ".join([" "] + list(s2))) for i in range(m+1): row = [s1[i-1] if i > 0 else " "] for j in range(n+1): row.append(str(dp[i][j])) print(" ".join(row)) return dp[m][n] Example: "book" to "back" s1 = "book" s2 = "back" distance = levenshtein_distance(s1, s2) print(f"nLevenshtein distance between '{s1}' and '{s2}' is {distance}") **Levenshtein Distance Matrix:** **b a c k** **0 1 2 3 4** **b 1 0 1 2 3** **o 2 1 1 2 3** **o 3 2 2 2 3** **k 4 3 3 3 2** Расстояние Левенштейна между ‘book’ и ‘back’ равно 2
Использование библиотек Python для расстояния Левенштейна
1. Использование python-Levenshtein
!pip install python-Levenshtein import Levenshtein s1 = "book" s2 = "back" distance = Levenshtein.distance(s1, s2) print(f"Levenshtein distance: {distance}") 2. Использование fuzzywuzzy (для нечеткого сопоставления)
!pip install fuzzywuzzy python-Levenshtein from fuzzywuzzy import fuzz s1 = "book" s2 = "back" Fuzzy match ratio based on Levenshtein distance ratio = fuzz.ratio(s1, s2) print(f"Fuzzy match ratio: {ratio}%")
Примечание: fuzz.ratio() возвращает процент схожести, а не само расстояние.
3. Использование rapidfuzz (легкий и быстрый)
!pip install rapidfuzz from rapidfuzz.distance import Levenshtein s1 = "book" s2 = "back" distance = Levenshtein.distance(s1, s2) print(f"Levenshtein distance: {distance}") 4. Использование distance (простой и чистый Python)
!pip install distance import distance s1 = "book" s2 = "back" distance_val = distance.levenshtein(s1, s2) print(f"Levenshtein distance: {distance_val}") 5. Использование textdistance (гибкий и поддерживает множество алгоритмов)
!pip install textdistance import textdistance s1 = "book" s2 = "back" distance = textdistance.levenshtein(s1, s2) print(f"Levenshtein distance: {distance}") Полное бенчмаркинговое тестирование производительности Python
Предоставленный ниже скрипт для бенчмаркинга на Python сравнивает производительность расстояния Левенштейна среди библиотек: rapidfuzz, python-Levenshtein, textdistance и distance.
Сначала установите зависимости, если вы еще этого не сделали:
pip install matplotlib rapidfuzz python-Levenshtein textdistance distance import time import matplotlib.pyplot as plt import Levenshtein import textdistance import distance as dist from rapidfuzz.distance import Levenshtein as r_lev Strings to compare s1 = "book" s2 = "back" N = 100_000 Store results results = {} Benchmark function def benchmark(name, func): start = time.time() for _ in range(N): func(s1, s2) end = time.time() duration = end - start avg_time_us = duration / N * 1e6 results[name] = (duration, avg_time_us) print(f"{name:<25}: {duration:.4f} sec (Avg: {avg_time_us:.2f} µs)") print("Benchmarking Levenshtein Distance (100,000 repetitions):n") Run benchmarks benchmark("rapidfuzz", lambda a, b: r_lev.distance(a, b)) benchmark("python-Levenshtein", lambda a, b: Levenshtein.distance(a, b)) benchmark("textdistance", lambda a, b: textdistance.levenshtein(a, b)) benchmark("distance (pure Python)", lambda a, b: dist.levenshtein(a, b)) Plotting the results libraries = list(results.keys()) total_times = [results[lib][0] for lib in libraries] avg_times = [results[lib][1] for lib in libraries] plt.figure(figsize=(10, 5)) bars = plt.bar(libraries, avg_times, color=['#66c2a5', '#fc8d62', '#8da0cb', '#e78ac3']) plt.title("Levenshtein Distance Avg Time per Call (µs)") plt.ylabel("Average Time (µs)") plt.xlabel("Python Library") plt.grid(axis='y', linestyle='--', alpha=0.7) plt.tight_layout() Annotate bars with actual times for bar, avg in zip(bars, avg_times): yval = bar.get_height() plt.text(bar.get_x() + bar.get_width() / 2, yval + 0.5, f"{avg:.2f}", ha='center', va='bottom', fontsize=9) plt.show() Бенчмаркинг расстояния Левенштейна (100 000 повторений):
rapidfuzz : 0.0866 сек (ср. : 0.87 мкс)
python-Levenshtein : 0.0881 сек (ср. : 0.88 мкс)
textdistance : 0.3400 сек (ср. : 3.40 мкс)
distance (чистый Python) : 1.4420 сек (ср. : 14.42 мкс)
Сравнение с другими метриками сходства строк
Матрицы сходства строк — это процесс, при котором структурированное представление строк используется для количественной оценки того, насколько схожи или различны слова. Это достигается путем фиксации различий на уровне символов или токенов в табличной форме. Эти матрицы являются центральными для таких алгоритмов, как Левенштейн, Дамерау-Левенштейн и других, где каждая ячейка матрицы обозначает «стоимость» или «расстояние», необходимое для преобразования одной подстроки в другую с помощью последовательности операций, таких как вставка, удаление, замена или транспозиция.
Матрица обычно инициализируется с увеличивающимися значениями вдоль ее первой строки и столбца, представляющими стоимость преобразования пустой строки в символы другой строки.
Поскольку матрица заполняется построчно и по столбцам, каждая ячейка вычисляется на основе рекуррентного соотношения, которое сравнивает текущие символы и выводит минимальную стоимость из предыдущих ячеек. Этот процесс создает сетку динамического программирования, где ячейка в правом нижнем углу содержит окончательный показатель схожести или расстояния между полными строками. Матрицы схожести строк служат основой для сложных задач обработки естественного языка, таких как проверка правописания, нечеткое сопоставление и дедупликация данных.
Разные метрики имеют разные цели, и они могут подчеркивать расстояние редактирования, сходство токенов или фонетическое звучание.
| Метрическая система | Тип | Что это измеряет | Диапазон | Заметки |
|---|---|---|---|---|
| Расстояние Левенштейна | Редакционное расстояние | Минимальные вставки, удаления, замены | от 0 до бесконечности | Наказывает каждое изменение на уровне знака одинаково |
| Дамерау-Левенштейн | Редакционное расстояние | Как Левенштейна, но также учитывает транспозиции | от 0 до ∞ | Более реалистично для опечаток (например, «acress» → «caress») |
| Расстояние Хэмминга | Редакционное расстояние | Количество различных позиций (только для одинаковой длины) | от 0 до n | Быстро, но менее гибко |
| Джаро/Джаро-Уинклер | Сходство | Измеряет согласие символов и транспозиции | 0.0–1.0 | Хорошо для коротких строк и имен |
| Сходство Жаккара | Set-Based | Пересечение над объединением множеств/токенов | 0.0–1.0 | Хорошо для более длинных текстов или сравнения на основе токенов |
| Косинусное сходство | Vector-Based | Угол между представлениями TF-IDF или векторными представлениями слов | -1.0–1.0 | Используется в NLP-пайплайнах; требует векторизации |
| Соренсен-Дайс | Set-Based | 2 * | A ∩ B | Этот метр оценивает сходство между изображением, сегментированным компьютером, и его соответствующей истинной меткой (правильным ответом). |
| Звуковой код/Метафон | Фонетический | Кодирует строки по произношению | Совпадение/Нет совпадения | Лучше всего подходит для совпадений по именам или произношению (например, в генеалогии) |
Давайте снова рассмотрим пример с “книгой” и “спиной”:
| Метрическая система | Значение | Толкование |
|---|---|---|
| Левенштейн | 2 | Нужно внести 2 правки |
| Damerau-Levenshtein | 2 | То же самое, что и Левенштейн (без транспозиции здесь) |
| Хэмминг | 2 | Действительно только потому, что длины равны |
| Jaro-Winkler | ~0,83 | Довольно похожие короткие строки |
| Жаккара (набор символов) | 0.5 | {‘b’} |
| Косинус (TF-IDF) | Зависит от корпуса | Нужна векторизация |
Хотя расстояние Левенштейна отлично подходит для общего сравнения строк на уровне символов, более специализированные метрики обеспечивают улучшенную производительность для конкретных случаев использования. Джаро-Винклера и Дамерау-Левенштейн особенно эффективны для обработки сопоставления имен и опечаток, поскольку они присваивают более высокое сходство строкам с общими префиксами или транспонированными символами.
В отличие от этого, метрики, основанные на наборах, такие как коэффициент Жаккара и коэффициент Дайса, лучше подходят для сравнения строк на уровне слов или токенов, что делает их идеальными для задач по аналогии документов или фраз.
Для улавливания смысла, выходящего за рамки поверхностных символов, векторные метрики, такие как косинусное сходство, которые работают на основе TF-IDF или векторных вложений, являются мощными инструментами для семантического сравнения в приложениях полного текста или обработки естественного языка (NLP). Каждая из этих метрик предлагает уникальную перспективу на сходство, и выбор зависит от гранулярности и контекста сравнения.
Применения в НЛП и ЛЛМ
Расстояние редактирования Левенштейна рассматривается как основной инструмент в задачах обработки естественного языка. Его способность количественно оценивать, насколько различны две строки, вычисляя минимальное количество вставок, удалений или замен, делает его идеальным для работы с шумным или сгенерированным пользователями текстом. В современных потоках обработки естественного языка и больших языковых моделях (LLMs) расстояние Левенштейна часто играет вспомогательную роль, будь то в задачах предварительной обработки, таких как очистка данных, исправление ошибок или в задачах оценки, таких как сравнение сгенерированных выводов с эталонными ответами. Вот несколько ключевых применений расстояния редактирования Левенштейна:
- Проверка орфографии и автокоррекция Определите и исправьте опечатки, находя ближайшее слово из словаря с использованием минимального расстояния редактирования.
- Нечеткое соответствие строк Совпадение неправильно написанных или приблизительно похожих строк в таких приложениях, как поиск, автозаполнение и оптическое распознавание символов (OCR).
- Нормализация текста Предварительная обработка шумного или сгенерированного пользователем текста перед подачей его в NLP-пайплайны.
- Совпадение именованных сущностей Улучшите разрешение сущностей в задачах, таких как удаление дубликатов и связывание имен с незначительными различиями.
- Оценка генерации текста Сравните ответы, сгенерированные моделью, с эталонными данными в таких задачах, как суммирование или перевод.
- Распознавание намерений в чат-ботах Помогает сопоставлять запросы пользователей с предопределенными намерениями, несмотря на ortograficheskiye oshibki ili varianty.
- Удаление дубликатов данных Обнаружение почти дублирующихся записей в наборах данных, особенно в базах данных с несоответствующими записями.
Преимущества расстояния Левенштейна
Расстояние Левенштейна легко понять и сравнительно легко вычислить, как обсуждается в этой статье. Оно требует измерения минимального числа односимвольных изменений, необходимых для преобразования одной строки в другую. Эта простота делает его идеальным решением для многих базовых задач сравнения строк. Более того, операция является языконезависимой, поскольку она работает исключительно на уровне символов. Расстояние Левенштейна не требует каких-либо специфичных для языка правил, что делает его применимым для различных языков и наборов символов. Вычисляемое расстояние является точным и детерминированным, обеспечивая четкую и воспроизводимую меру различия между строками.
Недостатки расстояния Левенштейна
- Вычисление расстояния Левенштейна может быть вычислительно затратным, так как его временная сложность составляет O(m × n) (где m и n — это длины входных строк), что может быть медленно для длинных строк или при сравнении больших наборов данных.
- Расстояние Левенштейна не учитывает контекст и значение, так как оно измеряет только различия на уровне символов и не учитывает семантическое значение. Например, слова «кошка» и «первичный» имеют высокое редактирование расстояния, но семантически они схожи.
- Базовое расстояние Левенштейна плохо справляется с переставленными символами. Например, «form» и «from» похожи по значению и внешнему виду, но имеют расстояние 2. Алгоритм Дамерау-Левенштейна обрабатывает это лучше.
- Расстояние Левенштейна рассматривает вставки, удаления и замены с одинаковым весом. В реальных приложениях некоторые изменения (например, замена похожих по виду символов) могут быть более вероятными или менее затратными, чем другие.
- Поскольку расстояние Левенштейна сосредоточено на отдельных символах, оно менее эффективно для задач, требующих сходства на уровне токенов или фраз, таких как семантическое соответствие или классификация текста.
Часто задаваемые вопросы
Как рассчитать расстояние Левенштейна на Python? Вы можете использовать python-Levenshtein, rapidfuzz или написать собственное решение на основе динамического программирования.
Как вычислить расстояние Левенштейна в Python без использования библиотеки? Используйте вложенный цикл и таблицу динамического программирования, как показано в приведённом выше примере кода.
Какова временная сложность расстояния Левенштейна? O(m*n), где m и n — длины двух строк.
В чем разница между расстоянием Левенштейна и расстоянием Хэмминга? Хэмминг работает только для строк одинаковой длины и считает несовпадения символов; Левенштейн также учитывает вставки и удаления.
Какая библиотека Python является самой быстрой для вычисления расстояния Левенштейна? rapidfuzz обычно является самой быстрой и эффективной для использования в производстве.
Используется ли расстояние Левенштейна в машинном обучении или LLM? Да. Оно используется в предварительной обработке, дедубликации и постобработке. Оно также дополняет техники семантического сопоставления в конвейерах LLM.
Заключение
Расстояние Левенштейна остается основным алгоритмом для сравнения строк в Python. Хотя новые семантические модели расширили возможности в области NLP, Левенштейн по-прежнему играет ключевую роль в задачах, требующих буквального сравнения строк. С мощными библиотеками, такими как rapidfuzz, и гибридными подходами, совмещающими расстояние редактирования с векторными представлениями, разработчики на Python имеют больше инструментов, чем когда-либо, для решения задач нечеткого сравнения строк.
Готовы к экспериментам? Попробуйте интегрировать сопоставление Левенштейна в ваш следующий проект по обработке естественного языка или чат-бота с использованием Python и GPU Droplets от DigitalOcean для масштабируемых вычислений.
Связанные ресурсы
- https://linux-console.net/resources/articles/machine-learning-vs-natural-language-processing
- https://linux-console.net/community/tutorials/nlp-models-using-backtracking
- https://linux-console.net/resources/articles/nlp-vs-nlu
- https://linux-console.net/community/tutorials/prompt-based-learning-in-natural-language-processing
- Улучшение моделей НЛП против атак с использованием подрывных методов
Добавить комментарий