Введение
В вычислительной лингвистике и информатике расстояние редактирования — это метрика строк, то есть способ количественной оценки степени несхожести двух строк (например, слов), измеряемый минимальным количеством операций, необходимых для преобразования одной строки в другую. Расстояния редактирования находят применение в обработке естественного языка, где автоматическая коррекция орфографии может определять возможные варианты исправления неправильно написанного слова, выбирая слова из словаря с минимальным расстоянием до исходного слова. В биоинформатике оно может использоваться для оценки сходства последовательностей ДНК, которые можно рассматривать как строки, состоящие из букв A, C, G и T. Различные определения расстояния редактирования используют разные наборы операций. Операции расстояния Левенштейна включают удаление, вставку или замену символа в строке. Поскольку это наиболее распространенная метрика, термин «расстояние Левенштейна» часто используется как синоним расстояния редактирования.
In computational linguistics and computer science, edit distance is a string metric, i. e. a way of quantifying how dissimilar two strings (e. g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T.
Different definitions of an edit distance use different sets of like operations. Levenshtein distance operations are the removal, insertion, or substitution of a character in the string. Being the most common metric, the term Levenshtein distance is often used interchangeably with edit distance.
Типы расстояния редактирования
Различные типы расстояния редактирования допускают разные наборы строковых операций. Например:
Расстояние Левенштейна допускает удаление, вставку и замену символов. Расстояние, основанное на наибольшей общей подпоследовательности (LCS), допускает только вставку и удаление, но не замену. Расстояние Хэмминга допускает только замену, поэтому оно применимо только к строкам одинаковой длины. Расстояние Дамерау — Левенштейна допускает вставку, удаление, замену и транспозицию (перестановку) двух соседних символов. Расстояние Джаро допускает только транспозицию. Некоторые расстояния редактирования определяются как параметризуемая метрика, вычисляемая с использованием определенного набора допустимых операций редактирования, каждой из которых присваивается стоимость (возможно, бесконечная). Это еще больше обобщается алгоритмами выравнивания последовательностей ДНК, такими как алгоритм Смита — Уотермана, который делает стоимость операции зависимой от места ее применения.
The Levenshtein distance allows deletion, insertion and substitution. The longest common subsequence (LCS) distance allows only insertion and deletion, not substitution. The Hamming distance allows only substitution, hence, it only applies to strings of the same length. The Damerau–Levenshtein distance allows insertion, deletion, substitution, and the transposition (swapping) of two adjacent characters. The Jaro distance allows only transposition. Some edit distances are defined as a parameterizable metric calculated with a specific set of allowed edit operations, and each operation is assigned a cost (possibly infinite). This is further generalized by DNA sequence alignment algorithms such as the Smith–Waterman algorithm, which make an operation's cost depend on where it is applied.
Формальное определение и свойства
При наличии двух строк a и b в алфавите Σ (например, набор символов ASCII, набор байтов [0–255] и т. д.), расстояние редактирования — это минимальный вес последовательности операций редактирования, преобразующих строку a в строку b. Один из самых простых наборов операций редактирования был предложен Левенштейном в 1966 году. Были предложены и дополнительные элементарные операции. Расстояние Дамерау-Левенштейна рассматривает как одну операцию редактирования распространённую ошибку: транспозицию двух соседних символов, формально определяемую операцией, заменяющей uxyv на uyxv. Другие варианты расстояния редактирования получаются путём ограничения набора допустимых операций. Расстояние, основанное на наибольшей общей подпоследовательности (LCS), является расстоянием редактирования, в котором используются только операции вставки и удаления, обе с единичной стоимостью. Расстояние Левенштейна и расстояние LCS с единичной стоимостью удовлетворяют вышеуказанным условиям и, следовательно, аксиомам метрики. В литературе также рассматриваются варианты расстояния редактирования, которые не являются корректными метриками.
Additional primitive operations have been suggested. Damerau–Levenshtein distance counts as a single edit a common mistake: transposition of two adjacent characters, formally characterized by an operation that changes uxyv into uyxv. Other variants of edit distance are obtained by restricting the set of operations. Longest common subsequence (LCS) distance is edit distance with insertion and deletion as the only two edit operations, both at unit cost. Levenshtein distance and LCS distance with unit cost satisfy the above conditions, and therefore the metric axioms. Variants of edit distance that are not proper metrics have also been considered in the literature.
Общий алгоритм
Используя оригинальные операции Левенштейна, (несимметричное) расстояние редактирования между строками и задаётся выражением , определяемым рекуррентным соотношением, хотя оно неоднократно изобреталось независимо. Общий рекурсивный алгоритм "разделяй и властвуй" для решения подобных рекуррентных соотношений и эффективного извлечения оптимальной последовательности операций с использованием кэша, занимающего линейное пространство относительно размера входных данных, представлен Чоудхури, Ле и Рамачандран.
Улучшенные алгоритмы
Улучшая алгоритм Вагнера-Фишера, описанный выше, Укконен описывает несколько вариантов, один из которых принимает две строки и максимальное расстояние редактирования s и возвращает результат. Это достигается за счет вычисления и хранения лишь части таблицы динамического программирования вокруг её диагонали. Этот алгоритм выполняется за время , где m и n — длины строк. Объём используемой памяти составляет или , в зависимости от необходимости восстановления последовательности редактирования. Для конечного алфавита и стоимостей редактирования, кратных друг другу, самый быстрый известный точный алгоритм Масека и Патерсона имеет максимальное время работы O(nm/logn).
Приложения
Расстояние редактирования находит применение в вычислительной биологии и обработке естественного языка, например, для исправления орфографических ошибок или ошибок оптического распознавания символов, а также для приближенного сопоставления строк, где целью является поиск соответствий для коротких строк в большом количестве более длинных текстов в ситуациях, когда ожидается небольшое число различий. Существуют различные алгоритмы, решающие задачи, помимо вычисления расстояния между двумя строками, для решения связанных типов задач. Алгоритм Хиршберга вычисляет оптимальное выравнивание двух строк, при котором оптимальность определяется как минимизация расстояния редактирования. Приближенное сопоставление строк может быть сформулировано в терминах расстояния редактирования. Алгоритм Укконена 1985 года принимает строку p, называемую образцом, и константу k; затем он строит детерминированный конечный автомат, который находит в произвольной строке s подстроку, расстояние редактирования которой до p не превышает k (см. алгоритм Aho–Corasick, который аналогичным образом строит автомат для поиска любого из множества образцов, но без учета операций редактирования). Алгоритм битапа является аналогичным алгоритмом для приближенного сопоставления строк, также определенным в терминах расстояния редактирования. Автоматы Левенштейна – это конечные автоматы, распознающие множество строк в пределах ограниченного расстояния редактирования от фиксированной эталонной строки, где является расстоянием редактирования строк. Когда язык L не зависит от контекста, существует алгоритм динамического программирования с кубической сложностью, предложенный Ахо и Петерсоном в 1972 году, который вычисляет расстояние редактирования языка. Для менее выразительных семейств грамматик, таких как регулярные грамматики, существуют более быстрые алгоритмы для вычисления расстояния редактирования. Расстояние редактирования языка нашло множество различных применений, таких как свертывание РНК, коррекция ошибок и решения задачи оптимальной генерации стека.