Редактировать расстояние в сублинейном пространстве

Какова наиболее известная сложность для вычисления точного расстояния редактирования между двумя строками одинаковой длины с использованием рабочего пространства, которое является сублинейным по размеру ввода? Я предполагаю, что вход хранится в каком-то формате только для чтения. Это ранее изученная проблема?

Чтобы сделать вопрос немного более конкретным, как насчет пространства где - длина каждой входной строки. $\Theta(\sqrt{n})$ $n$

Редактировать. После ответа Дэвида Эппштейна, кажется, хороший вопрос заключается в том, можно ли просто найти расстояние редактирования за полиномиальное время и пространство . Любые нижние границы также будут интересны. $\Theta(\sqrt{n})$

ds.algorithms edit-distance space-time-tradeoff Феликс
источник

Что касается редактирования: я думаю, вы что-то неправильно поняли. Ответ Дэвида Эппштейна показывает, что проблема разрешима в НЛ, а значит и в П.

Эмиль Йержабек поддерживает Монику

... На самом деле, оригинальный алгоритм Вагнера-Фишера уже делает это.

Эмиль Йержабек поддерживает Монику

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

Дэвид Эппштейн

@DavidEppstein Да, именно так. Я снова отредактировал для уточнения.

Феликс

Кстати, предполагая, что стандартная модель ценообразования 1 для midmatch / delete / insert, затем, если расстояние редактирования равно l, то путь, реализующий кратчайший путь в матрице расстояния редактирования, проходит на расстоянии не более l от главной диагонали, а затем расстояние редактирования вычисляется с использованием пробела O (l). Таким образом, с помощью пространства sqrt (n) вы можете вычислить расстояние редактирования, если оно мало (т. Е. Меньше, чем sqrt (n)). Только если оно большое, это кажется трудным. Конечно, в этом случае, возможно, вам должно быть все равно.

Сариэль Хар-Пелед

$O(\log^2 n)$ $n^{O(\log n)}$

В http://arxiv.org/abs/1106.4412 есть несколько нижних границ пробела для редактирования, но я не думаю, что они соответствуют вашей версии проблемы.

Дэвид Эппштейн
источник

Как вы убедитесь, что путь, который вы нашли, является оптимальным?

Лембик

Бинарный поиск или последовательный поиск наименьшего расстояния, на котором может быть найден путь, т. Е. Ничего кроме стандартной эквивалентности решения и поиска проблем. Это не влияет на формы ограничения пространства или времени.

Дэвид Эппштейн

@ Дэвид, я думаю, ты прав, поэтому я удалил свой ответ.

Самид

Это даже вычислимо в пространстве журнала?

Лембик

Редактировать расстояние в сублинейном пространстве

Ответы: