Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 55
Текст из файла (страница 55)
00006786 по пяти атрибутам 0,00000728 по шести атрибутам 0.00000082 Таблица 2 ПРИМЕР КОДИРОВАНИЯ МЕТОДОМ НАЛОЖЕНИЯ Наложенные коды 0000100100 Медовые пряники П1ШПП Меренги 1000ППП Моравское печеиье со специями 001010П01 Овсяные палочки с финиками ОООПП101 Старинное сахарное печенье 101П1ОП1 1000 10П 00 100П 100П 1000100100 0000ОПОП 001000П01 0000001001 ППШП1 0000001001 Печенье с арахисовым маслом Юбочки 0010001001 ОПП1ОПО ОО1О1ОПОО ОООПГПО1 Печенье с перцем Шотландские овскиме коржики Песочные звездочки Анисовое печенье Воздушное леченье 0000000000 ООПОПООО 0000001001 Пирог с начиикой Финский какор Глазироввнкые имбирные пряники Печенье с орехами Драгоценное леченье 10П10П01 0100100101 100П1001 0 ОООООООООО 1000000010 001010П01 000010П01 Шведский крендель Швейцарское рас~ыпчатое печеиье с корицей Ириски Вакильно-ореховое мороженое П01010ПО ОО1ОИН1О1 10000010П 10П100101 Перепутакица Малайский крендель Таким образом, если имеется М записей, которые не удовлетворяют двухатрибутному запросу, то около 0.007М записей будут иметь иаложеппые коды, соответствующие всем битам зтих двух атрибутов (все вероятности вычисляются в упр.
4). Общее количество битов, необходимых для представления инвертированного файла, составляет 32, умноженное па количество записей„что меньше половины количества битов, требуемых для описания всех атрибутов в исходном файле. Экстракт миицаля Душистый перец Зерна аниса Яблочный соус Абрикос В анапы Засахаренная вишня Кардамон Шоколад Корица Цукаты Гвоздика Кокосовый орех Кофе Смородиковое желе Миндальные вафли с ромом Печенье с яблочным соусом Баканово-овсяное печенье Шоколадный хворост Миндальное печенье с кокосами Печенье со сливочным сыром Ароматные палочки с черносливом Драже в шоколаде Райские палочки Коды отдельных 0100000001 0000100001 ОООООПООО 0010010000 1000010000 ОООО1ООО1О ОООО1О1ООО 1ОООООООО1 0010001000 1ООООООО1О 0100000010 ооопооооо ООО1О1ОООО ОООЮО01ОО ОО1ОООООО1 приправ Финики Имбирь Мед Лимонный сок Лимонная цедра Мускатный цвет Патока Мускатный орех Орехи Апельсины Арахисовое масло Перец Чернослив Изюм Ванили н 1000000100 оооопоооо оооооаооп юооивооо оопоооооо 0000010100 1ОО1ОООООО оооооюою 0000100100 ОИВОООИВ 0000000101 0010000100 ОО1ООООО1О О1ОИВОООО 0000001001 При аккуратном использовавии неслучайных кодов можво избежать ложных выпадений, как показано в работе 97.
Н. Каша апб В. С. Йпй1есоп, ХЕЕЕ Тгапв. 1Т-10 (1964), 363-377: одна из таких конструкций рассматривается в упр. 16. Малкольм Ч. Харрисон (Ма1сойп С. Нагбвоп) [САСМ 14 (1971), 777-779] обнаружил, что кодирование методом наложения может использоваться для ускорения поиска шекспю. Пусть нужно найти все вхождения некоторой строки символов в тексте большого объема без построения обширных таблиц алгоритма 6.3Р. Предположим также, что текст разделен на строки, например, по 50 символов: ела»... ело.
Харрисов предложил кодировать каждую из 49 пар с»сз, сзсз, ... „щэсло методом хешировавия каждой из вих в число, скажем, от 0 до 127, а затем подсчитать "ключ" строки с|ся... с;о, который представляет собой строку из 128 бит ЬоЬ» ...6шт, где 6; = 1 тогда и талька тогда, когда Ь(с»с»„ы) = 1 для некоторого у. Пусть необходимо найти все вхождения слова МЕКОНГЕ (ИГОЛКА) в больпюм файле с именем НАУБТАСК (СТОГ СЕНА).
При этом мы просто просмотрим все строки, ключи которых содержат 1 в позициях Ь(МЕ), Ь(ЕЕ), Ь(ЕО), Ь(Ш.) и Ь(1Е). Считая хепь функцию случайной, вероятвость того, что случайная строка содержит все зти биты в своем ключе, можно оценить как 0.00341 (см. упр. 4). Следовательно, пересечение пяти инвертированных списков битовых строк позволит быстро обнаружить все строки, содержащие МЕЕО1.Е (естественво, с векоторым количеством ложных выпадений).
Предположение случайвостн на самом деле мало применимо для текста, поскольку обычный текст весьма избыточен и пары символов в вем распределены весьма неравномерно. Например, может оказаться полезным опустить все пары с;с +ы содержащие символ пробела, в связи с тем, что пробел встречается в тексте гораздо чаще прочих символов. Другое интересное приложение кодирования методом ввложевия к задачам поиска было предложено Бартоном Блюмом (Вигсоп В1оош) ]САСМ 13 (1970), 422-426]. Его метод ва самом деле примевим для выборки по первичным ключам, хотя более подходящее место для его обсуждения — этот раздел.
Представьте себе приложение для поиска в балыпой базе данных, которое не требует каких-либо дальнейших действий, если поиск оказался неудачным. Например, нужно просто проверить чью-то кредитную карточку или номер паспорта и, если в файле вет записей о данной персоне, никаких дальнейших действий предпринимать не требуется. Авалогичвый метод применим и при компьютерной верстке для правильвых переиосов слов. Например, у вас есть метод расстановки переносов,корректво работающий с болыпивством слов, ио имеющий некоторое количество исключений на 50 000 слов; если слово ие найдено в файле исключевий, можно использовать простой алгоритм. В такой ситуации можно хранить таблицу битов во внутренней памяти, чтобы отсутствие большинства ключей распознавалась 6еэ обращевий к внешней памяти, Вот как зто можно сделать: обозначим внутреннюю битовую таблицу через ЬоЬ» ... Ьл» м где АХ очень велико, Для каждого ключа К» в файле вычислим Ь независимых хеш-функций Ь~(К»),..., Ьл(К») и установим соответствующие Ь бит раввыми 1 (эти Ь значений ие обязаны быть различными).
Таким образом, Ь; = 1 тогда и только тогда, когда Ь~(К») = 1 для некоторых у и 1. Теперь, чтобы определить наличие аргумента поиска К во внешнем файле, сначала выясним, справедливо ли соотношение Ьлдв» = 1 при 1 < 1 С Й. Если вет, то вет и необходимости обращаться к внешней памяти, но если соотношение справедливо, то при корректном выборе Ь и М последовательный поиск, вероятно, найдет К. Вероятность ложного выпадения при Х записях в файле равна примерно (1 — е "аУм)".
По сути, метод Блума рассматривает весь файл как одну запись, в которой первичные ключи представлены как атрибуты, а кодирование методом наложения производится в огромном М-битовом поле. Еще один вариант кодирования методом наложения был разработан Ричардом А. Густафсоном (В)сйап1 А. Опвга(воп) [РЬ. В. М~ев1в (Вппс Бопсй Сагойпа, 1969)[. Предположим, что есть Х записей и что каждая из ннх имеет шесть атрибутов, выбранных из 10000 возможных, Запись может представлять, например, техническую статью, а атрибуты — ключевые слова, описывающие зту статью. Пусть Л вЂ” это хеш-функция, отображающая каждый атрибут в число между 0 и 15. Запись с атрибутами амат,...,ав Густафсон предлагает отображать в 16-битовое число Ье6~ ...Ьнн где Ь; = 1 тогда и только тогда, когда Л(а1) = 1 для некоторого з1 И далее, если только Л < 6 бит Ь равны 1, то другие б — й единиц добавляются некоторым случайным л1етодом (необязательно зависящим от самой записи). Дано ('ве) = 8008 16-битовых кодов, в которых имеется ровно п1есть единичных битов, и при определенной доле везения примерно Ж/8008 записей будут отображены на каждое значение.
Можно хранить 8 008 списков записей, непосредственно вычисляя адрес, соответствующий Ье61...Ьпп с использованием подходящей формулы. В самом деле, если единицы встречаются в позициях О < р1 < рз « ° р», то функция конвертирует каждую строку Ьо6|... Ьш в единственное число между 0 и 8087, как будет показано в упр. 1.2,6-56 и 2.2.6-7.
Теперь, чтобы найти все записи, имеющие три определенных атрибута Аы Аз и Аз, вычислим Л(А1), Л(Аз), Л(Аз); предполаия„что все зги значения различны, нужно будет просмотреть только записи, хранящиеся в ('з) = 286 списках, битовые коды 6о61... Ьы которых содержат единицы в соответствующих трех позициях. Другими словами, только 286/8008 3.5% записей должны будут проверяться при поиске. Превосходим'описание кодирования методом наложения вместе с приложением для работы с большой базой данных телефонных номеров можно найти в статье С.
8. ВоЬеггв, Ргос. ЖЕЕ/ 67 (1979), 1624-1642. Приложение метода к программному обеспечению проверки орфографии обсуждается в работе 1. К. Мц!1ш апб В. 3. Магйо)1аа6, Войк ага Ргасбсе Й Ехрег. 20 (1990), 625-630, Комбинаторное хеширование. Идея, лежащая в основе только что описанного метода Густафсопа, заключается в поиске некоторого пути отображения записей на адреса в памяти, такого, что к определенному запросу имеет отношение лишь сравнительно неболыпое количество адресов памяти. Однако зтот метод применим только к включающим запросам в том случае, когда отдельные записи обладают небольп1им количеством атрибутов.
Другой тип отображения, предназначенный для обработки произвольных базовых запросов типа (10), в которых содержатся нули, единицы и звездочки, был разработан в 1971 году Рональдом Д. Ривестом [см. 81СОМР 5 (1976), 19 — 50]. Предположим сначала, что необходимо создать словарь для составления кроссвордов, содержащий все шестибуквенные слова английского языка; типичный запрос ищет все слова вида, например, ИээйеЕ н получает ответ (ИЕЕО1.Е,И1001.Е,ИОО01.Е, ИО001.Е,ИООШ.Е). Мож орешитьэтузадачуяр ~о~ощи2'з и снов, поместивслово ИЕЕШ.Е в список номер Ь(И) Ь(Е) Ь(Е) Ь(О) Ь(1.) Ь(Е), Здесь Ь вЂ” хепьфункцня, переводящая каждую букву в двухбитовое значение, и мы получаем 12-битовый адрес, записывая рядом шесть пар битов.
Затем запрос Иэ*Р*Е может быть обработан в результате просмотра только 64 списков из 4 096, Аналогично предположим, что есть 1000000 записей, в каждой из которых содержится 10 вторичных ключей, а каждый вторичный ключ имеет большое ко. личество возможных значений. Можно отобразить записи со вторичными ключами (К~ „Кз,..., К~е) в 20-битовое число Ь(%) Ь(Кз) ° Ь(Кш) (12) где Ь вЂ” хеш-функция, преобразуюгцая каждый вторичный ключ в двухбитовое число, и (12) образуется после размещения этих десяти пар битов в одном 20-битовом числе. Данная схема отображает 1000000 записей в 2~ = 1 048 676 возможных значений, и отображение, в целом, может рассматриваться как хеш-функция с М = 2зо Для разрешения коллизий может использоваться метод цепочек.
Чтобы получить все записи г определенными значениями пяти вторичных ключей, потребуется просмотреть только 2'~ списков, соответствующих пяти неопределенным парам битов в (12). Таким образом, в среднем придется проверить около 1000 = ~/КИ записей. (Подобный подход был предложен М. Арисавой (М. Апзана) (,7. ЬК Ргос. Яос.,уарап 12 (1971), 163-167] н Б. Двайером (В. Пъуег) (не опубликовано). Двайер предложил использовать более гибкое по сравнению с (12) отображение, а именно (Ь~Ж) + Аз(Ка) +'''+)ноЖо)) пкн1 М где М вЂ”. любое подходящее число, а Ь; — произвольные хеш-функции, возможно, вида ю;К, для "случайного" и;.) Ривест продолжил разработку этой идеи, так что во многих случаях возникает следующая ситуация.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
