Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[254]

заданным содержимым (т.е. получающийся из образца параллельным переносом).

34-2.4 У Ани на компьютере есть га-битовый файл А = (an i, ап 2, , ао), а У Бори - га -битовый файл В = (bn-i, Ьп 2, ,Ьо). Они хотят проверить, идентичны ли эти файлы, не пересылая их друг другу, следующим образом. Выбирается простое число q > 1000га и случайное целое число х £ {0,1,..., q - 1}. После этого Аня вычисляет выражение

А(х) = I ajX% J mod q,

\г=0 /

а Боря вычисляет аналогичное выражение В(х). Покажите, что, если А ф В, существует лишь один шанс из тысячи, что А(х) = В(х) (и уж конечно А(х) = В(х), если А = В). (Указание: воспользуйтесь упражнением 33.4-4).

34.3. Поиск подстрок с помощью конечных автоматов

Многие алгоритмы для поиска подстрок начинают с того, что строят конечный автомат, который находит в тексте Г все вхождения образца Р. В этом разделе мы опишем, как можно построить такой автомат. Сам по себе поиск подстроки с помощью конечного автомата весьма эффективен: каждый символ поступает на вход конечного автомата только единожды, а обработка каждого символа занимает ограниченное время, так что общее время работы есть ©(га) - после того, однако, как автомат построен! К сожалению, время на построение конечного автомата может быть велико, если велик алфавит У (в разд. 34.4 мы обсудим остроумный способ обойти эту трудность).

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

34.3.1. Конечные автоматы

По определению, конечный автомат (finite automaton) - это пятерка М = (Q, до, А, У, S), где:

•Q - конечное множество состояний (states);

•Qo & Q - начальное состояние (start state);

•ACQ - конечное множество допускающих состояний (accepting states);


Рис. 34.5. Переводы слов в рисунке: input - вход, state - состояние.

Подпись:

Конечный автомат со множеством состояний Q = {0,1}, начальным состоянием д0 = 0 и входным алфавитом £ = {а, b}. (а) Таблица значений функции перехода S. (б) Функция перехода в виде диаграммы. Состояние 1 - единственное допускающее состояние (чёрное). Стрелками показаны переходы. Например стрелка из состояния 1 в состояние 0, помеченная буквой Ь, означает, что 5(1,Ъ) = 0. Этот автомат допускает строки, оканчивающиеся на нечётное число букв а (точнее говоря, строки вида ya.k, где строка у пуста или оканчивается на Ь, а число к нечётно). Например, для входной строки abaaa последовательность состояний (включая исходное) будет (0,1, 0,1, 0,1), и эта строка допускается; для входной строки abbaa последовательность состояний будет (0,1, 0, 0,1, 0), и эта строка отвергается.

•£ - конечный входной алфавит (input alphabet);

•6 - функция из Q X £ в Q, называемая функцией перехода (transition function) автомата.

Первоначально конечный автомат находится в состоянии до! затем он по очереди читает символы из входной строки. Находясь в состоянии q и читая символ а, автомат переходит в состояние S(q, а). Если автомат находится в состоянии q £ А, говорят, что он допускает (accepts) прочитанную часть входной строки; если же q £ А, то прочитанная часть строки отвергнута (is rejected). На рис. 34.5 показан пример простого автомата с двумя состояниями.

С конечным автоматом М связана функция (р: £* -> Q, называемая функцией конечного состояния (final-state function), определяемая следующим образом: <~p(w) есть состояние, в которое придёт автомат (из начального состояния), прочитав строку w. Автомат допускает строку w тогда и только тогда, когда <~p(w) £ А. Функцию Lp можно определить рекуррентно:

34.3.2. Автоматы для поиска подстрок

Для каждого образца Р можно построить конечный автомат, ищущий этот образец в тексте (см. рис. 34.6, где изображен автомат, соответствующий образцу Р = ababaca). Зафиксируем до конца этого раздела строку-образец Р.

Первым шагом в построении автомата, соответствующего строке-образцу Р[1..га], будет построение по Р вспомогательной

для любых w £ £* и а £ £.


функции а: £* -> {0,1,..., то}, называемой суффикс-функцией (suffix function). По определению, а сопоставляет строке ж длину максимального суффикса ж, являющегося префиксом Р:

Поскольку Р0 = е является суффиксом любой строки, а определена на всем £*. Пример: если Р = ab, то а(е) = 0, <т(ссаса) = 1, (т(ссаЬ) = 2. Если длина Р равна то, то <т(ж) = то тогда и только тогда, когда Р - суффикс ж. Если ж □ у, то и (ж) <?(у)-

Теперь определим конечный автомат, соответствующий образцу Р[1..то], следующим образом:

•Множество состояний есть Q = { 0,1,..., то }. Начальное состояние до = 0, единственное допускающее состояние есть то.

•Функция перехода 6 определена следующей формулой (д - состояние, a G £ - символ):

Объясним, откуда берётся формула (34.3). Мы хотим сконструировать автомат таким образом, чтобы при его действии на строку Г соотношение

являлось инвариантом (тогда равенство <~р(Т{) = то будет равносильно тому, что Р входит в Г со сдвигом г - тп, и автомат тем самым найдёт все допустимые сдвиги). Но в этом случае вычисление перехода по формуле (34.3) необходимо для поддержания истинности инварианта (см. теорему 34.4 ниже).

Например, в автомате рис. 34.6, имеем 5(5, b) = 4: если g = 5, прочитанная часть входа кончается на ababa, и после добавления входного символа b наибольший суффикс прочитанной части, являющийся префиксом Р, будет равен abab.

Запишем действие конечного автомата, ищущего подстроку Р длины то в данном тексте Г, в виде программы (8 обозначает функцию перехода):

Finite-Automaton-Matcher(Т,\deltа,т)

1п \gets length[Т]

2q \gets О

3for i \gets 1 to n

4do q \gets \delta(q, T[i])

5if q=m

6then s \gets i-m

7print Образец входит со сдвигом s

Поскольку эта программа обрабатывает каждый символ из текста Г по разу, время её работы есть 0(п). Однако следует учесть

а (ж) = max{ к : Рк □ ж }.

(34.3)

(34.4)



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]