2.6 Применение методов хеширования для поиска по соответствию
Напомним, что основная цель введения адресации по содержанию состояла в выделении всех элементов, определенные фрагменты которых в точности совпадали бы с заданным аргументом поиска. Очевидно, что работа биологической ассоциативной памяти построена несколько на иных принципах. Например, человек способен воспроизводить события, часто руководствуясь весьма неопределенной ключевой информацией. Однако важнейшая особенность памяти человека, отличающая ее от АЗУ ЭВМ, состоит в том, что она не производит перебора всей информации, отвечающей в какой-то мере ключевой, а концентрируется обычно на одном воспоминании, степень совпадения для которого оказывается максимальной. Вероятно, процесс выборки данных из биологической памяти более близок к работе устройств, предназначенных для распознавания образов.
В этих устройствах объект представляется в виде набора сигналов, формируемых во времени либо параллельно, либо последовательно. В результате анализа некоторых характеристик указанного набора (часто именуемых признаками) устройство выдает решение, позволяющее либо идентифицировать объект, либо причислить его к определенному классу. Классический подход к машинному распознаванию образов базируется на применении систем, получивших название персептрон.
Персептрон – система автоматического распознавания образов, реализующая корректируемое в процессе обучения персептрона решающее правило в пространстве вторичных признаков, которые обычно являются фиксированными заранее случайно выбранными линейными пороговыми функциями от первичных признаков.
Математическим аналогом персептрона является дискриминантная функция.
(Дискриминант – на языке Ада - отличительный компонент объекта, или значение именуемого типа).
(далее…)
27.02.09 значение, идентификатор, коллизия, процедура, расстояние, способ, функции, хеш-функции, цифры, ЭВМ, элемент Ассоциативная память и ассоциативные процессоры в интеллектуальных компьютерах
2.5 Многоключевой поиск
В таблицах символов обычно существует взаимно однозначное соответствие между ключевым словом и связанным с ним значением. Последнее (т.е. значение) может быть абсолютным или относительным адресом некоторой переменной, участвующей в программе. Иная ситуация наблюдается в разного рода справочниках, списках заказчиков и других документах, содержащих информацию относительного характера. В них, как правило, каждый запоминаемый элемент данных (ЗЭД) снабжается несколькими ключевыми словами, или дескрипторами, причем одно и то же ключевое слово может присутствовать в произвольном количестве записей. Например, в анкетных файлах атрибут “пол” (представленный в двоичной форме), принимает одинаковые значения, по меньшей мере, в половине записей.
Для тех задач, в которых часто возникает необходимость в выборке всех элементов, отвечающих заданному ключу, наиболее подходят последовательные методы поиска. Такова, в частности, задача селективного отбора информации.
Селективный отбор информации является одной из форм обслуживания, предоставляемого современными библиотеками.
Абоненты (библиотек) описывают совокупность интересующих их предметов в виде логического выражения, содержащего набор соответствующих дескрипторов. ЭВМ одновременно обрабатывает запросы большого количества абонентов, сравнивая представленные ими данные с дескрипторами, записанными в документах. При этом могут использоваться различные функции, с помощью которых устанавливается степень сходства сравниваемых дескрипторов.
(далее…)
27.02.09 Абоненты, ЗЭД, инвертированный, Многоключевой поиск, Мультисписки, набор, подходы Ассоциативная память и ассоциативные процессоры в интеллектуальных компьютерах
2.4 Структура и форматы таблиц хеширования
2.4.1 Непосредственная и косвенная адресация
а) Индексные таблицы хеширования (ТХ)
Для размещения данных, хранящихся в ТХ совместно с ключевыми словами или их идентификаторами, часто требуются большие объемы памяти. Размеры ЭД могут изменяться, однако, как правило, таблицы хеширования строятся исходя из максимальной длины. В результате – часть памяти используется непроизводительно. Кроме того, с увеличением длины записей возрастает трудоемкость (время) поиска. Допуская некоторые увеличения количества обращений к памяти (что неизбежно при использовании многоуровневой памяти) можно повысить эффективность поиска. Для этого ЭД необходимо размещать в специально отведенной области, а в основной таблице хеширования хранить только указатели, содержащие адреса элементов в этой области, а также соответствующие идентификаторы. При такой структуре в процессе поиска проверке подвергаются только ключевые слова (или их идентификаторы) и обращение к отдельной области памяти производится только после того, как будет найден требуемый элемент. Преимущество предлагаемой схемы также состоит в том, что при необходимости основную таблицу хеширования (которую в дальнейшем будем называть индексной таблицей хеширования) можно без особых затруднений поместить в другую область.
Индексные таблицы хеширования достаточно распространены, особенно в СУБД. Однако с их помощью не всегда удается достичь желаемого результата. Например, при использовании только коротких имен (ключевых слов), внутренней адресации (т.е. цепочек внутри ТХ, и т.д.).
б) Комбинированная адресация в хеш-таблице (ступенчатое хеширование)
Рассмотренный выше принцип построения ТХ можно рассматривать как простейшую форму косвенной адресации. Такая адресация является обязательным элементом индексной хеш-таблицы. Ее можно сделать более эффективно, если наряду с косвенной адресацией использовать и прямую (непосредственную) адресацию. Для задания режима адресации в каждой ячейке таблицы отводится специальный разряд, именуемый флажком связи.
(далее…)
27.02.09 Буферизация, ВЗУ, вычеркивания, занято, объемы памяти, ТХ, ЭД Ассоциативная память и ассоциативные процессоры в интеллектуальных компьютерах
2.3 Обработка коллизий
2.3.1 Основные концепции
Все существующие методы обработки коллизий можно разделить на две основные категории:
- методы, называемые внутренней адресацией, в которых в качестве резервных используются ячейки самой таблицы хеширования;
- методы, в которых для хранения элементов с одинаковыми хеш-адресами отводится специальная область переполнения.
Для внутренней адресации используются различные, часто сложные, алгоритмы, позволяющие повысить эффективность поиска. В отличие от этих методов – методы 2-го типа (переполнения) – достаточно просты.
Если определить эффективность как среднее число операций поиска, необходимых для выборки одного элемента таблицы, то преимущество 2-й группы методов может показаться очевидным. Тем не менее, больше применяются методы 1-й группы (т.е. внутренняя адресация).
Процедура, при помощи которой в методе внутренней адресации отыскиваются резервные ячейки, получила название пробинга. В сущности, пробинг является методом проб и ошибок, примененным к поиску пустой ячейки. Какой бы конкретный алгоритм ни был положен в основу этой процедуры, последовательность определяемых им действий обязательно должна быть детерминированной, т.к. при записи и выборке ЭД выполняются одни и те же операции.
Разработано много различных высокоэффективных алгоритмов пробинга, о некоторых из них кратко будет сказано ниже.
(далее…)
27.02.09 квадратичный, линейный, пробинг, процедура, случайный, способ Ассоциативная память и ассоциативные процессоры в интеллектуальных компьютерах
2.2 Функции хеширования
2.2.1 Как уже отмечалось, основная идея хеширования заключается в том, что элемент данных заносится в память по адресу, который легко вычислить, зная содержимое ключевого слова (КлСл), присвоенного этому элементу. На выбор КлСл не накладывается практически никаких ограничений: могут использоваться обычные имена или произвольные числовые коды (ЧК), причем к ним не требуется добавлять какие-нибудь контрольные метки или символы. Длина КлСл также выбирается произвольно, хотя в вычислениях участвуют обычно только несколько первых символов. В результате набор или область допустимых слов (т.е. пространство имен) оказывается весьма обширным. Например, количество слов, которые можно составить из шести букв английского алфавита = 256 млн. (≈ 300 млн.!) 
.
Первая мысль, которая приходит в голову при рассмотрении возможных вариантов преобразования пространства имен в пространство адресов (ПрИм → ПрАдр) – это желание осуществить тем или иным способом сжатие пространства имен (ПрИм). Коэффициент заполнения ПрИм в реальных условиях оказывается крайне малым. Поэтому хотелось бы подобрать такую функцию, у которой в области значений (совпадающей с адресным пространством) адреса распределялись бы более равномерно и с большей плотностью.
Если бы ключевым словам были поставлены в соответствие некоторые числовые значения v, случайно распределенные по закону, близкому к равномерному, то задача решалась бы достаточно просто.
Обозначим F(v) интегральную функцию распределения случайной переменной v. Если в качестве хеш-адреса, соответствующего данному v, взять величину 
, где
H – общее количество допустимых адресов;
B – первый адрес,
то на отрезке [B, B+H] хеш-адреса будут распределены равномерно.
(далее…)
27.02.09 алгоритм, алфавит, перевод, Рандомизация, функции, хеш-функции Ассоциативная память и ассоциативные процессоры в интеллектуальных компьютерах