Практика функционального программирования

Аннотация:

В этой статье при помощи ряда красивых алгоритмических приемов из мира функционального программирования строится Java-библиотека для инкрементального сопоставления строк с регулярными выражениями. Целевая аудитория статьи: 1) алгоритмисты, любящие пополнить свой арсенал новыми инструментами и 2) люди, интересующиеся тем, как идеи из ФП ложатся на императивные языки.

1  Введение

Задача сопоставления строк с регулярными выражениями известна давно (с 1960-х гг.) и имеет множество решений. Сопутствующие алгоритмы очень красивы, и редок тот программист, кто не попытался хотя бы раз в жизни написать для развлечения движок регулярных выражений.

Для понимания дальнейшего материала будет полезно освежить в памяти основные концепции регулярных выражений в одном из общедоступных источников, например [13].

Подходы к решению этой задачи довольно сильно отличаются по области применимости.

Вот некоторые из вопросов, встающих перед разработчиком очередного движка:

• Какие операторы поддерживать? Поддерживать ли «захватывающие группы (capturing groups)», «обратные ссылки (backreferences)», исполнение произвольного кода, «жадное» сопоставление и т. п.? Чем больше возможностей поддерживается, тем труднее реализовать движок эффективно — большинство из них исключают сразу целые классы алгоритмов сопоставления.
• Каков будет размер и количество искомых регулярных выражений? Будут ли это небольшие выражения для валидации данных, или допускается возможность создания полноценного лексера с десятками или сотнями токенов, заданных своими выражениями?
• Как много раз происходит сопоставление с каждым выражением? Допустимо ли очень долго «компилировать» его, но зато очень быстро выполнять сопоставление?
• Насколько велик объем сопоставляемого текста, как часто он меняется и каков характер изменений?
• И т. п.

Перечислим некоторые из существующих подходов и движков.

• Автоматный подход: awk, grep, re2 [10] (благодаря автоматному подходу он обладает рядом особенностей, делающих возможным существование Google Code Search) — гарантируется линейное время сопоставления, однако некоторые возможности (например, обратные ссылки) принципиально не реализуемы; затруднено (но возможно) извлечение «захватывающих групп»; иногда возможен экспоненциально большой объем потребляемой памяти (впрочем, re2 избегает этой проблемы за счет перехода к недетерминированным автоматам при нехватке памяти);
• Модифицированный автоматный подход, «помеченные (tagged)» автоматы: libtre [20], regex-tdfa [19] — также гарантируется линейное время сопоставления; возможен нечеткий поиск;
• Подход на основе полуколец: weighted-regexp [26] — также гарантированное линейное время сопоставления и линейный (относительно размера выражения) объем требуемой памяти; очень простая, красивая и эффективная реализация;
• Рекурсивный спуск: большинство движков (Perl и PCRE-движки, Java, irregexp и т. п.) — полный спектр возможностей, однако возможны «патологические» случаи, когда время сопоставления резко возрастает;

В блог-посте [24] Дэн Пипони¹ наметил еще один подход, связанный с использованием моноидов и т. н. «подвешенных деревьев (finger trees)²». Этот подход работает только для «истинных» регулярных выражений (фактически, в нашем распоряжении лишь символы, скобки и операторы +, *, ?, |), однако позволяет выполнять сопоставление инкрементально, то есть, при изменениях входной строки результат сопоставления пересчитывается очень быстро, без повторного сканирования. К изменениям относятся склейка двух строк и разрезание строки в произвольном месте. Ясно, что через эти операции легко выражаются и все остальные (вставка в середину, дописывание в конец и т. п.).

По мнению автора настоящей статьи, упомянутый блог-пост представляет собой жемчужину программирования. Долгое время автор ограничивался пламенным пересказом его содержания знакомым, коллегам и студентам, однако в конечном итоге желание «копнуть поглубже» возобладало. Данная статья посвящена доработке подхода Дэна Пипони и реализации его в виде библиотеки на языке Java.

Язык Java выбран для того, чтобы достигнуть сразу несколько целей:

• Повысить вероятность того, что разработанная библиотека принесет пользу, а не останется «академической игрушкой» из-за трудностей включения ее в существующие проекты;
• Облегчить понимание кода для весьма широкого на настоящий момент сообщества программистов на Си-подобных языках;
• Показать, что изучение идей из мира функционального программирования приносит плоды и при программировании на не-функциональных языках.

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

• Возможность быстро перестраивать результат при изменениях строки была бы полезна в текстовых редакторах для инкрементальной подсветки произвольного синтаксиса, где токены заданы регулярными выражениями (например, vim позволяет достаточно гибко задавать правила синтаксиса, однако не всегда правильно выполняет подсветку и переподсветку при редактировании, поскольку использует «наивный» подход к подсветке).
• Можно представить себе задачу из области биоинформатики, где при помощи, скажем, генетического алгоритма ([16]) из кусков ДНК-последовательностей при помощи склеиваний и разрезов собирается новая последовательность, и оптимизируется какая-то функция, зависящая от наличия и положения в ней определенных паттернов.

Дальнейший текст будет структурирован следующим образом:

• Краткое рассмотрение автоматного подхода к регулярным выражениям и главная идея инкрементального сопоставления — манипулирование переходными функциями автоматов;
• Идея структуры данных «верёвка», предназначенной для представления последовательностей с эффективными операциями разрезания и склейки;
• Связь переходных функций автоматов с понятием моноида; краткая иллюстрация этого понятия на других примерах в программировании;
• Идея комбинирования верёвок и моноидов;
• Общая схема программы;
• Выделение основных алгоритмических и технических трудностей;
• Описание конкретной реализации верёвок и идея чисто функциональной структуры данных;
• Демонстрация программы: примеры и тесты;
• Перечисление нерешенных вопросов и дальнейших направлений развития.

2  Автоматный подход

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

По регулярному выражению при помощи, например, т. н. «конструкции Томсона» [12] строится конечный автомат, в котором одно или несколько состояний объявлены «начальными», одно или несколько состояний — «терминальными», и некоторые состояния соединены дугами. Дуга из состояния A в состояние B, подписанная символом c, означает: «если состояние A активно и на вход подается символ c, то вместо состояния A активируется состояние B». Есть также є (эпсилон)-дуги: если A соединено є-дугой с B, то при активации A немедленно активируется и B. Если же из состояния «некуда» выйти по очередному входному символу, то оно просто деактивируется. Автомат называется «недетерминированным» потому, что в каждый момент могут быть активны сразу несколько состояний.

Для выполнения сопоставления активируется начальное состояние и на вход по очереди подается каждый символ последовательности. Если в итоге оказывается активным хотя бы одно «терминальное» состояние — сопоставление объявляется успешным.

---

Рис. 1: Недетерминированный автомат, соответствующий выражению «.*a(b*a|bc+)a»

---

Пример. Регулярное выражение «.*a(b*a|bc+)a». Автомат для этого выражения приведен на рис. 1, а вот его последовательность активных состояний при подаче на вход строки «aabcca».

---

Увиденная порция строки	Активные состояния
	{s1}
a	{s1,  s2,  s3,  s4}
aa	{s1,  s2,  s3,  s4,  s5,  s8}
aab	{s1,  s3,  s6}
aabc	{s1,  s6,  s7,  s8}
aabcc	{s1,  s6,  s7,  s8}
aabcca	{s1,  s2,  s3,  s4,  s9}

---

Поскольку по окончании просмотра строки в активном множестве содержится терминальное состояние s₉, сопоставление объявляется успешным.

Для ускорения сопоставления из автомата иногда убирают є-дуги и выполняют его детерминизацию (из каждого состояния разрешается не более одной исходящей дуги, подписанной одним и тем же символом). Для детерминизации существует несколько алгоритмов; они описаны, например, в [17] и [29]. Получается совершенно другой автомат, однако соответствующий тому же регулярному выражению . Тогда в каждый момент при сопоставлении оказывается активно лишь одно состояние, что позволяет построить более эффективную реализацию сопоставления. Однако мы не будем использовать детерминизацию, поскольку в результате нее автомат может экспоненциально разрастись: например, любой автомат для выражения вида (0|(01*)(01*)(01*)… 0)* будет иметь размер порядка O(2ⁿ), где n — количество повторений (01*), что, как мы увидим далее, в нашей задаче совершенно недопустимо. Мы воспользуемся лишь первым ее этапом — удалением є-дуг; оно может только уменьшить размер автомата (ср. рис. 1 и 2). Алгоритм удаления є-дуг очень прост: конец каждой дуги переставляется на каждый из узлов, достижимых по є-дугам из «бывшего» конца этой дуги, затем удаляются недостижимые узлы.

---

Рис. 2: Недетерминированный автомат, соответствующий выражению «.*a(b*a|bc+)a», после удаления є-дуг

---

Обратим внимание, что можно «расслоить» этот автомат посимвольно. Если для каждого символа из алфавита выбирать из автомата только те переходы, которые активируются при подаче этого символа, то можно разделить исходный автомат на несколько подавтоматов (рис. 3).

---

Рис. 3: Недетерминированный автомат, соответствующий выражению «.*a(b*|c+)a», расслоённый посимвольно

---

Изобразим эти подавтоматы несколько иначе (рис. 4). Становится видно, что каждый из них можно рассмотреть как таблицу: каждому из возможных входных символов соответствует «переходная функция» — «Каким будет следующее состояние автомата после подачи на вход этого символа, если текущее его состояние — S?». Кроме того, становится видно, что понятие такой «переходной функции» имеет смысл не только для отдельных символов, но и для целых строк. Имея переходную функцию для строки, какой бы длинной эта строка ни была, можно сэмулировать подачу ее на вход автомата, не рассматривая ее символы по отдельности. Переходная функция строки легко вычисляется по переходным функциям ее символов; точно так же, имея переходные функции для двух строк, можно вычислить функцию для их конкатенации³.

---

Рис. 4: Переходные функции недетерминированного автомата и их композиция

---

Вот и половина решения нашей задачи инкрементального сопоставления, а именно — быстрый пересчет результата при склейке строк!

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

3  Верёвки

Следующая грань задачи — представление строк, допускающее эффективную склейку и разрезание. Такая структура данных давно известна и называется «верёвка (rope)». Верёвка представляет собой сбалансированное дерево из «сегментов (chunks)» — небольших массивов символов. При склейке и разрезании используются операции, аналогичные тем, что используются для сбалансированных деревьев, но с дополнительными действиями на уровне листьев дерева, то есть, сегментов. Разновидности верёвок отличаются способом балансировки. Одна из разновидностей описана в статье [9]. Мы пока не будем останавливаться на этой структуре данных подробно; вполне достаточно уже изложенной основной идеи.

Вспомним, как мы собирались решить задачу инкрементального сопоставления с регулярным выражением:

• При склейке переходные функции перемножаются;
• Переходные функции для подпоследовательностей кэшируются и используются при разрезании.

Если кэшировать переходные функции в узлах этого дерева-верёвки, то получится структура данных «верёвка, всегда знающая свою переходную функцию» (то есть, фактически, свой результат сопоставления с регулярным выражением). Пример такой структуры показан на рис. 5.

Более точно, во время операций перебалансировки верёвок, происходящих при склейке и разрезании, просто будем собирать переходные функции новых узлов из произведений переходных функций узлов, оставшихся нетронутыми (к сожалению, при склейке и разрезании листовых сегментов переходную функцию для получающихся новых сегментов придется всё же считать заново).

---

Рис. 5: Пример верёвки с закэшированной переходной функцией относительно выражения «.*a(b*|c+)a» для строки bcabbccabcccab

---

3.1  Разрезание по монотонному условию

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

Пусть есть некоторый предикат (свойство) f над строками. Пусть f такова, что всякая строка может лишь приобрести (но не потерять) свойство f при дописывании символов справа, то есть, ∀ s₁, f(s₁) ⇒ ∀ s₂, f(s₁+s₂). В этом случае будем называть свойство f монотонным.

Тогда у каждой строки, удовлетворяющей свойству f, существует минимальный префикс, удовлетворяющий f. Проиллюстрируем это понятие и алгоритм его быстрого вычисления на верёвке с помощью рис. 6.

---

Рис. 6: Разрезание верёвки для строки acabaabacabccaaba по монотонному условию «содержит bcc»

---

На рисунке красным отмечены рёбра, удовлетворяющие условию «там, где ребро кончается, условие уже верно». Очевидно, что чтобы найти точку разреза, надо спуститься от корня верёвки до листа, двигаясь вниз и вправо, и на каждом уровне просматривая ребра слева направо, пока не встретится красное ребро, а затем разрезать лист — уже с помощью обычного линейного поиска. Цифры «0» и «1» написаны вокруг просматриваемых ребер и означают, верно ли условие для соответствующего префикса строки (до ребра, между ребрами и т. п.)

Поскольку движение осуществляется вниз и вправо, то в каждый момент просмотренные ребра суммарно покрывают целиком все возрастающий префикс исходной строки, и с каждым просмотренным ребром к этому префиксу прибавляется покрываемая данным ребром подстрока. Если при этом оказывается, что до просмотра ребра условие еще не было верно, а после просмотра — стало, то надо спуститься внутрь узла, в который ведет это ребро.

Чтобы постоянно быть в курсе, верно ли уже условие, надо, чтобы можно было быстро вычислять f(p s), зная f(p) и f(s) для любых строк p и s, поскольку при движении вниз и вправо «текущий префикс» (p) при просмотре каждого очередного ребра увеличивается на покрываемую этим ребром подстроку (s), а при просмотре каждого очередного символа при линейном поиске внутри листового блока — на строку из одного этого символа.

Проиллюстрируем алгоритм разрезания на еще одном примере — рис. 7. На нем изображена верёвка из чисел, знающая сумму их квадратов, и проводится операция разрезания для поиска минимального префикса с суммой квадратов более 140. Алгоритм напоминает игру «горячо —холодно»; на рисунке показаны суммы квадратов префиксов до и после различных ребер и (при просмотре листового блока) символов; те, что еще не удовлетворяют условию, отмечены «холодным» синим цветом, а те, что удовлетворяют — «горячим» красным. На этом рисунке заметно, что при просмотре листовых блоков необходимо перевычислять квадраты некоторых чисел, то есть, информации, «закэшированной» в узлах дерева, уже недостаточно.

Операция разрезания пригодится нам позднее для поиска позиций вхождений регулярного выражения в строке.

---

Рис. 7: Разрезание верёвки из чисел по монотонному условию «сумма квадратов больше 140»

---

4  Моноиды

Как было сказано выше, имея конечный автомат, можно сопоставить каждой строке «переходную функцию» относительно этого автомата, и при склейке строк их переходные функции комбинируются (обозначим композицию функций f₁ и f₂ как f₁ ∘ f₂).

Умножение переходных функций (как, кстати, и склейка строк) обладает парой простых и полезных свойств, в истинности которых проще всего убедиться визуально, глядя на рис. 4:

• Для любых трех переходных функций f, g, h верно f ∘ (g ∘ h) = (f ∘ g) ∘ h, то есть значение выражения вида a ∘ b ∘ c ∘ … не зависит от расстановки скобок, поэтому скобки можно опускать и говорить о таком выражении как о «композиции a, b, c и т. д.». Это свойство называется «ассоциативностью» оператора «∘».
• Существует особая переходная функция u, отображающая каждое состояние автомата в это же состояние. Она называется «единицей» оператора «∘», потому что, как для оператора умножения верно 1 · x = x · 1 = x, так и для «∘» верно u ∘ f = f ∘ u = f. В графической нотации рис. 4 такая функция выглядит как «лесенка» из горизонтальных линий.

Благодаря наличию этих двух свойств говорят, что переходные функции конечного автомата образуют моноид.

Более точно: говорят, что множество M, операция ⊗ и элемент u ∈ M (называемый «единицей» этой операции) образуют моноид, если выполняются вышеописанные два свойства.

Поскольку понятие моноида настолько простое и общее, неудивительно, что приглядевшись к «повседневным» объектам в программировании, можно увидеть десятки моноидов. Некоторые из них перечислены в табл. 4. С некоторыми применениями моноидов в программировании можно ознакомиться, например, в статье [25] (перевод [28]).

Некоторые моноиды из мира программирования

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

Например, на рис. 8 приведена верёвка из чисел, «знающая» свой минимум и максимум. Очевидно, такая верёвка может быть использована, например, для быстрого определения минимума и максимума любого подотрезка. В этой верёвке используется моноид с операцией композиции (m₁,M₁) ⊕ (m₂,M₂) = (min(m₁,m₂), max(M₁,M₂)) и единицей (∞,−∞).

---

Рис. 8: Пример верёвки из чисел с закэшированным минимумом и максимумом

---

5  Схема программы

Теперь сведём представленные алгоритмы воедино и рассмотрим схему устройства всей программы. Графически эта схема представлена на рис. 9 и далее. На рисунках использован способ представления знаний «концепт-карта (concept map)»; схемы выполнены с помощью инструмента IHMC CmapTools [3].

Рис. 9 «Общая схема программы»: Пользователь задает несколько регулярных выражений в виде строк, в результате компиляции которых (синтаксический разбор, а затем преобразование в автомат) получается объект типа PatternSet. Такой объект умеет «индексировать» обычные строки, давая объекты типа IndexedString. Они, в свою очередь, позволяют эффективно найти в себе все вхождения шаблонов, а также могут быть склеены или разрезаны (по монотонному предикату).

Рис. 10 «Верёвки и моноиды»: «Индексированные строки» реализованы при помощи верёвок (Rope). В программе реализованы только верёвки над символами, поскольку дальнейшее обобщение нецелесообразно в рамках текущей задачи и при реализации в рамках системы типов Java привело бы к большому количеству синтаксического мусора. Верёвка — это строка, знающая свою «меру» некоторого типа M. Мера вычисляется как сумма мер отдельных символов (Function<Character,M>) в некотором моноиде (Reducer). Верёвки реализованы с помощью особого вида сбалансированных деревьев, который будет описан далее в статье. При перебалансировках меры новых узлов складываются из мер старых при помощи заданного моноида. Для сопоставления с регулярными выражениями используется моноид комбинирования переходных функций для автомата, соответствующего заданной системе выражений (точнее, для двух автоматов — прямого и обратного, подробнее об этом будет написано далее в разделе «Поиск позиций вхождений»).

---

Рис. 9: Общая схема программы

---

---

Рис. 10: Схема программы: Верёвки и моноиды

---

---

Рис. 11: Схема программы: Конечные автоматы

---

---

Рис. 12: Схема программы: Связь детерминированных и недетерминированных автоматов

---

Рис. 11 «Конечные автоматы»: Автоматы реализованы таким образом, чтобы было удобно представлять и вычислять их «переходные функции». Автомат позволяет получить свою переходную функцию для любого заданного символа (операция расслоения), а переходная функция — это функция из типа состояний автомата в этот же тип. Состояние — это «черный ящик», про который известен лишь список «завершаемых» им шаблонов: если состояние автомата после просмотра некоторой строки завершает некоторые шаблоны, значит, в конце этой строки имеют место их вхождения. Переходные функции представлены не в виде произвольных функций, а в виде специфических объектов, допускающих эффективное вычисление композиции (уместна аналогия с тем, как в графических приложениях преобразования координат задаются не произвольными функциями, а числовыми матрицами, допускающими эффективное перемножение). Существование такого оператора композиции означает существование «моноида переходных функций» для каждого автомата. Этот моноид подставляется в верёвки, используемые в качестве «индексированных строк», как сказано ранее.

Рис. 12 «Связь детерминированных и недетерминированных автоматов»: Абстрактное понятие автомата используется в программе двумя способами: для детерминированных и для недетерминированных автоматов. Строго говоря, детерминированные автоматы в программе не нужны, они использовались лишь при тестировании, и стимулировали создание абстракции автомата, частным случаем которой являются оба перечисленных вида. У детерминированного автомата множество состояний — это множество чисел от 0 до некоторого N, соответственно переходные функции — это отображения из 0 … N в 0 … N. Они реализованы в виде одномерных int[]-массивов, и их композиция вычисляется очевидным образом с помощью перемножения перестановок. У недетерминированных же автоматов множество состояний состоит из подмножеств некоторого «базисного» набора состояний, а переходная функция недетерминированного автомата определяется тем, в какие базисные состояния она отображает каждое базисное состояние по отдельности, т. е. она задается отображением вида int → int[] (см., например, рис. 4). Это отображение для эффективности реализовано в виде булевой матрицы, у которой каждый элемент соответствует одному биту в общем массиве.

6  Design challenges

У читателя уже должно было сложиться представление о механизме работы программы, однако остается еще несколько «тёмных мест».

• Поиск позиций вхождений. Мы рассмотрели структуру данных «верёвка, кэширующая свою переходную функцию относительно автомата некоторого регулярного выражения». Однако имея строку и ее переходную функцию, можно лишь узнать, подходит ли она (или хоть какая-нибудь из ее подстрок) под регулярное выражение, но нельзя узнать, где именно расположено вхождение.
• Сразу несколько регулярных выражений. Рассмотренная структура данных позволяет сравнить строку лишь с одним регулярным выражением. Напрашивается значительно более практически полезное обобщение: сравнение сразу с большим количеством выражений (к этой задаче известны и другие подходы, например, [23]). Результатом такого сравнения является набор фактов вида «под k-е выражение подошел отрезок строки i..j».
• Реализация верёвок. Выбор разновидности верёвок, наиболее подходящей для реализации наших алгоритмов — также задача, достойная обсуждения. Встают вопросы о размере листовых «блоков», о способе балансировки и т. п.

6.1  Позиции вхождений

Во-первых, напомним, что речь идет не просто о сравнении строки с регулярным выражением R, а о поиске вхождения R в строке. Эту задачу можно отчасти переформулировать как сравнение строки с выражением «.*R.*», однако при этом получается лишь ответ на вопрос «есть ли в строке вхождение R?», но не на вопрос «где именно расположено вхождение».

С ответом на второй вопрос нам помогут две ключевых идеи.

• Заметим, что ответ на первый вопрос (о наличии вхождения) «монотонен» в смысле, указанном в разделе «Разрезание по монотонному условию». То есть, начиная с некоторого префикса строки, для всех дальнейших префиксов ответ также положителен. Именно там, где заканчивается первый из таких префиксов, заканчивается и первое вхождение R.
• Известно⁴, что имея регулярное выражение R или соответствующий ему автомат A, можно построить регулярное выражение R′ и автомат A′, распознающие зеркальные отражения строк, распознаваемых R и A, просто перевернув все последовательности внутри R, и, соответственно, все стрелки в A. Например: под выражение «a+(b|c*d)x*» подходит строка «abbdxx», а под выражение «x*(b|dc*)a+» — «xxdbba». Поэтому можно найти начало вхождения, запустив перевёрнутый автомат (автомат для перевёрнутого выражения) в обратную сторону строки от места, где вхождение заканчивается.

Таким образом, с помощью быстрой операции разрезания по монотонному предикату мы найдем конец первого вхождения (разрезание будет производиться по монотонному условию «переходная функция префикса отображает начальное состояние автомата в одно из терминальных» — при этом, как и в случае с суммой квадратов, в листовых блоках работы будет гораздо больше, чем во внутренних узлах), а затем с помощью перевёрнутого автомата найдем его начало. Если выражение таково, что подходящие под него строки обычно невелики, то можно просто запустить перевернутый автомат посимвольно, а если нет, то можно кэшировать в узлах верёвки переходную функцию как строки, так и ее зеркального отражения (легко убедиться, что при этом лишь тривиальным образом изменяется моноид, подставляемый с структуру данных «верёвка»). Тогда поиск начала вхождения также выразится через операцию разрезания по монотонному предикату (хотя при большом количестве вхождений посимвольный просмотр, скорее всего, будет эффективнее; возможно, оптимален какой-то гибридный подход).

На самом деле здесь имеется ряд осложнений, связанных с возможными перекрытиями вхождений различных элементов заданной системы регулярных выражений (или даже одного и того же выражения), однако общая идея сохраняется — с помощью одного разрезания находится конец вхождения, с помощью второго — начало. С подробностями можно ознакомиться в исходном коде (класс DFAMatcher).

6.2  Эффективные по памяти деревья

Как уже говорилось, при представлении строки сбалансированным деревом для обеспечения разумного потребления памяти нужно сопоставлять каждому листу дерева не один символ, а целый блок. Поэтому структура данных, предложенная в [24] («подвешенные деревья (finger trees)», описанные, например, в [4] и [15]), нам не подходит: в ней создается по узлу на каждый элемент последовательности⁵.

Остается выбрать один из видов сбалансированных деревьев, подходящий под требования. Основные требования же будут таковы:

• Возможность хранить в узле дерева сумму поддерева согласно некоторого моноида;
• Дешевизна обновления этой суммы при перебалансировках дерева (и малое число перебалансировок);
• Логарифмическая (от числа элементов) высота;
• Эффективные операции разрезания и склейки.

Одни из самых простых в реализации, но в то же время достаточно эффективных сбалансированных деревьев — это деревья постоянной высоты, к которым относятся, например, 2–3-деревья [7] и B-деревья [8] (часто используемые для индексов в СУБД). В таких деревьях длина пути от корня до всех листьев одинакова, поэтому (поскольку у каждого нелистового узла есть хотя бы два ребенка) они имеют логарифмическую высоту. Обычно они решают совершенно другой класс задач — задачи представления множеств и поиска в них — однако отлично подходят и для представления последовательностей (строк). Основная идея таких деревьев в том, что узлу разрешается иметь от K до 2K−1 детей (для некоторого значения K), и при этом большинство операций, такие как вставка, разрезание или склейка, не нарушают это свойство — а когда все-таки нарушают, то производится перебалансировка и переполнившийся узел разбивается на два, или, наоборот, два «иссякших» узла склеиваются в один.

Этой идеей мы и воспользуемся: будем использовать вариацию на тему 2–3 деревьев с блоками определенного размера в листьях, где размер блока может варьироваться от N до 2N−1, и все данные хранятся лишь в листьях, но не во внутренних узлах. На рис. 13 схематически показаны реализации всех операций с такими деревьями. Фактически, достаточно реализовать лишь две операции: разрезание и склейку; все остальные выражаются через них. При осознании картинок нужно помнить, что мы имеем дело с деревьями постоянной высоты. Также отметим, что инвариант размера блока может нарушаться, но только в том случае, если в дереве содержится менее N элементов — в этом случае оно представляется всего одним таким маленьким блоком.

---

Рис. 13: Операции над веревками

---

Один из самых важных аспектов нашей реализации этой структуры данных — ее «чистота»: операции над ней не изменяют существующий экземпляр, а формируют новый, то есть, являются функциями в математическом смысле. У такого подхода есть масса преимуществ (см. также статью [27]):

Исключительная простота реализации. Фактически, можно взять вышеизображенные графические схемы операций и один-в-один перенести их в код. За счет отказа от изменяемости код становится намного проще и его корректность (или, наоборот, некорректность) становится более очевидной, поскольку в нем пропадает измерение времени и чтобы понять механизм его работы, не нужно мысленно отслеживать последовательность операций⁶ — код представляет собой всего-навсего разбор случаев, где для каждой ветки декларируется «из таких-то входов получаются такие-то выходы». И, действительно, первая же компилирующаяся версия кода прошла все тесты после исправления пары глупых ошибок.

Удобство отладки. При отладке часто возникает необходимость «заблаговременно» посмотреть на результаты тех или иных выражений, чтобы понять, нужна ли их пошаговая отладка, или же их результат верен и ошибка где-то дальше⁷. Когда же эти выражения являются «чистыми» (т. е. не имеют побочных эффектов), такой подход вполне возможен. Если же побочные эффекты присутствуют (например, изменяется какая-то структура данных), то вычисление выражения в отладчике изменит внутреннее состояние программы и дальнейшая отладка будет бессмысленной.

Полная потокобезопасность. Хорошо известно, что большинство стандартных изменяемых структур данных не допускает одновременное чтение и изменение, и доступ к ним в многопоточной программе необходимо координировать. Нередко все же бывает желательно обеспечить возможность неблокирующего чтения, пусть и не самого «актуального» состояния структуры. Существуют хитроумные трюки, позволяющие этого добиться и для изменяемых структур (см., например, реализацию класса ConcurrentHashMap или ConcurrentSkipListMap в стандартной библиотеке Java — [21], [22]), однако для чистых структур никаких трюков не нужно — любой экземпляр такой структуры можно безопасно считывать, не боясь, что он будет одновременно изменен извне.

Высокая производительность и низкое потребление памяти в некоторых сценариях. Существуют ситуации, когда полезно после применения некоторой операции к структуре не терять и ее «первоначальную» версию (например, после выполнения склейки двух веревок не терять возможности использовать склеенные части по отдельности). Например, сюда относятся алгоритмы перебора с бэктрекингом, или генетические алгоритмы (например, если два генома можно скомбинировать несколькими разными способами, или хочется оставить в живых и сами геномы, и результат их комбинирования). Конечно, можно просто скопировать первоначальную структуру — но это может быть очень неэффективно, если структура велика. В случае же чистой структуры в копировании нет необходимости: получается выигрыш в производительности. Кроме того, как видно из рис. 13, при выполнении многих операций над веревками выделяется лишь мизерное (константное или логарифмическое) количество дополнительной памяти. На рис. 14 изображен граф объектов для двух веревок и их склейки. Как видно, большая часть памяти используется этими тремя объектами совместно, и в то же время каждый объект доступен по отдельности.

---

Рис. 14: Совместное использование памяти при склейке верёвок

---

7  Примеры и тесты

Приведем теперь пример использования получившейся библиотеки.

Программа выводит на экран:

  [0@(15,3), 1@(25,3)]

Это означает, что были найдены вхождения первого и второго шаблонов соответственно в позициях 15–17 и 25–27.

В этом коде задействованы следующие элементы API:

• RegexCompiler.compile — компиляция нескольких регулярных выражений в автомат, распознающий каждое из них.
• PatternSet.match — индексирование «обычной» строки, т. е. подготовка ее к поиску заданных шаблонов.
• IndexedString.append — склейка двух строк, индексированных одним и тем же набором шаблонов.
• IndexedString.getMatches — поиск в индексированной строке.

Теперь поговорим о производительности получившейся библиотеки.

Этот разговор получится непростым, поскольку на производительность библиотеки влияет большое количество факторов.

• Размер автомата, зависящий примерно линейно от количества и размера отдельных регулярных выражений: он влияет линейно и на производительность всех операций, и на потребление памяти (чем больше, тем хуже). В программе используется алгоритм минимизации недетерминированных автоматов, описанный в [18] (правда, он реализован крайне неэффективно, но на время сопоставления это не влияет), однако он обычно уменьшает размер автомата лишь на десятки процентов.
• Размер листовых блоков верёвок линейно влияет на производительность операций поиска (чем больше, тем хуже), практически не влияет на производительность склейки, и линейно влияет на потребляемый объем памяти (чем больше блоки, тем меньше потребляется памяти).
• Особенности конкретного регулярного выражения влияют на «форму» автомата, от которой зависит скорость операций над ним (чем выражение менее «ветвистое», тем лучше производительность, поскольку «ветвистые» выражения приводят к плотным матрицам для переходных функций, которые медленнее перемножаются в текущей реализации).
• Количество вхождений: в текущей реализации линейно влияет на время поиска (чем больше, тем хуже), однако здесь возможна оптимизация.

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

Ввиду вышесказанного рассмотрим лишь один тест и проанализируем его производительность. Возьмем набор регулярных выражений из задачи «regex-dna» с Language Shootout [1] и посмотрим на производительность операций поиска в сравнении со стандартным движком регулярных выражений языка Java (java.util.regex.Pattern [5]) при различных длинах входной ДНК-строки (но при постоянном общем количестве вхождений) и при различных размерах листового блока: 8, 16, 32, 64, 128, 256, 512 символов. Производительность резки отдельно не измеряется, поскольку резка используется при поиске, а производительность склейки не измеряется потому, что склейка выполняется настолько быстро (выделение нескольких объектов, плюс перемножение нескольких матриц), что трудно придумать сценарий, где ее производительность будет определяющим фактором.

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

В качестве входной строки возьмем случайную последовательность из символов «a,g,c,t» длины 50000 N (N будет варьироваться от 1 до 10), где каждые два последовательных символа различны (поэтому вхождения указанных шаблонов там встретиться не могут), и вставим в 100 ее случайно выбранных мест вхождения случайно выбранных строк из 8 × 2 × 3 = 48 строк, задаваемых указанным набором паттернов. Программа будет подсчитывать, сколько раз встречается каждый из паттернов.

На рис. 15 изображены результаты тестирования. Характеристики производительности каждой из двух программ (рассматриваемый движок и стандартный движок регулярных выражений Java) показаны в тех терминах, которые наиболее осмысленны для них: для нашего движка указана скорость индексирования (символов в секунду — поскольку длительность индексирования пропорциональна числу символов на входе) и скорость поиска (вхождений в секунду — поскольку скорость поиска пропорциональна числу вхождений). Для движка Java более осмыслена была бы характеристика «количество обрабатываемых символов в секунду»; она указана на одном графике со «скоростью индексирования» нашего движка, хотя это сравнение и не совсем корректно.

---

Рис. 15: Тестирование производительности

---

На графиках в левой части различные кривые соответствуют различным базовым размерам листового блока в структуре данных «верёвка», а жирная кривая соответствует использованию стандартного движка Java.

Наилучший ответ на вопрос «Когда наш движок лучше, чем стандартный движок Java» дает график зависимости скорости поиска от длины строки (слева вверху). Видно, что время поиска для движка Java пропорционально длине строки, а для нашего движка — числу вхождений. При малых базовых размерах блока (4–32 символа) наш движок существенно быстрее для больших строк.

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

Можно сделать вывод, что для больших строк с малым числом вхождений наш движок более эффективен, особенно если настроить его на малый размер листовых блоков. При этом, однако, резко возрастает потребление памяти — см. рис. 16: видно, что потребление памяти на листовой блок не зависит от размеров блока, однако, например, 4-байтовых блоков в строке в 128 раз больше, чем 512-байтовых, поэтому в 128 раз больше и потребление памяти.

---

Рис. 16: Издержки потребления памяти

---

Практически всё время расходуется на перемножение булевых матриц для пересчета переходных функций листовых блоков при разрезании (например, если базовый размер листового блока равен 512, то листовые блоки будут иметь размер от 512 до 1023 символов, и при резке такого блока надо будет умножать в среднем 768 матриц); практически вся «дополнительная» память — на хранение этих матриц.

Мы не рассмотрели зависимость производительности от сложности регулярных выражений и от числа вхождений. Полное рассмотрение вопросов производительности заняло бы слишком много места; читателям предлагается самим «поиграться» с библиотекой.

Кроме того, индексирование строки можно тривиальным образом распараллелить или даже распределить по нескольким машинам с практически линейной масштабируемостью (строка бьется на несколько частей, они параллельно индексируются по отдельности, а затем склеиваются). Эта возможность в текущей версии программы никак не задействована, и сравнение параллельной реализации нашего движка с последовательной реализацией движка Java было бы некорректным, однако на практике распараллеливание почти наверняка будет оправдано.

8  Что дальше?

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

• В программе вовсе не уделено внимание таким вопросам, как, например, «жадность» сопоставления. Неясно, какие из распространенных решений (POSIX, Perl, …) поддаются эффективной реализации в рамках автоматного подхода.
• Не поддерживаются «захватывающие группы». В [11] описано, как можно реализовать их поддержку в движке на основе автоматного подхода, однако предложенный алгоритм не сочетается с подходом настоящей статьи.
• Для умножения булевских матриц (используемого при комбинировании переходных функций) используется хорошо оптимизированный, но довольно наивный алгоритм; вероятно, для некоторых сценариев использования были бы более эффективны другие алгоритмы (например, использующие разреженные представления матриц).
• При сопоставлении с помощью разрезания выполняется довольно много лишней работы: например, при обратном разрезании (выполняемом для поиска начала вхождения) нет никакой необходимости вычислять переходную функцию для полученных двух строк. Исправление этого недостатка позволило бы увеличить производительность на несколько десятков процентов.
• Время сопоставления пропорционально количеству вхождений, размеру листового блока и размеру автомата. Это делает программу бесполезной в качестве инкрементального лексера, поскольку в этой ситуации количество вхождений очень велико. Один из возможных способов исправления этой проблемы — модификация алгоритма разрезания строки на две части по монотонному условию, при которой разрезание будет производиться сразу на много частей, например, по возрастанию монотонной целочисленной функции.

9  Заключение

Итак, перед нами библиотека, осуществляющая инкрементальное сопоставление строк с набором регулярных выражений при помощи сбалансированных деревьев и моноидов. Библиотека очень эффективна в ситуации «длинные строки, не очень много регулярных выражений, мало вхождений, частый инкрементальный пересчет, много свободной памяти» и весьма неэффективна в остальных случаях. Трудно сказать, для каких еще ситуаций ее можно сделать эффективной — можно ли, например, все-таки сделать из нее высокопроизводительный инкрементальный лексер, и можно ли, вообще, признать этот эксперимент однозначно удачным с алгоритмической точки зрения. Автор, во всяком случае, выражает надежду, что рассмотренные техники стимулируют полет мысли у читателей-алгоритмистов и пригодятся им в других задачах.

Однако можно точно сказать, что проведенная разработка — интересный и удачный опыт скрещивания миров функционального и императивного программирования.

Рассмотрим, какие техники, идеи и «обычаи» из мира функционального программирования были использованы, и насколько удачно они сочетались с императивной природой целевого языка.

• Главная структура данных — верёвка — является «чистой» (неизменяемой). Это решение прекрасно легло на язык Java и кардинально упростило разработку и отладку, несмотря на отсутствие таких языковых средств, как алгебраические типы или сопоставление с образцом.
• Вообще, практически весь API библиотеки — «чистый» (т. е. не обладает побочными эффектами). Но отказ от изменяемого состояния производится лишь на «архитектурном» уровне, а внутри реализаций этого API изменяемое состояние используется достаточно обильно — в целях повышения производительности (например, перемножение булевских матриц), а кое-где, как ни парадоксально, в целях упрощения и сокращения кода (например, построение недетерминированного конечного автомата из регулярного выражения). За деталями предлагается обратиться непосредственно в исходный код. В целом это означает, что «чистый» подход к программированию прекрасно ложится и на императивные языки, не мешая использованию изменяемого состояния в тех задачах, где оно полезно.
• Вопреки распространенному мифу «чистое программирование не может быть эффективным и приводит к излишнему потреблению памяти», единственное узкое место производительности находится в императивном алгоритме перемножения переходных функций, а память расходуется на хранение этих функций для узлов верёвки в виде битовых масок. По-видимому, никакой связи издержек с «чистой» природой алгоритмов в данном случае нет⁸.
• В основе всей программы лежит манипулирование функциями высшего порядка: например, верёвка параметризована моноидом, а самая важная ее операция — разбиение по предикату. Поскольку Java не поддерживает компактный синтаксис определения функций (например, лямбда-выражения) и вывод типов, то использование этих сущностей сопряжено с большим количеством синтаксического мусора (особенно это касается типов в объявлениях). Однако использование их хоть и крайне важно для всей программы, но сосредоточено в сравнительно небольшом количестве кода, изолированном от конечных клиентов библиотеки. Впрочем, если бы система типов Java была чуть мощней и чуть лаконичней, можно было бы без ущерба для производительности обобщить библиотеку до поиска не только в строках, но и в произвольных последовательностях.

Автор благодарит Дмитрия Демещука, Юлию Астахову, Алексея Отта, Сергея Пластинкина и других рецензентов за предоставленные замечания.

Проект опубликован на GitHub: http://github.com/jkff/ire⁹.

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

[1]

Computer language benchmarks game: regex-dna. http://shootout.alioth.debian.org/u32q/performance.php?test=regexdna.

[2]

Cyk algorithm. Статья в Wikipedia, http://en.wikipedia.org/wiki/CYK_algorithm.

[3]

IHMC CmapTools. http://cmap.ihmc.us/.

[4]

Monoids and finger trees. http://apfelmus.nfshost.com/monoid-fingertree.html.

[5]

Документация к классу java.util.regex.pattern. http://download.oracle.com/javase/1.5.0/docs/api/java/util/regex/Pattern.html.

[6]

Документация к модулю Data.Sequence. http://www.haskell.org/ghc/docs/6.12.2/html/libraries/containers-0.3.0.0/Data-Sequence.html.

[7]

Alfred V. Aho and John E. Hopcroft. The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1974.

[8]

Rudolf Bayer and E. McCreight. Organization and maintenance of large ordered indexes. pages 245–262, 2002.

[9]

Hans-J. Boehm, Russ Atkinson, and Michael Plass. Ropes: an alternative to strings. Software — Practice and Experience, 25(12):1315–1330, 1995.

[10]

Russ Cox. Re2: an efficient, principled regular expression library. Проект на Google Code, http://code.google.com/p/re2/.

[11]

Russ Cox. Regular expression matching in the wild. http://swtch.com/~rsc/regexp/regexp3.html.

[12]

Russ Cox. Regular expression matching can be simple and fast (but is slow in java, perl, php, python, ruby, …). http://swtch.com/~rsc/regexp/regexp1.html, 2007.

[13]

Jeffrey E. F. Friedl. Mastering Regular Expressions. O’Reilly & Associates, Inc., Sebastopol, CA, USA, 2 edition, 2002.

[14]

Dick Grune and Ceriel J.H. Jacobs. Parsing techniques — a practical guide. Веб-сайт книги, http://www.few.vu.nl/~dick/PTAPG.html.

[15]

Ralf Hinze and Ross Paterson. Finger trees: a simple general-purpose data structure. J. Funct. Program., 16(2):197–217, 2006.

[16]

John H. Holland. Adaptation in natural and artificial systems. MIT Press, Cambridge, MA, USA, 1992.

[17]

John E. Hopcroft. An n log n algorithm for minimizing the states in a finite automaton. In Z. Kohavi, editor, The Theory of Machines and Computations, pages 189–196. Academic Press, 1971.

[18]

Lucian Ilie and Gonzalo Navarro. On NFA reductions. In THEORY IS FOREVER, pages 112–124. Springer, 2004.

[19]

Christopher Kuklewicz. regex-tdfa. Пакет на hackage, http://hackage.haskell.org/package/regex-tdfa.

[20]

Ville Laurikari. TRE: The free and portable approximate regex matching library. http://laurikari.net/tre/.

[21]

Doug Lea. Реализация класса java.util.concurrent.concurrenthashmap. http://www.docjar.com/html/api/java/util/concurrent/ConcurrentHashMap.java.html.

[22]

Doug Lea. Реализация класса java.util.concurrent.concurrentskiplistmap. http://www.docjar.com/html/api/java/util/concurrent/ConcurrentSkipListMap.java.html.

[23]

Wei Lin, Yi Tang, Bin Liu, Derek Pao, and XiaoFei Wang. Compact dfa structure for multiple regular expressions matching. In ICC’09: Proceedings of the 2009 IEEE international conference on Communications, pages 899–903, Piscataway, NJ, USA, 2009. IEEE Press.

[24]

Dan Piponi. Fast incremental regular expression matching with monoids. Блог-пост, http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html.

[25]

Dan Piponi. Haskell monoids and their uses. Пост в блоге, http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html.

[26]

Thomas Wilke, Frank Huch, and Sebastian Fischer. Weighted regexp matching. http://sebfisch.github.com/haskell-regexp/.

[27]

Кирпичёв Е. Изменяемое состояние: опасности и борьба с ними. Практика функционального программирования, 1, July 2009.

[28]

Пипони, Дэн. Моноиды в haskell и их использование (перевод Кирилла Заборского). Практика функционального программирования, 1, July 2009.

[29]

Советов, П. Алгоритм Бржозовского для минимизации конечного автомата. http://sovietov.com/txt/minfa/minfa.html.

1

Дэн Пипони (Dan Piponi) — специалист по графическим спецэффектам, участвовал в создании всех трех «Матриц», «Star Trek» и многих других фильмов (http://www.imdb.com/name/nm0685004/, http://homepage.mac.com/sigfpe/).

2

Насколько известно автору, общепринятого перевода этого термина на русский язык не существует. Данный перевод выбран исходя из особенностей устройства этой структуры данных.

3

Как отметил один из рецензентов, схожий подход используется в алгоритме разбора контекстно-свободных грамматик Кока-Янгера-Касами [2], который, кроме того, так же как и наш алгоритм, допускает параллельную реализацию — она описана, например, в [14].

4

Эта идея почерпнута из статьи Расселла Кокса [11] и используется в его движке re2.

5

Похожая структура используется для похожей цели в модуле «Data.Sequence» [6] из стандартной библиотеки языка Haskell.

6

Читателю предлагается для сравнения ознакомиться, например, с какой-либо реализацией перебалансировки в изменяемых красно-черных деревьях.

7

Впрочем, ни для кого не секрет, что Настоящие Программисты не используют отладчик — что ж, они не смогут оценить данное преимущество.

8

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

9

ire — 1) incremental regular expressions, 2) гнев, ярость (англ.)

Этот документ был получен из L^AT_EX при помощи H^EV^EA

© 2009—2011  «Практика функционального программирования»ISSN 2075-8456