Max Home IndustryРасстояние редактирования — это мера того, насколько близко расположены две строки, и оно используется во многих важных приложениях, включая проверку орфографии и анализ генома. В настоящее время самый известный алгоритм требует O (n ^ 2) операций, и это часто слишком медленно. Теперь у нас есть доказательство того, что вы не можете сделать ничего лучше.
Расстояние редактирования, также называемое расстоянием Левенштейна, между двумя струнами определить легко. Это просто наименьшее количество удалений, вставок или замен, которое вам нужно, чтобы превратить одну строку в другую.
Другими словами, это наименьшее количество точечных мутаций, необходимых для преобразования одной строки в другую. Эта терминология пришла из генетики, где расстояние редактирования используется для измерения того, насколько далеко одна нить ДНК находится от другой.
Вы также можете догадаться, что это полезно в корректорах орфографии, измеряющих, насколько близко слово с ошибкой написано к возможным правильным кандидатам. В приложении для проверки орфографии расстояние редактирования часто изменяется, чтобы обеспечить транспонирование между двумя соседними символами, поскольку это распространенная ошибка.
Расстояние редактирования легко определить, но трудно вычислить. Например, каково расстояние редактирования между abc и bca? Вы могли бы подумать, что его три — замените a на b, b на c и c на a, но это не так. Фактически, вы можете заменить вторую строку первой, удалив a и вставив a в начале, что дает расстояние редактирования 2.
Кажется, что вам нужен некоторый интеллект, чтобы рассчитать расстояние редактирования, из-за необходимости найти наименьшее количество точечных правок. Фактически существует рекурсивное определение, которое приводит к рекурсивному алгоритму.
Ясно, что если одна из двух строк S1, S2 равна нулю, расстояние равно длине ненулевой строки или нулю, если обе строки равны нулю.
Если оба значения не равны нулю и мы знаем расстояние редактирования S1-1 и S2-1, то есть обе строки с удаленным последним символом, то расстояние редактирования составляет минимум три случая:
Отредактируйте (S1-1, S2-1) +1, если последние символы разные, и Отредактируйте (S1-1, S2-1), если они совпадают.
Редактировать (S1-1, S2) +1 и Редактировать (S1, S2-1) +1
Попробуем это на abc и bca. Обе строки не равны нулю, поэтому нам нужно работать:
Edit (ab, bc) = 2 удалить c вставить a
Edit (ab, bca) = 3 удалить c удалить b вставить b
Edit (abc, bc) = 1 вставить
Используя эти значения, получаем
Изменить (abc, bca) = min (2 + 1,3,1 + 1) = 2
Обратите внимание, что при разработке значений Edit (ab, bc) и остальных мы использовали бы рекурсию, пока не достигли Edit (a, null), Edit (null, b) и Edit (null, null), а затем работали бы вперед. .
Это рекурсивное определение точное, но медленное. Обычный способ решения проблемы — отказаться от рекурсии и просто двигаться вперед от Edit (a, null) Edit (null, b) и Edit (null, null). Это можно организовать в виде таблицы, которую можно заполнять по очереди. Все записи с нулевым значением тривиальны и представляют собой всего лишь длину строки:
null b bc bca
ноль 0 1 2 3
а 1
ab 2
abc 3
Остальную часть следующей строки можно вычислить, используя только те значения, которые у нас уже есть.
Поскольку a! = B
Edit (a, b) = min (Edit (null, b), Edit (a, null), Edit (null, null)) + 1 = 1
Поскольку a! = C
Edit (a, bc) = min (Edit (null, bc), Edit (a, b), Edit (null, b)) + 1 = 2
Как а == а
Edit (a, bca) = Edit (null, bc) = 2
Теперь у нас есть следующая строка таблицы:
null b bc bca
ноль 0 1 2 3
а 1 1 2 2
ab 2
abc 3
Для получения третьей строки используем тот же метод:
Поскольку b = b
Edit (ab, b) = Edit (a, null) = 1
Поскольку b! = C
Edit (ab, bc) = min (Edit (a, bc), Edit (ab, b), Edit (a, b)) + 1 = 2
Поскольку b! = A
Edit (ab, bca) = min (Edit (a, bca), Edit (ab, bc), Edit (a, bc)) + 1 = 3
Это делает таблицу:
null b bc bca
ноль 0 1 2 3
а 1 1 2 2
ab 2 1 2 3
abc 3
Последняя строка рассчитывается таким же образом:
Поскольку c! = B
Edit (abc, b) = min (Edit (ab, b), Edit (abc, null), Edit (ab, null)) + 1 = 2
Поскольку c == c
Правка (abc, bc) = Правка (ab, b)) = 1
Поскольку c! = A
Edit (abc, bca) = min (Edit (ab, bca), Edit (abc, bc), Edit (ab, bc)) + 1 = 2
Полная таблица:
null b bc bca
ноль 0 1 2 3
а 1 1 2 2
ab 2 1 2 3
abc 3 2 1 2
и мы можем прочитать расстояние редактирования между abc и bca как 2.
Вы можете видеть, что этот алгоритм, небольшая модификация алгоритма Вагнера-Фишера, работает с примерно n-квадратными операциями для строк длины n. Для определения расстояния редактирования последовательностей ДНК с миллионами пар оснований это слишком медленно. хотя это не экспоненциально. Из-за его практической важности много времени было посвящено поиску лучшего алгоритма, который был бы субквадратичным.
Теперь мы знаем, что вся эта работа была потрачена зря, потому что два исследователя из Массачусетского технологического института доказали, что квадратичный почти наверняка оптимален.
Доказательство интересно само по себе и привело к тому, что эта техника была применена к другим нерешенным задачам. Идея состоит в том, чтобы продемонстрировать, что существование субквадратичного алгоритма для расстояния редактирования подразумевает существование субэкспоненциального алгоритма для задачи 3-SAT. Задача 3-SAT — просто найти набор значений для трех переменных, который делает логическое выражение истинным — и в целом это NP-полная. Сильная гипотеза экспоненциального времени утверждает, что это невозможно, и для решения всех NP-полных задач требуется экспоненциальное время.
Итак, пока сохраняется сильная гипотеза экспоненциального времени, не существует магического субквадратичного алгоритма для расстояния редактирования. Большинство компьютерных ученых, но не все из них, похоже, считают, что сильная гипотеза экспоненциального времени верна. Верно, что если оно имело место, то P! = NP, но если это неверно, это не имеет никакого отношения к вопросу P! = NP, т.е. оно может быть ложным и P! = NP. Таким образом, он не «защищен» вероятностью того, что P действительно не равно NP.
Это означает, что некоторые все еще могут попытаться найти более быстрый алгоритм расстояния редактирования. хотя бы для того, чтобы опровергнуть сильную гипотезу экспоненциального времени.