Приближенное сравнение регулярных выражений: различия между версиями

'''Теорема 1 (Майерс и Миллер, 1989 [3]). Существует решение с временем выполнения O(mn) в наихудшем случае для задачи AREM с использованием взвешенного расстояния редактирования.'''

Для целочисленных весов можно получить лучший результат за счет использования RAM-модели с единичной стоимостью при помощи «метода четырех русских». Идея заключается в следующем. Возьмем небольшое подвыражение R, порождающее НКА, который будет преобразовываться в небольшой подграф каждого графа <math>G_i</math>. В момент распространения стоимостей путей по этому автомату с каждой вершиной будет связан счетчик, (говорящий о текущем кратчайшем пути из <math>s_0</math>). Этот счетчик может быть сведен к числу в диапазоне [0, k + 1], где k + 1 обозначает «больше, чем k». Если небольшой НКА имеет r состояний, то для полного описания счетчиков соответствующего подграфа <math>G_i</math> требуется <math>r \lceil log_2 \; (k + 2) \rceil</math> бит. Более того, учитывая начальный набор значений для счетчиков, можно предварительно вычислить будущее распространение, которое будет происходить в пределах одного подграфа <math>G_i</math>, в таблице, имеющей <math>2^{r \lceil log_2 \; (k + 2) \rceil}</math> записей – по одной на каждую возможную конфигурацию счетчиков. Чтобы стоимость построения и хранения этих таблиц была ограничена o(n), достаточно обеспечить выполнение соотношения <math>r < \alpha \; log_{k + 2} \; n</math> для некоторого <math>\alpha < 1</math>. При помощи этих таблиц распространение внутри подграфа можно осуществить за константное время. Аналогично, распространение затрат по одному и тому же подграфу в <math>G_{i + 1}</math> также может быть предварительно вычислено в таблицах, поскольку оно зависит только от текущих счетчиков в <math>G_i</math> и от символа текста <math>t_{i + 1}</math>, для которых есть только a альтернативных вариантов.