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