Последовательное точное сравнение строк

Материал из WEGA
Перейти к навигации Перейти к поиску

Ключевые слова и синонимы

Точное сравнение с шаблоном

Постановка задачи

Пусть даны строка шаблона [math]\displaystyle{ P = p_1 p_2 ... p_m }[/math] и текстовая строка [math]\displaystyle{ T = t_1 t_2 ... t_n }[/math], представляющие собой последовательности над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math]. Задача точного сравнения строк (exact string matching, ESM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, в которых P входит в T; иначе говоря, в вычислении множества [math]\displaystyle{ \{ j | 1 \le j \le n - m + 1, P = t_j t_{j + 1} ... t_{j + m - 1} \} }[/math]. Предполагается, что шаблон задается первым, после чего производится поиск его вхождения в нескольких текстах.


Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из [math]\displaystyle{ \Sigma }[/math]. Для простоты и практичности будем далее полагать m = o(n).

Основные результаты

Большинство алгоритмов решения задачи ESM содержат два этапа: этап предварительной обработки шаблона P и этап поиска в тексте T. Этап предварительной обработки служит для сбора предварительной информации о шаблоне с целью ускорения этапа поиска.


Этап поиска алгоритмов сравнения строк работает следующим образом. Вначале он выравнивает левые концы шаблона и текста, затем сравнивает выровненные символы текста и шаблона – эта операция называется попыткой или сканированием – а после обнаружения совпадения всего шаблона либо несовпадения перемещает шаблон вправо. Эта процедура повторяется до тех пор, пока правый конец шаблона не выйдет за правый конец текста. Фаза сканирования может рассматриваться как операция над текстом сквозь окно, размер которого чаще всего совпадает с длиной шаблона. Данный вид обработки называется механизмом сканирования и сдвига. Различные стратегии сканирования окна легли в основу разных алгоритмов, обладающих различными свойствами и преимуществами.


Алгоритм решения задачи ESM полным перебором выполняет проверку вхождения P на каждой позиции j строки T, где [math]\displaystyle{ 1 \le j \le n - m + 1 }[/math]. Ему не требуется этап предварительной обработки. Этот алгоритм требует O(mn) времени и константной дополнительной памяти и в среднем производит O(n) сравнений символов. Его можно сравнить со следующими границами.


Теорема 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).


Разбор текста в онлайновом режиме

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


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


Поиск можно осуществить с использованием реализованного детерминированного конечного автомата с поиском потомка по умолчанию [math]\displaystyle{ \mathcal{D}(P) }[/math], распознающего язык [math]\displaystyle{ \Sigma * P }[/math]. Размер реализации алгоритма составляет O(m) и не зависит от размера алфавита в силу того, что автомат [math]\displaystyle{ \mathcal{D}(P) }[/math] имеет m + 1 состояний, m прямых дуг и не более m обратных дуг. Использование конечного автомата для поиска в тексте позволяет получить алгоритм с эффективной задержкой (представляющей собой максимальное время обработки символа текста).


Теорема 4 (Ханкарт, 1993 [10]). Поиск шаблона P может быть произведен с задержкой в [math]\displaystyle{ O(min \{ \sigma, log_2 \; m ) \} ) }[/math] сравнений букв.


Заметим, что в большинстве алгоритмов предварительная обработка шаблона не обязательно производится перед разбором текста, поскольку ее можно выполнить «на лету» в процессе разбора.


Практически эффективные алгоритмы

Алгоритм Бойера-Мура считается одним из самых эффективных алгоритмов решения задачи ESM. Его упрощенная версия либо весь алгоритм полностью нередко применяется в программах редактирования текстов для выполнения операций поиска и замены.


Алгоритм сканирует символы в окне справа налево, начиная с самого правого символа. В случае несовпадения (либо полного совпадения с шаблоном) он использует две предварительно вычисляемые функции для сдвига шаблона вправо. Эти две функции сдвига носят название сдвига плохого символа и сдвига хорошего суффикса. Они основаны на следующих наблюдениях. Предположим, что несовпадение обнаруживается между символом [math]\displaystyle{ p_i = a }[/math] шаблона и символом [math]\displaystyle{ t_{i + j} = b }[/math] текста после попытки в позиции j. Тогда [math]\displaystyle{ p_{i + 1} ... p_m = t_{i + j + 1} ... t_{j + m} = u }[/math] и [math]\displaystyle{ p_i \ne t_{i + j} }[/math]. Сдвиг хорошего суффикса заключается в выравнивании сегмента [math]\displaystyle{ t_{i + j + 1} ... t_{j + m} }[/math] с его самым правым вхождением в P, предшествующим символу, отличному от [math]\displaystyle{ p_i }[/math]. Еще один вариант, называемый сдвигом лучшего суффикса, заключается в выравнивании сегмента [math]\displaystyle{ t_{i + j} ... t_{j + m} }[/math] с его самым правым вхождением в P. Вычисление обоих вариантов требует O(m) времени и памяти, независимо от размера алфавита. Если такого сегмента не существует, сдвиг заключается в выравнивании самого длинного суффикса v строки [math]\displaystyle{ t_{i + j + 1} ... t_{j + m} }[/math] с совпадающим префиксом x. Сдвиг плохого символа заключается в выравнивании символа текста [math]\displaystyle{ t_{i + j} }[/math] с его самым правым вхождением в [math]\displaystyle{ p_1 ... p_{m - 1} }[/math]. Если [math]\displaystyle{ t_{i + j} }[/math] не встречается в шаблоне и никакое вхождение P в T не перекрывает символ [math]\displaystyle{ t_{i + j} }[/math], тогда левый конец шаблона выравнивается с символом в позиции i + j + 1. В этом случае поиск может быть выполнен за время O(n/m) в наилучшем случае.


Теорема 5 (Коул, 1994 [5, 14]). В ходе поиска непериодического шаблона P длины m (такой, что длина самой длинной границы P меньше m/2) в тексте T длины n алгоритм Бойера-Мура производит не более 3n сравнений между буквами P и T.


Граница Яо может быть достигнута благодаря использованию индексной структуры для реверсивного шаблона. Это выполняется при помощи алгоритма обращения сегмента (Reverse Factor), также известного как BDM (Backward Dawg Matching, сопоставление с обращенным ориентированным ациклическим графом слов, ОАГС).


Теорема 6 (Крочмор и др., 1994 [4]). Поиск может быть выполнен за оптимальное ожидаемое время O((log m/m) x n) с использованием суффиксного конечного автомата или суффиксного дерева реверсивного шаблона.


Вместо индексной структуры может использоваться фактор-оракул, поскольку единственной строкой длины m, принимаемая оракулом строки w длины m, является сама строка w. Это выполняется при помощи алгоритма сопоставления с обращенным оракулом (Backward Oracle Matching, BOM) Аллозена, Крочмора и Раффино [1]. На практике его поведение схоже с поведением алгоритма BDM.


Алгоритмы, оптимальные по времени и памяти

Алгоритмы этого типа выполняются за линейное время (это относится к предварительной обработке и поиску) и требуют константного объема памяти в дополнение к объему входных данных.


Теорема 7 (Галил, Сейферас, 1983 [8]). Поиск может быть выполнен оптимальным образом за время O(n) с использованием константного объема памяти.


После первого решения Галила и Сейфераса другие варианты были предложены Крочмором и Перреном [6] и Риттером [6]. Алгоритмы разбивают шаблон на две части; вначале они выполняют поиск правой части шаблона слева направо, а затем, если не обнаружено несовпадений, ищут левую часть. Разбиение может представлять собой идеальную факторизацию [8] или критическую факторизацию [8] либо основываться на лексикографически максимальном суффиксе шаблона [13]. Еще одно решение Крочмора [2] представляет собой вариант KMP [11]: оно на лету вычисляет нижние границы периодов префиксов шаблона и не требует предварительной обработки.


Бит-параллельное решение

Для решения задачи ESM можно применить технику битового параллелизма.


Теорема 8 (Баэса-Йейтс и Гоннет, 1992; Ву и Манбер, 1992 (см. [5, 14])). Если длина m строки P меньше количества бит в машинном слове, этап предварительной обработки может быть выполнен с использованием [math]\displaystyle{ \Theta(\sigma) }[/math] времени и памяти. Этап поиска требует [math]\displaystyle{ \Theta(n) }[/math] времени.


Данную технику битового параллелизма можно применить даже для моделирования алгоритма BDM. Это выполняется при помощи алгоритма сопоставления обратных недетерминированных ОАГС (Backward Non-deterministic Dawg Matching, BNDM) [2, 12].


На практике при сканировании окна справа налево в ходе попытки иногда оказывается более эффективным использовать только сдвиг плохого символа. Вначале такой подход был применен в алгоритме Хорспула [2, 12]. Также высокой практической эффективностью отличаются алгоритмы быстрого поиска (Quick Search) Сандея и настроенный алгоритм Бойера-Мура, разработанный Хьюмом и Сандеем (оба см. в [2, 12]).


Существует и другой метод, использующий технику битового параллелизма, оптимальную в среднем случае, который фактически представляет собой метод фильтрации. Он рассматривает разреженные q-граммы и, таким образом, избегает сканирования большого количества текстовых позиций. Этот алгоритм был предложен Фредрикссоном и Грабовски [7].

Применение

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

Открытые вопросы

В этой сфере остается не так уж много нерешенных задач. Все еще неизвестно, возможно ли разработать алгоритм сравнения строк с оптимальным в среднем случае временем выполнения и константным объемом требуемой памяти. Также до сих пор неизвестен точный размер конечного автомата Бойера-Мура [5].

Экспериментальные результаты

Книга Наварро и Раффино [12] может служить подходящим введением в проблему, в ней также представлена экспериментальная карта алгоритмов ESM для разных значений размера алфавита и длины шаблона. В частности, алгоритм сдвига Shift-Or эффективен для небольших алфавитов и коротких шаблонов, BNDM – для алфавитов и шаблонов среднего размера, алгоритм Хорспула – для больших алфавитов, а BOM – для длинных шаблонов.

Ссылка на код

На сайте http://monge.univ-mlv.fr/~lecroq/string представлено большое количество алгоритмов для решения задачи ESM (см. также [2]). Каждый алгоритм реализован на языке C и снабжен Java-апплетом.

См. также

Литература

1. Allauzen, C., Crochemore, M., Raffinot, M.: Factor oracle: a new structure for pattern matching. In: SOFSEM'99. LNCS, vol. 1725, pp. 291-306. Springer, Berlin (1999)

2. Charras, C., Lecroq, T.: Handbook of exact string matching algorithms. King's College London Publications, London (2004)

3. Cole, R., Hariharan, R., Paterson, M., Zwick, U.: Tighter lower bounds on the exact complexity of string matching. SIAM J. Comput. 24(1), 30-45 (1995)

4. Crochemore, M., Czumaj, A., G^sieniec, L., Jarominek, S., Lecroq, T., Plandowski, W., Rytter, W.: Speeding up two string matching algorithms. Algorithmica 12(4/5), 247-267 (1994)

5. Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on strings. Cambridge University Press, New York (2007)

6. Crochemore, M., Perrin, D.: Two-way string matching. J. ACM 38(3),651-675(1991)

7. Fredriksson, K., Grabowski, S.: Practical and optimal string matching. In: Proceedings of SPIRE'2005. LNCS, vol. 3772, pp. 374-385. Springer, Berlin (2005)

8. Galil, Z., Seiferas, J.: Time-space optimal string matching. J. Comput. Syst. Sci. 26(3), 280-294 (1983)

9. Gusfield, D.: Algorithms on strings, trees and sequences. Cambridge University Press, Cambridge, UK (1997)

10. Hancart, C.: On Simon's string searching algorithm. Inf. Process. Lett. 47(2), 95-99 (1993)

11. Knuth, D.E., Morris, J.H. Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(1), 323-350 (1977)

12. Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings - Practical on-line search algorithms for texts and biological sequences. Cambridge University Press, Cambridge, Uk (2002)

13. Rytter, W.: On maximal suffixes and constant-space linear-time versions of KMP algorithm. Theor. Comput. Sci. 299(1-3), 763-774 (2003)

14. Smyth, W.F.: Computing Patterns in Strings. Addison Wesley Longman, Harlow, UK (2002)

15. Yao, A.: The complexity of pattern matching for a random string. SIAM J. Comput. 8,368-387 (1979)

Источник — http://pco.iis.nsk.su/wega/index.php?title=Последовательное_точное_сравнение_строк&oldid=13882