хранения места на картах с перфорацией по краям, принципы которых применимы и для представления компьютерных файлов. Кодирование методом наложения представляет собой технологию, схожую с хешированием, хотя оно было разработано за несколько лет до изобретения хеширования. Идея заключается в отображении атрибутов в случайные /с-битовые коды в п-битовых полях и наложении кодов каждого атрибута, имеющегося в записи. Включающий запрос для некоторого множества атрибутов может быть конвертирован во включающий запрос для соответствующих наложенных битовых кодов. Такому запросу могут удовлетворять несколько дополнительных записей, но количество подобных "ложных выпадений" может быть статистически учтено [см. Calvin N. Mooers, Amer. Chem. Soc. Meeting 112 (September, 1947), 14E-15E; American Documentation 2 (1951), 20-32].

В качестве примера кодирования методом наложения вновь обратимся к табл. 1, но только к той ее части, которая относится к специям, не рассматривая основные компоненты наподобие пекарного порошка, яиц и муки. В табл. 2 показано, что произойдет, если назначить случайные двухбитовые коды в десятибитовых полях каждой из специй и использовать наложение. Например, "Шоколадный хворост" будет получен в результате наложения кодов шоколада, орехов и ванилина:

0010001000 V 0000100100 V 0000001001 = 0010101101.

Наложение данных кодов даст также несколько ложных атрибутов; в нашем конкретном случае - душистый перец, засахареннзто вишню, смородиновое желе, арахисовое масло и перец. Это вызовет ложные выпадения при некоторых запросах (тем самым будет предложено разработать новый рецепт - "Ложновьшадающее печенье"! :-)).

Для табл. 2 кодирование методом наложения работает не так уж хорошо, поскольку эта таблица представляет всего лишь маленький пример с большим количеством атрибутов. В самом деле, "Печенье с яблочным соусом" будет выпадать при каждом запросе, поскольку оно получено наложением семи кодов, покрывающих все десять позиций. Еще хуже обстоят дела в случае рецепта печенья с перце.м (впрочем, с точки зрения кодов и ложных выпадений совершенно все равно, как получена цепочка из десяти единиц: наложением семи или двенадцати кодов. - Прим. перев.), полученного в результате наложения двенадцати кодов. С другой стороны, иногда табл. 2 работает на удивление неплохо; например, дав запрос "Ванилин", мы получим только одно ложное выпадение - "Печенье с перцем"

Более подходящий пример кодирования методом наложения получается при наличии, скажем, 32-битового поля и набора из (3) = 4 960 различных атрибутов, где каждая запись может иметь до шести атрибутов и каждый атрибут кодируется тремя из 32 бит. В этой ситуации в предположении, что каждая запись имеет шесть случайно выбранных атрибутов, вероятности ложных выпадений в случае включающего запроса составляют:

по одному атрибуту 0.07948358

по двум атрибутам 0.00708659

по трем атрибутам 0.00067094 , ,

по четырем атрибутам 0.00006786

по пяти атрибутам 0.00000728

по шести атрибутам 0.00000082

Таблица 2

ПРИМЕР КОДИРОВАНИЯ МЕТОДОМ НАЛОЖЕНИЯ

Таким образом, если имеется М записей, которые не удовлетворяют двухатрибут-ному запросу, то около 0.007М записей будут иметь наложенные коды, соответствующие всем битам этих двух атрибутов (все вероятности вычисляются в упр. 4). Общее количество битов, необходимых для представления инвертированного файла, составляет 32, умноженное на количество записей, что меньше половины количества битов, требуемых для описания всех атрибутов в исходном файле.

При аккуратном использовании неслучайных кодов можно избежать ложных выпадений, как показано в работе W. Н. Kautz and R. С. Singleton, IEEE Trans. IT-10 (1964), 363-377; одна из таких конструкций рассматривается в упр. 16.

Малкальм Ч. Харрисон (Malcolm С. Harrison) [САСМ 14 (1971), 777-779] обнаружил, что кодирование методом наложения может использоваться для ускорения поиска текста. Пусть нужно найти все вхождения некоторой строки символов в тексте большого объема без построения обширных таблиц алгоритма 6.3Р. Предположим также, что текст разделен на строки, например, по 50 символов: ciC2 ... Cso-Харрисон предложил кодировать каждую из 49 пар CiC2, C2C3, ..., С49С50 методом хеширования каждой из них в число, скажем, от О до 127, а затем подсчитать "ключ" строки С1С2...С50, который представляет собой строку из 128 бит bobi...bi27, где bi = 1 тогда и только тогда, когда h{cjCj+i) = i для некоторого j.

Пусть необходимо найти все вхождения слова NEEDLE (ИГОЛКА) в большом файле с именем HAYSTACK (СТОГ СЕНА). При этом мы просто просмотрим все строки, ключи которых содержат 1 в позициях /i(NE), /г(ЕЕ), /г(ЕО), h{DL) и /i(LE). Считая хеш-функцию случайной, вероятность того, что случайная строка содержит все эти биты в своем ключе, можно оценить как 0.00341 (см. упр. 4). Следовательно, пересечение пяти инвертированных списков битовых строк позволит быстро обнаружить все строки, содержащие NEEDLE (естественно, с некоторым количеством ложных выпадений).

Предположение случайности на самом деле мало применимо для текста, поскольку обычный текст весьма избыточен и пары символов в нем распределены весьма неравномерно. Например, может оказаться полезным опустить все пары CjCj+i, содержащие символ пробела, в связи с тем, что пробел встречается в тексте гораздо чаще прочих символов.

Другое интересное приложение кодирования методом наложения к задачам поиска было предложено Бартоном Блюмом (Burton Bloom) [САСМ 13 (1970), 422-426]. Его метод на само.м деле применим для выборки по первичным ключам, хотя более подходящее место для его обсуждения - этот раздел. Представьте себе приложение для поиска в большой базе данных, которое не требует каких-либо дальнейших действий, если поиск оказался неудачным. Например, нужно просто проверить чью-то кредитную карточку или номер паспорта и, если в файле нет записей о данной персоне, никаких дальнейших действий предпринимать не требуется. Аналогичный метод применим и при компьютерной верстке для правильных переносов слов. Например, у нас есть метод расстановки переносов, корректно работающий с большинством слов, но имеющий некоторое количество исключений на 50000 слов; если слово не найдено в файле исключений, можно использовать простой алгоритм.

В такой ситуации можно хранить таблицу битов во внутренней памяти, чтобы отсутствие большинства ключей распознавалось без обращений к внешней памяти. Вот как это можно сделать: обозначим внутреннюю битовую таблицу через bobi... Ьм-\, где М очень велико. Для каждого ключа Kj в файле вычислим к независимых хеш-функций hi{Kj),... ,hk{Kj) и установим соответствующие к бит равными 1 (эти к значений не обязаны быть различными). Таким образом, bj = 1 тогда и только тогда, когда hi{Kj) = i для некоторых j к I. Теперь, чтобы определить наличие аргумента поиска К во внешнем файле, сначала выясним, справедливо ли соотношение bh,{K) - 1 при 1 <1 <к. Если нет, то нет и необходимости обращаться к