Репетиторам – НЕТ !

2.6 Применение методов хеширования для поиска по соответствию

Напомним, что основная цель введения адресации по содержанию состояла в выделении всех элементов, определенные фрагменты которых в точности совпадали бы с заданным аргументом поиска. Очевидно, что работа биологической ассоциативной памяти построена несколько на иных принципах. Например, человек способен воспроизводить события, часто руководствуясь весьма неопределенной ключевой информацией. Однако важнейшая особенность памяти человека, отличающая ее от АЗУ ЭВМ, состоит в том, что она не производит перебора всей информации, отвечающей в какой-то мере ключевой, а концентрируется обычно на одном воспоминании, степень совпадения для которого оказывается максимальной. Вероятно, процесс выборки данных из биологической памяти более близок к работе устройств, предназначенных для распознавания образов.

В этих устройствах объект представляется в виде набора сигналов, формируемых во времени либо параллельно, либо последовательно. В результате анализа некоторых характеристик указанного набора (часто именуемых признаками) устройство выдает решение, позволяющее либо идентифицировать объект, либо причислить его к определенному классу. Классический подход к машинному распознаванию образов базируется на применении систем, получивших название персептрон.

Персептрон – система автоматического распознавания образов, реализующая корректируемое в процессе обучения персептрона решающее правило в пространстве вторичных признаков, которые обычно являются фиксированными заранее случайно выбранными линейными пороговыми функциями от первичных признаков.

Математическим аналогом персептрона является дискриминантная функция.

(Дискриминант – на языке Ада -  отличительный компонент объекта, или значение именуемого типа).

Для каждой категории образов, подлежащих распознаванию, строится своя дискриминантная функция, которая при подстановке в нее соответствующего набора значений входных сигналов дает результат в виде скалярной величины. Решение о принадлежности заданного образа к одному из классов принимается исходя из сравнения результатов, полученных для различных дискриминантных функций.

Отметим, что создание электронных схем параллельного действия для устройств типа персептрона представляет собой крайне сложную техническую задачу.

Более перспективны программные методы, позволяющие достаточно эффективно решать аналогичные задачи.

Рассмотрим эти методы.

Если признаки принимают только дискретные значения, то процедуры классификации можно построить на базе методов хеширования. Одна из таких непосредственно реализует способ выборки и названа поиском по соответствию.

Эта процедура осуществляет идентификацию одного или нескольких образов, обладающих наибольшим сходством с заданным поисковым аргументом. Основная идея этого метода заключается в том, что ключевое слово или соответствующий фрагмент данных преобразуется в набор атрибутов или признаков. Далее полученные признаки рассматриваются как новые ключевые слова, по которым производится выборка записи из таблицы хеширования. Принципиальным элементом данного метода является также процедура статистической обработки результатов успешного поиска, проведенного по указанным выше признакам.

Будем рассматривать предлагаемый метод применительно к задаче идентификации слов по аргументу поиска, который представляет собой искаженный вариант одного из хранящихся в памяти слов. Такой подход предполагает, естественно, и коррекцию неправильно заданных слов.

Рассмотрим пример, который должен показать, что с помощью адресации по содержанию можно организовать поиск, исходя  из приближенного описания объекта с применением методов хеширования.

Отметим, что этот метод (предлагаемый Кохоненом) допускает возможность появления искаженных фрагментов в любых не установленных заранее участках ключевой информации.

Процедуры выделения признаков

В рассматриваемом примере ключевое слово раскладывается на ряд признаков, которые служат его локальными характеристиками.

Каждый признак представляет собой небольшую группу букв, причем эти буквы могут накладываться друг на друга. Чтобы локальные ошибки оказывались на минимальном количестве признаков, каждая группа формируется из последовательно расположенных букв.

Группы могут также образовываться по циклическому принципу из букв, стоящих в конце и начале слова. В этом случае надо соблюдать дополнительные соглашения о порядке букв, входящих в подобную группу. Учитывая это, необходимо уметь различать слова, полученные друг из друга путем циклической перестановки букв (например, table и eatable), в группе следует соблюдать тот же порядок букв, что и в исходном слове. Предположим, что локальные признаки должны иметь 3 буквы. В этом случае слову table, например, соответствует такой набор признаков:

Tab, abl, ble, tle, tae.

Признаки, формируемые из n циклически последовательных символов в соответствии с рассмотренным выше правилом, будем называть далее n-граммами (в частности, монограммами, биграммами, триграммами и квадриграммами при n = 1, 2, 3 и 4 соответственно).

Следующая проблема связана с выбором количества символов, образующих признак. Очевидно, что оптимум определяется как содержанием ключевых слов, так и их количеством. Предположим, что используются только буквы английского алфавита. При этом общее количество различных монограмм – 26, биграмм – 676 (262)… Для практических задач этого, по-видимому, недостаточно, поскольку по ним должны вычисляться впоследствии хеш-адреса.

Если же взять триграммы, то их число  = 263 = 17576.

Разумеется, в словах естественного языка будет представлена лишь часть сочетаний. Однако, это число достаточно велико, чтобы выбрать его в качестве диапазона изменения функции хеширования.

Если признаки задавать только триграммами, то минимальная длина слов, в которых при наличии любой одиночной ошибки сохранялся бы, по меньшей мере, один верный признак, составляет  4  символа.

Если же ошибки могут допускаться в более коротких словах, в качестве признаков следует использовать наряду с триграммами также биграммы и монограммы (а это, естественно, приводит к увеличению ключевых слов и требуемого объема памяти).

Хеширование по признакам

Вначале (перед выбором функции хеширования) необходимо выяснить, что происходит с признаками, когда в строке символов, из которых они формируются, образуются ошибки. Эти ошибки можно разделить на 3 категории:

1. ошибки замены (одна буква заменена другой);
2. ошибки включения (введена дополнительная буква);
3. ошибки исключения (буква пропущена).

Появление ошибки типа включения или исключения приводит к тому, что позиции всех букв, расположенных справа от того места, где она произошла, меняются.

Этого не происходит лишь в случае, когда две ошибки противоположного типа компенсируют действие друг друга.

Для того, чтобы в поисковом аргументе, несмотря на возможные искажения, могло сохраниться возможно большее количество правильных хеш-адресов, могут применяться разные методы. Одним из наиболее простых является следующая комбинированная процедура. Она состоит из двух этапов:

1. вычисляются функции хеширования для локальных признаков (n-грамм), не зависящие от их позиций в поисковом аргументе;
2. осуществляется комбинационный поиск, в котором эти признаки используются как ключевые слова. В результате получается целый набор слов.

Количество этих слов можно затем сократить, отбрасывая те слова, у которых признаки по сравнению с поисковым аргументом смещены, например, более чем на 2 позиции.  Число 2 было выбрано исходя из следующих соображений:

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

Поскольку на ключевые слова не накладывается никаких ограничений, их можно рассматривать как строки символов, распределенные случайным образом (необязательно равномерно). Что касается ошибок, так же носящих случайный характер, то вполне допустимо считать их равномерно распределенными по строке. Будем также считать, что ошибки разного типа встречаются с одинаковой вероятностью.

Следует особо отметить, что в нашем случае, в отличие от задачи кодирования с коррекцией ошибок, нельзя построить процедуру идентификации, которая обеспечила бы идентификацию слов произвольного типа со 100 %-й  точностью. Это объясняется тем, что без дополнительной информации установить наличие в слове ошибок принципиально невозможно, ввиду чего вероятность правильной идентификации ключевого слова определяется его содержанием.

Упрощая задачу, будем полагать, что в качестве признаков употребляются только триграммы.

Адреса этих признаков вычисляются следующим образом:

Пусть используется алфавит (A, B, C…) (всего 26 букв).  Обозначив буквы, входящие в триграмму,  как ,  поставим ей в соответствие величину

Если  размер таблицы хеширования равен H, а начинается она с адреса B, то хеш-адрес, вычисляемый методом деления, определяется по формуле:

.

Организация таблицы хеширования

В задачах многоключевого поиска цепочки разных ячеек могут достигать большой длины, поэтому хеш-таблицу желательно хранить во ВЗУ. Размер таблицы должен выбираться достаточно большим, чтобы коэффициент ее заполнения был невелик. При этом можно использовать процедуру линейного пробинга с основанием, равным длине стандартной страницы. Если таблица хранится на ВЗУ, ее целесообразно формировать по клеточному принципу. Применение клеток позволяет также увеличить общий размер таблицы.

В нашем примере число хеш-адресов ограничено количеством различных триграмм, которое для 26-буквенного алфавита составляет лишь 17576. Если использовать клеточную структуру, то размер хеш-таблицы будет равен этому числу, умноженному на количество позиций в каждой клетке.

В таблицах с клеточной структурой клетки могут объединяться в связанные списки. При этом время выборки оказывается вполне приемлемым, хотя метод списков не обеспечивает такого быстродействия, как обычные процедуры хеширования.

Использование метода деления для построения функции хеширования позволяет получить не только равномерное распределение хеш-адресов, но и сократить до минимума пространство, отведенное для записи идентификаторов ключевых слов.

Рассмотренная структура приведена на рисунке 2.15.

A, B, X – признаки-триграммы.

Вследствие коллизии по признаку A использована резервная ячейка, ближайшая незанятая по отношению к вычисленному хеш-адресу.

В каждой ячейке таблицы хеширования помещается идентификатор некоторой триграммы, а также указатель на область документов, в которой хранятся искомые записи. На рисунке 2.15 явно не показано, что таблица построена по клеточному принципу. В качестве резервной ячейки используется позиция клетки, ближайшая к вычисленному адресу (коллизия для А).

По заданному поисковому аргументу из индексной таблицы хеширования извлекается столько указателей, сколько признаков содержится в аргументе. Если хотя бы один из признаков, отвечающих правильному ключевому слову, присутствует в аргументе, то по меньшей мере один указатель дает адрес нужной записи.

Если в поисковом аргументе присутствуют ошибки, то наряду с верными будут выбраны и неправильные указатели. Впрочем, количество различных указателей, во всяком случае, не превышает количества признаков в аргументе, которые на рисунке 2.15 обозначены буквами.

Следующим этапом поиска является более тщательный отбор  записей – кандидатов на выборку. На этом этапе производится сверка позиций, которые триграмма занимает в поисковом аргументе. Если относительное смещение не превышает заданной величины (было предложено ? 2), то считается, что признаки совпадают.

Дальнейшее развитие метода

Рассмотренный метод хеширования с последующей проверкой можно использовать при решении ряда других задач.

1. В частности, с его помощью можно провести комбинационный поиск по нескольких ключевым словам, содержащим (предположительно) ошибки. Последовательность поиска в этом случае, в основном, аналогична рассмотренной выше.

Если имеется несколько аргументов, связанных с одним и тем же ЭД, в ходе записи его признаки независимо друг от друга запоминаются в ячейках индексной таблицы хеширования.

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

С помощью 2-й процедуры для этих указателей вычисляются хеш-функции, которые

- либо заносятся сортировочные таблицы Б и В (рисунок 2.15);

- либо сравниваются с адресами указателей полученных на предыдущем этапе.

По мере перебора аргументов число указателей-кандидатов постоянно уменьшается, и в итоге остаются лишь те, которые с наибольшей вероятностью отвечают  искомым записям.

2. Метод хеширования с проверкой можно усовершенствовать путем введения статистической обработки признаков, благодаря которой удается выявить запись, наиболее похожую на поисковый аргумент. Такой способ поиска часто называют поиском по соответствию. Его можно использовать для решения такой задачи, как коррекция неправильно произнесенных слов. В этом случае поисковый аргумент сравнивается со всеми словами, хранящимися в словаре (выполняющим роль области документов Г на  рисунке 2.15). Выбирается то слово, которое в наибольшей степени соответствует аргументу.

Рассмотрим этот вариант процедуры поиска подробнее.

Статистический анализ признаков при проведении поиска по соответствию

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

Далее остается лишь найти запись, ключевое слово которой имеет максимальное число совпадений с аргументом.

Ранее уже отмечалось, что в расчет берутся только те указатели, у которых в ключевых словах смещение признаков относительно тех же признаков в поисковом аргументе не превышает заданной величины (в нашем примере она ? 2 символическим позициям). Однако при сравнении слов совсем не обязательно ограничиваться только подсчетом отобранных таким способом указателей. Т.к. ключевые слова могут иметь разную длину, можно, например, каким-то образом учитывать и несовпадение размеров.

Результаты ряда экспериментов показывают, что при случайно распределенных ошибках хорошей мерой несходства, которую можно использовать и для распознавания ключевых слов, служит признаковое расстояние FD. Для двух слов X и Y, это расстояние определяется как

FD (X, Y) = max ( nx, ny ) – ne,

где nx и ny – количества признаков, извлеченных соответственно из X и Y.

ne – количество не совпавших признаков.

В методе хеширования с проверкой величина ne равна числу указателей ячейки области документов, у которых смещения признаков не выходят из установленного диапазона.

В ходе каждой операции поиска для подсчета указателей строится таблица совпадений. Указатель, найденный по некоторому признаку в таблице хеширования, заносится в эту таблицу совпадений, если в его ключевом слове обнаруживается такой же признак. Если данный указатель уже имеется в таблице совпадений, то содержимое соответствующего ему счетчика просто увеличивается на 1. В тех случаях, когда количество поисковых аргументов невелико (а обычно так и бывает), сравнение указателей, помещенных в таблицу, может осуществляться путем их последовательного перебора. Если необходимо добиться максимального быстродействия, то таблицу совпадений можно организовать по принципу хеширования.

Рассмотренный метод был опробован в экспериментах с двумя достаточно большими словарями, которые служили источниками ключевых слов. Один из них содержал более тысячи наиболее употребительных английских слов. Второй словарь был составлен из фамилий, взятых из справочника «Кто есть кто в науке», причем некоторые фамилии были      транслитерированы таким образом, что бы их можно было записать буквами английского алфавита. Было исследовано действие всевозможных типов одиночных и двойных ошибок.

Одиночные ошибки задавались поочередно в каждой символьной позиции каждого слова. Что касается двойных ошибок, то они формировались при помощи ДСЧ таким образом, что  вероятность появления любой неправильной буквы в любой позиции была одинакова.

В результате экспериментов была собрана весьма внушительная статистика:

• к каждому из 2-х словарей было произведено ~ 50.0 тыс. обращений по аргументам поиска, содержащим ошибки.

Усредненные цифры, выражающие относительное количество успешных операций поиска, приведены в таблице.

Были оценены:

Зависимость точности восстановления неправильно записанных слов, входящих в набор из 1021 наиболее употребительного английского слова, от их длины (строки) при различных сочетаниях ошибок (столбцов).

Все результаты выражены в процентах (данные округлены).

Уровень 1 – относится к тем реализациям, в которых правильное слово имеет минимальное значение FD среди всех кандидатов на выборку.

Уровень 2 – относится к реализациям, в которых правильному слову соответствовал либо наименьший показатель FD, либо ближайший к нему.