Аноним

Последовательное точное сравнение строк: различия между версиями

Материал из WEGA
Строка 26: Строка 26:
'''Разбор текста в онлайновом режиме'''
'''Разбор текста в онлайновом режиме'''


Первый линейный алгоритм решения задачи ESM появился в 1970-х. Этап предварительной обработки этого алгоритма заключался в вычислении периодов префиксов образка или, что эквивалентно, длине самой длинной границы для всех префиксов образца. Граница строки является одновременно и префиксом, и суффиксом строки, отличным от нее самой. Обозначим за next[i] длину самого длинного пути в p1 … pi-\. Рассмотрим попытку сравнения в позиции j, где образец p1.. pm выровнен с сегментом tj …  tj+m-i текста. Предположим, что первое несовпадение (при сканировании слева направо) имеет место между символами pi и ti+j для 1 < i < m. Тогда p 1.. pi-\ = tj..t f,+j_i = u и a = pi ф ti+j = b. При сдвиге разумно будет ожидать, что префикс v образца будет соответствовать некоторому суффиксу фрагмента u текста. Таким образом, после сдвига сравнение может возобновиться для позиций pnext[i] и ti+j без потери каких-либо вхождений P в T и необходимости выполнения возврата в тексте. Существуют два подхода, различающихся в зависимости от того, должен ли pnext[i] отличаться от pi.
Первый линейный алгоритм решения задачи ESM появился в 1970-х. Этап предварительной обработки этого алгоритма заключался в вычислении периодов префиксов образка или, что эквивалентно, длине самой длинной границы для всех префиксов образца. Граница строки является одновременно и префиксом, и суффиксом строки, отличным от нее самой. Обозначим за next[i] длину самого длинного пути в <math>p_1 ... p_{i - 1}</math>. Рассмотрим попытку сравнения в позиции j, где образец <math>p_1 ... p_m</math> выровнен с сегментом <math>t_j ... t_{j + m - 1}</math> текста. Предположим, что первое несовпадение (при сканировании слева направо) имеет место между символами <math>p_i</math> и <math>t_{i + j}</math> для <math>1 \le i \le m</math>. Тогда <math>p_1 ... p_{i - 1} = t_j ... t_{i + j - 1} = u</math> и <math>a = p_i \ne t_{i + j} = b</math>. При сдвиге разумно будет ожидать, что префикс v образца будет соответствовать некоторому суффиксу фрагмента u текста. Таким образом, после сдвига сравнение может возобновиться для позиций <math>p_{next[i]}</math> и <math>t_{i + j}</math> без потери каких-либо вхождений P в T и необходимости выполнения возврата в тексте. Существуют два подхода, различающихся в зависимости от того, должен ли <math>p_{next[i]}</math> совпадать с <math>p_i</math>.




'''Теорема 3 (Кнут, Моррис и Пратт, 1977 [11])). Текстовый поиск может быть выполнен за время O(n) с использованием памяти в размере O(m). Предварительная обработка образца может быть выполнена за время O(m).'''
'''Теорема 3 (Кнут, Моррис и Пратт, 1977 [11])). Текстовый поиск может быть выполнен за время O(n) с использованием памяти в размере O(m). Предварительная обработка образца может быть выполнена за время O(m).'''
4551

правка