Работа со словарем. Иоиск и вставка. Хеширование.

 

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

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

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

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

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

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

Пусть функция code (с) по заданной букве выдает ее номер в латинском алфавите (если символ не является буквой латинского алфавита, то будем считать, что функция code возвращает значение 0). Вот как, например, может выглядеть эта функция:

 

int code (char c)

 {

return strchr("abcdefghijklmnopqrstuvwxyz",   c) + 1;

}

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

Далее эту функцию можно использовать как базовую для определения функции расстановки. Прежде всего, обеспечим зависимость значения функции расстановки от всех символов слова. Для этого сложим коды всех букв. Дополнительно, для того чтобы позиция буквы в слове также играла некоторую роль, будем добавлять к коду каждой буквы номер ее позиции. Далее решим, словарь какого размера нам потребуется. В конечном итоге значение функции хеширования должно получиться достаточно равномерно распределенным на множестве всех обрабатываемых слов, и попадать в диапазон [0, n-1], где п — размер словаря. Достаточно равномерное распределение получается, если вычислять индекс по формуле (Р * Х+ Q) % n, где числа Р и Q — это некоторые простые числа, по порядку близкие к п, X — вычисленная сумма кодов букв слова, а символ % задает операцию вычисления остатка от целочисленного деления. Если, например, считать, что словаря в 1000 слов будет достаточно для наших целей, то можно выбрать для Р и Q значения 557 и 811, и тогда функция расстановки примет следующий вид:

int hash (const string & str) {

  int sum = 0;

for (int i = 0; i < str.length(); i++) {

sum += code(str[i]) + i;

}

return (557 * sum + 811) % 1000;

}

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

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

 

Листинг: Определение простого словаря

Файл dictionary. h

// Класс, представляющий словарь в виде хеш-таблицы

class HashDictionary

{

private:

static const int P = 557;

static const int Q = 811;

static const int LENGTH = 1000;

string *dict[1000];             // хранилище на 1000 слов

 

// Функция определяет код буквы как ее

// порядковый номер в латинском алфавите

static int code (const char с);

 

public:

// Функция расстановки, основанная на сложении кодов

// букв со смещением, соответствующим их позиции

static int hash (const string & str);

 

private:

 

// Внутренняя функция поиска позиции слова в словаре

int findPos (const string & word) const;

public:

// Конструктор записывает в словарь пустые ссылки

HashDictionary() { memset(dict, 0, sizeof (dict)); }

 

//Функция добавления слова в словарь. Если слово уже было

// в словаре, то второй раз оно в словарь не попадает

void add (const string & word);

 

// Функция проверки наличия слова в словаре

bool hasWord (const string & word) const;

};

 

Файл  dictionary.cpp

// Реализация функций

int HashDictionary::code (char c)

{

return strchr("abcdefghijklmnopqrstuvwxyz", c) + 1;

}

int HashDictionary::hash (const string & str) {

  int sum =0;

 for (int i = 0; i < str.length(); i++) {

sum += code(str[i]) + i;

 }

return (P * sum + Q) % LENGTH;

}

int HashDictionary::findPos (const string & word) const {

  int i = hash(word);                           // текущий индекс слова в словаре

for (int counter = 0;

counter < LENGTH; counter++)

{

if (dict[i] == NULL || *dict[i] — word) {

return i;                                        // слово или позиция для его вставки найдено

} else if (++i — LENGTH) {

i = 0;                                            // переход к следующему индексу

}} return - l;                               // перебраны все позиции в словаре!

}

void HashDictionary::add (const string & word) {

int i = findPos(word);                   // позиция слова в словаре

if (i==-1) return;                            // только в случае переполнения словаря!

if (dict[i] == NULL) dict[i] = new string();

*dict[i] = word;                          // добавление слова или его перезапись

}

bool HashDictionary::hasWord (const string & word) const {

int i = findPos(word);                 // позиция слова в словаре

return i!=1 && dict[i]!= NULL; }

 

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

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

Листинг: Реализация хеш-таблицы

Файл " hashtable. h ".

 

// Класс, представляющий хеш-таблицу пар (ключ, значение), причем

// ключом является строка, а значением может быть произвольный объект.

//В таблице хранятся не сами эти объекты, а ссылки на них.

template <class Object>

class HashTable {

private:

static const int P= 557;

static const int Q= 811;

static const int LENGTH = 1000;

 

// Элемент списка, содержащий ключ и связанный с ним объект

struct ListElem {

string key;             // ключ

Object *obj;           // связанный объект

ListElem *next;    // ссылка на следующий элемент

 

// Простой конструктор для создания элементов списка

ListElem (const string & k, Object *o, ListElem *n) {

key = k; obj = o; next =n; }

};

 

// Массив списков, содержащих слова словаря

ListElem * diсt[LENGTH];

public:

 

// Конструктор

HashTable() { memset (dict, 0, sizeof (dict)); }

 

// Функция расстановки, основанная на сложении кодов символов

static int hash {const char * str);

 

// Функция добавления нового объекта по ключу. Если объект,

// связанный с этим ключом, уже содержится в словаре,

//то новый объект замещает собою старый, а старое значение

// возвращается в качестве результата работы функции.

Object * add (const char * key, Object * obj);

 

// Функция поиска объекта по ключу. Если ключ не найден,

 //то функция возвращает пустую ссылку

Object * find(const char * key) const;

 

// Функция удаления объекта по заданному ключу.

// Результат функции - указатель на удаляемый объект.

// Если ключ не найден, то функция возвращает пустую ссылку

Object * remove(const char * key);

};

template < class Object>

int HashTable<Object>::hash(const char * str) {

int sum = 0;

for (int i = 0; str[i]; i++) {

sum += str[i] + i;

}

return ((P * sum + Q) & 0x7FFF) % LENGTH;

}

template < class Object>

Object * HashTable<Object>::add(const char * key, Object * obj) {

if (key == NULL || key[0] == 0 || obj == NULL) {

throw NullValueException();

}

int index - hash(key);                   // Значение hash-функции

ListElem *current =dict[index]; // Текущий элемент списка

// Поиск ключа в словаре:

while (current && key!= current->key) {

current = current->next; }

Object * result = NULL;

if (current) {                                  // Ключ уже есть в словаре

result = current->obj;

current->obj = obj;

} else {

// Создаем новый элемент списка и добавляем в начало списка

ListElem * newElem = new ListElem(key, obj, dict[index]);

dict[index] = newElem;

} return result; }

template <class Object>

Object * HashTable<Object>:: find (const char * key) const {

if {key == NULL || key[0] == 0) {

throw NullValueException();

}

int index = hash(key);                     // Значение hash-функции

ListElem *current * dict[index]; // Текущий элемент списка

 

 

// Поиск ключа в словаре:

while (current && key!- current->key) {

current = current->next;

}

if (current == NULL) return NULL; // Ключ не найден

return current->obj;

}

template <class Object>

Object * HashTable<Object>::remove(const char * key) {

if (key == NULL || key[0] == 0) {

throw NullValueException();

}

int index = hash(key);                     // Значение hash-функции

ListElem *current = diсt[index]; // Текущий элемент списка

ListElem *pred = NULL;                     // Предыдущий элемент списка

// Поиск ключа в словаре:

while (current && key!= current->key) {

pred = current;

current = current->next;

}

if (current = NULL) return NULL; // Ключ не найден

// Исключение элемента из списка:

if (pred == NULL) {

diсt[index]  = current->next;

} else {

pred->next = current->next;

}

// Возврат результата:

Object * result = current->obj;

delete current;

return result;

}

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

int size();                                  // Количество слов в словаре

Iterator<string> keys (); // Итератор всех ключей словаря

Iterator<Object> objects (); // Итератор всех связанных объектов

 

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

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

На самом деле совершенно неважно, являются ли ключами для поиска в хеш-таблице именно слова. Фактически ключами могут служить любые объекты, лишь бы для них можно было определить подходящую функцию расстановки.

Поиск подстроки в строке

 

Часто приходится сталкиваться со специфическим поиском, так называемом поиском подстроки в строке. Его можно определить следующим образом. Пусть задана строка S из N элементов и строка p из M элементов. Описаны они так:

string S [ N ], P [ M ];

Задача поиска подстроки P в строке S заключается в нахождении первого слева вхождения P в S, т.е. найти значение индекса i, начиная с которого

S [ i ] = P, S [ i + 1] = P,…, S [ i + M – 1] = P [ M – 1].

Разберем самый очевидный, самый «прямолинейный» алгоритм поиска.