Изменить расстояние

Метрика сходства строк в компьютерных науках

В вычислительной лингвистике и информатике расстояние редактирования — это строковая метрика , то есть способ количественной оценки того, насколько непохожи друг на друга две строки (например, слова), который измеряется путем подсчета минимального количества операций, необходимых для преобразования одной строки в другую. Расстояния редактирования находят применение в обработке естественного языка , где автоматическая коррекция орфографии может определять кандидаты на исправление неправильно написанного слова, выбирая из словаря слова, которые имеют небольшое расстояние до рассматриваемого слова. В биоинформатике его можно использовать для количественной оценки сходства последовательностей ДНК , которые можно рассматривать как строки букв A, C, G и T.

Различные определения расстояния редактирования используют различные наборы подобных операций. Операции расстояния Левенштейна — это удаление, вставка или замена символа в строке. Будучи наиболее распространенной метрикой, термин расстояние Левенштейна часто используется взаимозаменяемо с расстоянием редактирования . ^[1]

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

Различные типы расстояния редактирования допускают различные наборы строковых операций. Например:

Некоторые расстояния редактирования определяются как параметризуемая метрика, вычисляемая с помощью определенного набора разрешенных операций редактирования, и каждой операции назначается стоимость (возможно, бесконечная). Это далее обобщается алгоритмами выравнивания последовательностей ДНК , такими как алгоритм Смита-Уотермана , которые делают стоимость операции зависящей от того, где она применяется.

Формальное определение и свойства

Если даны две строки a и b в алфавите Σ (например, набор символов ASCII , набор байтов [0..255] и т. д.), расстояние редактирования d( a , b ) представляет собой минимально-весовой ряд операций редактирования, который преобразует a в b . Один из простейших наборов операций редактирования определен Левенштейном в 1966 году: ^[2]

Вставка одного символа. Если a = u v , то вставка символа x даёт u x v . Это также можно обозначить ε→ x , используя ε для обозначения пустой строки.

Удаление одного символа изменяет u x v на u v ( x →ε).

Замена одного символа x на символ y ≠ x изменяет u x v на u y v ( x → y ).

В первоначальном определении Левенштейна каждая из этих операций имеет единичную стоимость (за исключением того, что замена символа на самого себя имеет нулевую стоимость), поэтому расстояние Левенштейна равно минимальному числу операций, необходимых для преобразования a в b . Более общее определение связывает с операциями неотрицательные весовые функции w _ins ( x ), w _del ( x ) и w _sub ( x ,  y ). ^[2]

Были предложены дополнительные примитивные операции. Расстояние Дамерау–Левенштейна считается одним редактированием распространенная ошибка: транспозиция двух соседних символов, формально характеризуемая операцией, которая изменяет u x y v на u y x v . ^{[3] [4]} Для задачи исправления вывода OCR использовались операции слияния и разделения , которые заменяют один символ на пару или наоборот. ^[4]

Другие варианты расстояния редактирования получаются путем ограничения набора операций. Расстояние самой длинной общей подпоследовательности (LCS) — это расстояние редактирования, в котором вставка и удаление являются единственными двумя операциями редактирования, обе по стоимости единицы. ^{[1] : 37} Аналогично, разрешая только замены (опять же по стоимости единицы), получается расстояние Хэмминга ; это должно быть ограничено строками одинаковой длины. ^[1] Расстояние Джаро–Винклера можно получить из расстояния редактирования, где разрешены только транспозиции.

Пример

Расстояние Левенштейна между «котёнок» и «сидит» равно 3. Минимальный сценарий редактирования, преобразующий первое во второе, выглядит следующим образом:

1. k itten → s itten (замените «k» на «s»)
2. sitt e n → sitt i n (замените «e» на «i»)
3. ситтин → ситтин г (вставьте "г" в конце)

Расстояние LCS (только вставки и удаления) дает другое расстояние и минимальный сценарий редактирования:

1. k itten → itten (удалить «k» в цифре 0)
2. itten → s itten (вставьте "s" в 0)
3. sitt e n → sittn (удалить «e» в цифре 4)
4. sittn → sitt i n (вставьте «i» в цифру 4)
5. сижу → сижу г (вставьте "г" в 6)

на общую стоимость/расстояние 5 операций.

Характеристики

Расстояние редактирования с неотрицательной стоимостью удовлетворяет аксиомам метрики , что приводит к метрическому пространству строк, когда выполняются следующие условия: ^{[1] : 37}

• Каждая операция редактирования имеет положительную стоимость;
• Для каждой операции существует обратная операция с равной стоимостью.

При этих свойствах метрические аксиомы выполняются следующим образом:

d ( a , b ) = 0 тогда и только тогда, когда a = b, поскольку каждая строка может быть тривиально преобразована в себя с использованием ровно нуля операций.

d ( a , b ) > 0, когда a ≠ b , так как для этого потребуется как минимум одна операция с ненулевой стоимостью.

d ( a , b ) = d ( b , a ) по равенству стоимости каждой операции и ее обратной.

Неравенство треугольника: d ( a , c ) ≤ d ( a , b ) + d ( b , c ). ^[5]

Расстояние Левенштейна и расстояние LCS с единичной стоимостью удовлетворяют вышеуказанным условиям, а значит, и аксиомам метрики. Варианты расстояния редактирования, которые не являются собственными метриками, также рассматривались в литературе. ^[1]

Другие полезные свойства расстояний редактирования удельной стоимости включают в себя:

• Расстояние LCS ограничено сверху суммой длин пары строк. ^{[1] : 37}
• Расстояние LCS является верхней границей расстояния Левенштейна.
• Для строк одинаковой длины расстояние Хэмминга является верхней границей расстояния Левенштейна. ^[1]

Независимо от стоимости/веса, для всех расстояний редактирования справедливо следующее свойство:

• Когда a и b имеют общий префикс, этот префикс не влияет на расстояние. Формально, когда a = uv и b = uw , то d ( a , b ) = d ( v , w ). ^[4] Это позволяет ускорить многие вычисления, включающие расстояние редактирования и скрипты редактирования, поскольку общие префиксы и суффиксы можно пропустить за линейное время.

Вычисление

Первый алгоритм для вычисления минимального расстояния редактирования между парой строк был опубликован Дамеро в 1964 году. ^[6]

Общий алгоритм

Используя оригинальные операции Левенштейна, (несимметричное) расстояние редактирования от до задается выражением , определяемым рекуррентным соотношением ^[2] ${\displaystyle a=a_{1}\ldots a_{m}}$ ${\displaystyle b=b_{1}\ldots b_{n}}$ ${\displaystyle d_{mn}}$

${\displaystyle {\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}}$

Этот алгоритм можно обобщить для обработки транспозиций, добавив еще один член в минимизацию рекурсивного предложения. ^[3]

Прямой, рекурсивный способ оценки этой рекуррентности занимает экспоненциальное время . Поэтому его обычно вычисляют с использованием алгоритма динамического программирования , который обычно приписывают Вагнеру и Фишеру , ^[7] хотя он имеет историю множественных изобретений. ^{[2] [3]} После завершения алгоритма Вагнера-Фишера минимальная последовательность операций редактирования может быть считана как обратный след операций, используемых во время алгоритма динамического программирования, начиная с . ${\displaystyle d_{mn}}$

Этот алгоритм имеет временную сложность Θ( m n ), где m и n — длины строк. Когда построена полная таблица динамического программирования, ее пространственная сложность также равна Θ( m n ) ; ее можно улучшить до Θ(min( m , n )), заметив, что в любой момент времени алгоритму требуется только две строки (или два столбца) в памяти. Однако эта оптимизация делает невозможным считывание минимальной серии операций редактирования. ^[3] Линейно-пространственное решение этой проблемы предлагается алгоритмом Хиршберга . ^{[8] : 634} Общая рекурсивная структура «разделяй и властвуй» для решения таких рекуррентных уравнений и извлечения оптимальной последовательности операций с эффективностью кэширования в пространстве, линейном по размеру входных данных, предоставлена ​​Чоудхури, Ле и Рамачандраном. ^[9]

Улучшенные алгоритмы

Улучшая алгоритм Вагнера-Фишера, описанный выше, Укконен описывает несколько вариантов, ^[10] один из которых берет две строки и максимальное расстояние редактирования s и возвращает min( s , d ) . Он достигает этого, вычисляя и сохраняя только часть таблицы динамического программирования вокруг ее диагонали. Этот алгоритм занимает время O( s ×min( m , n )) , где m и n — длины строк. Сложность пространства составляет O( s ² ) или O( s ) , в зависимости от того, нужно ли считывать последовательность редактирования. ^[3]

Дальнейшие усовершенствования Ландау , Майерса и Шмидта [1] дают алгоритм со временем O( s ² + max( m , n )) ^[11]

Для конечного алфавита и кратных друг другу затрат на редактирование самым быстрым из известных точных алгоритмов является алгоритм Масека и Патерсона ^[12], в худшем случае время выполнения которого составляет O(nm/logn).

Приложения

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

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

• Алгоритм Хиршберга вычисляет оптимальное выравнивание двух строк, где оптимальность определяется как минимизация расстояния редактирования.
• Приблизительное сопоставление строк можно сформулировать в терминах расстояния редактирования. Алгоритм Укконена 1985 года берет строку p , называемую шаблоном, и константу k ; затем он строит детерминированный конечный автомат , который находит в произвольной строке s подстроку, расстояние редактирования которой до p не превышает k ^[13] (ср. алгоритм Ахо–Корасика , который аналогичным образом создает автомат для поиска любого из нескольких шаблонов, но не допускает операций редактирования). Похожий алгоритм для приблизительного сопоставления строк — алгоритм bitap , также определенный в терминах расстояния редактирования.
• Автоматы Левенштейна — это конечные автоматы, которые распознают набор строк в пределах ограниченного расстояния редактирования фиксированной опорной строки. ^[4]

Расстояние редактирования языка

Обобщением расстояния редактирования между строками является расстояние редактирования языка между строкой и языком, обычно формальным языком . Вместо того, чтобы рассматривать расстояние редактирования между одной строкой и другой, расстояние редактирования языка является минимальным расстоянием редактирования, которое может быть достигнуто между фиксированной строкой и любой строкой, взятой из набора строк. Более формально, для любого языка L и строки x над алфавитом Σ расстояние редактирования языка d ( L , x ) задается как ^[14] , где — расстояние редактирования строки. Когда язык L является контекстно-свободным , существует алгоритм динамического программирования с кубическим временем, предложенный Ахо и Петерсоном в 1972 году, который вычисляет расстояние редактирования языка. ^[15] Для менее выразительных семейств грамматик, таких как регулярные грамматики , существуют более быстрые алгоритмы для вычисления расстояния редактирования. ^[16] ${\displaystyle d(L,x)=\min _{y\in L}d(x,y)}$ ${\displaystyle d(x,y)}$

Расстояние редактирования языка нашло множество разнообразных применений, таких как сворачивание РНК, исправление ошибок и решения проблемы оптимальной генерации стека. ^{[14] [17]}

Смотрите также

• Расстояние редактирования графика
• Проблема коррекции строка-строка
• Метрика строки
• Расстояние редактирования искажения времени

Ссылки

1. Наварро, Гонсало (1 марта 2001 г.). "A guided tour to approxive string matching" (PDF) . ACM Computing Surveys . 33 (1): 31–88. CiteSeerX  10.1.1.452.6317 . doi :10.1145/375360.375365. S2CID  207551224 . Получено 19 марта 2015 г. .
2. Дэниел Джурафски; Джеймс Х. Мартин. Обработка речи и языка . Pearson Education International. С. 107–111.
3. Эско Укконен (1983). О приближенном сопоставлении строк . Основы теории вычислений. Springer. С. 487–495. doi :10.1007/3-540-12689-9_129.
4. Шульц, Клаус У.; Михов, Стоян (2002). «Быстрая коррекция строк с помощью автоматов Левенштейна». Международный журнал анализа и распознавания документов . 5 (1): 67–85. CiteSeerX 10.1.1.16.652 . doi :10.1007/s10032-002-0082-8. S2CID  207046453. 
5. Лей Чен; Рэймонд Нг (2004). О браке Lp-норм и расстояния редактирования (PDF) . Труды 30-й Международной конференции по очень большим базам данных (VLDB). Том 30. doi :10.1016/b978-012088469-8.50070-x.
6. Кукич, Карен (1992). «Методы автоматического исправления слов в тексте» (PDF) . ACM Computing Surveys . 24 (4): 377–439. doi :10.1145/146370.146380. S2CID  5431215. Архивировано из оригинала (PDF) 27-09-2016 . Получено 09-11-2017 .
7. Р. Вагнер; М. Фишер (1974). «Проблема коррекции строка-в-строку». J. ACM . 21 : 168–178. doi : 10.1145/321796.321811 . S2CID  13381535.
8. Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science+Business Media . Bibcode :2008adm..book.....S. ISBN 978-1-849-96720-4.
9. Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (июль 2010 г.). «Динамическое программирование без учета кэша для биоинформатики». IEEE/ACM Transactions on Computational Biology and Bioinformatics . 7 (3): 495–510. doi :10.1109/TCBB.2008.94. PMID  20671320. S2CID  2532039.
10. Укконен, Эско (1985). "Алгоритмы для приблизительного сопоставления строк" (PDF) . Информация и управление . 64 (1–3): 100–118. doi : 10.1016/S0019-9958(85)80046-2 .
11. Ландау; Майерс; Шмидт (1998). «Инкрементальное сравнение строк». Журнал SIAM по вычислениям . 27 (2): 557–582. CiteSeerX 10.1.1.38.1766 . doi :10.1137/S0097539794264810. 
12. Масек, Уильям Дж.; Патерсон, Майкл С. (февраль 1980 г.). «Более быстрый алгоритм вычисления расстояний редактирования строк». Журнал компьютерных и системных наук . 20 (1): 18–31. doi : 10.1016/0022-0000(80)90002-1 . ISSN  0022-0000.
13. Эско Укконен (1985). «Нахождение примерных закономерностей в строках». Дж. Алгоритмы . 6 : 132–137. дои : 10.1016/0196-6774(85)90023-9.
14. Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna ; Williams, Virginia Vassilevska (2016). «Истинно субкубические алгоритмы для расстояния редактирования языка и РНК-фолдинга с помощью быстрого ограниченного разностного минимально-плюс продукта» (PDF) . 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) . стр. 375–384. arXiv : 1707.05095 . doi : 10.1109/focs.2016.48. ISBN 978-1-5090-3933-3. S2CID  17064578.
15. Ахо, А.; Петерсон, Т. (1972-12-01). «Парсер с минимальным расстоянием исправления ошибок для контекстно-свободных языков». Журнал SIAM по вычислениям . 1 (4): 305–312. doi :10.1137/0201022. ISSN  0097-5397.
16. Вагнер, Роберт А. (1974). «Коррекция порядка n для регулярных языков». Сообщения ACM . 17 (5): 265–268. doi : 10.1145/360980.360995 . S2CID  11063282.
17. Саха, Б. (2014-10-01). Проблема расстояния редактирования языка Дика в почти линейном времени . 55-й ежегодный симпозиум IEEE 2014 года по основам компьютерной науки. С. 611–620. doi :10.1109/FOCS.2014.71. ISBN 978-1-4799-6517-5. S2CID  14806359.