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

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

Сравнение со словарем

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

Пусть даны конечное множество строк шаблона $\mathcal{P}=\{P^1,P^2,...,Pk\}$ и текстовая строка $T=t_1{t}_2...t_n$, где $T$ и $P^i$ представляют собой последовательности над алфавитом $\mathrm{\Sigma }$ размера $\sigma$. Задача сравнения нескольких строк (multiple string matching, MSM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, начиная с которых $P^i$ входит в $T$; или, говоря более точно, в вычислении множества $\{j|\mathrm{\exists }i,P^i=t_j{t}_{j+1}...t_{j+|P^i|-1}\}$ или эквивалентного множества $\{j|\mathrm{\exists }i,P^i=t_{j-|P^i|+1}{t}_{j-|P^i|+2}...t_j\}$. Отметим, что при выдаче всех вхождений шаблонов размер выходных данных может стать квадратичным (например, в случае, когда $P^i$ и $T$ берутся из однобуквенного алфавита). Обозначим длину самого короткого шаблона в $\mathcal{P}$ за $\ell min$. Предполагается, что шаблоны задаются в самом начале, после чего производится поиск их вхождения в нескольких текстах. Данная задача является расширением задачи точного сравнения строк.

Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из $\mathrm{\Sigma }$. Для простоты и практичности будем далее полагать $|P^i|=o(n),1\le i\le k$.

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

Первое решение задачи сравнения нескольких строк заключается в применении алгоритма точного сравнения строк для локализации каждого шаблона в $\mathcal{P}$. Сложность этого алгоритма составляет O(kn) в наихудшем случае. Существуют более эффективные решения, основанные на двух подходах. Первый подход, предложенный Ахо и Корасик [1], представляет собой расширение алгоритма сравнения одной строки с помощью конечного автомата. Второй подход, реализованный Комменц-Уолтер [3], расширяет алгоритм Бойера-Мура на случай нескольких шаблонов.

Алгоритм Ахо-Корасик вначале строит префиксное дерево $T(\mathcal{P})$ – цифровое дерево, распознающее шаблоны $\mathcal{P}$. $T(\mathcal{P})$ представляет собой дерево, ребра которого помечены буквами, а вдоль ветвей можно прочесть шаблоны $\mathcal{P}$. Вершина p префиксного дерева $T(\mathcal{P})$ ассоциируется с уникальным словом w, «написанным» по пути в $T(\mathcal{P})$, ведущему из его корня в p. Сам корень идентифицируется с пустым словом $\epsilon$. Заметим, что если w является вершиной в $T(\mathcal{P})$, то w является префиксом некоторого шаблона $P^i\in \mathcal{P}$. Если вдобавок к этому $a\in \mathrm{\Sigma }$, то child(w, a) совпадает с wa, если wa является вершиной в $T(\mathcal{P})$, и равно NIL в противном случае.

На втором этапе, когда шаблоны добавляются к префиксному дереву, алгоритм инициализирует выходную функцию out. Он ассоциирует одноэлементное множество $\{P^i\}$ с вершинами $P^i(1\le i\le k)$ и пустое множество – со всеми другими вершинами $T(\mathcal{P})$.

Наконец, последним этапом предварительной обработки является создание ссылок для случаев несовпадения для каждой вершины префиксного дерева и одновременное завершение создания выходной функции. Функция несовпадения fail определяется на вершинах следующим образом (w является вершиной): fail(w) = u, где u – самый длинный подходящий суффикс w, принадлежащий к $T(\mathcal{P})$. Вычисление ссылок для несовпадений выполняется в процессе обхода $T(\mathcal{P})$ в ширину. Завершение выходной функции осуществляется в ходе вычисления функции для несовпадения с использованием следующего правила: если $fail(w)=u$, то $out(w)=out(w)\cup out(u)$.

Чтобы избежать возвратов по ссылкам для несовпадений при вычислении этих ссылок, а также для обхода символов текста, для которых не был определен переход от корня на этапе поиска, к корню префиксного дерева добавляется цикл для этих символов. В результате получаем механизм поиска совпадений с шаблонами или конечный автомат Ахо-Корасик (см. рис. 1).

Рисунок 1. Механизм поиска совпадений с шаблонами или конечный автомат Ахо-Корасик для множества строк {search, ear, arch, chart}

После завершения этапа предварительной обработки алгоритм переходит к этапу поиска, заключающемуся в разборе текста T при помощи $T(\mathcal{P})$. Он начинается с корня $T(\mathcal{P})$ и использует ссылки с несовпадениями в случаях, когда символ в T не совпадает ни с одной из меток исходящих ребер текущей вершины. Каждый раз, когда встречается вершина с непустым выходным значением, это значит, что в тексте были обнаружены шаблоны выходного текста, заканчивающиеся в текущей позиции. Эта позиция является выходной.

Теорема 1 (Ахо и Корасик [1]). После предварительной обработки $\mathcal{P}$ поиск вхождений строк из $\mathcal{P}$ в тексте T может быть выполнен за время $O(n\times log\sigma )$. Время выполнения соответствующего этапа предварительной обработки составляет $O(|\mathcal{P}|\times log\sigma )$. Обе операции требуют дополнительной памяти в объеме $O(|\mathcal{P}|)$.

Алгоритм Ахо-Корасик, в сущности, представляет собой расширение алгоритма Морриса-Пратта для точного сравнения строк на случай конечного множества строк.

Комменц-Уолтер [3] обобщила алгоритм точного сравнения строк Бойера-Мура для случая нескольких строк. Ее алгоритм строит префиксное дерево для обращенных шаблонов в $\mathcal{P}$ вместе с двумя таблицами сдвига и применяет стратегию сканирования справа налево. Однако он довольно сложен в реализации и имеет квадратичную временную сложность в наихудшем случае.

Алгоритм сравнения с помощью ОАГС (DAWG-match algorithm) является обобщением алгоритма BDM для точного сравнения строк. Он включает построение точной индексной структуры для обращенных строк $\mathcal{P}$, такой как фактор-автомат или обобщенное суффиксное дерево, вместо простого префиксного дерева, как в предыдущем варианте (см. рис. 2). Алгоритм в целом может быть сделан оптимальным за счет использования как индексной структуры для обращенных шаблонов, так и конечного автомата Ахо-Корасик для шаблонов. Поиск в этом случае включает сканирование некоторых фрагментов текста слева направо, а некоторых – справа налево. Это позволяет пропускать большие фрагменты текста T.

Рисунок 2. Пример ОАГС, индексной структуры, используемой для сравнения множества строк {search, ear, arch, chart}. Конечный автомат принимает обращенные префиксы строк

Теорема 2 (Крочмор и др., [4]). Алгоритм сравнения с помощью ОАГС выполняет не более 2n сравнений символов. Предполагая, что сумма длин шаблонов в $\mathcal{P}$ меньше $\ell mi{n}^k$, алгоритм сравнения с помощью ОАГС производит в среднем $O((nlog\ell min)/\ell min)$ проверок символов текста.

Узким местом ОАГС-алгоритма является объем времени и памяти, затрачиваемых на построение точной индексной структуры. Этого можно избежать, заменив точную индексную структуру оракулом фактора для множества строк. При использовании только оракула фактора получается алгоритм сопоставления с обращенным оракулом множества (Set Backward Oracle Matching, SBOM) [2]. Этот точный алгоритм демонстрирует почти такое же хорошее поведение, как и алгоритм сравнения с помощью ОАГС.

Техника битового параллелизма может применяться для моделирования ОАГС-алгоритма. В результате получается алгоритм Наварро и Раффино MultiBNDM [7]. Эта стратегия эффективно работает в случае, когда $k\times \ell min$ бит помещаются в нескольких машинных словах. Префиксы строк $\mathcal{P}$ длины $\ell min$ упаковываются в один битовый вектор. После этого поиск выполняется так же, как в алгоритме точного сравнения строк BNDM, и осуществляется для всех префиксов в одно и то же время.

Обобщение подхода со сдвигом плохого символа, как в алгоритме точного сравнения строк Хорспула, оказывается неэффективным для задачи MSM из-за высокой вероятности нахождения каждого символа алфавита в одной из строк $\mathcal{P}$.

Алгоритм Ву и Манбера [11] рассматривает блоки длины $\ell$. Блоки такой длинны хэшируются при помощи функции h в значения меньше maxvalue. Значение функции сдвига shift[h(B)] определяется как минимальное значение из $|P^i|-j$ и $\ell min-\ell +1$ с $B=p_{j-\ell +1}^i...p_j^i$ для $1\le i\le k$ и $1\le j\le |P^i|$. Значение $\ell$ варьируется в зависимости от минимальной длины строк в $\mathcal{P}$ и размера алфавита. Значение maxvalue варьируется в зависимости от объема доступной памяти.

На этапе поиска этого алгоритма производится чтение блоков B длины $\ell$. Если shift[h(B)] > 0, то выполняется сдвиг на длину shift[h(B)]. В противном случае при shift[h(B)] = 0 шаблоны, оканчивающиеся на блок B, проверяются в тексте один за другим. Первым сканируется блок $t_{\ell mjn-\ell +1}...t_{\ell mjn}$. Данный метод встроен в команду agrep [10].

Применение

Алгоритмы решения задачи сравнения нескольких строк (MSM) служат базой для многомерного сравнения с шаблоном и приближенного сравнения с шаблоном с использованием подстановочных знаков. Эта задача часто встречается в таких областях, как вычислительная биология, поиск в базах данных, библиографический поиск, выявление вирусов в потоках данных и многие другие.

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

Книга Наварро и Раффино [8] будет полезна для введения в данную область. В ней представлены графики экспериментов, отражающие экспериментальную оценку работы алгоритмов сравнения нескольких строк для различных значений размера алфавита, длины шаблона и размера множества шаблонов.

Ссылка на код

Эффективное решение задачи MSM обеспечивают такие хорошо известные пакеты, как agrep (http://webglimpse.net/download.html, поддиректория верхнего уровня agrep/) и grep с опцией F (http://www.gnu.org/software/grep/grep.html).

См. также

• Индексированное сравнение строк относится к случаю, при котором возможна предварительная обработка текста
• Многомерное сравнение строк относится к случаю, при котором текст имеет больше одного измерения
• Сравнение регулярных выражений – более сложный случай, где шаблон может быть регулярным выражением
• Последовательное точное сравнение строк – версия, в которой в тексте ищется один шаблон

Литература

Дополнительную информацию можно найти в следующих книгах: [5, 6, 8] и [9].

1. Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. C. ACM 18(6), 333-340 (1975)

2. 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)

3. Commentz-Walter, B.: A string matching algorithm fast on the average. In: Proceedings of ICALP'79. LNCS, vol. 71, pp. 118-132. Springer, Berlin (1979)

4. Crochemore, M., Czumaj, A., Gasieniec, L., Lecroq, T., Plandowski, W., Rytter, W.: Fast practical multi-pattern matching. Inf. Process. Lett. 71(3-4), 107-113 (1999)

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

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

7. Navarro, G., Raffinot, M.: Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM J. Exp. Algorithm 5,4 (2000)

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

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

10. Wu, S., Manber, U.: Agrep - a fast approximate pattern-matching tool. In: Proceedings of USENIX Winter (1992) Technical Conference, pp. 153-162. USENIX Association, Berkeley (1992)

11. Wu, S., Manber, U.: A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ (1994)