длины. Нетрудно понять, что все это можно уложить в требуемое
число действий (хотя константа зависит от числа букв в алфави-
те). Относящиеся к этому подробности см. в главе об алгоритмах
на графах.
Можно поинтересоваться, какие свойства слов можно распозна-
вать с помощью конечных автоматов. Оказывается, что существует
просто описываемый класс образцов, задающий все такие свойства -
класс регулярных выражений.
Определение. Пусть фикисирован конечный алфавит Г, не со-
держащий символов 'l', 'e', '(', ')', '*' и '|' (они будут ис-
пользоваться для построения регулярных выражений и не должны пе-
ремешиваться с буквами). Регулярные выражения строятся по таким
правилам:
(а) буква алфавита Г - регулярное выражение;
(б) символы 'l', 'e' - регулярные выражения;
(в) если A,B,C,..,E - регулярные выражения, то (ABC...E) -
регулярное выражение.
(г) если A,B,C,..,E - регулярные выражения, то
(A|B|C|...|E) - регулярное выражение.
(д) если A - регулярное выражение, то A* - регулярное выра-
жение.
Каждое регулярное выражение задает множество слов в алфавите Г
по таким правилам:
(а) букве соответствует одноэлементное множество, состоящее
из однобуквенного слова, состоящего из этой буквы;
(б) символу 'e' соответствует пустое множество, а символу
'l' - одноэлементное множество, единственным элементом
которого является пустое слово;
(в) регулярному выражению (ABC...E) соответствует множество
всех слов, которые можно получить, если к слову из A
приписать слово из B, затем из C,..., затем из E ("кон-
катенация" множеств);
(г) регулярному выражению (A|B|C|...|E) соответствует
объединение множеств, соответствующих выражениям
A,B,C,..,E;
(д) регулярному выражению A* соответствует "итерация" мно-
жества, соответствующего выражению A, то есть множество
всех слов, которые можно так разрезать на куски, что
каждый кусок принадлежит множеству, соответствующему
выражению A. (В частности, пустое слово всегда содер-
жится в A*.)
Примеры
Выражение Множество
(a|b)* все слова из букв a и b
(aa)* все слова из четного числа букв a
(l|a|b|aa|ab|ba|bb) любое слово из не более чем 2 букв a,b
10.7.5. Написать регулярное выражение, которому соот-
ветствует множество всех слов из букв a и b, в которых число
букв a четно.
Решение. Выражение b* задает все слова без a, а выражение
(b* a b* a b*)
- все слова ровно с двумя буквами a. Остается объединить эти
множества, а потом применить итерацию:
((b* a b* a b*) | b*)*
10.7.6. Написать регулярное выражение, которое задает мно-
жество всех слов из букв a,b,c, в которых слово bac является
подсловом.
Решение. ((a|b|c)* bac (a|b|c)*)
Теперь задачу о поиске образца в слове можно переформулиро-
вать так: проверить, принадлежит ли слово множеству, соот-
ветствующему данному регулярному выражению.
10.7.7. Какие выражения соответствуют образцам a?b и ab*cd,
рассмотренным ранее? (В образце '*' используется не в том смыс-
ле, что в регулярных выражениях!) Предполается, что алфавит со-
держит буквы a,b,c,d,e.
Решение. ((a|b|c|d|e)* a (a|b|c|d|e) b (a|b|c|d|e)*) и
((a|b|c|d|e)* ab (a|b|c|d|e)* cd (a|b|c|d|e)*).
10.7.8. Доказать, что для всякого регулярного выражения
можно построить конечный автомат, который распознает соот-
ветствующее этому выражению множество слов.
Решение. Нам потребуется новое понятие - понятие источника
(или недетерминированного конечного автомата). Представим себе
ориентированный граф - картинку из нескольких точек (вершин) и
некоторых стрелок, соединяющих эти точки (ребер). Пусть на неко-
торых ребрах написаны буквы (не обязательно на всех). Пусть так-
же среди вершин выбраны две - начальная Н и конечная К. Такая
картинка называется источником.
Будем двигаться различными способами из Н в К, читая буквы
по дороге (на тех стрелках, где они есть). Каждому пути из Н в
К, таким образом, соответствует некоторое слово. А источнику в
целом соответствует множество слов - тех слов, которые можно
прочесть на путях из Н в К.
Замечание. Если нарисовать состояния конечного автомата в
виде точек, а переходы при чтении букв изобразить в виде стре-
лок, то станет ясно, что конечный автомат - это частный случай
источника.
Мы будем строить конечный автомат по регулярному выражению
в два приема. Сначала мы построим источник, которому соот-
ветствует то же самое множество слов. Затем для произвольного
источника построим автомат, который проверяет, принадлежит ли
слово соответствующему множеству.
10.7.9. По регулярному выражению построить источник, зада-
ющий то же множество.
Решение. Индукция по построению регулярного выражения. Бук-
вам соответствуют графы из одной стрелки. Объединение реализует-
ся так:
|---------|
---->|*Н1 К1*|->---
/ |---------| \
/ |---------| \
* --------->|*Н2 К2*|--->-----* К
Н \ |---------| /
\ |---------| /
--->|*Н3 К3*|--->--
|---------|
Нарисована картинка для объединения трех множеств, прямо-
угольники - это источники, соответствующие им; указаны начальные
и конечные вершины. На новых стрелках (их 6) букв не написано.
Конкатенации соответствует картинка
|--------| |--------| |--------|
Н*--->|*Н1 К1*|---->----|*Н2 К2*| ---->----|*Н3 К3*|-->--*К
|--------| |--------| |--------|
Наконец, итерации соответствует картинка
Н*--------->----------*----------->----------*К
/ \
/ \
| |
V ^
| |
-------------
| *Н1 К1* |
-------------
10.7.10. Дан источник. Построить конечный автомат, проверя-
ющий, принадлежит ли входное слово множеству, соответствующему
источнику (т.е. можно ли прочесть это слово, идя из Н в К).
Решение. Состояниями автомата будут множества вершин источ-
ника. Именно, прочтя некоторое начало X входного слова, мы будем
помнить множество всех вершин источника, в которые можно пройти
из начальной, прочитав на пути слово X.
Оказывается, что регулярные выражения, автоматы и источники
распознают одни и те же множества. Чтобы убедиться в этом, нам
осталось решить такую задачу:
10.7.11. Дан источник. Построить регулярное выражение, за-
дающее то же множество, что и этот источник.
Решение. (Сообщено участниками просеминара по логике.)
Пусть источник имеет вершины 1..k. Будем считать, что 1 - это
начало, а k - конец. Через D[i,j, s] обозначим множество всех
слов, которые можно прочесть на пути из i в j, если в качестве
промежуточных пунктов разрешается использовать только вершины
1,...,s. Согласно определению, источнику соответствует множество
D[1,k,k].
Индукцией по s будем доказывать регулярность всех множеств
D[i,j,s] при всех i и j. При s=0 это очевидно (промежуточные
вершины запрещены, поэтому каждое из множеств состоит только из
букв).
Из чего состоит множество D[i,j,s+1]? Отметим на пути мо-
менты, в которых он заходит в s+1-ую вершину. При этом путь раз-
бивается на части, каждая из которых уже не заходит в нее. По-
этому легко сообразить, что
D[i,j,s+1] = (D[i,j,s]| (D[i,s+1,s] D[s+1,s+1,s]* D[s+1,j,s]))
(вольность записи: мы используем для операций над множествами
обозначения как для регулярных выражений). Остается воспользо-
ваться предположением индукции.
10.7.12. Где еще используется то же самое рассуждение?
Ответ. В алгоритме Флойда вычисления цены кратчайшего пути,
см. главу 9 (Некоторые алгоритмы на графах).
10.7.13. Доказать, что класс множеств, задаваемых регуляр-
ными выражениями, не изменился бы, если бы мы разрешили ис-
пользовать не только объединение, но и отрицание (а следова-
тельно, и пересечение - оно выражается через объединение и отри-
цание).
Решение. Для автоматов переход к отрицанию очевиден.
Замечание. На практике важную роль играет число состояний
автомата. Оказывается, что тут все не так просто, и переход о
источника к автомату требует экспоненциального роста числа сос-
тояний. Подробное рассмотрение связанных с этим теоретических и
практических вопросов - дело особое.
Глава 11. Представление множеств. Хеширование.
11.1. Хеширование с открытой адресацией
В предыдущей главе было несколько представлений для мно-
жеств, элементами которых являются целые числа произвольной ве-
личины. Однако в любом из них хотя бы одна из операций проверки
принадлежности, добавления и удаления элемента требовала коли-
чества действий, пропорционального числу элементов множества. На
практике это бывает слишком много. Существуют способы, позволя-
ющие получить для всех трех упомянутых операций оценку C*log n.
Один из таких способов мы рассмотрим в следующей главе. В этой
главе мы разберем способ, которые хотя и приводит к C*n действи-
ям в худшем случае, но зато "в среднем" требует значительно
меньшего их числа. (Мы не будем уточнять слов "в среднем", хотя
это и можно сделать.) Этот способ называется хешированием.
Пусть нам необходимо представлять множества элементов типа
T, причем число элементов заведомо меньше n. Выберем некоторую
функцию h, определенную на значениях типа T и принимающую значе-
ния 0..(n-1). Было бы хорошо, чтобы эта функция принимала на
элементах будущего множества по возможности более разнообразные
значения. Худший случай - это когда ее значения на всех элемен-
тах хранимого множества одинаковы. Эту функцию будем называть
хеш-функцией.
Введем два массива
val: array [0..n-1] of T;
used: array [0..n-1] of boolean;
(мы позволяем себе писать n-1 в качестве границы в определении
типа, хотя в паскале это не разрешается). В этих массивах будут
храниться элементы множества: оно равно множеству всех val [i]
для тех i, для которых used [i], причем все эти val [i] различ-
ны. По возможности мы будем хранить элемент t на месте h(t),
считая это место "исконным" для элемента t. Однако может слу-
читься так, что новый элемент, который мы хотим добавить, пре-
тендует на уже занятое место (для которого used истинно). В этом
случае мы отыщем ближайшее справа свободное место и запишем эле-
мент туда. ("Справа" значит "в сторону увеличения индексов";
дойдя до края, мы перескакиваем в начало.) По предположению,
число элементов всегда меньше n, так что пустые места гарантиро-
ванно будут.
Формально говоря, в любой момент должно соблюдаться такое
требование: для любого элемента множества участок справа от его
исконного места до его фактического места полностью заполнен.
Благодаря этому проверка принадлежности заданного элемента
t осуществляется легко: встав на h(t), двигаемся направо, пока
не дойдем до пустого места или до элемента t. В первом случае
элемент t отсутствует в множестве, во втором присутствует. Если
элемент отсутствует, то его можно добавить на найденное пустое
место. Если присутствует, то можно его удалить (положив used =
false).
11.1.1. В предыдущем абзаце есть ошибка. Найдите ее и
исправьте.
Решение. Дело в том, что при удалении требуемое свойство
