Расстояние Левенштейна
Расстоя́ние Левенштéйна (или редакцио́нное расстоя́ние) — это метрика, используемая для измерения разницы между двумя последовательностями символов. Она определяется как минимальное количество операций вставки, удаления и замены одного символа, необходимых для преобразования одной строки в другую[1]. Этот метод широко применяется в различных областях, таких как обработка естественного языка, биоинформатика, коррекция ошибок ввода и сравнение текстов.
История[править]
Концепция расстояния Левенштейна была впервые предложена советским математиком Владимиром Левенштейном в 1965 году[1]. В своей работе он исследовал задачи коррекции ошибок в передаче данных и предложил алгоритм для вычисления минимального числа операций, необходимых для преобразования одной строки в другую. Хотя сам термин «расстояние Левенштейна» стал широко использоваться позже, его идеи оказали значительное влияние на развитие алгоритмов обработки строк[2].
Определение[править]
Расстояние Левенштейна между двумя строками и длиной и соответственно определяется как минимальное количество операций редактирования, необходимых для преобразования в . Допустимыми операциями являются:
- вставка символа;
- удаление символа;
- замена символа на другой.
Формально, расстояние Левенштейна можно вычислить с помощью рекуррентного соотношения[3]:
где равно 0, если символы и совпадают и 1 в противном случае.
![{\displaystyle d(i,j)={\begin{cases}\max(i,j),&{\text{если }}\min(i,j)=0,\\\min {\begin{cases}d(i-1,j)+1,\\d(i,j-1)+1,\\d(i-1,j-1)+\delta (S[i],T[j]),\end{cases}}&{\text{иначе}},\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25a2d317d31f67210b5271bd3c53c6cc57994a3a)
![{\displaystyle \delta (S[i],T[j])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7163a80a5f0a185f8d1c635b176fdb3883ae7f7a)
![{\displaystyle S[i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcac18d365382145819781be2eb59d84dd8b4496)
![{\displaystyle T[j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb1f9ca1ed801caf88d5004aa3685644667099b6)
Алгоритм вычисления[править]
Наиболее известный алгоритм для вычисления расстояния Левенштейна был предложен Робертом Вагнером и Майклом Фишером в 1974 году[3]. Этот алгоритм использует динамическое программирование и строит матрицу размером , где каждая ячейка содержит расстояние Левенштейна между подстроками и . Сложность алгоритма составляет .
![{\displaystyle d[i][j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e55a31f5609a7970e2147c14db834b72c299e82)
![{\displaystyle S[1..i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5aeb3a1b0d8166cad66dd24c1ea5faeec430ae2)
![{\displaystyle T[1..j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a68f1546f038b6333f71c508b30f41f25bad404)
Применения[править]
Расстояние Левенштейна находит применение во множестве областей:
- Обработка естественного языка. В задачах автоматической коррекции текста расстояние Левенштейна используется для поиска наиболее вероятных исправлений ошибок ввода[4]. Например, при наборе слова «teh» система может предложить исправление на «the», так как расстояние Левенштейна между этими словами равно 1.
- Биоинформатика. В биоинформатике расстояние Левенштейна применяется для анализа последовательностей ДНК, РНК и белков[5]. Оно помогает оценивать степень сходства между генетическими последовательностями и выявлять мутации.
- Поиск информации. В системах поиска информации расстояние Левенштейна используется для улучшения релевантности результатов поиска. Например, если пользователь вводит запрос с опечаткой, система может найти документы, содержащие слова, близкие к запросу по расстоянию Левенштейна[6].
Оптимизации[править]
Для больших строк стандартный алгоритм вычисления расстояния Левенштейна может быть неэффективным. Существуют различные оптимизации, такие как использование двух строк вместо полной матрицы[7], что снижает пространственную сложность до . Также разработаны приближенные методы, такие как алгоритмы на основе суффиксных деревьев[8].
Альтернативные метрики[править]
Помимо расстояния Левенштейна, существуют другие метрики для сравнения строк, такие как расстояние Хэмминга[9], которое учитывает только замены символов, и расстояние Дамерау-Левенштейна[10], которое дополнительно учитывает транспозицию соседних символов.
Примечания[править]
- ↑ 1,0 1,1 Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady.
- ↑ 3,0 3,1 Wagner, R. A., & Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM (JACM).
- ↑ Brill, E., & Moore, R. C. (2000). An improved error model for noisy channel spelling correction. In Proceedings of the 38th Annual Meeting on Association for Computational Linguistics.
- ↑ Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998). Biological sequence analysis: Probabilistic models of proteins and nucleic acids. Cambridge University Press.
- ↑ Crochemore, M., Hancart, C., & Lecroq, T. (2003). Algorithms on strings. Cambridge University Press.
- ↑ Myers, G. (1999). A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM (JACM).
- ↑ Ukkonen, E. (1985). Algorithms for approximate string matching. Information and Control.
- ↑ Hamming, R. W. (1950). Error detecting and error correcting codes. Bell System Technical Journal.
- ↑ Damerau, F. J. (1964). A technique for computer detection and correction of spelling errors. Communications of the ACM.
 | Одним из источников, использованных при создании данной статьи, является статья из википроекта «Знание.Вики» («znanierussia.ru») под названием «Расстояние Левенштейна», расположенная по следующим адресам:
Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Знание.Вики предлагается прочитать материал «Почему Циклопедия?». |
|---|