внешней памяти, но если соотношение справедливо, то при корректном выборе ки М последовательный поиск, вероятно, найдет К. Вероятность ложного выпадения при N записях в файле равна примерно (1 -e"*"/)*. По сути, метод Блума рассматривает весь файл как одну запись, в которой первичные ключи представлены как атрибуты, а кодирование методом наложения производится в огромном М-битовом поле.

Еще один вариант кодирования методом наложения был разработан Ричардом А. Густафсоном (Richard А. Gustafson) [Ph. D. thesis (Univ. South Carolina, 1969)]. Предположим, что есть N записей и что каждая из них имеет шесть атрибутов, выбранных из 10000 возможных. Запись может представлять, например, техническую статью, а атрибуты - ключевые слова, описывающие эту статью. Пусть h - это хеш-функция, отображающая каждый атрибут в число между О и 15. Запись с атрибутами ai,a2,...,a6 Густафсон предлагает отображать в 16-битовое число bobi... bi5, где = 1 тогда и только тогда, когда h{aj) - i для некоторого j. И далее, если только к < 6 бит b равны 1, то другие 6 - к единиц добавляются некоторым случайным методом (необязательно зависящим от самой записи). Дано (б) ~ 8008 16-битовых кодов, в которых имеется ровно шесть единичных битов, и при определенной доле везения примерно iV/8008 записей будут отображены на каждое значение. Можно хранить 8 008 списков записей, непосредственно вычисляя адрес, соответствующий bobi.. .bi5, с использованием подходящей формулы. В самом деле, если единицы встречаются в позициях О < pi < Рг < ••• < Ре, то функция

конвертирует каждую строку bobi... bis в единственное число между О и 8087, как будет показано в упр. 1.2.6-56 и 2.2.6-7.

Теперь, чтобы найти все записи, имеющие три определенных атрибута Ai, А2 и Аз, вычислим h{Ai), /1(2), Л(Аз); предполагая, что все эти значения различны, нужно будет просмотреть только записи, хранящиеся в (3) = 286 списках, битовые коды ЬоЬх... bi5 которых содержат единицы в соответствующих трех позициях. Другими словами, только 286/8008 яа 3.5% записей должны будут проверяться при поиске.

Превосходное" описание кодирования методом наложения вместе с приложением для работы с большой базой данных телефонных номеров можно найти в статье

C. S. Roberts, Ргос. IEEE/ 67 (1979), 1624-1642. Приложение метода к программному обеспечению проверки орфографии обсуждается в работе J. К. Mullin and

D. J. Margoliash, Software Practice & Exper. 20 (1990), 625-630.

Комбинаторное хеширование. Идея, лежащая в основе только что описанного метода Густафсона, заключается в поиске некоторого пути отображения записей на адреса в памяти, такого, что к определенному запросу имеет отношение лишь сравнительно небольшое количество адресов памяти. Однако этот метод применим только к включающим запросам в том случае, когда отдельные записи обладают небольшим количеством атрибутов. Другой тип отображения, предназначенный для обработки произвольных базовых запросов типа (10), в которых содержатся нули, единицы и звездочки, бьш разработан в 1971 году Рональдом Л. Ривестом [см. SICOMP 5 (1976), 19-50].

Предположим сначала, что необходимо создать словарь для составления кроссвордов, содержащий все шестибуквенные слова английского языка; типичный запрос ищет все слова вида, например, N**D*E и получает ответ {NEEDLE, NIDDLE, NODDLE, NOODLE, NUDDLE}. Можно решить эту задачу при помощи 2 списков, поместив слово NEEDLE в список номер

/i(N)/i(E)/i(E)/i(D)/i(L)/i(E).

Здесь h - хеш-функция, переводящая каждую букву в двухбитовое значение, и мы получаем 12-битовый адрес, записывая рядом шесть пар битов. Затем запрос N**D*E может быть обработан в результате просмотра только 64 списков из 4096.

Аналогично предположим, что есть 1000000 записей, в каждой из которых содержится 10 вторичных ключей, а каждый вторичный ключ и.меет большое количество возможных значений. Можно отобразить записи со вторичными ключами {Ki,К2,Кю) в 20-битовое число

h{Ki)h{K2) ...ЦКго), (12)

где h - хеш-функция, преобразующая каждый вторичный ключ в двухбитовое число, и (12) образуется после размещения этих десяти пар битов в одном 20-битово.м числе. Данная схема отображает 1000000 записей в 2 = 1048 576 возможных значений, и отображение, в целом, может рассматриваться как хеш-функция с М = 29 Для разрешения коллизий .может использоваться метод цепочек. Чтобы получить все записи с определенными значениями пяти вторичных ключей, потребуется просмотреть только 2° списков, соответствующих пяти неопределенным парам битов в (12). Таким образом, в среднем придется проверить около 1000 = % V записей. (Подобный подход был предложен М. Арисавой (М. Arisawa) [J. Inf. Ргос. Soc. Japan 12 (1971), 163-167] и Б. Двайером (В. Dwyer) [не опубликовано]. Двайер предложил использовать более гибкое по сравнению с (12) отображение, а именно

(/ll [Кг) + h2{K2) + + hioiK.o)) mod М,

где М - любое подходящее число, а /г, - произвольные хеш-функции, возможно, вида WiKi для "случайного" №,.)

Ривест продолжил разработку этой идеи, так что во многих случаях возникает следующая ситуация. Предположим, что имеется ЛГ « 2" записей, в каждой из которых содержится т вторичных ключей. Каждая запись отображается в п-битовый хеш-адрес таким образом, что запрос, оставляющий неопределенными значения к ключей, соответствует примерно ЛГ*/™ хеш-адресам. Все другие методы, обсуждавшиеся ранее в этом разделе (за исключением метода Густафсона), требуют порядка ЛГ шагов для получения информации, хотя и с малым коэффициентом пропорциональности; для больших значений ЛГ метод Ривеста более быстр и не требует инвертированных файлов.

Но прежде чем применять эту технологию, следует определить подходящее отображение. Ниже рассматривается пример с небольшими параметрами, с m = 4 и п = 3 и вторичными ключами, принимающими два значения. Можно отобразить 4-битовые записи в восемь адресов следующим образом.

*001->0 *110->4

0*00->1 1*11->5 ,,,4

10*0->2 01*1->6

110*->3 001*->7

Исследование этой таблицы показывает, что все записи, соответствующие запросу О * * *, отображаются в позиции О, 1, 4, 6 и 7. Точно так же любой базовый запрос с тремя символами "*" соответствует в точности пяти позициям, базовый запрос с двумя "*" - трем позициям и с одной "*" - одной или двум позициям, (8 X 1 + 24 X 2)/32 = 1.75 в среднем. Таким образом, имеем следующее.

Количество неопределенных Количество позиций

битов в запросе поиска

4 8 = 8"/"

3 5«8/ (14)

2 3 « 82/»

1 1.75 « 81/"

О 1 = 8°/

Конечно, это всего лишь маленький пример, и в таких случаях гораздо проще осуществлять поиск "в лоб" Этот метод приводит к появлению нетривиальных приложений, поскольку его можно использовать и тогда, когда m = 4г и п = Зг, отображая 4г-битовые записи на 2*" и Л позиций путем разделения вторичных ключей на г групп по 4 бит и применяя (13) к каждой группе. Получающееся отображение имеет требуемое свойство: запрос, оставляющий к из т бит неопределенными, соответствует примерно N" позищ1Ям (см. упр. 6).

В 1997 году А. Э. Брувер (А. Е. Brouwer) нашел привлекательный способ сжатия 8 бит до 5 бит при помощи отображения, аналогичного (13). Каждый 8-битовый байт принадлежит в точности одному из следующих 32 классов.

0*000*0* 01*0**11 00*11**1 *11**101

1*000*0* 11*0**11 10*11**1 *11**010

0*010*0* 01*1**11 00*0*01* *10*0*10

1*010*0* 11*1**11 10*0*01* *10*1*01

0*Ш*1*0 0*1*000* *01*01*1 *0*1001*

1*10*1*0 1*1*000* *10*10*0 *0*0100*

0*11*1*0 0*0*11*0 *00*011* *0*011*1

(15)

1*11*1*0 1*0*11*0 *11*100* *0*110*0

Звездочки в этой конструкции расположены таким образом, что в каждой строке их по 3, а в каждом столбце - по 12. В упр. 18 поясняется, каким образом строятся подобные схемы, сжимающие записи с m = 4" бит в п = 3-битовые адреса. На практике используются блоки размером b и N ! 2"6; случай, когда 6 = 1, использовался выше для упрощения изложения материала.

Ривест предложил также другой простой путь обработки базовых запросов. Предположим, имеется Л « 2° записей по 30 бит и необходимо ответить на произвольный 30-битовый базовый запрос, подобный (10). В этом случае мы можем просто поделить 30 бит на три 10-битовых поля и поддерживать три отдельные хеш-таблицы размером М = 2°. Каждая запись хранится в трех местах, в списках, соответствующих битовым конфигурациям трех полей. При соответствующих уело-