Реферат Курсовая Конспект
Работа сделанна в 2002 году
Алгоритм Рабина - Курсовая Работа, раздел Связь, - 2002 год - Технологии поиска документальной информации в INTERNET Алгоритм Рабина. Этот Алгоритм Основан На Простой Идее. Представим Себе, Что ...
|
Алгоритм Рабина. Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом.
Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам. В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить значение функции на слове в окошечке, все равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом.
Тем не менее выигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция. Привести пример удобной для вычисления функции. Решение. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.
Для каждой функции существуют слова, к которым она применима плохо. Зато другая функция в этом случае может работать хорошо. Возникает идея надо запасти много функций и в начале работы алгоритма выбирать из них случайную. Тогда враг, желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией ему бороться. Привести пример семейства удобных функций. Решение. Выберем некоторое число p желательно простое, смотри далее и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел заменив буквы кодами.
Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства для каждой пары p и x получается, таким образом, своя функция. Сдвиг окошка на 1 соответствует вычитанию старшего члена хn-1 следует вычислить заранее, умножению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны.
Пусть число p фиксировано и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены мы предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита. Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку. 4.
– Конец работы –
Эта тема принадлежит разделу:
Internet - глобальная компьютерная сеть, охватывающая весь мир. Сегодня Internet имеет около 30 миллионов абонентов в более чем 180 странах мира.… В сложившихся условиях потребность в информации о сети Internet становится… В действительности Internet не просто сеть она есть структура, объединяющая обычные сети. Internet - это Сеть…
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм Рабина
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов