AOP_Tom3 (1021738), страница 145
Текст из файла (страница 145)
Можно хранить 8 008 списков записей, непосредственно вычисляя адрес, соответствующий баб|...Ьгя, с использованием полходящей формулы. В самом деле, если единицы встречаются в позициях 0 < рг ( ря ( . < ря, то функция конвертирует каждую строку бяб, ... бш в единственное число между 0 и 8087, как будет показано в упр. 1.2.6 — 56 и 2.2.6 — 7. Теперь, чтобы найти все записи, имеющие три определенных атрибута Аы Ая и Ая, вычислим И(А,), Ь(Аз), Ь(Ая); предполагая, что все зти значения различны, нужно будет просмотреть только записи, хранящиеся в Я) = 286 списках, битовые коды баб~, бш которых содержат единицы в соответствующих трех позициях, Другими словами, только 286/8008 - 3.5Уа записей должны будут проверяться при поиске.
Превосходное описание кодирования методом наложения вместе с приложением для работы с большой базой данных телефонных номеров можно найти в статье С. 8. ВоЬегяя, Ргос. 1ЕЕЕ/ 67 (1979), 1624 — 1642. Приложение метода к программному обеспечению проверки орфографии обсуждается в работе д. К. МпВ1п апг1 П. Л. МагйойяяЬ, Яа1гггаге Ргягг1се яг Ехрег. 20 (1990), 625 — 630.
Коыбинаторное хеширование. Иден, лежащая в основе только что описанного метода Густафсоиа, заключается в поиске некоторого пути отображения записей на адреса в памяти, такого, что к определенному запросу имеет отношение лишь сравнительно небольшое количество адресов памяти. Однако этот метод применим только к включающим запросам в том случае, когда отдельные записи обладают небольшим количеством атрибутов. Другой тип отображения, предназначенный для обработки произвольных базовых запросов типа (10), в которых содержатся нули, единицы и звездочки, был разработан в 1971 году Рональдом Л. Ривестом [см. 61СОМР 5 (1976), 19 — 50].
Предположим сначала, что необходимо создать словарь для составления кроссвордов, содержащий все шестибуквенные слова английского языка; типичный запрос ищет все слова вида, например, ИэьОьЕ и получает ответ (ИЕЕОЕЕ,И100ЕЕ,И000ЕЕ, И000ЕЕ, ИУ00ЕЕ). Можно решить эту задачу при помощи 2' списков, поместив слово ИЕЕОЕЕ в список номер А(И) А(Е) А(Е) А(0) А(~.) А(Е).
Здесь А — хеш-функция, переводящая каждую букву в двухбитовое значение, н мы получаем 12-битовый адрес, записывая рядом шесть пар битов. Затем запрос ИээйэЕ может быть обработан в результате просмотра только 64 списков из 4096. Аналогично предположим, что есть 1000000 записей, в каждой из которых содержится 10 вторичных ключей, а каждый вторичный ключ имеет большое количество возможных значений. Можно отобразить записи со вторичными ключами (Км Км, .., Кю) в 20-битовое число А(%) Ь(Кг) .
А(%о), (12) где Ь вЂ” хеш-функция, преобразующая каждый вторичный ключ в двухбитовое число, и (12) образуется после размещения этих десяти пар битов в одном 20-битовом числе. Данная схема отображает 1 000000 записей в 2э" = 1 048 576 возможных значений, и отображение, в целом, может рассматриваться как хеш-функция с М = 2~в Для разрешения коллизий может использоваться метод цепочек. Чтобы получить все записи с определенными значениями пяти вторичных ключей, потребуется просмотреть только 2' списков, соответствующих пяти неопределенным парам битов в (12).
Таким образом, в среднем придется проверить около 1000 = ~/Х записей. (Подобный подход был предложен М. Арисавой (М. Аг1ваиа) [,7. 1пб Ргос. Яос. 3арап 12 (1971), 168 -167) и Б. Двайером (В. Пжуег) (не опубликовано). Двайер предложил использовать более гибкое по сравнению с (12) отображение, а именно (А~(К~) + Аэ(Кэ) +." + Ецэ(К~в)) пюб М, где М вЂ” любое подходящее число, а И; — произвольные хеш-функции, возможно, вида влК, для "случайного" щ.) Ривест продолжил разработку этой идеи, так что во многих случаях возникает следующая ситуация.
Предположям, что имеется Х - 2" записей, в каждой из которых содержится пг вторичных ключей. Каждая запись отображается в п-битовый хеш-адрес таким образом, что запрос, оставляющий неопределенными значения й ключей, соответствует примерно Мьй" хеш-адресам. Все другие методы, обсуждавшиеся ранее в этом разделе (за исключением метода Густафсона), требуют порядка Х шагов для получения информации, хотя и с малым коэффициентом пропорциональности; для больших значений Х метод Ривеста болев быстр и не требует инвертированных файлов.
Но прежде чем применять эту технологию, следует определить подходящее отображение. Ниже рассматривается пример с небольшими параметрами, с тп = 4 и и = 3 и вторичными ключами, принимающими два значения. Можно отобразить 4-битовые записи в восемь адресов следующим образом. я001-+О э110->4 Ов00-э1 1а11-э5 (13) 1 О я О -+ 2 01*1-+6 110*-+3 001я-+7 Исследование этой таблицы показывает, что все записи, соответствующие запросу 0 я ь э, отображаются в позиции О, 1, 4, 6 и 7.
Точно так же любой базовый запрос с тремя символами "*" соответствует в точности пяти позициям, базовый запрос с двумя "~" — трем позициям и с одной "е" — одной или двум позициям, (8 х 1+ 24 х 2)/32 = 1.75 в среднем. Таким образом, имеем следующее. Количество неопределенных битов в запросе 4 3 2 1 0 Количество позиций поиска 8 — 84/м 5 — 8з/4 3 8/4 1,75 =~ 8"~~ 8о/а (14) Конечно, это всего лишь маленький пример, и в таких случаях гораздо проще осуществлять поиск "в лоб'! Этот метод приводит к появлению нетривиальных приложений, поскольку его можно использовать и тогда, когда гп = 4г и и = Зг, отобраясэя 4г-битовые записи на 2э" а М позиций путем разделения вторичных ключей на г групп по 4 бит и применяя (13) к каждой группе.
Получающееся отображение имеет требуемое свойство: запрос, оставляюгляй й нз т бнг неопределелнымн, соответствует примерно Хь~'" позициям (см. упр. 6). В 1997 году А. Э. Брувер (А. Е. Вгопжег) нашел привлекательный способ сжатия 8 бит до 5 бит при помощи отображения, аналогичного (13). Каждый 8-битовый байт принадлежит в точности одному из следующих 32 классов. 0*000ьО* 01кОяя11 00я11яя1 э11вэ101 1ь000яОя 11яОв*11 10*11х*1 я11*я010 Ок010яОя 01я1*к11 00яОя01я я10яОя10 1*010*0* 11я1ья11 10яОя01я *10э1ь01 (15) 0.10.1*0 0*1*000. .01.01*1 *0*1001.
1я10я1*0 1*1я000в я10я10яО я0*0100я Оя11я1яО ОьОк11*0 *ООь011я эОэ011ь1 1я11я1ьО 1~0э11вО «11я100я яОя110я0 Звездочки в этой конструкции расположены таким образом, что в каждой строке их по 3, а в каждом столбце — по 12. В упр. 18 поясняется, каким образом строятся подобные схемы, сжимающие записи с гп = 4" бит в п = 3"-битовые адреса. На практике используютсн блоки размером 5 и М вЂ” 2"Ь; случай, когда 5 = 1, использовался выше для упрощения изложения материала. Ривест предложил также другой простой путь обработки базовых запросов. Предположим, имеется Х вЂ” 2'с записей по 30 бит и необходимо ответить на произвольный 30-битовый базовый запрос, подобный (10), В этом случае мы можем просто поделить 30 бит на три 10-битовых поли и поддерживать три отдельные хеш-таблицы размером М = 2'с.
Каждая запись хранится в трех местах, в списках, соответствующих битовым конфигурациям трех полей. При соответствующих усло- виях в каждом списке будет содержаться около одного элемента. В данном базовом запросе с Л неопределенными битами как минимум одно из полей будет иметь 1Лсс31' или меньше неопределенных битов. Следовательно, потребуется просмотреть не более 2(луз1 - Лс"lэо списков для поиска всех ответов на запрос. Впрочем, можно использовать и любую другую технологию для обработки базовых запросов в выбранных полях.
Обобщенные лучи (1г1ее). Ривест предложил еще один подход, который основан на структурах данных, подобных использованным в разделе 6.3 лучам. Можно предположить, что каждый внутренний узел обобщенного бинарного луча определяет представленные в записи биты. Например, используя приведенные в табл. 1 данные, можно положить корнем луча Ваяилян. Тогда левый подлуч будет соответствовать тем 16 рецептам, в которых ванилин не нужен„в то время как в правом подлуче собираются 15 рецептов с ванилином.
Такое разбиение 16-15 удачно делит файл практически пополам; каждый из подфайлов обрабатывается аналогично, и когда на некоторой стадии подфайл становится достаточно мал, его можно представить в качестве конечного узла. Для поиска по обобщенному лучу с корнем, определяющим атрибут, которому в запросе соответствует О илн 1, переходим к поиску в левом или правом подлуче соответственно; если этому атрибуту в запросе соответствует "л", просматриваем оба подлуча. Предположим, что атрибуты не бинарны, но представлены в бинарной записи. Можно построить луч, рассматривая сначала первый бит атрибута 1, затем — первый бит атрибута 2,..., первый бит атрибута т, второй бит атрибута 1 и т. д. Такая структура называется т-с1-лучолс, по аналогии с т-с1-деревьями (которые ветвятся в результате сравнении, а не проверки битов).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
