4551
правка
Последовательное точное сравнение строк: различия между версиями
Материал из WEGA
Последовательное точное сравнение строк (посмотреть исходный код)
Версия от 12:59, 29 апреля 2019
, 29 апреля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
'''Теорема 8 (Баэса-Йейтс и Гоннет, 1992; Ву и Манбер, 1992 (см. [5, 14])). Если длина m строки P меньше количества бит в машинном слове, этап предварительной обработки может быть выполнен с использованием <math>\Theta(\sigma)</math> времени и памяти. Этап поиска требует <math>\Theta(n)</math> времени.''' | '''Теорема 8 (Баэса-Йейтс и Гоннет, 1992; Ву и Манбер, 1992 (см. [5, 14])). Если длина m строки P меньше количества бит в машинном слове, этап предварительной обработки может быть выполнен с использованием <math>\Theta(\sigma)</math> времени и памяти. Этап поиска требует <math>\Theta(n)</math> времени.''' | ||
Данную технику битового параллелизма можно применить даже для моделирования алгоритма BDM. Это выполняется при помощи алгоритма сопоставления обратных недетерминированных ОАГС (Backward Non-deterministic Dawg Matching, BNDM) [2, 12]. | |||
На практике при сканировании окна справа налево в ходе попытки иногда оказывается более эффективным использовать только сдвиг плохого символа. Вначале такой подход был применен в алгоритме Хорспула [2, 12]. Также высокой практической эффективностью отличаются алгоритмы быстрого поиска авторства Сандея и настроенный алгоритм Бойера-Мура, разработанный Хьюмом и Сандеем (оба см. в [2, 12]). | |||
Существует и другой метод, использующий технику битового параллелизма, оптимальную в среднем случае, который фактически представляет собой метод фильтрации. Он рассматривает разреженные q-граммы и, таким образом, избегает сканирования большого количества текстовых позиций. Этот алгоритм был предложен Фредрикссоном и Грабовски [7]. | |||
== Применение == | |||
