2010 → Выпуск 6

Быстрое инкрементальное сопоставление с регулярными выражениями при помощи моноидов

Dan Piponi
(Перевод Евгения Кирпичёва)

Аннотация: В статье рассматривается применение моноидов к задаче сопоставления строк с регулярными выражениями, а затем строится инкрементальный алгоритм сопоставления, позволяющий при изменениях строки обновлять результат за O(log N). Алгоритм основан на структуре данных «подвешенное дерево», позволяющей сделать инкрементальным любой подобный алгоритм на основе моноидов1.

1  Задача

Пусть заданы регулярное выражение R и строка длины N, и мы хотим выяснить, подходит ли строка под выражение R. Что ж — скорее всего, придётся просмотреть всю строку посимвольно. Как быстро можно выполнить повторную операцию, если строка слегка изменилась? Кажется, в общем случае придётся еще раз просмотреть строку с начала, или, по крайней мере, начиная с изменённого места. Но оказывается, сопоставление с регулярным выражением можно делать инкрементально, и тогда для большинства изменений, производимых над строкой, пересчёт соответствия строки выражению потребует лишь O(log N) времени. Это верно даже в случаях, когда для успешного сопоставления требуется учитывать символы на противоположных концах строки. Более того, применение подвешенных деревьев и моноидов делает реализацию этого алгоритма удивительно простой.

Дальнейший материал предполагает некоторый набор знаний, которые можно почерпнуть из ресурсов, доступных в вебе: знакомство с моноидами [1], понимание материалов, представленных Heinrich Apfelmus в статье «Введение в подвешенные деревья» [2] или оригинальной статье о них [5], и уверенное понимание идеи компиляции регулярных выражений в конечные автоматы.

Этот пост, как обычно, написан на Literate Haskell. Нам понадобится пакет fingertree и несколько импортов.

{-# LANGUAGE TypeSynonymInstances,FlexibleInstances, MultiParamTypeClasses #-} import qualified Data.Array as B import Data.Array.Unboxed as U import Data.Foldable import Data.Monoid import Data.FingerTree hiding (fromList) import qualified Data.List as L

2  Конечные автоматы

Рассмотрим простое регулярное выражение: .*(.*007.*).*. Мы ищем строку 007, заключенную в скобки, которые могут находиться на расстоянии миллионов символов друг от друга.

Стандартный способ поиска регулярных выражений — компиляция их в конечный автомат. Кода для этого нужно довольно много, но он совершенно обыкновенный. Поэтому я не буду его приводить, а построю автомат для этого выражения вручную.

Рис. 1: Автомат для выражения .*(.*007.*).*

На рисунке 1 непомеченные ребра означают «если никакое помеченное ребро не подошло». Правила перехода этого автомата можно описать функцией fsm.

fsm 0 '(' = 1 fsm 0 _ = 0 fsm 1 '0' = 2 fsm 1 _ = 1 fsm 2 '0' = 3 fsm 2 _ = 1 fsm 3 '7' = 4 fsm 3 '0' = 3 fsm 3 _ = 1 fsm 4 ')' = 5 fsm 4 _ = 4 fsm 5 _ = 5

Начальное состояние автомата — 0, а успешное сопоставление соответствует состоянию 5.

Cтроки можно сопоставлять с помощью следующего кода:

matches s = Prelude.foldl fsm 0 s==5

Попробуйте вычислить matches "(00 7)" и matches "He(007xxxxxxxxxxxx)llo".

Входные символы можно рассматривать как действия над автоматом. Каждый очередной символ — это функция, переводящая автомат из одного состояния в другое. Мы могли бы воспользоваться (.) — функцией композиции языка Haskell — чтобы скомбинировать эти функции. Однако (.) ничего особенного не делает, f . g это лишь замыкание, означающее «когда придёт время, примени g, а затем f».

Впрочем, такие функции переходов можно табулировать следующим образом:

tabulate f = array (0,5) [(x,f x) | x <- range (0,5)]

Для каждой буквы алфавита у нас есть одна табулированная функция:

letters = array (' ','z') [(i,tabulate (flip fsm i)) | i <- range (' ','z')]

Имея две табулированные функции, легко составить таблицу для их композиции. Табулированные функции образуют моноид с композицией mappend. Для большей эффективности воспользуемся распакованными массивами:

type Table = UArray Int Int instance Monoid Table where mempty = tabulate id f `mappend` g = tabulate (\state -> (U.!) g ((U.!) f state))

Тут есть одна тонкость: объект типа Table в принципе может бы быть любым массивом целочисленных значений с индексами типа Int. Но если мы ограничим индексы и значения массива числами от 0 до 5, то действительно получится моноид.

Мы можем проверить соответствие любой строки нашему регулярному выражению: выберем из массива letters значения типа Table, соответствующие каждому символу строки, объединим таблицы и проверим, отображает ли полученная табулированная функция начальное состояние 0 в конечное состояние 5:

matches' s = table!0==5 where table = mconcat (map ((B.!) letters) s)

Этот способ медленнее и сложнее, чем наша первоначальная реализация matches, но зато мы выделили в задаче моноидальную структуру. Если хранить строку как последовательность символов, представленную подвешенным деревом, то можно в каждом узле дерева хранить массив Table для подстроки, представляемой этим узлом. Каждый раз при перебалансировке узлов дерева необходимо пересчитывать соответствующие массивы Table. Но это нам подходит, обычно перебалансировка требует лишь O(log N) операций, а писать код для этого вовсе не надо — подвешенные деревья сделают всё за нас. В результате представление каждой подстроки обладает тем свойством, что для неё всегда известен соответствующий ей массив Table. Такие деревья можно свободно резать и склеивать, зная что Table всегда будет содержать свежие данные.

Осталось одна небольшая загвоздка: мне хотелось бы иметь возможность произвольного доступа к n-му символу дерева. Как это сделать, разъяснено у apfelmus [2]. Понадобятся одновременно моноиды Size и Table, поэтому я воспользуюсь произведением моноидов [1].

data Elem a = Elem { getElem :: a } deriving Show data Size = Size { getSize :: Int } deriving (Eq,Ord,Show) instance Monoid Size where mempty = Size 0 Size m `mappend` Size n = Size (m+n)

Остается реализовать measure из статьи о подвешенных деревьях [5]:

instance Measured (Size,Table) (Elem Char) where measure (Elem a) = (Size 1,(B.!) letters a)

3  Подвешенные деревья

Теперь мы можем определить строки следующим образом:

type FingerString = FingerTree (Size,Table) (Elem Char)

Процедура вставки примерно такая же, как в статье:

insert :: Int -> Char -> FingerString -> FingerString insert i c z = l >< (Elem c <| r) where (l,r) = split (\(Size n,_) -> n>i) z

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

Вот пример строки. Подберите её длину в соответствии с имеющейся памятью и мощностью процессора:

fromList = L.foldl' (|>) empty string = fromList (map Elem $ take 1000000 $ cycle "the quick brown fox jumped over the lazy dog")

(Я использую энергичную версию fromList, чтобы обеспечить гарантированное построение дерева.)

Функция сопоставления просто вычленяет вторую компоненту моноида и проверяет, отображает ли она начальное состояние в конечное:

matches007 string = ((U.!) (snd (measure string)) 0)==5

4  Цикл взаимодействия

Советую компилировать этот код с оптимизацией, например ghc --make -O5 -o regexp regexp.lhs:

loop string = do print $ "matches? " ++ show (matches007 string) print "(Position,Character)" r <- getLine let (i,c) = read r loop $ insert i c string main = do loop string

Теперь можно работать с программой интерактивно. На вход принимаются значения вроде (100, ’f’) (вставить ’f’ в позиции 100). Исходное дерево может вычисляться несколько секунд, после чего каждое сопоставление будет мгновенным. (Впрочем, вторая проверка тоже может занять несколько секунд, поскольку, несмотря на foldl’, дерево ещё не построилось полностью.)

Вот пример входных данных:

(100,'(') (900000,')') (20105,'0') (20106,'0') (20107,'7')

5  Обсуждение

Обратите внимание, что этот вариант решения содержит значительные издержки. Для каждого символа я храню массив Table целиком. Вы вполне можете хранить строку поблочно (как в структуре данных «верёвка» [3]). Тогда при редактировании строки придётся просматривать некоторые блоки повторно — но просмотр, к примеру, блока в 1 килобайт куда дешевле, чем просмотр гигабайтного файла целиком. Кроме того, поблочная обработка, вероятно, ускорит и первый проход, поскольку требует построения дерева значительно меньшего размера.

Когда Хинзе и Патерсон писали первую статью про подвешенные деревья, они черпали вдохновение из алгоритмов на основе префиксных сумм. Почти любой алгоритм на их основе можно сделать инкрементальным с помощью подвешенных деревьев. Настоящая статья основана на идее применения подвешенных деревьев к схеме параллельного синтаксического разбора, описанной Хиллисом и Стилом в их классической статье о Connection Machine [4].

Зачем же может понадобиться сопоставлять строки с подобным фиксированным регулярным выражением? Ну, например, на основе этого метода можно построить полноценный инкрементальный лексер. Он будет обновлять результат мгновенно, даже если вставка очередного символа в строку меняет тип лексемы в миллиарде символов от него. С деталями можно ознакомиться в статье Хиллиса и Стила.

Примечательно, что в этом коде нет ничего особенно «Хаскельного» — разве что, на Хаскеле было особенно легко написать прототип. Вы можете сделать то же самое и на С++, скажем, с помощью красно-чёрных деревьев.

Список литературы

[1]
Haskell monoids and their uses. http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html, также переведено в первом выпуске журнала <<Практика функционального программирования>>.
[2]
Monoids and finger trees. http://apfelmus.nfshost.com/monoid-fingertree.html.
[3]
Rope implementation overview. http://www.sgi.com/tech/stl/ropeimpl.html.
[4]
W. Daniel Hillis and Guy L. Steele, Jr. Data parallel algorithms. Commun. ACM, 29(12):1170–1183, 1986.
[5]
Ralf Hinze and Ross Paterson. Finger trees: a simple general-purpose data structure. J. Funct. Program., 16(2):197–217, 2006.
[6]
Dan Piponi. Fast incremental regular expression matching with monoids. http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html, 2009.
1
Аннотация составлена переводчиком. Оригинал статьи доступен по адресу [6].
Этот документ был получен из LATEX при помощи HEVEA