AOP_Tom3 (1021738), страница 144
Текст из файла (страница 144)
Идея заключается в отображении атрибутов в случайные Л-битовые коды в и-битовых полях и наложении кодов каждого атрибута, имеющегося в записи. Включающий запрос для некоторого множества атрибутов может быть конвертирован во включающий запрос для соответствующих наложенных битовых кодов. Такому запросу могут удовлетворять несколько дополнительных записей, но количество подобных "ложных выпадений" может быть статистически учтено 1см. Са!хш 1 51ооегэ, Ашег. СЛет. 5ос. Л1еег1п8 112 (БергешЬег, 1947), 14Š— 15Е; Ашег1сап Посшпешлбоп 2 (1951), 20-32).
В качестве примера кодирования методом наложения вновь обратимся к табл. 1, ио только к той ее части, которая относится к специям, не рассматривая основные компоненты наподобие пекарного порошка, яиц н муки. В табл. 2 показано, что произойдет, если наэначнть случайные двухбитовые коды в десятибнтовых полях каждой из специй и испольэовать наложение. Например, "Шоколадный хворост" будет получен в результате наложения кодов шоколада, орехов и ванилина: 0010001000 ч'0000100100 Ч 0000001001 = 0010101101. по одному атрибуту по двум атрибутам по трем атрибутам по четырем атрибутам по пяти атрибутам по шести атрибутам 0.07948358 0.00708659 0.00067094 0.00006786 О.
00000728 0.00000082 Наложение данных кодов даст также несколько ложных атрибутов; в нашем конкретном случае — душистый перец, засахаренную вишню, смородиновое желе, арахисовое масло и перец. Это вызовет ложные выпадения при некоторых запросах 1тем самым будет предложено разработать новый рецепт — — РПожновыпадающее печенье"! э)).
Для табл. 2 кодирование методом наложения работает не так уж хорошо, поскольку эта таблица представляет всего лишь маленький пример с большим количеством атрибутов. В самом деле, "Печенье с яблочным соусом" будет выпадать при каждом запросе, поскольку оно получено наложением семи кодов, покрывающих все десять позиций. Еще хуже обстоят дела в случае рецепта печенья с перцем (впрочем, с точки зрения кодов и ложных выпадений совершенно все равно, как получена цепочка из десяти единиц: наложением семи или двенадцати кодов. — Прим.
перев.), полученного в результате наложения двенадцати кодов. С другой стороны, иногда табл. 2 работает на удивление неплоха: например, дав запрос "Ванилин", мы получим только одно ложное выпадение — 'Печенье с перцем". Более подходящий пример кодиронания методом наложения получается при наличии, скажем, 32-битового поля и набора из (э) = 4 960 различных атрибутов, где каждая запись может иметь до шести атрибутов и каждый атрибут кодируется тремя из 32 бит.
В этой ситуации в предположении, что каждан запись имеет шесть случайно выбранных атрибутов, вероятности ложных выпадений в случае включающего запроса составляют: Таблица 2 ПРИМЕР КОДИРОВАНИЯ МЕТОДОМ НАЛОЖЕНИЯ Наложенные коды 0000100100 Медовые пряники 1111111!11 Меренги 1000111111 Моравское печенье со специями 0010101101 Овсяные палочки с финиками 0001111101 Старивиое сахарное печенье 1011110111 1000101100 1001110011 1000!00100 0000011011 0010001101 0000001001 111ГП1111 0000001001 Печенье с арахисовым маслом Юбочки 0010001001 0111110110 0010101100 0001111101 Печенье с перцем Шотландские овсяные коржики Песочиые звездочки Анисовое леченье Воздушное печенье Пирог с начинкой Финский кахар Глазированные имбирные пряники Печенье с орехами Драгоценное печенье 0000000000 0011011000 0000001001 1011101101 О!ОО1ОО!О! 1001110010 0000000000 1000000010 0010101101 0000101101 Шведский крендель Швейцарское рассыпчатое печенье с корицей Ириски Ванильио-ореховое мороженое 1101010110 ОО!0101101 1000001011 1011100101 Перепутаница Малайский крендель Таким образом, если имеется М записей, которые не удовлетворяют двухатрибутному запросу, та окало 0.007М записей будут иметь наложенные коды, соответствующие всем битам этих двух атрибутов (все вероятности вычисляются в упр.
4). Общее количество битов, необходимых для представления инвертированного файла, составляет 32, умноженное на количество записей, чта меньше половины количества битов, требуемых для описания всех атрибутов в исходном файле. Экстракт миндаля Душистый перец Зерна аниса Яблочный соус Абрикос Бананы Засахаренная вишня Кардамон Шоколад Корица Цу Гвоздика Кокосовый орех Кофе Смородииовое желе Миндальные вафли с ромом Печенье с яблочным соусом Бананово-овсяное печенье Шоколадный хворост Миндальное печенье с кокосами Печенье со сливочным сыром Ароматные палочки с черносливом Драже в шоколаде Райские палочки Коды отдельных 0100000001 0000100001 0000011000 0010010000 1000010000 0000100010 0000101000 1000000001 0010001000 1000000010 0100000010 0001100000 0001010000 0001000100 0010000001 приправ Финики Имбирь Мед Лимонный сок Лимонная цедра Мускатный цвет Патока Мускатный орех Орехи Апельсины Арахисовое масло Перец Чернослив Изюм Ванилин 1000000100 0000110000 0000000011 1000100000 0011000000 0000010100 1001000000 0000010010 0000100100 0100000100 0000000101 0010000100 0010000010 0101000000 0000001001 При аккуратном игпользовании неслучайных кодов можно избежать ложных выпадений, как показано в работе %".
Н. КапСх апс( В. С. 81пя1есоп, 1ЕЕЕ Тгапа 1Т-10 (1964), 363 — 377; одна из таких конструкций рассматривается в упр. 16. Малкольм Ч. Харрисон (Ма!со!ш С. Нагпэоп) [САСМ 14 (1971), 777 — 779) обнаружил, что кодирование методом наложении может использоваться для ускорения поиска тпексгла.
Пусть нужно найти все вхождения некоторой строки символов в тексте большога объема без построения обширных таблиц алгоритма 6.3Р. Предположим также, что текст разделен на строки, например, по 50 символов: ос се... сш. Харрисон предложил кодировать каждую из 49 пар сссю сэсэ, ... „с4эсэв методом хеширования каждой из них в число, скажем, от 0 до 127, а затем подсчитать "ключ" строки с,сэ ..
сэв, который представляет собой строку из 128 бит ЬеЬ,...Ьщг, где Ь, = 1 тогда и только тогда, когда 6(с,су с) = 1 для некоторого 71 Пусть необходимо найти все вхождения слова МЕЕООЕ (ИГОЛКА) в болыпам файле с именем НАУНТАСК (СТОГ СЕНА). При этом мы просто просмотрим все строки, ключи которых содержат 1 в позициях 6(МЕ), 6(ЕЕ), 6(ЕО), 6(ОЦ и 6(1.Е). Считая хешфункцию случайной, вероятность того, что случайная строка содержит все эти биты в своем ключе, можно оценить как 0.00341 (см. упр. 4). Следовательно, пересечение пяти инвертированных списков битовых строк позволит быстро обнаружить все строки, содержащие МЕЕО1.Е (естественно, с некоторым количеством ложных выпадений).
Предположение случайности на самом деле мало применимо для текста, поскольку обычный текст весьма избыточен и пары символов в нем распределены весьма неравномерно. Например, может оказаться полезным опустить все пары с су+м содержащие символ пробела, в связи с тем, что пробел встречается в тексте гораздо чаще прочих символов. Другое интересное приложение кодирования методом наложения к задачам поиска было предложена Бартоном Блюмам (Впгсоп В!оогп) (САСМ 13 (1970), 422 — 426). Его метод на самом деле применим для выборки по первичнььи ключам, хотя более подходящее место для ега обсуждения — этот раздел. Представьте себе приложение для поиска в большой базе данных, которое не требует каких-либо дальнейших действий, если поиск оказался неудачным.
Например, нужно просто проверить чыа-то кредитную карточку или номер паспорта и, если в файле нет записей о данной персоне, никаких дальнейших действий предпринимать не требуется. Аналогичный метод применим и при компьютерной верстке для правильных переносов слов. Например, у нас есть метод расстановки переносов, корректно работающий с большинством слов, но имеющий некоторое количество исключений на 50000 слов; егли слово не найдено в файле исключений, можно использовать простой алгоритм.
В такой ситуации можно хранить таблицу битов во внутренней памяти, чтобы отсутствие большинства ключей распознавалась беа обращений к внешней памяти. Вот как это можно сделать: обозначим внутреннюю битовую таблицу через Ьвбс... Ьм м где ЛТ очень велико. Для каждого ключа Л„в файле вычислим Й независимых хеш-функций 61(К,),..., 6ь(К ) и установим соответствующие 6 бвт равными 1 (эти 6 значений не обязаны быть различными). Таким образом, Ь; = 1 тогда и только тогда, когда lм(К.) =1 для некоторых у и 1.
Теперь, чтобы определить наличие аргумента поиска К во внешнем файле, сначала выясним, справедливо ли соотношение Ьм~к~ = 1 при 1 (1 < 6. Если нет, то нет и необходимости обращаться к внешней памяти, но если соотношение справедливо, то при корректном выборе Ь и М последовательный поиск, вероятно, найдет К. Вероятность ложного выпадения при Аг записях в файле равна примерно (1 — е "лузг)ь.
По сути, метод Блума рассматривает весь файл как одну запись, в которой первичные ключи представлены как атрибуты, а кодирование методом наложения производится в огромном М-битовом поле. Еще один вариант кодирования методом наложения был разработан Ричардам А. Густафсоном (ВлсЬагд А. Опяса1яоп) [РЬ. П. 1Ьея1я (11шч. ВопяЬ Саго!ша, 1969)]. Предположим, что есть Аг записей и что каждая из них имеет шесть атрибутов, выбранных из 10000 возможных. Запись может представлять, например, техническую статью, а атрибуты — ключевые слова, описывающие зту статью.
Пусть Ь вЂ” зто хеш-функция, отображающая каждый атрибут в число между 0 и 15. Запись с атрибутами аг, ая,..., ая Густафсон предлагает отображать в 16-битовое число Ьяб,...бнп где Ь; = 1 тогда и только тогда, когда Ь(а ) = 1 для некоторого ~. И далее, если талька б < 6 бит Ь равны 1, то другие 6 — Ь единиц добавляются некоторым случайным методом (необязательна зависящим от самой записи). Дано ['яЯ) = 8008 16-битовых кодов, в которых имеется ровно шесть единичных битов, и при определенной доле везения примерно Аг/8008 записей будут отображены на каждое значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
