Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 149
Текст из файла (страница 149)
Процедура поиска состоит в следующем. Для каждого 1, 1 < 1 < т — и+1 = г, сравнить Ирбб(Х) с )урбб(У(г)) для каждого простого числа р, = р(з), где 1 < ) < й, пока не найдется такое г, что Хебб(Х) = Хр0)(У(г)) для всех 1, 1 < г' < к, и тогда объявляется, что "соответствие" имеет место, или пока 1 не достигнет значения 1 = г, что будет означать, что "соответствие" не найдено.
Отметим, что для полного соответствия необходимо, чтобы все й идентифицирующих функций давали соответствие. Другим важным моментом является выбор простых чисел рырз,...,рь случайным образом из достаточно большого множества. При этом наличие ошибочного соответствия все еще возможно, а РАэдеЛ 22. я приложение: поиск по образу 833 именно, когда 1ттрбй(Х) = )Ур~ ~(У(т)) длЯ всех т, но Х ~ У(1). СУть, однако, заключается в том, что вероятность или возможность ошибочного соответствия может быть сделана сколь угодно малой.
Эта последняя особенность воплошает в себе то, что понимают под вероятностным алгоритмом. ПРИМЕР 22.1. Чтобы лучше понять идею приведенного выше алгоритма, рассмотрим в качестве примера небольшую задачу, предназначенную для иллюстрации применения метода. Предположим, что Х = [1001 101Ц где п = 8 и У = [1011011001101100..0], где тп = 300. Пусть т = пт — и + 1 = 293 и и = пта = 686792.
Предположим, что й = 2 и случайным образом получены простые числа рт — — 47 и рз = 31. Вычисляя первичные вычеты, получим сначала идентификаторы строки Х Дтрнн(Х) = [[.Пт(Х)]]р(Ц = [[1обто]]4т —— 14; Юрбн(Х) = [[Ю(Х)]]рбб = [[155то]]зт = О. Начиная с г = 1, вычислим идентификаторы (строки) У(т), взамно простые с простыми числами 47 и 31, и проверим на соответствие. Соответствия с каждым из двух идентификаторов отмечены звездочкой (*). Первое соответствие наблюдается на позиции 7 в битовой строке У. Следует отметить, что в этом примере мы провели прямое вычисление вычетов, поскольку числа достаточно малы. Компьютерная реализация потребовала бы использования модулярных операций и корректирующей формулы, описанных выше.
П Следуя Карпу и Рабину, получим теперь предельное значение вероятности ошибочного соответствия при использовании этого алгоритма. Для начала нам потребуются два понятия: вероятности и теоретико-числовой функции. Пусть Т вЂ” непустое множество "возможностей", и любая из этих возможностей может быть выбрана. Пусть подмножество А множества Т содержит интересуюшие нас возможности. Выберем один элемент из Т.
Вероятность выбора элемента из А определена соотношением Количество элементов в А Количество элементов в Т 834 ГПЛ8А 22. Приложения теории чисел В такой ситуации будем говорить, что элемент выбран случайным образом из множества Т (каждый элемент множества Т имеет такую же возмножность быть выбранным, как и любой другой ) и событие А имеет место, если выбранный элемент принадлежит множеству А. Формула, приведенная выше, дает вероятность события А. Например, предположим, что Т вЂ” множество граней игрального кубика, так что Т = (1, 2, 3, 4, 5, 6), и мы бросаем кубик один раз (выбираем сторону случайным образом).
Пусть А — событие (множество возможных исходов), состояшее в получении числа точек, выраженного простым числом. А = (2, 3, 5). Тогда РВОВ(А) = 3/6 = 0.5. Очевидно, вероятность любого события лежит между 0 и 1 включительно. Пусть п(ю) количество простых чисел, которые меньше или равны ю.
Таким образом, гг(1) = О, я(2) = 1, я(5) = 3 и гг(20) = 8. Сформулируем два результата, полученные Дж. Россером и Л. Шонфилдом в работе [103]. ТЕОРЕМА 22.2. Если ю > 29, то РгР .Р г 1>2 где ры Рг, Рз,...,р ( 1 — простые числа, которые меньше или равны ю. ТЕОРЕМА 22.3. Если ю > 17, то иг 1.25506ю < я(ю) < 1ой(ю) 1ой(ю) ДОКАЗАТЕЛЬСТВО. Допустим, что ю > 29 и Ь < 2, но Ь имеет не менее гг(ю) простых делителей. Пусть дг < Иг « .
г1, — простые делители числа Ь, так что г > я(ю). Пусть рг < рг « рь — первые й простых чисел для любого Ь. Тогда 2 >Ь Ь > г(гг1гг1з . г(г, г1 г г1г ' ' ' г(г > Ргрг ' ' ' Р Ргрг ' Р - > Ргрг ' Ря(шг ргрг . .р г„,г > 2 дано поскольку гггг(г..гг, ~ Ь поскольку г(г > р, для каждого г поскольку г > я(ю) по теореме 22.2. Но 2 > 2 является противоречием.
Таким образом, Ь должно иметь менее, чем я(ю) простых делителей. Как упоминалось выше, рассмотренный алгоритм поиска имеет возможность завершения с ошибочным соответствием. От этого алгоритма мало пользы, если ошибочное соответствие будет наблюдаться часто. Приведенная ниже теорема утверждает, что вероятность получения ошибочного соответствия в результате применения алгоритма не превышает некоторое определенное значение. ТЕОРЕМА 22.4. Если ю > 29 и Ь < 2, то Ь имеет менее, чем я(ю) простых делителей, РАЗЦЕЛ 22.1.
Проложение: поиск по образу 836 ТЕОРЕМА 22.6. Если алгоритм применен к задаче поиска для Х и У с характеристиками п, т, 1, М, к и Я, то вероятность ошибочного соответствия меньше или равна ДОКАЗАТЕЛЬСТВО. Допустим, что п > 29, 1 < т < 1 и Х Ф У(г). Поскольку 0 < )т"(Х) < 2" и 0 < )т'(У(г)) < 2", то (Аг(Х) — Аг(У(г))( < 2". По теореме 22.4 количество простых чисел, которые делят )Аг(Х) — Аг(У(г))), меньше, чем я(п); следовательно, для любого 1, 1 < у < и, учитывая, что простое число р выбрано случайным образом из множества 5, в котором имеется я(М) элементов, имеем РКОВ(р делит ~)У(Х) — Аг(У(г))~) < ™ .
Поскольку й простых чисел рг,рз,...,рь выбраны случайно и независимо, то по свойству вероятности пересечения и таких событий имеем РВОВ(р делит ~Аг(Х) — Аг(У(г))~ для всех 1) < ~ — ( / я(п) з -~ (М)( Поскольку имеется 1 взаимоисключающих событий для г, то по свойству вероятности все простые числа рг,рз,...,рь делят ~Аг(Х) — Аг(У(г))~ для некоторого т, / я(п) 1 и сама вероятность меньше или равна 1 ~ ) ТЕОРЕМА 22.6.
При выполнении предположений теоремы 22.5, если М = пгз, где и > 29, то вероятность ошибочного соответствия меньше или равна (1.25506)" Г гз~ гг (1+ 0.6 1оя(1))". ДОКАЗАТЕЛЬСТВО. Из теоремы 22.5 следует, что Гг я(и) г РВОВ (ошибочного соответствия) < 1 ~ ) Из теоремы 22.3 следует, что п па~ 2 я(п) < с †, где с = 1.25506, и < я(пт ). 1оя(п) ' ' 1оя(паз) Таким образом, ( с п 1оя(п1~)1 РВОВ (ошибочного соответствия) < 1 ~ 1оя(п) птз — 1+2 Но для п > 29 имеем 1ой(п) > 1оя(29).
Следовательно, теорема верна, поскольку 2 2 непосредственное вычисление показывает, что « 0.6. 1оя(п) 1оя(29) 836 ГпАВл 22. Лрилохгенил теории чисел Для иллюстрации теоремы 22.6 предположим, что имеется задача сопоставления строк с образом Х длины пО, которая соответствует 26 в 8-битовой А5СП- кодировке, с текстовой строкой У длины 32000, соответствующей 4000 в кодировке АБСП. Тогда Г = 31801 и М = п1з < 200(32000)~ = 2ы 10з — 2ы 2ав в < 2зв так что компьютерные представления простых чисел р, и соответствующих вычетов в двоичной системе счисления будут иметь менее 38 битов. Если и = 4, то вероятность ошибочного соответствия не будет превосходить величину 2 10 зз.
Алгоритм Карпа и Рабина является алгоритмом, выполняющимся в реальном времени и требующим одинакового времени вычисления для каждого символа текста. Он также требует постоянного количества памяти, зависящего только от и, )с и г. Можно доказать, что алгоритм имеет малую вероятность ошибки.
Более того, метод можно леко обобщить для применения в многомерных задачах. Помимо Юр этот метод может использовать и другие "идентифицирующие" функции. Заметим, что Карпу и Рабину принадлежат другие подобные, но отличные от вероятностных алгоритмы поиска по образцу, которые можно найти в ссылках, приведенных ранее. Информацию о некоторых эффективных невероятностных алгоритмах поиска для сравнения можно найти в работах (1) РазГ РаГГегп МаГсй1пд .'и 5!г1пдз, авторы Д. Э. Кнут, Дж. Х. Моррис и В.
Р. Пратт [65[; (2) А РазГ 5!г1пд БеагсйГпд А(доггГйт, авторы Р. С. Боер н Дж. С. Мур [12[; (3) Ра!Гегп МаГсй(пу А(Гегпабоез: Тпеогу из. Ргас!(се, автор Джек Пардум [93[ и (4) А Уегу РазГ БиЬзГгту БеагсИ А1дог11пт, автор Даниэль М. Сандей [111[. ° УПРАЖНЕНИЯ 1.
Докажите, что если И' и У вЂ” битовые строки длины п, то [Х(И') — л((У)[ < 2". 2. В теореме 22.2 было показано, что произведение всех простых чисел, которые меньше или равны щ превышает величину 2, если ш > 29. Определите, для какого положительного целого числа ш < 29 также выполняется утверждение этой теоремы. 3. В теореме 22.3 были показаны два неравенства, которые имеют место для каждого положительного числа и > 17. Используя непосредственные вычисления, покажите, какое положительное целое число ю < 17 также удовлетворяет этим неравенствам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
