анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 14 Алгоритмы работы со строками В этой главе обсуждаются вопросы обработки строк. В разделе 14.1 рассмотрена структура префиксного дерева для хранения множества строк. Затем обсуждаются алгоритмы динамического програм- мирования для определения наибольшей общей подпоследовательности и редакторского расстояния. В разделе 14.2 обсуждаются методы хеширования строк, лежащие в ос- нове эффективных алгоритмов работы со строками. Идея заключается в том, чтобы сравнивать хеш-коды строк вместо символов, это позволяет сравнивать строки за постоянное время. В разделе 14.3 мы познакомимся с Z-алгоритмом, который для каждой позиции строки находит самую длинную подстроку, одновременно явля- ющуюся префиксом строки. Z-алгоритм – альтернативный подход ко мно- гим задачам, которые можно решить также с помощью хеширования. В разделе 14.4 обсуждается структура суффиксного массива, используе- мого для решения многих нетривиальных задач обработки строк. 14.1. Базовые методы В этой главе предполагается, что индексирование строк начинается с 0, т. е. строка s длины n состоит из символов s [0], s [1], …, s [ n − 1]. Подстрокой называется последовательность соседних символов строки. s [ a … b] обозначает подстроку, которая начинается в позиции a и закан- чивается в позиции b. Префиксом называется подстрока, начинающаяся первым символом строки, а суффиксом – подстрока, заканчивающаяся по- следним символом строки. Подпоследовательностью называется любая последовательность симво- лов строки в их исходном порядке. Любая подстрока является подпоследо- вательностью, но обратное неверно (рис. 14.1). E N V E L O P E a substring E N V E L O P E a subsequence Рис. 14.1. NVELO –подстрока, NEP – подпоследовательность Подстрока Подпоследовательность 14.1. Базовые методы 261 14.1.1. Префиксное дерево Префиксным деревом (trie)называется корневое дерево для хранения множества строк. Каждая строка хранится в виде цепочки символов, на- чинающейся в корне. Если у двух строк имеется об- щий префикс, то у них также будет общая цепочка в дереве. Префиксное дерево на рис. 14.2 соответ- ствует множеству строк {CANAL, CANDY, THE, THERE} Двойной окружностью обозначены вершины, в ко- торых некоторая строка заканчивается. Построив префиксное дерево, мы можем легко проверить, содержит ли оно данную строку. Для этого нужно проследовать по цепочке, начинаю- щейся в корневом узле. Чтобы добавить в дерево новую строку, нужно тоже следовать по цепочке, добавляя в нужных местах новые вершины. Вре- менная сложность обеих операций равна O(n), где n – длина строки. Префиксное дерево можно сохранить в массиве int trie[N][A]; где N – максимальное число вершин (суммарная длина всех строк во мно- жестве), а A – размер алфавита. Вершины дерева нумеруются числами 0, 1, 2, … таким образом, что корень имеет номер 0, а trie [ s][c] определяет ту вершину в цепочке, в которую мы переходим из вершины s, встретив символ c. Структуру префиксного дерева можно обобщить несколькими спосо- бами. Пусть, например, требуется вычислить количество строк с опреде- ленным префиксом. Это можно сделать эффективно, сохранив в каждой вершине дерева количество строк, чьи цепочки проходят через эту вер- шину. 14.1.2. Динамическое программирование Методом динамического программирования можно решить много за- дач, относящихся к строкам. Ниже мы рассмотрим два примера. Наибольшая общая подпоследовательность. Наибольшей общей под- последовательностью двух строк называется самая длинная строка, встре- чающаяся в качестве подпоследовательности в обеих строках. Например, OR – наибольшая общая подпоследовательность строк TOUR и OPERA Применив динамическое программирование, мы можем определить наибольшую общую подпоследовательность двух строк x и y за время O(nm), где n и m – длины строк. Для этого определим функцию lcs (i, j), ко- C T A N A D L Y H E R E Рис. 14.2. Префиксное дерево, содержащее строки CANAL , CANDY , THE и THERE 262 Глава 14. Алгоритмы работы со строками торая возвращает длину наибольшей общей подпоследовательности пре- фиксов x [0 … i] и y [0 … j]. Тогда имеет место рекуррентное соотношение lcs (i − 1, j – 1) + 1 x [i ] = y [j ] lcs (i, j) = � max( lcs (i, j − 1), lcs (i − 1, j)) в противном случае Идея в том, что если символы x [i ] и y [j ] равны, то мы их учитываем и увеличиваем длину самой длинной общей подпоследовательности на едини- цу. В противном случае удаляем последний символ из x или y в зависимости от того, какой выбор лучше. На рис. 14.3 показаны значения функции lcs в нашем примере. Редакторское расстояние. Редакторским рас- стоянием (или расстоянием Левенштейна) между двумя строками называется наименьшее число операций редактирования, преобразующих пер- вую строку во вторую. Разрешены следующие опе- рации: • вставка символа (например, ABC → ABCA ); • удаление символа (например, ABC → AC ); • замена символа (например, ABC → ADC ). Так, редакторское расстояние между строками LOVE и MOVIE равно 2, потому что мы можем сна- чала выполнить операцию LOVE → MOVE (замена), а затем операцию MOVE → MOVIE (вставка). Вычислить редакторское расстояние между стро- ками x и y можно за время O(nm), где n и m – длины строк. Обозначим edit (i, j)редакторское расстоя- ние между префиксами x [0 … i] и y [0 … j]. Значение этой функции можно вычислить, пользуясь рекур- рентным соотношением: edit (a, b) = min( edit (a, b − 1) + 1, edit (a − 1, b) + 1, edit (a − 1, b − 1) + cost (a, b)), где cost (a, b)= 0, если x [a ] = y [ b], а в противном случае cost (a, b)= 1. В этой формуле учтены три способа редактирования строки x : вставка символа в конец x , удаление последнего символа x и совпадение либо замена послед- него символа x . В последнем случае, если x [a ] = y [ b], последние символы можно оставить без изменения. На рис. 14.4 показаны значения функции edit в нашем примере. T O U R O P E R A 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 2 0 1 1 2 Рис. 14.3. Значения функции lcs для опре- деления самой длинной общей подпоследова- тельности строк TOUR и OPERA L O V E M O V I E 1 2 3 4 2 1 2 3 3 2 1 2 4 3 2 2 5 4 3 2 Рис. 14.4. Значения функции edit для определения редакторского расстояния между строками LOVE и MOVIE 14.2. Хеширование строк 263 14.2. Хеширование строк Хеширование строк позволяет эффективно отвечать на вопрос о равенстве строк, сравнивая их хеш-коды. Хеш-код – это целое число, вычисляемое по символам строки. Если две строки равны, то их хеш-коды тоже равны, благодаря чему мы можем сравнивать строки, зная хеш-коды. 14.2.1. Полиномиальное хеширование Чаще всего реализуют полиномиальное хеширование строк, при котором хеш-код строки s длины n вычисляется по формуле ( s [0]A n −1 + s [1]A n −2 + … + s [ n − 1]A 0 ) mod B, где s [0], s [1], …, s [ n − 1] интерпретируются как коды символов, а A и B – за- ранее выбранные константы. Вычислим, к примеру, хеш-код строки ABACB . Коды символов A , B и C рав- ны 65, 66, и 67. В качестве констант выберем A = 3 и B = 97. Тогда хеш-код равен (65 · 3 4 + 66 · 3 3 + 65 · 3 2 + 66 · 3 1 + 67 · 3 0 ) mod 97 = 40. При использовании полиномиального хеширования хеш-код любой подстроки строки s можно вычислить за время O(1)после предобработки, занимающей время O(n). Идея в том, чтобы построить массив h – такой, что h [ k] содержит хеш-код префикса s [0 … k]. Элементы массива вычисля- ются рекурсивно по формуле: h [0] = s [0] h [ k] = ( h [ k − 1]A + s [ k])mod B. Дополнительно строится массив p , для которого p [ k] = A k mod B: p [0] = 1 p [ k] = ( p [ k − 1]A)mod B. Для построения этих массивов требуется время O(n). После этого хеш- код любой подстроки s [ a … b] можно вычислить за время O(1) по формуле ( h [ b] − h [ a − 1] p [ b − a + 1])mod B в предположении, что a > 0. Если a = 0, то хеш-код равен просто h [ b]. 14.2.2. Применения С помощью хеширования можно решить много задач, относящихся к строкам, потому что мы можем сравнивать произвольные подстроки строк за время O(1). Фактически хеширование зачастую позволяет сделать эффективным алгоритм полного перебора. 264 Глава 14. Алгоритмы работы со строками Сопоставление с образцом. Фундаментальной задачей для строк является сопоставление с образцом: даны строка s и образец p, требует- ся установить, в каких позициях s встречается p. Например, образец ABC встречается в строке ABCABABCA в позициях 0 и 5 (рис. 14.5). A B C A B A B C A 0 1 2 3 4 5 6 7 8 Рис. 14.5. Образец ABC встречается в строке ABCABABCA дважды Эту задачу можно решить за время O(n 2 )методом полного перебора: пробежаться по всем позициям s, в которых может встретиться p, и срав- нить строки посимвольно. Но этот алгоритм можно сделать эффективным за счет хеширования, поскольку тогда каждое сравнение занимает время O(1). Таким образом, мы получаем алгоритм с временной сложнос тью O(n). Различные подстроки. Рассмотрим задачу о подсчете числа различных подстрок длины k заданной строки. Например, в строке ABABAB имеется две различные подстроки длины 3: ABA и BAB . Применив хеширование, мы мо- жем вычислить хеш-коды каждой подстроки и свести задачу к подсчету чис- ла различных целых чисел в списке, что можно сделать за время O(n log n). Минимальная циклическая перестановка. Циклическая перестанов- ка строки создается путем перемещения первого символа строки в конец. Например, циклическими перестановками строки ATLAS являются ATLAS , TLASA , LASAT , ASATL и SATLA . Рассмотрим задачу о нахождении лексикогра- фически минимальной циклической перестановки строки. Например, для строки ATLAS таковой является циклическая перестановка ASATL Для эффективного решения задачи мы воспользуемся комбинацией хе- ширования строк и двоичного поиска. Ключевая идея заключается в том, что определить лексикографический порядок двух строк можно за ло- гарифмическое время. Сначала мы вычисляем длину общего префикса строк, применяя двоичный поиск. Здесь хеширование позволяет за время O(1) проверить, совпадают ли префиксы определенной длины. Затем про- веряем следующий за общим префиксом символ, который и определяет взаимный порядок строк. Теперь, чтобы решить задачу, мы строим строку, содержащую две рас- положенные подряд копии исходной строки ( ATLASATLAS ), и перебираем ее подстроки длины n, запоминая по ходу минимальную подстроку. Посколь- ку для одного сравнения нужно время O(log n), полная временная слож- ность алгоритма равна O(n log n). 14.2.3. Коллизии и параметры Очевидной опасностью при сравнении хеш-кодов является коллизия – ситуация, когда строки различны, но их хеш-коды совпадают. В таком 14.2. Хеширование строк 265 случае алгоритм, основанный на хеш-кодах, заключает, что строки оди- наковы, хотя на самом деле это не так, поэтому алгоритм может давать неправильные результаты. Избавиться от коллизий невозможно, потому что число различных строк больше числа возможных хеш-кодов. Однако вероятность коллизии мала, если константы A и B выбраны с умом. Обычно выбирают случайные константы, близкие к 10 9 , например: A = 911382323, B = 972663749. При таком выборе для вычисления хеш-кодов можно использовать тип long long , поскольку произведения AB и BB в него укладываются. Но до- статочно ли иметь примерно 10 9 различных хеш-кодов? Рассмотрим три случая, в которых применяется хеширование. Случай 1. Строки x и y сравниваются между собой. Вероятность коллизии равна 1/B в предположении, что все хеш-коды равновероятны. Случай 2. Строка x сравнивается со строками y 1 , y 2 , ..., y n . Вероятность хотя бы одной коллизии равна 1 − (1 − 1/B) n . Случай 3. Строки x 1 , x 2 , ..., x n сравниваются попарно. Вероятность хотя бы одной коллизии равна 1 − B · (B − 1) · (B − 2) ··· (B − n + 1) . B n Таблица 14.1. Вероятности коллизий при разных применениях хеширования Константа B Случай 1 Случай 2 Случай 3 10 3 0.00 1.00 1.00 10 6 0.00 0.63 1.00 10 9 0.00 0.00 1.00 10 12 0.00 0.00 0.39 10 15 0.00 0.00 0.00 10 18 0.00 0.00 0.00 В табл. 14.1 приведены вероятности коллизий для различных значе- ний B при n = 10 6 . Как видно, в случаях 1 и 2 вероятность коллизии прене- брежимо мала, если B ≈ 10 9 . Однако в случае 3 все совсем по-другому: при B ≈ 10 9 коллизия произойдет почти наверняка. Ситуация в случае 3 известна под названием парадокс дней рождения: если в комнате находится n человек, то вероятность того, что какие-то два из них родились в один день, велика даже при совсем небольших n. И точ- 266 Глава 14. Алгоритмы работы со строками но так же, когда все хеш-коды сравниваются попарно, велика вероятность, что какие-то два из них одинаковы. Вероятность коллизии можно уменьшить, если вычислять несколько хеш-кодов с разными параметрами. Крайне маловероятно, что колли- зия произойдет одновременно в нескольких хеш-кодах. Например, два хеш-кода с параметром B ≈ 10 9 эквивалентны одному хеш-коду с парамет- ром B ≈ 10 18 , при котором вероятность коллизии очень мала. Некоторые выбирают B = 2 32 или B = 2 64 из-за удобства операций с 32- и 64-разрядными целыми числами по модулю 2 32 и 2 64 . Но это плохой выбор, поскольку можно сконструировать такие входные данные, что при любой константе вида 2 x коллизии произойдут обязательно [27]. 14.3. Z-алгоритм Z-массив z строки s длины n для каждого k = 0, 1, ..., n − 1 содержит дли- ну максимальной (самой длинной) подстроки s , которая начинается в позиции k и является префиксом s . Таким образом, z [ k] = p означает, что s [0 ... p − 1] равно s [ k … k + p − 1], но символы s[p] и s [ k + p] различны (или длина строки равна k + p). На рис. 14.6 показан Z-массив строки ABCABCABAB . В нем z [3] = 5, посколь- ку подстрока ABCAB длины 5 является префиксом s , а подстрока ABCABA дли- ны 6 таковым не является. A B C A B C A B A B – 0 0 5 0 0 2 0 2 0 0 1 2 3 4 5 6 7 8 9 Рис. 14.6. Z-массив строки ABCABCABAB 14.3.1. Построение Z-массива Далее мы опишем Z-алгоритм эффективного построения Z-массива за время O(n) 1 . Алгоритм вычисляет элементы Z-массива слева направо, при этом используется уже сохраненная в массиве информация и производит- ся посимвольное сравнение строк. Для эффективного вычисления элементов Z-массива алгоритм хранит диапазон [x, y] – такой, что s [ x … y] – префикс s , значение z [x ] уже опре- делено, а значение y максимально возможное. Поскольку мы знаем, что s [0 … y − x] совпадает с s [ x … y], то можем воспользоваться этой инфор- мацией при вычислении последующих элементов массива. Предположим, что уже вычислены элементы z [0], z [1], …, z [ k − 1] и требуется вычислить z [ k]. Возможны три случая. 1 В работе Gusfield [15] Z-алгоритм представлен как простейший из известных методов сопоставле- ния с образцом за линейное время. При этом авторы ссылаются на оригинальную идею, изложен- ную в работе Main, Lorentz [26]. 14.3. Z-алгоритм 267 Случай 1: y < k. В этом случае у нас нет информации о позиции k, поэтому мы вычисляем z [ k], сравнивая подстроки посимвольно. Так, на рис. 14.7 диапазона [x, y] еще не существует, поэтому подстроки, начинающиеся в позициях 0 и 3, сравниваются посимвольно. Поскольку z [3] = 5, то новым диапазоном [x, y] становится [3, 7]. A B C A B C A B A B – 0 0 ? ? ? ? ? ? ? 0 1 2 3 4 5 6 7 8 9 A B C A B C A B A B – 0 0 5 ? ? ? ? ? ? 0 1 2 3 4 5 6 7 8 9 x y Рис. 14.7. Случай 1: вычисление значения z [3] Случай 2: y ≥ k и k + z [ k − x] ≤ y. В этом случае мы знаем, что z [ k] = z [ k − x], потому что s [0 … y − x] и s [ x … y] равны, и мы остаемся внутри диапазона [x , y]. В ситуации на рис. 14.8 мы заключаем, что z [4] = z [1] = 0. A B C A B C A B A B – 0 0 5 ? ? ? ? ? ? 0 1 2 3 4 5 6 7 8 9 x y A B C A B C A B A B – 0 0 5 0 ? ? ? ? ? 0 1 2 3 4 5 6 7 8 9 x y Рис. 14.8. Случай 2: вычисление значения z [4] Случай 3: y ≥ k и k + z [ k − x] > y. В этом случае мы знаем, что z [ k] ≥ y − k + 1. Однако поскольку у нас нет никакой информации после позиции y, то мы должны посимвольно сравнить подстроки, начинающиеся в позициях y − k + 1 и y + 1. Так, на рис. 14.9 мы знаем, что z [6] ≥ 2. А поскольку s [2] ≠ s [8], то получается, что z [6] = 2. Этот алгоритм имеет временную сложность O(n), поскольку всякий раз, как при посимвольном сравнении строки два символа совпадают, значе- ние y увеличивается. Следовательно, полное время работы, необходимое для сравнения подстрок, равно всего лишь O(n). 268 Глава 14. Алгоритмы работы со строками A B C A B C A B A B – 0 0 5 0 0 ? ? ? ? 0 1 2 3 4 5 6 7 8 9 x y A B C A B C A B A B – 0 0 5 0 0 2 ? ? ? 0 1 2 3 4 5 6 7 8 9 x y Рис. 14.9. Случай 3: вычисление значения z [6] 14.3.2. Применения Z-алгоритм предлагает альтернативный способ решения многих задач со строками, которые можно решить и с помощью хеширования. Но, в от- личие от хеширования, Z-алгоритм всегда дает правильные результаты без риска коллизий. Что применять на практике – хеширование или Z-ал- горитм, – зачастую дело вкуса. Сопоставление с образцом. Снова рассмотрим задачу о сопоставлении с образцом, в которой требуется найти все вхождения образца p в строку s. Мы уже решили ее с помощью хеширования, а теперь посмотрим, как при- менить к ней Z-алгоритм. При обработке строк часто эксплуатируется одна и та же идея: постро- ить строку, состоящую из нескольких частей, разделенных специальными символами. В данном случае мы можем построить строку p#s, где p и s разделены специальным символом #, не встречающимся ни в одной из строк. Тогда Z-массив строки p#s даст нам позиции вхождений p в s: это те элементы, которые содержат длину p. На рис. 14.10 показан Z-массив для строки s = ABCABABCA и образца p = ABC В элементах 4 и 9 находится значение 3, а это значит, что p входит в s, на- чиная с позиций 0 и 5. A B C # A B C A B A B C A – 0 0 0 3 0 0 2 0 3 0 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 Рис. 14.10. Сопоставление с образцом с помощью Z-алгоритма Нахождение границ. Границей строки s называется строка b, являю- щаяся одновременно префиксом и суффиксом s, но не совпадающая с s. Например, границами строки ABACABACABA являются A , ABA и ABACABA . Все 14.4. Суффиксные массивы 269 границы строки можно эффективно найти с помощью Z-алгоритма, по- тому что суффикс, начинающийся в позиции k, является границей тогда и только тогда, когда k + z[k] = n,где n – длина строки. Так, на рис. 14.11 4 + z [4] = 11, т. е. ABACABA – граница строки. A B A C A B A C A B A – 0 1 0 7 0 1 0 3 0 1 0 1 2 3 4 5 6 7 8 9 10 Рис. 14.11. Нахождение границ с помощью Z-алгоритма 14.4. Суффиксные массивы Суффиксный массив строки описывает лекси- кографический порядок ее суффиксов. Каж- дый элемент суффиксного массива содержит начальную позицию некоторого суффикса. На рис. 14.12 показан суффиксный массив строки ABAACBAB Часто удобно располагать суффиксный массив вер- тикально вместе с соответствующими суффиксами (рис. 14.13). Отметим, однако, что сам по себе суф- фиксный массив содержит только начальные пози- ции суффиксов, а не составляющие их символы. 14.4.1. Метод удвоения префикса Простой и эффективный способ построения суф- фиксного массива строки дает метод удвоения пре- фикса, имеющий временную сложность O(n log 2 n) или O(n log n) в зависимости от реализации 2 . Алго- ритм состоит из раундов с номерами 0, 1, …, ⌈log 2 n⌉, на i-м раунде обрабатываются подстроки длины 2 i В ходе раунда каждой подстроке x длины 2 i назнача- ется целочисленная метка l(x) – такая, что l(a)= l(b), тогда и только тогда, когда a = b,и l(a) < l(b)тогда и только тогда, когда a < b. На раунде 0 все подстроки состоят из одного символа, и можно исполь- зовать, например, метки A = 1, B = 2 и т. д. Если же i > 0, то на i-м раунде для построения меток подстрок длины 2 i используются метки для подстрок длины 2 i –1 . Чтобы назначить метку l(x)подстроке x длины 2 i , мы разби- ваем x на две половины a и b длины 2 i −1 с метками l(a)и l(b). (Если вторая 2 Идея метода удвоения префикса изложена в работе Karp, Miller, Rosenberg [20]. Существуют также более эффективные алгоритмы построения суффиксного массива с временной сложностью O(n); в работе Kärkkäinen, Sanders [19] приведен пример довольно простого алгоритма такого рода. 2 6 0 3 7 1 5 4 0 1 2 3 4 5 6 7 Рис. 14.12. Суффиксный массив строки ABAACBAB 2 6 0 3 7 1 5 4 AACBAB AB ABAACBAB ACBAB B BAACBAB BAB CBAB 0 1 2 3 4 5 6 7 Рис. 14.13. Другой способ представ- ления суффиксного массива 270 Глава 14. Алгоритмы работы со строками половина начинается за пределами строки, то предполагаем, что ее метка равна 0.) Сначала мы назначаем в качестве начальной метки x пару (l(a), l(b)). После того как всем подстрокам длины 2 i назначены начальные мет- ки, мы сортируем эти метки и назначаем конечные метки – целые числа 1, 2, 3 и т. д. Цель назначения конечных меток состоит в том, чтобы по за- вершении последнего раунда у каждой подстроки была уникальная метка, и эти метки отражали лексикографический порядок подстрок. И наконец, на основе этих меток легко построить суффиксный массив. На рис. 14.14 показан процесс построения меток для строки ABAACBAB После раунда 1 мы знаем, что l( AB )= 2 и l( AA ) = 1. Поэтому на раунде 2 под- строке ABAA назначается начальная метка (2, 1). Поскольку существуют две меньшие начальные метки ((1, 6) и (2, 0)), то конечная метка будет равна l( ABAA ) = 3. Отметим, что в этом примере после раунда 2 все метки уже уникальны, потому что лексикографический порядок подстрок полностью определен первыми четырьмя символами. – – – – – – – – 1 2 1 1 3 2 1 2 initial labels final labels round 0 length 1 1, 2 2, 1 1, 1 1, 3 3, 2 2, 1 1, 2 2, 0 2 5 1 3 6 5 2 4 initial labels final labels round 1 length 2 2, 1 5, 3 1, 6 3, 5 6, 2 5, 4 2, 0 4, 0 3 6 1 4 8 7 2 5 initial labels final labels round 2 length 4 3, 8 6, 7 1, 2 4, 5 8, 0 7, 0 2, 0 5, 0 3 6 1 4 8 7 2 5 initial labels final labels round 3 length 8 Раунд 0 Длина 1 Раунд 1 Длина 2 Раунд 2 Длина 4 Раунд 3 Длина 8 Начальные метки Начальные метки Начальные метки Начальные метки Конечные метки Конечные метки Конечные метки Конечные метки Рис. 14.14. Построение меток для строки ABAACBAB Этот алгоритм работает за время O(n log 2 n), поскольку число раундов равно O(log n), и на каждом раунде сортируется список n пар. На самом деле возможна также реализация с временной сложностью O(n log n), поскольку для сортировки пар можно использовать алгоритм с линейным временем. Тем не менее прямолинейная реализация со временем O(n log 2 n), для ко- торой не нужно ничего, кроме стандартной функции C++ sort , обычно до- статочно эффективна. 14.4.2. Поиск образцов Имея суффиксный массив, можно эффективно искать все вхождения произвольного образца в строку. Это делается за время O(k log n), где 14.4. Суффиксные массивы 271 n – длина строки, а k – длина образца. Идея заключается в том, чтобы об- рабатывать образец символ за символом и поддерживать диапазон суф- фиксного массива, который соответствует уже обработанному префиксу образца. Чтобы эффективно обновить диапазон после обработки очеред- ного символа, применяется двоичный поиск. Найдем, например, вхождения образца BA в строку ABAACBAB (рис. 14.15). Первоначально диапазон поиска равен [0, 7], т. е. покрывает весь суффикс- ный массив. После обработки символа B диапазон сужается до [4, 6]. Нако- нец, после обработки символа A остается диапазон [5, 6]. Таким образом, мы заключаем, что образец BA входит в строку ABAACBAB дважды – начиная с позиций 1 и 5. 2 6 0 3 7 1 5 4 AACBAB AB ABAACBAB ACBAB B BAACBAB BAB CBAB 0 1 2 3 4 5 6 7 2 6 0 3 7 1 5 4 AACBAB AB ABAACBAB ACBAB B BAACBAB BAB CBAB 0 1 2 3 4 5 6 7 2 6 0 3 7 1 5 4 AACBAB AB ABAACBAB ACBAB B BAACBAB BAB CBAB 0 1 2 3 4 5 6 7 Рис. 14.15. Поиск вхождений образца BA в строку ABAACBAB с помощью суффиксного массива По сравнению с хешированием строк и Z-алгоритмом, суффиксный мас- сив имеет то преимущество, что позволяет эффективно обрабатывать не- сколько запросов для разных образцов, и знать эти образцы заранее при построении суффиксного массива необязательно. 14.4.3. LCP-массивы LCP-массив строки для каждого ее суффикса дает значение LCP: длину наибольшего общего префикса (longest common prefix) этого суффикса и следую- щего суффикса в суффиксном массиве. На рис. 14.16 показан LCP-массив для строки ABAACBAB . Например, значение LCP суффикса BAACBAB равно 2, поскольку наибольший общий префикс BAACBAB и BAB равен BA Отметим, что у последнего суффикса в суффиксном массиве нет значения LCP. Далее мы рассмотрим эффективный алгоритм (Kasai et al. [18]) построения LCP-массива строки в предположении, что уже построен ее суффиксный 1 2 1 0 1 2 0 – AACBAB AB ABAACBAB ACBAB B BAACBAB BAB CBAB 0 1 2 3 4 5 6 7 Рис. 14.16. LCP-мас- сив строки ABAACBAB 272 Глава 14. Алгоритмы работы со строками массив. Алгоритм основан на следующем наблюдении. Рассмотрим суф- фикс, для которого значение LCP равно x. Если удалить первый символ из суффикса, то значение LCP нового суффикса заведомо должно быть не меньше x − 1. Например, на рис. 14.16 значение LCP суффикса BAACBAB рав- но 2, поэтому значение LCP суффикса AACBAB должно быть не меньше 1. На самом деле оно в точности равно 1. Воспользовавшись этим наблюдением, мы можем эффективно по- строить LCP-массив, вычисляя значения LCP в порядке убывания длины суффикса. Для каждого суффикса мы вычисляем его значение LCP, по- символьно сравнивая этот суффикс и следующий за ним в суффиксном массиве. Теперь воспользуемся тем фактом, что нам известно значение LCP суффикса, который на один символ длиннее. Следовательно, текущее значение LCP должно быть не меньше x − 1, где x – предыдущее значение LCP, и нам не нужно сравнивать первые x – 1 символов суффиксов. Полу- чающийся алгоритм работает за время O(n), поскольку производит всего O(n)сравнений. С помощью LCP-массива можно эффективно решать некоторые нетри- виальные задачи со строками. Например, чтобы вычислить количество различных подстрок строки, мы можем просто вычесть сумму всех эле- ментов LCP-массива из общего числа подстрок, т. е. ответ равен ( 1) , n n c c + − где n – длина строки, а c – сумма всех элементов LCP-массива. Например, в строке ABAACBAB имеется 8 9 7 29 2 ⋅ − = различных подстрок. 14.5. Строковые автоматы Автомат 3 – это ориентированный граф, вершины которого называются состояниями, а ребра – переходами. Одно из состояний является началь- ным, оно помечается входящим ребром. Может существовать сколько угодно допускающих состояний, обозначаемых двойными кружками. Каж- дому переходу сопоставляется некоторый символ. Автомат можно использовать для проверки правильности формата строки. Для этого мы стартуем в начальном состоянии, а затем обраба- тываем символы слева направо, двигаясь по переходам. Если после обра- ботки всей строки мы оказываемся в допускающем состоянии, то строка допускается, в противном случае отвергается. 3 Точнее, нас будут интересовать детерминированные конечные автоматы, или ДКА. 2 14.5. Строковые автоматы 273 В теории автоматов множество строк называется языком. Язык автомата состоит из всех допускаемых им строк. Говорят, что автомат распознает язык, если он допускает все строки, принадлежащие этому языку, и отвер- гает все прочие строки. Например, автомат на рис. 14.17 допускает все строки, состоящие из символов A и B , в которых первый и последний символы различны, т. е. язык этого автомата состоит из строк вида { AB , BA , AAB , ABB , BAA , BBA , ...}. В этом автомате состояние 1 начальное, а состояния 3 и 5 допускающие. Если на вход автомата подается строка ABB , то он проходит по цепочке состояний 1 → 2 → 3 → 3 и допускает строку, а если подается строка ABA , то он проходит по цепочке состояний 1 → 2 → 3 → 2 и отвергает строку. 1 2 3 4 5 A B A A B B A B B A Рис. 14.17. Автомат, допускающий все AB-строки, в которых первый и последний символы различны Мы предполагаем, что автоматы детерминированные, т. е. не существует двух переходов из одного состояния, помеченных одним и тем же сим- волом. Это позволяет эффективно и однозначно применять автомат для обработки любой строки. 14.5.1. Регулярные языки Язык называется регулярным, если существует распознающий его авто- мат. Например, множествов AB -строк, в которых первый и последний сим- волы различны, является регулярным языком, потому что его распознает автомат на рис. 14.17. Оказывается, что язык является регулярным тогда и только тогда, ког- да существует регулярное выражение, описывающее допустимый формат принадлежащих ему строк. Регулярные выражения состоят из следующих структурных элементов: • вертикальная черта | означает выбор одного из нескольких вариан- тов. Например, регулярное выражение AB|BA|C допускает строки AB , BA и C ; 274 Глава 14. Алгоритмы работы со строками • скобки ( и ) применяются для группировки. Например, регулярное выражение A(A|B)C допускает строки AAC и ABC ; • звездочка * означает, что предшествующую ей часть можно повто- рять произвольное число раз (в т. ч. нуль). Например, регулярное выра жение A(BC)* допускает строки A , ABC , ABCBC и т. д. Ниже приведено регулярное выражение для автомата на рис. 14.17: A(A|B)*B|B(A|B)*A В этом случае имеется два варианта: либо строка начинается символом A и заканчивается символом B , либо начинается B и заканчивается A . Часть (A|B)* соответствует любой строке, состоящей из символов A и B Интуитивно понятно, что язык регулярный, если можно создать алго- ритм, который просматривает входную строку слева направо один раз, ис- пользует постоянный объем памяти и может определить, принадлежит ли строка языку. Например, язык { AB , AABB , AAABBB , AAAABBBB , ...} не является регулярным, потому что мы должны запомнить количество символов A , а затем проверить, что символов B столько же, но для произ- вольно длинных строк это невозможно сделать в памяти постоянного объ- ема. Заметим, что в реализациях регулярных выражений в языках програм- мирования часто имеются расширения, позволяющие распознавать язы- ки, не являющиеся строго регулярными, для которых невозможно создать автомат. 14.5.2. Автоматы для сопоставления с образцом Автомат для сопоставления с образцом можно использовать для эффек- тивного обнаружения всех вхождений образца в строку. Идея заключается в том, чтобы создать автомат, допускающий строку тогда и только тогда, когда образец является ее суффиксом. Тогда при обработке строки автомат всегда переходит в допускающее состояние, если обнаружил вхождение образца. Если задан образец p, содержащий n символов, то автомат для сопо- ставления с ним имеет n + 1 состояний. Состояния нумеруются числами 0,1, ..., n, так что состояние 0 начальное, а единственным допускающим является состояние n. Если мы находимся в состоянии i, то уже произвели сопоставление с префиксом p[0 ... i − 1], т. е. с первыми i символами образ- ца. Далее мы переходим в состояние i + 1, если следующий входной символ совпадает с p[i], а в противном случае возвращаемся в какое-то состояние x ≤ i. 14.5. Строковые автоматы 275 Например, на рис. 14.18 показан автомат для сопоставления с образцом ABA . В про- цессе обработки строки ABABA он переме- щается по цепочке состояний 0 → 1 → 2 → 3 → 2 → 3. В допускающее состояние 3 он попадает дважды, это значит, что образец входит в строку два раза. Для построения автомата мы должны определить все переходы между состоя ниями. Обозначим nextState[s][c] состояние, в которое мы перехо- дим из состояния s в результате чтения символа c. Например, на рис. 14.18 nextState[1][B] = 2 , потому что после чтения B в состоянии 1 мы перехо- дим в состояние 2. Оказывается, что значения nextState можно эффек- тивно вычислить, создав сначала массив граней для образца, т. е. массив, в котором border [i ] обозначает длину самой длинной (собственной) грани p[0 ... i]. Например, на рис. 14.19 пока- зан массив граней образца ABAABABAAA В частности, border [4] = 2, потому что AB – грань ABAAB максимальной длины. Массив граней можно построить за время O(n)следующим образом: border[0] = 0; for (int i = 1; i < n; i++) { int k = border[i-1]; while (k != 0 && p[k] != p[i]) { k = border[k-1]; } border[i] = (p[k] == p[i]) ? k+1 : 0; } Алгоритм вычисляет значения border [i ], используя уже вычислен- ные элементы массива. Идея заключается в том, чтобы обойти грани p[0 ... i − 1] и выбрать самую длинную грань, которую можно расширить, добавив символ p[i]. Время работы алгоритма имеет порядок O(n), потому что border [ i + 1] ≤ border [i ] + 1, поэтому общее число итераций цикла while равно O(n). После построения массива граней мы можем воспользоваться формулой ⎧s + 1 если s < n и p[s] = c nextState [ s][c] = ⎨ 0 если s = 0 ⎩ nextState [ border [ s − 1]][c] в противном случае для вычисления переходов. Если мы можем расширить префикс, сопостав- ленный в текущий момент, то переходим в следующее состояние. Если не 0 1 2 3 A B A B B A B A Рис. 14.18. Автомат для сопоставления с образцом ABA A B A A B A B A A A 0 0 1 1 2 3 2 3 4 1 0 1 2 3 4 5 6 7 8 9 Рис. 14.19. Массив граней ABAABABAAA 276 Глава 14. Алгоритмы работы со строками можем и находимся в состоянии 0, то в нем и остаемся. В противном случае определяем самую длинную грань текущего префикса и следуем по ранее вычисленному переходу. Пользуясь этой формулой, мы можем построить автомат для сопоставления с образцом за время O(n)в предположении, что алфавит не изменяется. Алгоритм Кнута–Морриса–Пратта [24] – хорошо известный алгоритм сопоставления с образцом, основанный на моделировании автомата для сопоставления с образцом. Его можно рассматривать как альтернативу Z-алгоритму (раздел 14.3). 14.5.3. Суффиксные автоматы С уффиксным автоматом [5] называется автомат, который допускает все суффиксы строки 4 и имеет минимальное число состояний. На рис. 14.20 показан суффиксный автомат для строки BACA . Он допускает суффиксы A , CA , ACA и BACA . Каждое состояние суффиксного автомата соответствует некоторому множеству строк, т. е. если мы находимся в этом состоянии, значит, произошло сопоставление с одной из строк этого множества. На- пример, на рис. 14.20 состояние 3 соответствует множеству { C , AC , BAC }, а состояние 5 – множеству { A }. Обозначим length [x ] максимальную длину строки в состоянии x. Тогда length [3] = 3 и length [5] = 1. Оказывается, что все строки в некотором состоянии являются суффиксами самой длинной из них, а их длины полностью покрывают диапазоны соседних целых чи- сел. Например, в состоянии 3 все строки являются суффиксами BAC , а их длины образуют диапазон 1...3. 0 1 2 3 4 5 B A C A A C C Рис. 14.20. Суффиксный автомат для строки BACA Для данной строки s длины n мы хотим создать ее суффиксный автомат за время O(n), начав с пустого автомата, имеющего только состояние 0, и добавив в него все символы по одному. Для этого мы будем хранить для каждого состояния x > 0 суффиксную ссылку link [x ], указывающую на одно из предыдущих состояний автомата. Новый символ c добавляется в авто- мат следующим образом. 1. Обозначим x текущее последнее состояние автомата, т. е. состоя- ние, из которого не исходит ни один переход. Создадим новое 4 И только их. – Прим. ред. 14.5. Строковые автоматы 277 состоя ние y и добавим переход из x в y, помеченный c. Положим length [y ] = length [x ] + 1 и link [y ] = 0. 2. Следуем по суффиксным ссылкам, исходящим из x, для каждого по- сещенного состояния добавляем новый переход в y,помеченный c, пока не найдем состояние s, в которое уже ведет переход, помечен- ный c. Если такого состояния s нет, то завершаем работу, дойдя до состояния 0. В противном случае переходим к следующему шагу. 3. Обозначим u такое состояние, для которого существует переход из s в u, помеченный c. Если length [ s] + 1 = length [ u], полагаем link [y ] = u и завершаем работу. В противном случае переходим к следующему шагу. 4. Создаем новое состояние z, клонируя состояние u (копируем все ис- ходящие из u переходы в z и полагаем link [z ] = link [ u]), добавляем переход из s в z, помеченный c,и полагаем length [z ] = length [ s] + 1. Затем полагаем link [ u] = link [y ] = z. 5. Наконец, следуем по суффиксным ссылкам, исходящим из s. До тех пор пока из текущего состояния имеется переход в состояние u, по- меченный c, заменяем u на z в этом переходе. Если мы нашли со- стояние, из которого нет перехода в u, помеченного c, или дошли до состояния 0, то завершаем работу. На рис. 14.21 показан процесс создания суффиксного автомата для стро- ки BACA . После добавления последнего символа мы должны создать допол- нительное состояние 5 путем клонирования состояния 2. В этом примере все суффиксные ссылки указывают на состояние 0, и следует ожидать, что в окончательном автомате существует суффиксная ссылка из состояния 4 в состояние 5, обозначенная штриховым ребром. После создания автомата мы можем найти допускающие состояния, начав из последнего состояния и следуя по суффиксным ссылкам, пока не достигнем состояния 0. Все со- стояния на этом пути (в нашем примере – состояния 4 и 5) являются допус- кающими. Заметим, что суффиксная ссылка говорит, в какое состояние мы должны перейти, если хотим найти более короткие строки, являющиеся суффикса- ми строк в текущем состоянии. В нашем примере состояние 4 соответству- ет множеству { CA , ACA , BACA }, а состояние 5 – множеству { A }. Таким образом, суффиксную ссылку из состояния 4 в состояние 5 можно использовать для нахождения более короткого суффикса A. На самом деле, следуя по суф- фиксным ссылкам из состояния x в состояние 0, мы найдем все суффик- сы самой длинной строки в состоянии x, и каждый суффикс принадлежит ровно одному состоянию. После того как суффисный автомат создан, мы можем за время O(m)про- верить, встречается ли в строке любой образец длины m. Применив дина- 278 Глава 14. Алгоритмы работы со строками мическое программирование, мы сможем также найти, сколько раз встре- чается образец, вычислить количество различных подстрок и т. д. В общем случае суффиксные автоматы могут служить альтернативой суффиксным массивам, и с этой новой точки зрения можно рассмотреть многие задачи обработки строк. 0 1 B 0 1 2 B A A 0 1 2 3 B A C C A 0 1 2 3 4 5 B A C A A C C Рис. 14.21. Построение суффиксного автомата |