Случайный афоризм
Настоящий писатель, каким мы его мыслим, всегда во власти своего времени, он его слуга, его крепостной, его последний раб. Элиас Канетти
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

ранее для каждого конца Z нашего образца. Как  говорят  знатоки,
все  это  (вычисление  таблицы  сдвигов и использовани ее) можно
уложэить в C*(m+n) действий.

     10.6. Алгоритм Рабина

     Этот алгоритм основан на простой идее. Представим себе, что
в слове длины m мы ищем образем длины n. Вырежем окошечко разме-
ра  n  и будем двигать его по входному слову. Нас интересует, не
совпадает ли слово в окошечке с заданным образцом. Сравнивать по
буквам долго. Вместо этого фиксируем некоторую функцию на словах
длины n. Если значения этой функции на слове в окошечке и на об-
разце различны, то совпадения нет. Только если значения одинако-
вы, нужно проверять совпадение по буквам.

     Что мы выигрываем при таком подходе? Казалось бы, ничего  -
ведь  чтобы  вычислить значение функции на слове в окошечке, все
равно нужно прочесть все буквы этого слова. Так уж лучше их сра-
зу сравнить с образцом. Тем не менее выигрыш возможен, и вот  за
счет  чего.  При  сдвиге окошечка слово не меняется полностью, а
лишь добавляется буква в конце и убирается в начале. Хорошо  бы,
чтобы по этим данным можно было бы легко рассчитать, как меняет-
ся функция.

     10.6.1. Привести пример удобной для вычисления функции.

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

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

     10.6.2. Привести пример семейства удобных функций.

     Решение.  Выберем  некоторое  число  p (желательно простое,
смотри далее) и некоторый вычет x по модулю p. Каждое слово дли-
ны n будем рассматривать как последовательность целых чисел (за-
менив буквы кодами). Эти числа будем рассматривать как коэффици-
енты многочлена степени n-1 и вычислим значение этого многочлена
по модулю p в точке x. Это и будет  одна  из  функций  семейства
(для каждой пары p и x получается, таким образом, своя функция).
Сдвиг  окошка на 1 соответствует вычитанию старшего члена, умно-
жению на x и добавлению свободного члена.
     Следующее соображение говорит в пользу того, что совпадения
не слишком вероятны. Пусть число p фиксировано и к тому же прос-
тое,  а  X  и  Y  -  два различных слова длины n. Тогда им соот-
ветствуют различные многочлены (мы предполагаем, что  коды  всех
букв  различны  - это возможно при p, большем числа букв алфави-
та). Совпадение значений функции означает, что в точке x эти два
различных многочлена совпадают, то есть их разность обращается в
0. Разность есть многочлен степени n-1 и имеет не более n-1 кор-
ней. Таким образом, если n много меньше p, то случайному x  мало
шансов попасть в неудачную точку.


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 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.