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


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




[259]

Р[т] ф T[s + то]) и не встречается нигде в образце (представьте себе, что вы ищете подстроку ат в строке Ъп). В этом случае сдвиг s можно сразу увеличить на то: любой меньший сдвиг заведомо не подойдет, так как стоп-символ в тексте окажется напротив какого-то символа из образца. Если этот наиболее удачный случай повторяется постоянно, то при поиске подстроки мы просмотрим всего лишь 1/га часть текста (вот как полезно сравнивать справа налево!).

В общем случае эвристика стоп-символа (bad-character heuristic) работает так. Предположим, что при сравнении справа налево мы наткнулись на первое несовпадение: P[j] ф T[s + j], где 1 j то. Пусть к - номер самого правого вхождения символа T[s + j] в образец Р (если этот символ вообще не появляется в образце, считаем к равным 0). Мы утверждаем, что можно увеличить s на j - к, не упустив ни одного допустимого сдвига. В самом деле, если к = 0, то стоп-символ T[s + j] вообще не встречается в образце Р, так что можно сразу сдвинуть образец на j - к = j позиций вправо (рис. 34.12 (а)); если 0 < к < j, то образец можно сдвинуть на j - к позиций вправо, так как при меньших сдвигах стоп-символ в тексте не совпадёт с соответствующим символом образца (рис. 34.12 (б)). Наконец, если к > j, то эвристика предлагает сдвигать образец не вправо, а влево; алгоритм Бойера-Мура эту рекомендацию игнорирует, поскольку эвристика безопасного суффикса всегда предлагает ненулевой сдвиг вправо.

Чтобы применять эвристику стоп-символа, полезно для каждого возможного стоп-символа а £ £ вычислить значение к. Это делается простой процедурой Compute-Last-Occurrence-Function («найти последнее вхождение»), которая для каждого а £ £ вычисляет А[а] - номер крайнего правого вхождения а в Р, или нуль, если явРне входит. В этих обозначениях приращение сдвига, диктуемое эвристикой стоп-символа, есть j - \[T[s+j]], как и написано в строке 13 алгоритма Boyer-Moore-Matcher.

Compute-Last-Occurrence-Function(P,m,\Sigma)

1for (для) каждого символа a \in \Sigma

2do \lambda[a] \gets О

3for j \gets 1 to m

4do \lambda[P[j] ] \gets j

5return \lambda

Время работы процедуры Compute-Last-Occurrence-Function есть 0(£ + то).

34.5.2. Эвристика безопасного суффикса

Если Q и R - строки, будем говорить, что они сравнимы (обозначение: Q ~ R), если одна из них является суффиксом другой.


Рис. 34.12, занимающий целую страницу. Перевод надписи в рисунке: bad character - стоп-символ.

Подпись:

Рис. 34.12. Эвристика стоп-символа: три случая, (а) Стоп-символ в образце не встречается, так что образец можно сдвинуть на j = 11 позиций вправо, оставив стоп-символ позади, (б) Крайнее правое вхождение стоп-символа в образец - в позиции к < j. Образец можно сдвинуть вправо на j - к - так, чтобы стоп-символы в тексте и образце оказались друг под другом (в примере j = 10, к = 6, стоп-символ есть i, сдвиг на 10 - 6 = 4). (в) Стоп-символ встречается в образце в позиции к > j (в примере стоп-символ есть е, j = 10, к = 12). Эвристика предлагает сдвиг влево, но алгоритм это предложение игнорирует.


Если выровнять две сравнимые строки по правому краю, то символы, расположенные один под другим, будут совпадать. Отношение ~ симметрично: если Q ~ R, то и R ~ Q. Из леммы 34.1 следует, что

если Q □ R и S □ R, то Q ~ S.(34.7)

Эвристика безопасного суффикса (good-suffix heuristic) состоит в следующем: если P[j] ф T[s + j], где j < то (и число j - наибольшее с таким свойством), то мы можем безбоязненно увеличить сдвиг на

y[j] = т - max{ к : 0 к < то и P[j + l..m] ~ }.

Иными словами, y[j] - наименьшее расстояние, на которое мы можем сдвинуть образец без того, чтобы какой-то из символов, входящих в «безопасный суффикс» T[s + j + l..s + то] оказался напротив не совпадающего с ним символа из образца. Поскольку строка P[j + 1..то] заведомо сравнима с пустой строкой Ро, число корректно определено для всех j. Стоит также заметить, что > О для всех j, так что на каждом шаге алгоритма Бойера - Мура образец будет сдвигаться вправо хотя бы на одну позицию. Мы будем называть у функцией безопасного суффикса (good-suffix function), ассоциированной со строкой Р.

Посмотрим, как можно вычислить функцию безопасного суффикса у. Для начала заметим, что Рж[т] □ Р, откуда, в силу (34.7), имеем P[j + 1..то] ~ Рп[т] для любого j. Следовательно, максимум в правой части определения величины y[j] не меньше 7г[то], так что y[j] то - 7г[то] для всех j.

Стало быть, можно переписать наше определение у так:

y[j] = то - max{ k : ir[m] к < то и P[j + 1..то] ~ Р }.

Условие P[j + 1..то] ~ Pk может выполняться в двух случаях: либо когда P[j + 1..то] □ Pk, либо когда Pk □ P[j + 1..то]. Во втором случае, однако, имеем Pk □ Рт, откуда к 7г[то] и потому к = тг[т]. Поэтому определение у можно переписать еще и так:

y[j] = то - max ({тг[то]} U { к : тг[т] < к < то и P[j + 1..то] □ Pk })

Второе из этих множеств может оказаться пустым. В самом деле, мы ищем префикс Pk образца Р, в котором P[j + 1..то] является суффиксом; другими словами, мы ищем в образце участок равный его суффиксу P[j + 1..то] и расположенный левее (к < то)

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



[стр.Начало] [стр.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]