4551
правка
Последовательное точное сравнение строк: различия между версиями
Материал из WEGA
Последовательное точное сравнение строк (посмотреть исходный код)
Версия от 15:08, 22 апреля 2019
, 22 апреля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Теорема 1 (Коул и коллеги 1995 [3]). Минимальное количество сравнений символов для решения задачи ESM в наихудшем случае оказывается больше или равно n + 9/(4m)(n — m) и может быть сделано меньше или равно n + 8/(3(m + 1))(n - m). | '''Теорема 1 (Коул и коллеги, 1995 [3]). Минимальное количество сравнений символов для решения задачи ESM в наихудшем случае оказывается больше или равно n + 9/(4m)(n — m) и может быть сделано меньше или равно n + 8/(3(m + 1))(n - m).''' | ||
Теорема 2 (Яо 1979 [15])). Задача ESM может быть решена за оптимальное ожидаемое время O((log m/m) x n). | '''Теорема 2 (Яо 1979 [15])). Задача ESM может быть решена за оптимальное ожидаемое время O((log m/m) x n).''' | ||
'''Разбор текста в онлайновом режиме''' | '''Разбор текста в онлайновом режиме''' | ||
Первый линейный алгоритм решения задачи 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. | |||
'''Теорема 3 (Кнут, Моррис и Пратт, 1977 [11])). Текстовый поиск может быть выполнен за время O(n) с использованием памяти в размере O(m). Предварительная обработка образца может быть выполнена за время O(m).''' | |||
