рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 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 - глобальная компьютерная сеть, охватывающая весь мир. Сегодня Internet имеет около 30 миллионов абонентов в более чем 180 странах мира.… В сложившихся условиях потребность в информации о сети Internet становится… В действительности Internet не просто сеть она есть структура, объединяющая обычные сети. Internet - это Сеть…

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм Рабина

Что будем делать с полученным материалом:

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

Все темы данного раздела:

БРАУЗЕРЫ сравнительные характеристики Netscape Navigator и Microsoft Internet Explorer
БРАУЗЕРЫ сравнительные характеристики Netscape Navigator и Microsoft Internet Explorer. Документы Internet предназначены для отображения в электронном виде, причем автор документа не знает в

Механизмы поиска
Механизмы поиска. Поисковые cистемы обычно состоят из трех компонентов агент паук или кроулер, который перемещается по Сети и собирает информацию база данных, которая содержит всю информацию, собир

Алгоритмы поиска
Алгоритмы поиска. Алгоритм Кнута-Морриса-Пратта Алгоритм Кнута-Морриса-Пратта КМП получает на вход слово Xx1x2 xn и просматривает его слева направо буква за буквой, заполняя при этом массив натурал

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги