Лекция
№ 11
Тема: «Хеширование данных. Поиск в тексте»
План
лекции
1. Хеширование данных
2. Использование деревьев в задачах поиска
3. Поиск в тексте
1.
Хеширование данных
В рассмотренных выше методах поиска число итераций в лучшем случае было пропорционально O(log n). Естественно, возникает желание найти такой метод поиска, при котором число итераций не зависело бы от размера таблицы, а в идеальном случае поиск сводился бы к одному шагу.
Простейшей организацией таблицы, обеспечивающей идеально быстрый поиск, является таблица прямого доступа. В такой таблице ключ является адресом записи в таблице или может быть преобразован в адрес, причем таким образом, что никакие два разных ключа не преобразуются в один и тот же адрес. При создании таблицы выделяется память для хранения всей таблицы и заполняется пустыми записями. Затем записи вносятся в таблицу – каждая на свое место, определяемое ее ключом. При поиске ключ используется как адрес и по этому адресу выбирается запись, если выбранная запись пустая, то записи с таким ключом вообще нет в таблице. Таблицы прямого доступа очень эффективны в использовании, но, к сожалению, область их применения весьма ограничена.
Назовем пространством ключей множество всех теоретически возможных значений ключей записи. Назовем пространством записей множество тех ячеек памяти, которые выделяются для хранения таблицы.
Таблицы прямого доступа применимы только для таких задач, в которых размер пространства записей может быть равен размеру пространства ключей. В большинстве реальных задач, однако, размер пространства записей много меньше, чем пространства ключей. Так, если в качестве ключа используется фамилия, то, даже ограничив длину ключа 10 символами кириллицы, получаем 3310 возможных значений ключей.
Даже если ресурсы вычислительной системы и позволят выделить пространство записей такого размера, то значительная часть этого пространства будет заполнена пустыми записями, так как в каждом конкретном заполнении таблицы фактическое множество ключей не будет полностью покрывать пространство ключей.
Из соображений экономии памяти целесообразно назначать размер пространства записей, равным размеру фактического множества записей или превосходящим его незначительно. В этом случае необходимо иметь некоторую функцию, обеспечивающую отображение точки из пространства ключей в точку в пространстве записей, т. е., преобразование ключа в адрес записи: a := h(k), где a – адрес, k – ключ. Такая функция называется функцией хеширования (другие ее названия – функция перемешивания, функция рандомизации).
Идеальной хеш-функцией является такая функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса: k1 ≠ k2 ⇒ h(k1) ≠ h(k2).
При попытке отображения точек из некоторого широкого пространства в узкое неизбежны ситуации, когда разные точки в исходном пространстве отобразятся в одну и ту же точку в целевом пространстве.
Ситуация, при которой разные ключи отображаются в один и тот же адрес записи, называется коллизией, или переполнением, а такие ключи называются синонимами. Коллизии составляют основную проблему для хеш-таблиц и решение ее будет рассмотрено особо.
Если хеш-функция, преобразующая ключ в адрес, может порождать коллизии, то однозначной обратной функции: k := h’(a), позволяющей восстановить ключ по известному адресу, существовать не может. Поэтому ключ должен обязательно входить в состав записи хешированной таблицы как одно из ее полей.
К хеш-функции в общем случае предъявляются
следующие требования:
– она должна обеспечивать равномерное распределение отображений фактических ключей по пространству записей (рис. 2);
– она должна порождать как можно меньше коллизий для данного фактического множества записей;
– она не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов;
– она должна быть простой и быстрой для вычисления.
Приведем обзор и анализ некоторых наиболее простых из применяемых на практике хеш-функций.
Простейшей хеш-функцией является деление по модулю числового значения ключа на размер пространства записи. Результат интерпретируется как адрес записи. Следует иметь в виду, что такая функция плохо соответствует первым трем требованиям к хеш-функции и сама по себе может быть применена лишь в очень ограниченном диапазоне реальных задач. Однако операция деления по модулю обычно применяется как последний шаг в более сложных функциях хеширования, обеспечивая приведение результата к размеру пространства записей.
Следующей хеш-функцией является функция середины квадрата. Значение ключа преобразуется в число, это число затем возводится в квадрат, из него выбираются несколько средних цифр и интерпретируются как адрес записи.
Еще одной хеш-функцией можно назвать функцию свертки. Цифровое представление ключа разбивается на части, каждая из которых имеет длину, равную длине требуемого адреса. Над частями производятся какие-то арифметические или поразрядные логические операции, результат которых интерпретируется как адрес. Например, для сравнительно небольших таблиц с ключами – символьными строками неплохие результаты дает функция хеширования, в которой адрес записи получается в результате сложения кодов символов, составляющих строку ключ.
В качестве хеш-функции также применяют функцию преобразования системы счисления. Ключ, записанный как число в некоторой системе счисления P, интерпретируется как число в системе счисления Q > P. Обычно выбирают Q = P+1. Это число переводится из системы Q обратно в систему P, приводится к размеру пространства записей и интерпретируется как адрес.
2.
Использование деревьев в задачах поиска
Обычные деревья не дают выигрыша при хранении множества значений. При поиске элемента все равно необходимо просмотреть все дерево. Однако можно организовать хранение элементов в дереве так, чтобы при поиске элемента достаточно было просмотреть лишь часть дерева. Для этого надо ввести следующее требование упорядоченности дерева.
Двоичное дерево упорядочено, если для любой вершины x справедливо такое свойство: все элементы, хранимые в левом поддереве, меньше элемента, хранимого в x, а все элементы, хранимые в правом поддереве, больше элемента, хранимого в x.
Важное свойство упорядоченного дерева: все элементы его различны. Если в дереве встречаются одинаковые элементы, то такое дерево является частично упорядоченным.
В дальнейшем будет идти речь только о двоичных упорядоченных деревьях, опуская слово «упорядоченный».
Итак, основными операциями, производимыми с упорядоченным деревом, являются:
– поиск вершины;
– добавление вершины;
– удаление вершины;
– очистка дерева.
Алгоритм поиска можно записать в рекурсивном виде. Если искомое значение Item меньше Tree^.Data, то поиск продолжается в левом поддереве, если равен – поиск считается успешным, если больше – поиск продолжается в правом поддереве; поиск считается неудачным, если достигли пустого поддерева, а элемент найден не был.
function
Find_Tree(Item: TypeElement; Tree: PTree): boolean;
{Поиск вершины дерева, содержащую значение Item}
var
Current: PTree;
begin
Find_Tree := False;
if Tree <> nil then begin {Дерево не пустое}
Current := Tree;
if Current^.Data = Item then {Вершина найдена}
Find_Tree := True
else
if Current^.Data > Item then {Ищем в левом поддереве}
Find_Tree := Find_Tree(Item,
Current^.Left)
else {Ищем в правом поддереве}
Find_Tree := Find_Tree(Item,
Current^.Right);
end;
end;
Алгоритма добавления элемента в дерево. Сначала надо найти вершину, к которой в качестве потомка необходимо добавить новую вершину (фактически произвести поиск), а затем присоединить к найденной новую вершину, содержащую значение Item.
Алгоритм удаления элемента будет несколько сложнее. При удалении может случиться, что удаляемый элемент находится не в листе, т. е. вершина имеет ссылки на реально существующие поддеревья. Эти поддеревья терять нельзя, а присоединить два поддерева на одно освободившееся после удаления место невозможно. Поэтому необходимо поместить на освободившееся место либо самый правый элемент из левого поддерева, либо самый левый из правого поддерева.
Временная сложность этих алгоритмов (она одинакова для этих алгоритмов, так как в их основе лежит поиск) оценим для наилучшего и наихудшего случая. В лучшем случае, т. е. случае полного двоичного дерева, получаем сложность Omin(log n). В худшем случае дерево может выродиться в список. Такое может произойти, например, при добавлении элементов в порядке возрастания. При работе со списком в среднем придется просмотреть половину списка. Это даст сложность Omax(n).
В алгоритме очистки дерева применяется обратный метод обхода дерева. Использование обратного метода обхода гарантирует, что будут сначала посещены и удалены все потомки предка, прежде чем удалится сам предок.
3.
Поиск в тексте
Часто приходится сталкиваться со специфическим поиском, так называемым поиском слова. Его можно определить следующим образом.
Пусть задан массив Txt из N элементов, называемый текстом и массив Wrd из M элементов, называемый словом, причем 0 < M ≤ N. Описать их можно как строки.
Поиск слова обнаруживает первое вхождение Wrd в Txt. Это действие типично для любых систем обработки текстов, отсюда и очевидная заинтересованность в поиске эффективного алгоритма для этой задачи.
Задачи поиска слова в тексте используются в криптографии, различных разделах физики, сжатии данных, распознавании речи, сравнении участков ДНК и других сферах человеческой деятельности.
Прямой поиск
Разберем алгоритм поиска, который будем называть прямым поиском строки. Данный алгоритм заключается в посимвольном сравнении текста со словом. В начальный момент происходит сравнение первого символа текста с первым символом слова, второго символа текста со вторым символом слова и т. д. Если произошло совпадение всех символов, то фиксируется факт нахождения слова. В противном случае производится «сдвиг» слова на одну позицию вправо и повторяется посимвольное сравнение, т. е. сравнивается второй символ текста с первым символом слова, третий символ текста со вторым символом слова и т. д.
Эти «сдвиги» слова повторяются до тех пор, пока конец слова не достиг конца текста или не произошло полное совпадение символов слова с текстом (т. е. слово найдено).
Этот алгоритм работает достаточно эффективно, если допустить, что несовпадение пары символов происходит после незначительного количества сравнений во внутреннем цикле. При достаточно большом множестве символов это довольно частый случай. Можно предполагать, что для текстов, составленных из 128 символов, несовпадение будет обнаруживаться после одной или двух проверок. Тем не менее, в худшем случае алгоритм будет малоэффективен, так как его сложность будет пропорциональна
O((N – M)·M).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.
Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.
Алгоритм прямого поиска
Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,
Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.
Сложность алгоритма:
Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).
Недостатки алгоритма:
1. высокая сложность — O(N*M), в худшем случае – Θ((N-M+1)*M);
2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);
3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.
Программная
реализация
#include <iostream.h>
//прямой поиск
int
DirectSearch(char t[], char w[]);
int
main()
{
system("chcp 1251>nul");
char text[250],word[50];
cout<<"Введите текст";
cin.getline(text,250);
cout<<"Введите слово";
cin.getline(word,50);
int k=DirectSearch(text, word);
cout<<"k="<<k+1<<endl;
system("pause");
return 0;
}
int
DirectSearch(char t[], char w[]){
int tl, wl;
int res = -1;
tl = strlen(t);
wl = strlen(w);
if ( tl == 0 )
cout
<< "Неверно задана строка\n";
else if ( tl
== 0 )
cout
<< "Неверно задана подстрока\n";
else
for (int i = 0; i < tl - wl + 1; i++)
for (int j = 0; j < wl; j++)
if ( w[j] != t[i+j] )
break;
else if ( j == wl - 1 ){
res = i;
break;
}
return res;
}
Алгоритм Кнута,
Мориса и Пратта
Приблизительно в 1970 году Д. Кнут, Д. Морис и В. Пратт изобрели алгоритм (КМП-алгоритм), фактически требующий только O(N) сравнений даже в самом плохом случае. Новый алгоритм основывается на том соображении, что после частичного совпадения начальной части слова с соответствующими символами текста фактически известна пройденная часть текста и можно «вычислить» некоторые сведения (на основе самого слова), с помощью которых затем быстро продвинуться по тексту.
Основным отличием КМП-алгоритма от алгоритма прямого поиска является выполнение сдвига слова не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Таким образом, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим.
Если j определяет позицию в слове, содержащую первый несовпадающий символ (как в алгоритме прямого поиска), то величина сдвига Shift определяется как j – LenSuff–1. Значение LenSuff определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j (суффикс), которая полностью совпадает с началом слова. LenSuff зависит только от слова и не зависит от текста. Для каждого j будет своя величина Shift, которую обозначим Shift j.
Приведенный на рисунке пример поиска слова ABCABD показывает принцип работы такого алгоритма. Символы, подвергшиеся сравнению, здесь подчеркнуты. Обратите внимание: при каждом несовпадении пары символов слово сдвигается на переменную величину, и меньшие сдвиги не могут привести к полному совпадению.
Точный анализ КМП-алгоритма весьма сложен. Его изобретатели доказывают, что требуется порядка O(M + N) сравнений символов, что значительно лучше, чем O((N – M)·M) сравнений при прямом поиске.
Пример.
(Символы, подвергшиеся сравнению, подчеркнуты.)
Особенности КМП-поиска:
1. требуется порядка (N+M) сравнений символов для получения результата;
2. схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на единицу. К несчастью совпадения встречаются значительно реже чем несовпадения. Поэтому выигрыш от КМП-поиска в большинстве случаев текстов весьма незначителен.
Программная
реализация:
#include <iostream.h>
//прототип подпрограммы поиска методом
Кнута, Морриса и Пратта
int
KMPSearch(char *t, char *w);
int
main()
{
system("chcp 1251>nul");
char text[250],word[50];
cout<<"Введите текст";
cin.getline(text,250);
cout<<"Введите слово";
cin.getline(word,50);
int k=KMPSearch(text, word);
cout<<"k="<<k+1<<endl;
system("pause");
return 0;
}
//реализация подпрограммы поиска
методом Кнута, Морриса и Пратта
int
KMPSearch(char *t, char *w){
int
tl, wl;
int res = -1;
tl = strlen(t);
wl = strlen(w);
if ( tl == 0 )
cout
<< "Неверно задана строка\n";
else if ( wl
== 0 )
cout
<< "Неверно задана подстрока\n";
else {
int
i, j = 0, k = -1;
int
*d;
d =
new int[1000];
d[0] = -1;
while ( j < wl - 1 ) {
while ( k >= 0 && w[j] != w[k]
)
k = d[k];
j++;
k++;
if ( w[j] == w[k] )
d[j] = d[k];
else
d[j] = k;
}
i = 0;
j = 0;
while ( j < wl && i < tl ){
while ( j >= 0 && t[i] != w[j]
)
j = d[j];
i++;
j++;
}
delete [] d;
res =
j == wl ? i - wl : -1;
}
return res;
}
Алгоритм Боуера и
Мура
КМП-алгоритм дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае слово сдвигается более чем на единицу. К несчастью, это скорее исключение, чем правило: совпадения встречаются значительно реже, чем несовпадения. Поэтому выигрыш от использования КМП-алгоритма в большинстве случаев поиска в обычных текстах весьма незначителен.
Метод же, предложенный Р. Боуером и Д. Муром в 1975 году (БМ-алгоритм), не только улучшает обработку самого плохого случая, но дает выигрыш в промежуточных ситуациях.
БМ-алгоритм основывается на необычном соображении – сравнение символов начинается с конца слова, а не с начала. Как и в случае КМП-алгоритма, перед фактическим поиском на основе слова формируется некоторая таблица. Пусть для каждого символа x из алфавита величина Shiftx – расстояние от самого правого в слове вхождения x до правого конца слова. Представим себе, что обнаружено расхождение между словом и текстом, причем символ в тексте, который не совпал, есть x. В этом случае слово сразу же можно сдвинуть вправо так, чтобы самый правый символ слова, равный x, оказался бы в той же позиции, что и символ текста x. Этот сдвиг, скорее всего, будет на число позиций, большее единицы. Если несовпадающий символ текста x в слове вообще не встречается, то сдвиг становится даже больше: сдвигаем вправо так, чтобы ни один символ слова не накладывался на символ x. На рисунке приведен пример, иллюстрирующий этот процесс.
Почти всегда, кроме специально построенных примеров, данный алгоритм требует значительно меньше O(N) сравнений. В самых же благоприятных обстоятельствах, когда последний символ слова всегда попадает на несовпадающий символ текста, число сравнений пропорционально O(N/M).
Авторы алгоритма приводят и несколько соображений по поводу дальнейших усовершенствований алгоритма. Одно из них – объединить приведенную только что стратегию, обеспечивающую большие сдвиги в случае несовпадения, со стратегией Кнута, Морриса и Пратта, допускающей «ощутимые» сдвиги при обнаружении совпадения (частичного). Такой метод требует двух таблиц, получаемых при пред трансляции: Shift' – только что упомянутая таблица, а Shift'' – таблица, соответствующая КМП-алгоритму. Из двух сдвигов выбирается больший. Дальнейшее обсуждение этого предмета приводить не будем, поскольку дополнительное усложнение формирования таблиц и самого поиска, возможно, не оправдает видимого выигрыша в производительности. Фактические дополнительные расходы будут высокими и неизвестно, приведут ли все эти ухищрения к выигрышу или проигрышу.
Программная
реализация:
#include <iostream.h>
//прототип подпрограммы поиска методом
Бойера и Мура
int
BMSearch(char *t, char *w);
int
main()
{
system("chcp 1251>nul");
char text[250],word[50];
cout<<"Введите текст";
cin.getline(text,250);
cout<<"Введите слово";
cin.getline(word,50);
int k=BMSearch(text, word);
cout<<"k="<<k+1<<endl;
system("pause");
return 0;
}
//реализация подпрограммы поиска
методом Бойера и Мура
int
BMSearch(char *t, char *w){
int
tl, wl;
int res = -1;
tl = strlen(t);
wl = strlen(w);
if ( tl == 0
)
cout
<< "Неверно задана строка\n";
else if ( wl
== 0 )
cout
<< "Неверно задана подстрока\n";
else {
int
i, Pos;
int
BMT[256];
for ( i = 0; i < 256; i ++ )
BMT[i] = wl;
for ( i = wl-1; i >= 0; i-- )
if
( BMT[(short)(w[i])] == wl )
BMT[(short)(w[i])] = wl - i - 1;
Pos = wl - 1;
while ( Pos < tl )
if ( w[wl - 1] != t[Pos] )
Pos = Pos + BMT[(short)(t[Pos])];
else
for ( i = wl - 2; i >= 0; i-- ){
if ( w[i] != t[Pos - wl + i + 1] ) {
Pos += BMT[(short)(t[Pos - wl + i +
1])] - 1;
break;
}
else
if ( i == 0 )
return Pos - wl + 1;
cout << "\t" <<
i << endl;
}
}
return res;
}
Контрольные вопросы.
1. Что такое поиск?
2. Что называется пространством ключей?
3. Поясните понятие функции хеширования.
4. Что такое переполнение?
5. Какие требования предъявляются к функции
хеширования?
6. Назовите основные операции,
производимые с упорядоченным деревом?
7. В чем заключается алгоритм прямого поиска в
тексте?
8. В чем заключается алгоритм Кнута,
Мориса и Пратта?
9. В чем заключается алгоритм Боуера и Мура?