Расстояние Левенштейна (Levenshtein Distance или LD) определяет минимальное количество односимвольных операций — вставки, удаления или замены — необходимых для трансформации одной строки в другую. Эта метрика является основой для реализации алгоритмов нечёткого поиска (Fuzzy Search), которые позволяют обнаруживать текстовые совпадения при наличии опечаток, вариаций написания или незначительных ошибок в данных. Применение LD критично для задач, где требуется идентифицировать сходные, но не идентичные записи, например, при поиске по базе продуктов с возможными ошибками ввода или сопоставлении пользовательских запросов с релевантным контентом.
Проблема точного совпадения данных часто приводит к формированию «тёмных данных» (Dark Data) — неиспользованной информации, генерирующей затраты на хранение без получения ценности. Например, расхождения в написании названия компании на 5% могут привести к дублированию записей в CRM-системе, что увеличивает операционные издержки на 15-20% при обработке данных. Нечёткий поиск, использующий Расстояние Левенштейна, предоставляет механизм для обнаружения и исправления подобных несоответствий, значительно повышая качество данных и точность аналитики.
Архитектура решений, основанных на Расстоянии Левенштейна, часто включает индексы n-грамм или инвертированные индексы для предварительного отбора кандидатов, что сокращает вычислительную сложность полного сравнения. Метод динамического программирования используется для эффективного расчёта Расстояния Левенштейна, обеспечивая его применимость к строкам различной длины. Это позволяет использовать LD для широкого спектра задач: от дедупликации записей в реляционных базах данных до оптимизации поиска по неструктурированным текстовым массивам и анализа геномных последовательностей в биоинформатике.
Что такое Расстояние Левенштейна (LD): основы метрики различия строк
Расстояние Левенштейна (LD) представляет собой метрику, которая количественно определяет степень различия между двумя строками символов. Она измеряет минимальное количество односимвольных операций редактирования, необходимых для преобразования одной строки в другую. Эти операции включают вставку символа, удаление символа и замену одного символа другим. Каждая из этих операций считается одной «единицей» стоимости, а итоговое расстояние — это сумма таких единиц.
Данная метрика была предложена Владимиром Левенштейном в 1965 году и получила широкое распространение как фундаментальный инструмент в области нечёткого поиска и сопоставления строк. Понимание принципов Расстояния Левенштейна критически важно для разработки систем, способных эффективно обрабатывать текстовые данные с вариациями, опечатками или ошибками. Например, при поиске по продуктовой базе "Молоко 3,2%" и "Молок 3.2%" метрика LD позволяет идентифицировать эти записи как близкие, несмотря на расхождения, предотвращая дублирование и улучшая пользовательский опыт.
Основное значение Расстояния Левенштейна заключается в его способности предоставлять числовую оценку «схожести» двух строк, что позволяет ранжировать результаты поиска или группировать похожие данные. Чем меньше значение LD, тем более схожи строки. Этот принцип формирует основу для механизмов, используемых в проверке орфографии, системах рекомендаций, обнаружении плагиата и очистке данных.
Ключевые операции редактирования при вычислении Расстояния Левенштейна
Для преобразования одной строки в другую с использованием Расстояния Левенштейна применяются три элементарные операции. Каждая из этих операций имеет стоимость, равную единице, что делает метрику универсальной для оценки сложности трансформации.
Ниже представлены базовые операции редактирования и их характеристики:
| Операция | Описание | Пример (из «кошка» в «ложка») | Влияние на LD |
|---|---|---|---|
| Вставка | Добавление одного символа в строку. | «кошка» -> «кошкка» (вставка «к») | Увеличивает LD на 1 |
| Удаление | Удаление одного символа из строки. | «кошка» -> «коша» (удаление «к») | Увеличивает LD на 1 |
| Замена | Изменение одного символа на другой. | «кошка» -> «лошка» (замена «к» на «л») | Увеличивает LD на 1 (если символы разные) |
Принципы и свойства метрики Расстояния Левенштейна
Расстояние Левенштейна обладает рядом математических свойств, которые делают его надежным инструментом для измерения схожести строк. Эти свойства обеспечивают предсказуемость и применимость метрики в различных сценариях обработки данных.
- Неотрицательность: Расстояние Левенштейна всегда неотрицательно. LD(A, B) ≥ 0. Нулевое расстояние (LD = 0) означает, что строки A и B абсолютно идентичны.
- Симметричность: Порядок строк не влияет на результат. LD(A, B) = LD(B, A). Это означает, что стоимость преобразования строки A в B такая же, как стоимость преобразования B в A.
- Неравенство треугольника: LD(A, C) ≤ LD(A, B) + LD(B, C). Стоимость прямого преобразования строки A в C никогда не превышает суммы стоимостей преобразования A в B и затем B в C. Это фундаментальное свойство метрических пространств.
- Минимальность операций: Алгоритм всегда стремится найти минимальное количество операций, что гарантирует наиболее «эффективный» путь трансформации. Это ключевое отличие от простых подсчётов различий, где порядок или тип операций могут варьироваться.
Эти свойства подтверждают, что Расстояние Левенштейна является истинной метрикой, позволяющей корректно измерять «метрическое» расстояние между строками. Применение этой метрики в бизнес-процессах, таких как объединение данных из разных источников, позволяет достичь высокого уровня консистентности и снижения операционных издержек, связанных с обработкой некачественных или дублирующихся записей.
Механизм расчёта: ключевые операции редактирования Левенштейна
Расчёт расстояния Левенштейна (LD) основывается на последовательном применении трёх элементарных операций редактирования — вставки, удаления и замены символа. Эти операции, каждая из которых имеет единичную стоимость, позволяют количественно оценить минимальные трансформации, необходимые для преобразования одной строки в другую. Эффективное определение такого минимального пути трансформации является центральной задачей при вычислении LD и решается с помощью метода динамического программирования, что обеспечивает оптимальность и масштабируемость алгоритма для различных задач нечёткого поиска.
Динамическое программирование как основа расчёта расстояния Левенштейна
Метод динамического программирования (ДП) является стандартным подходом для вычисления расстояния Левенштейна. Он позволяет эффективно решить задачу, избегая избыточных вычислений за счёт сохранения и повторного использования результатов промежуточных подзадач. Основная идея заключается в построении матрицы (или таблицы), где каждая ячейка хранит минимальное расстояние Левенштейна между префиксами двух сравниваемых строк.
- Принцип оптимальной подструктуры: LD между двумя строками может быть найдено путём решения LD для их более коротких префиксов. Это позволяет разбить сложную задачу на ряд более простых, взаимосвязанных подзадач.
- Перекрывающиеся подзадачи: При решении исходной задачи многие подзадачи повторяются. Динамическое программирование кэширует результаты этих подзадач в матрице, предотвращая их многократное пересчитывание и значительно повышая производительность алгоритма.
Этот подход критически важен для обработки больших объёмов текстовых данных, где прямое рекурсивное вычисление без оптимизации ДП было бы крайне неэффективным. Применение ДП обеспечивает вычислительную реализуемость расстояния Левенштейна в реальных системах, от систем проверки орфографии до сложных механизмов дедупликации клиентских данных, где скорость обработки играет ключевую роль.
Стоимость операций: универсальный подход и вариации
В стандартной реализации расстояния Левенштейна стоимость каждой операции редактирования — вставки, удаления и замены — принимается равной единице. Такой универсальный подход обеспечивает простоту и широкую применимость метрики, отражая равнозначность каждой единичной трансформации.
Однако в некоторых специализированных сценариях, где контекст данных или природа ошибок известны, возможно применение взвешенных стоимостей операций. Это позволяет алгоритму быть более чувствительным к определённым типам различий. Например:
- Взвешенная замена: Если замена одного символа на другой является более или менее «дорогой» в зависимости от их схожести (например, замена «o» на «а» может быть дешевле, чем «o» на «z» из-за фонетической близости или близости на клавиатуре) можно назначить различные веса для разных пар замен.
- Взвешенные вставки/удаления: В некоторых случаях вставка или удаление символа может иметь большую или меньшую стоимость, чем замена, в зависимости от домена задачи.
Хотя стандартное LD использует фиксированную стоимость, понимание возможности варьирования этих весов открывает пути для создания более тонко настроенных алгоритмов нечёткого сопоставления. Это особенно ценно в таких областях, как анализ названий медицинских препаратов, где даже небольшие ошибки могут иметь критические последствия, или в системах идентификации клиентов, где необходимо учитывать распространённые опечатки. Такой гибкий подход к назначению весов может значительно повысить точность обнаружения релевантных совпадений и снизить количество ложноположительных или ложноотрицательных результатов.
Практический Расчёт Расстояния Левенштейна: Пример и Алгоритм
Для полного понимания принципов работы Расстояния Левенштейна (LD) необходимо рассмотреть его практический расчёт, который демонстрирует пошаговое применение метода динамического программирования. Этот механизм лежит в основе таких критически важных функций, как обнаружение дубликатов в базах данных или повышение релевантности поисковых запросов в системах нечёткого поиска, где даже незначительные расхождения могут исказить результаты, приводя к потере потенциальных клиентов или некорректной аналитике.
Подготовка к расчёту: инициализация матрицы Расстояния Левенштейна
Вычисление Расстояния Левенштейна начинается с формирования матрицы, которая будет использоваться для кэширования промежуточных результатов. Размер матрицы определяется длинами двух сравниваемых строк: если длина первой строки составляет m, а второй — n, то матрица будет иметь размер (m+1) на (n+1). Дополнительная строка и столбец необходимы для представления пустых префиксов строк.
В качестве практического примера рассмотрим вычисление Расстояния Левенштейна между двумя строками:
- Строка 1 (S1): "синица", длина m = 6
- Строка 2 (S2): "лисица", длина n = 6
Матрица будет иметь размер (6+1) x (6+1), то есть 7x7. Первая строка и первый столбец матрицы инициализируются значениями от 0 до максимальной длины соответствующего префикса. Это отражает стоимость преобразования пустой строки в префикс (путём последовательных вставок) или префикса в пустую строку (путём последовательных удалений).
Начальное состояние матрицы после инициализации выглядит следующим образом:
| л | и | с | и | ц | а | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| с | 1 | ||||||
| и | 2 | ||||||
| н | 3 | ||||||
| и | 4 | ||||||
| ц | 5 | ||||||
| а | 6 |
Пошаговое заполнение матрицы и вычисление LD
Заполнение матрицы происходит итеративно, начиная с ячейки D[1][1]. Каждая ячейка D[i][j] вычисляется как минимальное значение из трёх возможных операций редактирования, описанных ранее:
- Удаление символа из S1: Вычисляется как D[i-1][j] + 1. Эта операция отражает стоимость удаления i-го символа из первой строки, чтобы достичь префикса длины j из второй строки.
- Вставка символа в S1: Вычисляется как D[i][j-1] + 1. Эта операция отражает стоимость вставки j-го символа из второй строки, чтобы достичь префикса длины i из первой строки.
- Замена или совпадение символов: Вычисляется как D[i-1][j-1] + cost. Переменная cost равна 0, если i-й символ S1 совпадает с j-м символом S2 (операция совпадения), и 1, если они различаются (операция замены).
Рассмотрим несколько шагов заполнения матрицы для нашего примера "синица" и "лисица":
- Ячейка D[1][1] (сравниваем 'с' из "синица" и 'л' из "лисица"):
- Удаление 'с': D[0][1] + 1 = 1 + 1 = 2
- Вставка 'л': D[1][0] + 1 = 1 + 1 = 2
- Замена 'с' на 'л': D[0][0] + 1 (так как 'с' != 'л') = 0 + 1 = 1
- D[1][1] = min(2, 2, 1) = 1
- Ячейка D[2][2] (сравниваем 'и' из "синица" и 'и' из "лисица"):
- Удаление 'и': D[1][2] + 1 = 2 + 1 = 3 (при условии, что D[1][2] уже вычислено и равно 2)
- Вставка 'и': D[2][1] + 1 = 2 + 1 = 3 (при условии, что D[2][1] уже вычислено и равно 2)
- Совпадение 'и' с 'и': D[1][1] + 0 (так как 'и' == 'и') = 1 + 0 = 1
- D[2][2] = min(3, 3, 1) = 1
Последовательное применение этого правила для всех ячеек заполняет всю матрицу. Окончательное значение Расстояния Левенштейна находится в правом нижнем углу матрицы.
Полностью заполненная матрица для строк "синица" и "лисица":
| л | и | с | и | ц | а | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| с | 1 | 1 | 2 | 2 | 3 | 4 | 5 |
| и | 2 | 2 | 1 | 2 | 2 | 3 | 4 |
| н | 3 | 3 | 2 | 2 | 3 | 3 | 4 |
| и | 4 | 4 | 3 | 3 | 2 | 3 | 4 |
| ц | 5 | 5 | 4 | 4 | 3 | 2 | 3 |
| а | 6 | 6 | 5 | 5 | 4 | 3 | 2 |
Итоговое Расстояние Левенштейна между "синица" и "лисица" составляет 2, что соответствует значению в ячейке D[6][6]. Это означает, что для преобразования одной строки в другую необходимо выполнить минимум две операции редактирования, например, замену 'с' на 'л' и 'н' на 'с'.
В таблице ниже приведены примеры интерпретации Расстояния Левенштейна для различных бизнес-сценариев:
| Расстояние LD | Интерпретация | Бизнес-сценарий | Пример |
|---|---|---|---|
| 0 | Точное совпадение | Идентификация абсолютно идентичных записей, критичных для безопасности или уникальности данных. | Поиск по ID записи, сверка хешей данных, верификация уникальных идентификаторов. |
| 1 | Незначительное различие (1 опечатка/вставка/удаление) | Выявление опечаток в именах, названиях продуктов, адресах; исправление пользовательских запросов. | "iPhone" vs "iPhne", "Москва" vs "Мосвка", "Google" vs "Goggle". |
| 2-3 | Умеренное различие | Дедупликация записей с распространёнными вариациями написания, синонимами или акронимами, агрегация данных. | "Microsoft Corp." vs "Microsoft Corporation", "ООО Техно" vs "OOO Техно", "ФГУП" vs "ФГУП-Р". |
| >3 (с учётом длины строк) | Значительное различие | Может указывать на разные сущности, но может быть полезно для очень длинных строк или при очень "мягком" поиске, требующем высокой толерантности к ошибкам. | Поиск в больших текстовых документах, где допустимы множественные ошибки или вариации; семантический анализ длинных фраз. |
Сходные метрики различия строк: альтернативы и расширения Левенштейна
Расстояние Левенштейна (LD) является мощным и универсальным инструментом для оценки схожести строк. Однако в ряде специфических сценариев его ограничения, такие как высокая вычислительная сложность для длинных текстов, отсутствие семантического контекста и особенности обработки определённых типов ошибок (например, транспозиций), требуют применения альтернативных или расширенных метрик. Эти метрики предлагают более тонкую настройку и оптимизацию для конкретных бизнес-задач, от дедупликации клиентских данных до семантического поиска в больших текстовых массивах.
Расстояние Дамерау — Левенштейна: Учёт транспозиций
Расстояние Дамерау — Левенштейна (Damerau-Levenshtein Distance, DLD) является расширением стандартного расстояния Левенштейна, которое дополнительно учитывает одну из наиболее распространённых ошибок ввода — транспозицию (перестановку двух соседних символов) — как одну операцию редактирования. В стандартном LD транспозиция, например, преобразование "acb" в "abc", будет стоить 2 операции (замена 'c' на 'b', затем 'b' на 'c', или удаление 'c', вставка 'b', удаление 'b', вставка 'c' — в зависимости от пути). Расстояние Дамерау — Левенштейна снижает стоимость таких операций, признавая их единичными.
DLD особенно ценно для задач, где часты опечатки, связанные с перестановкой символов, например, при поиске по именам, названиям продуктов или вводе адресов. Рассматривая транспозицию как одну операцию, DLD обеспечивает более точную оценку человеческих ошибок, что приводит к более релевантным результатам в системах автокоррекции, поисковых подсказках и дедупликации данных. Например, для пар "teh" и "the", DLD будет равно 1, в то время как стандартное расстояние Левенштейна может быть равно 2.
Сравнение расстояния Левенштейна и расстояния Дамерау — Левенштейна:
| Характеристика | Расстояние Левенштейна (LD) | Расстояние Дамерау — Левенштейна (DLD) |
|---|---|---|
| Базовые операции | Вставка, удаление, замена | Вставка, удаление, замена, транспозиция |
| Стоимость транспозиции | 2 операции (удаление + вставка или 2 замены) | 1 операция |
| Вычислительная сложность | O(m*n) | O(m*n) (с небольшим усложнением для транспозиций) |
| Применимость | Общая метрика редактирования строк | Особенно эффективно для коррекции опечаток с транспозициями |
| Пример ("acb" в "abc") | LD = 2 | DLD = 1 |
Метрики на основе совпадения символов и токенов
Для сценариев, где стандартное посимвольное расстояние Левенштейна не всегда отражает истинную схожесть (например, из-за длины строк, порядка слов или семантических различий), применяются метрики, основанные на анализе совпадения символов, N-грамм или токенов. Эти подходы часто используются для более гибкой оценки схожести, особенно в задачах обработки естественного языка и информационного поиска.
Расстояние Джаро и Джаро-Винклера: Оценка схожести имён
Расстояние Джаро (Jaro Distance) и его модификация, расстояние Джаро-Винклера (Jaro-Winkler Distance), предназначены для измерения схожести строк, особенно эффективны для коротких строк, таких как имена людей, названия городов или организаций. Эти метрики сосредоточены на количестве совпадающих символов и их порядке, а не на операциях редактирования.
- Расстояние Джаро: Рассчитывает схожесть на основе количества совпадающих символов и транспозиций (не путать с операцией транспозиции DLD). Совпадающие символы должны находиться в пределах определённого радиуса.
- Расстояние Джаро-Винклера: Улучшает расстояние Джаро, придавая больший вес совпадениям в начале строк (общему префиксу). Это эмпирическое наблюдение, что ошибки в начале слова встречаются реже и имеют больший вес для человеческого восприятия схожести.
Бизнес-ценность метрик Джаро-Винклера проявляется в системах дедупликации клиентских баз данных, где важно сопоставлять имена и фамилии с возможными ошибками ввода, но без полного переписывания слов. Например, для "Smith" и "Smoth", LD будет 2, а Jaro-Winkler даст высокую оценку схожести из-за общего префикса "Sm" и небольшого расхождения далее. Это позволяет более точно выявлять дубликаты и улучшать клиентский опыт, снижая количество ложноотрицательных совпадений.
Коэффициент Жаккара и коэффициент Дайса (Сёренсена-Дайса): Анализ пересечения токенов
Коэффициент Жаккара (Jaccard Index) и коэффициент Дайса (Dice Coefficient, или Сёренсена-Дайса) — это метрики, которые измеряют схожесть между двумя множествами. Применительно к строкам, их часто используют для сравнения наборов N-грамм или токенов (слов), извлечённых из строк.
- Коэффициент Жаккара: Вычисляется как отношение размера пересечения двух множеств к размеру их объединения. Значение варьируется от 0 (нет общих элементов) до 1 (множества идентичны).
- Коэффициент Дайса: Вычисляется как удвоенное отношение размера пересечения двух множеств к сумме размеров этих множеств. Также варьируется от 0 до 1.
При сравнении строк эти метрики требуют предварительного этапа токенизации или генерации N-грамм. Например, для строк "кот ест рыбу" и "рыба ест кота" стандартное LD покажет большое расстояние из-за перестановки слов, тогда как метрики Жаккара или Дайса, при использовании слов как токенов, могут показать 100-процентную схожесть, так как набор слов одинаков. При использовании N-грамм эти метрики чувствительны к частичным совпадениям.
Бизнес-ценность этих коэффициентов высока в задачах кластеризации документов, поиске дубликатов в текстовых массивах, анализе плагиата и рекомендательных системах, где важно оценивать схожесть контента, а не только посимвольные различия. Они позволяют эффективно работать с более длинными текстами и оценивать "тематическое" сходство.
Косинусное сходство: Семантический анализ текстовых массивов
Косинусное сходство (Cosine Similarity) — это метрика, которая измеряет косинус угла между двумя ненулевыми векторами в многомерном пространстве. Применительно к тексту, строки преобразуются в векторы признаков (например, с использованием TF-IDF или векторов N-грамм), а затем вычисляется косинус угла между этими векторами. Чем ближе косинус к 1, тем более схожи тексты.
Эта метрика особенно эффективна для оценки семантической схожести или схожести тем в длинных текстовых документах. Она менее чувствительна к длине документа и порядку слов, чем посимвольные метрики, и хорошо работает с разреженными данными (большинство слов не встречаются в обоих документах).
Бизнес-ценность косинусного сходства огромна в системах рекомендаций, поиске релевантных документов, классификации текста, анализе тональности и при обнаружении похожих статей или новостей. Например, если пользователь ищет "финансовые новости", система может найти документы, которые содержат схожие термины, даже если точных совпадений по фразе нет. Это позволяет организациям более точно понимать пользовательские запросы и предоставлять более персонализированный контент.
Расстояние по наибольшей общей подпоследовательности (LCS)
Расстояние по наибольшей общей подпоследовательности (Longest Common Subsequence Distance, LCS Distance) — это метрика, которая определяет количество удалений, необходимых для преобразования одной строки в другую, после того как из обеих строк удалены символы, не входящие в их наибольшую общую подпоследовательность. Сама по себе LCS — это самая длинная последовательность символов, которая является подпоследовательностью обеих исходных строк (не обязательно непрерывная). Расстояние LCS рассчитывается как сумма длин двух строк минус удвоенная длина LCS.
В отличие от расстояния Левенштейна, LCS не учитывает операции замены. Оно фокусируется исключительно на порядке и наличии общих символов. Например, для "abcde" и "ace", LCS будет "ace" (длиной 3). LD будет 2 (удаление 'b', удаление 'd'), а LCS Distance = (5 + 3) - 2*3 = 8 - 6 = 2. Однако для "kitten" и "sitting", LCS = "ittn" (длиной 4), LCS Distance = (6+7) - 2*4 = 13 - 8 = 5. LD же для этой пары составляет 3.
LCS полезно в сценариях, где важно сохранить относительный порядок символов и оценить схожесть без учёта замен, например, при анализе последовательностей команд, логов систем или в некоторых задачах биоинформатики, где вставки и удаления более релевантны, чем замены. Оно используется в контроле версий (например, в системах Diff), где необходимо определить минимальные изменения между двумя версиями файла.
В таблице ниже представлено сравнительное резюме рассмотренных метрик и их рекомендуемое применение:
| Метрика | Основные особенности | Сфера оптимального применения | Преимущества перед LD | Ограничения |
|---|---|---|---|---|
| Расстояние Левенштейна (LD) | Минимальные вставки, удаления, замены | Общий нечёткий поиск, дедупликация коротких-средних строк | Универсальность, простота понимания | Не учитывает транспозиции как 1 операцию, низкая семантическая чувствительность, O(m*n) |
| Расстояние Дамерау — Левенштейна (DLD) | LD + транспозиции как 1 операция | Коррекция опечаток, дедупликация с частыми транспозициями | Более точная модель человеческих опечаток | Вычислительно сложнее, чем базовый LD для некоторых реализаций |
| Расстояние Джаро-Винклера | Совпадение символов, больший вес префиксам | Сравнение имён, коротких названий | Высокая эффективность для имён/коротких строк, чувствительность к порядку | Менее универсально, не подходит для очень длинных текстов |
| Коэффициент Жаккара/Дайса | Схожесть множеств (N-грамм, токенов) | Сравнение документов, кластеризация по содержимому | Хорошо для длинных текстов, нечувствительность к порядку слов (при токенизации) | Требует токенизации/N-граммирования, теряет порядок символов внутри токенов |
| Косинусное сходство | Косинус угла между векторными представлениями | Семантический поиск, рекомендации, классификация длинных текстов | Высокая устойчивость к длине текста, семантическая направленность (с TF-IDF) | Требует преобразования в векторное пространство, вычислительно дорого для построения векторов |
| Расстояние по наибольшей общей подпоследовательности (LCS) | Фокус на общих символах с сохранением порядка | Анализ версий, сравнение фрагментов кода, биоинформатика | Учитывает только вставки/удаления, игнорируя замены | Нечувствительно к заменам, менее универсально для общих задач |
Выбор и внедрение конкретной метрики, или их комбинации, должно быть подкреплено тщательным анализом данных, тестированием на реальных примерах и мониторингом метрик качества (точность, полнота) в продуктивной среде. Это позволит обеспечить максимальную эффективность нечёткого поиска и дедупликации, снизить операционные издержки и повысить ценность данных для принятия бизнес-решений.
Список литературы
- Levenshtein V. I. Binary codes capable of correcting deletions, insertions, and reversals // Soviet Physics Doklady. — 1966. — Vol. 10, No. 8. — P. 707–710.
- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. — 3rd ed. — MIT Press, 2009.
- Jurafsky D., Martin J. H. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. — 3rd ed. — Pearson Prentice Hall, 2018.
- Gusfield D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. — Cambridge University Press, 1997.
- Manning C. D., Raghavan P., Schütze H. Introduction to Information Retrieval. — Cambridge University Press, 2008.
