33

Лабораторна робота № 5

"Розробка та дослідження ефективності методів пошуку даних"

1. МЕТА РОБОТИ

Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.

2. ТЕОРЕТИЧНІ ВІДОМОСТІ

2.1. Приклади застосування хеш-таблиць

Одним з поширенних прикладів застосування хеш-таблиць є побудова і пошук в таблиці ідентифікаторів програми. Головною характеристикою будь-якого елемента вхідної програми є його ім'я. Саме з іменами змінних, констант, функцій і інших елементів вхідної мови оперує розробник програми - тому і компілятор повинен вміти аналізувати ці елементи по їхніх іменах.

Таким чином, завдання компілятора полягає в тому, щоб зберігати деяку інформацію, пов'язану з кожним елементом вхідної програми, і мати доступ до цієї інформації за ім'ям елемента. Для рішення цього завдання компілятор організує спеціальні сховища даних, що називаються таблицями ідентифікаторів або таблицями символів. Таблиця ідентифікаторів складається з набору полів даних (записів), кожне з яких відповідає одному елементу вхідної програми. Запис містить всю необхідну компілятору інформацію про даний елемент і ця інформація може доповнюватись під час роботи компілятора. Кількість записів залежить від способу організації таблиці ідентифікаторів, але їх не може бути менше, ніж елементів у програмі. В принципі, компілятор може працювати не з однією, а з декількома таблицями ідентифікаторів - їх кількість і структура залежать від реалізації компілятора.

Компілятор поповнює записи в таблиці ідентифікаторів під час аналізу вхідної програми і знаходження в ній нових елементів, що вимагають розміщення в таблиці. Пошук інформації в таблиці виконується щоразу, коли компілятору потрібні відомості про той або інший елемент програми. Причому варто помітити, що пошук елемента в таблиці буде виконуватися компілятором значно частіше, ніж розміщення в ній нових елементів. Так відбувається тому, що опис нових елементів у вхідній програмі, як правило, зустрічаються набагато рідше, ніж ці елементи використовуються. Крім того, кожному додаванню елемента в таблицю ідентифікаторів завжди буде передувати операція пошуку - щоб переконатися, що такого елемента в таблиці немає.

На кожну операцію пошуку елемента в таблиці компілятор буде затрачати час, і оскільки кількість елементів у вхідній програмі може бути достатньо велика (від одиниць до сотень тисяч залежно від обсягу програми), цей час буде істотно впливати на загальний час компіляції. Тому таблиці ідентифікаторів повинні бути організовані таким чином, щоб компілятор мав можливість максимально швидко виконувати пошук потрібного йому запису в таблиці по імені елемента, з яким зв'язаний цей запис.

Можна виділити наступні способи організації таблиці ідентифікаторів:

• прості і впорядковані списки;

• бінарне дерево;

• хеш-таблиця з рехешуванням;

• хеш-таблиця з використанням методу ланцюжків;

• комбінація хеш-таблиці зі списком або з бінарним деревом.

З невеликими модифікаціями метод хешування придатний для зберігання дуже великих словників на диску. Ця версія хешування називається розширюваним хешуванням (extensible hashing). Оскільки звертання до диска значно дорожче досліджень в оперативній пам'яті, краще здійснювати виконання більшої кількості досліджень, ніж звертань до диска. Відповідно, значення, що обчислюються за допомогою хеш-функції в розширюваному хешуванні, вказують адресу на диску, де перебуває блок (bucket), в якому може зберігатися до b ключів. Після того як визначений блок для шуканого ключа, всі ключі блоку зчитуються в оперативну пам'ять і серед них виконується пошук шуканого ключа.

2.2. Найпростіші методи побудови хеш-таблиць

У найпростішому випадку хеш-таблиця являє собою лінійний неупорядкований список, або одновимірний масив, кожний елемент якого містить певну інформацію. Розміщення нових елементів у такій таблиці виконується шляхом запису інформації в наступний елемент масиву або списку.

Пошук потрібного елемента в хеш-таблиці буде в цьому випадку виконуватися шляхом послідовного перебору всіх елементів і порівняння їх імені з ім'ям шуканого елемента, поки не буде знайдений елемент із таким же ім'ям. Тоді, якщо за одиницю часу прийняти час, затрачуваний на порівняння двох елементів (у сучасних обчислювальних системах таке порівняння найчастіше виконується однією командою), то для хеш-таблиці, що містить N елементів, у середньому буде виконуватись N/2 порівнянь.

Час, необхідний на додавання нового елемента в хеш-таблицю (T_д), не залежить від числа елементів у хеш-таблиці (N). Але, якщо N велике, то пошук місця потребує значних затрат часу. Час пошуку (Т_п) у такій хеш-таблиці можна оцінити як Т_п = О(N). Оскільки саме пошук у хеш-таблиці є найбільш часто виконуваною операцією, то такий спосіб організації хеш-таблиць є неефективним.

Пошук може бути виконаний більш ефективно, якщо елементи хеш-таблиці відсортовані. Оскільки пошук здійснюється за іменем, найбільш природним рішенням буде розташувати елементи хеш-таблиці в прямому або зворотному алфавітному порядку. Ефективним методом пошуку в упорядкованому списку з N елементів є бінарний пошук.

При бінарному пошуку на кожному кроці число елементів, які можуть містити шуканий елемент, скорочується в два рази, тому максимальне число порівнянь дорівнює 1 + log ₂ N. Тоді час пошуку елемента в хеш-таблиці можна оцінити, як Т_п = О(log ₂ N). Для порівняння: при N=128 бінарний пошук вимагає якнайбільше 8 порівнянь, а послідовний пошук у неупорядкованій хеш-таблиці — у середньому 64 порівняння.

Недоліком бінарного пошуку є вимога того, щоб хеш-таблиця була відсортованою. Тому що масив інформації, в якому виконується пошук, повинен бути впорядкованим, час його заповнення буде залежати від числа елементів в масиві. Якщо використовувати стандартні алгоритми для сортування масиву даних, то середній час, необхідний на розміщення всіх елементів у хеш-таблиці, можна оцінити як:

Т_д = О(N·log ₂ N) + k·О(N²),

де k- деякий коефіцієнт, що відображає співвідношення між часом, що витрачається комп'ютером на виконання операції порівняння і часом, необхідним для виконання операції перестановки даних.

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

2.3. Хеш-функції і хеш-адресація

Кращих результатів можна досягнути, якщо застосовувати методи, пов'язані з використанням хеш-функцій і хеш-адресацій. Хеш-функцією h називається деяке відображення множини вхідних елементів R на множину цілих невід'ємних чисел Z:

h(r) = z , r є R , z є Z.

Множина допустимих вхідних елементів R називається областю визначення хеш-функции. Множиною значень хеш-функції F називається підмножина М множини Z ( ), що містить всі можливі значення, які можуть повертатись функцією h:

Процес відображення області визначення хеш-функції на множину значень називається хешуванням.

Наприклад, при роботі з таблицею ідентифікаторів хеш-функція повинна виконувати відображення імен ідентифікаторів на множину цілих невід'ємних чисел. Областю визначення хеш-функції в цьому випадку буде множина всіх можливих імен ідентифікаторів.

Хеш-адресація полягає у використанні значення, що повертається хеш-функцією, як адреси комірки в деякому масиві даних. Тоді розмір масиву даних повинен відповідати області значень хеш-функції.

В ідеальному випадку для розміщення будь-якого елемента в хеш-таблиці достатньо тільки обчислити його хеш-функцію і звернутися до потрібної комірки масиву даних. Для пошуку елемента в хеш-таблиці також необхідно обчислити хеш-функцію для шуканого елемента і перевірити, чи не є задана нею комірка масиву порожньою (якщо вона не порожня - елемент знайдений, якщо порожня - не знайдений). Спочатку хеш-таблиця повинна бути заповнена інформацією, що дозволила б говорити про те, що всі її комірки є порожніми. Цей метод досить ефективний, оскільки як час розміщення елемента в хеш-таблиці, так і час його пошуку визначаються тільки часом, що витрачається на обчислення хеш-функції, що в загальному випадку значно менше часу, необхідного для багаторазових порівнянь елементів хеш-таблиці. Метод має два очевидних недоліки. Перший з них - неефективне використання об'єму пам'яті під хеш-таблицю: розмір масиву для її зберігання повинен відповідати всій області значень хеш-функції, у той час, як реально збережених у хеш-таблиці даних може бути істотно менше. Другий недолік – це необхідність відповідного розумного вибору хеш-функції. Цей недолік є настільки істотним, що не дозволяє безпосередньо використовувати хеш-адресацію для організації хеш-таблиць.

Проблема вибору хеш-функції не має універсального рішення. Хешування зазвичай відбувається за рахунок виконання над послідовністю вхідних символів деяких простих арифметичних або логічних операцій. Найпростішою хеш-функцією для одного символу є його код внутрішнього представлення в комп'ютері. Цю хеш-функцію можна використовувати і для послідовності символів, вибираючи перший символ в послідовності.

Очевидно, що така примітивна хеш-функція буде незадовільною: при її використанні виникне проблема — двом різним словам, що починаються з однієї і тої ж букви, буде відповідати те саме значення хеш-функції. Тоді при хеш-адресації в одну і ту саму комірку хеш-таблиці повинні бути розміщені два різних слова, що явно неможливо. Така ситуація, коли двом або більше вхідним даним відповідає одне і те саме значення хеш-функції, називається колізією. Природно, що хеш-функція, що допускає колізії, не може бути використана для хеш-адресації в хеш-таблиці. Причому досить одержати хоча б один випадок колізії на всій множинаі слів, щоб такою хеш-функцією не можна було користуватися. Але чи можливо побудувати хеш-функцію, яка б повністю виключала виникнення колізій? Для повного виключення колізій хеш-функція повинна бути взаємно однозначною: кожному елементу з області визначення хеш-функції повинне відповідати одне значення з її множини значень, і навпаки - кожному значенню з множини значень цієї функції повинен відповідати тільки один елемент із її області визначення. Тоді будь-яким двом довільним елементам з області визначення хеш-функції будуть завжди відповідати два різні її значення. Теоретично таку хеш-функцію побудувати можна, тому що і область визначення хеш-функції (наприклад, всі можливі імена ідентифікаторів), і область її значень (цілі невід'ємні числа) є нескінченними зліченими множинами, тому можна організувати взаємно однозначне відображення однієї множини на іншу.

Але на практиці існує обмеження, що робить створення взаємно однозначної хеш-функції неможливим. Справа в тому, що в реальності область значень будь-який хеш-функції обмежена розміром доступного адресного простору комп'ютера. Множина адрес будь-якого комп'ютера із традиційною архітектурою може бути достатньо великою, але завжди скінченою, тобто обмеженою. Організувати взаємно однозначне відображення нескінченної множини на скінчену навіть теоретично неможливо. Можна, звичайно, врахувати те, що довжина значимої частини імені ідентифікатора в реальних компіляторах на практиці також обмежена - зазвичай вона лежить в межах від 32 до 128 символів (тобто і область визначення хеш-функції скінчена). Але і тоді кількість елементів в скінченій множині, що складає область визначення хеш-функції, буде перевищувати їх кількість в скінченій множинаі області значень (кількість всіх можливих слів більша за кількість допустимих адрес в сучасних комп'ютерах). Таким чином, створити взаємно однозначну хеш-функцію на практиці неможливо. Отже, неможливо уникнути виникнення колізій.

Тому не можна організувати хеш-таблицю безпосередньо на основі однієї тільки хеш-адресації. Але існують методи, що дозволяють використовувати хеш-функції для організації хеш-таблиць навіть при наявності колізій.

2.4. Хеш-таблиця з рехешуванням

Для розв'язання проблеми колізії можна використовувати багато способів. Одним з них є метод рехешування (або повторного хешування). Відповідно до цього методу, якщо для елемента key адреса z₀ = h(key), що обчислена за допомогою хеш-функції h, вказує на вже зайняту комірку, то необхідно обчислити значення функції z₁ = h₁(key) і перевірити зайнятість комірки за адресою z₁. Якщо і вона зайнята, то обчислюється значення h₂(key), і так далі доти, поки або не буде знайдена вільна комірка, або чергове значення h_і(key) не співпаде зі значенням h(key). В останньому випадку вважається, що хеш-таблиця заповнена і місця в ній більше немає.

Пошук елемента key в хеш-таблиці, організованій таким чином, буде виконуватися по наступному алгоритму:

1. Обчислити значення хеш-функції z = h(key) для шуканого елемента з ключем key.

2. Якщо комірка за адресою z порожня, то робиться висновок, що елемент не знайдений і алгоритм завершує свою роботу, інакше необхідно порівняти ім'я елемента в комірці z з ім'ям шуканого елемента. Якщо вони співпадають, то робиться висновок, що елемент знайдений і алгоритм завершує свою роботу, інакше змінній i надається значення 1 і переходиться до кроку 3.

3. Обчислити z_і = h_і(key). Якщо комірка за адресою z_і порожня або z = z_і , то елемент не знайдений і алгоритм завершується, інакше — порівняти ім'я елемента в комірці z_і, з ім'ям шуканого елемента. Якщо вони співпадають, то елемент знайдений і алгоритм завершується, інакше і = i + 1 і повторюється крок 3.

Алгоритми розміщення і пошуку елемента схожі по операціях, що виконуються. Тому вони будуть мати однакові оцінки часу, необхідного для їх виконання.

При такій організації хеш-таблиць у випадку виникнення колізії алгоритм розміщує елементи в порожні комірки хеш-таблиці, вибираючи їх певним чином. При цьому елементи можуть попадати в комірки з адресами, які потім будуть співпадати з новими значеннями хеш-функції, що приведе до виникнення нових, додаткових колізій. Таким чином, кількість операцій, необхідних для пошуку або розміщення в хеш-таблиці елемента, залежить від степеня заповнення хеш-таблиці.

Для організації хеш-таблиці по методу рехешування необхідно визначити всі хеш-функції h_і для всіх i. Найчастіше функції h_і визначають як деякі модифікації хеш-функції h. Наприклад, найпростішим методом обчислення функції h_і(key) є її організація у вигляді:

h_і(key) = (h(key) + p_і ) mod m ,

де р_і - деяке ціле число, що обчислюється, а m - максимальне значення з області значень хеш-функції h. У свою чергу, найпростішим підходом тут буде покласти p_і = і. Тоді одержуємо формулу:

h_і(key) = (h(key) + і ) mod m .

В цьому випадку при співпадінні значень хеш-функції для яких-небудь елементів пошук вільної комірки в хеш-таблиці продовжується послідовно, починаючи від поточної позиції, заданої хеш-функцією h(key).

Цей спосіб не можна визнати особливо вдалим тому, що при співпадінні хеш-адрес елементи в хеш-таблиці починають групуватися навколо них, що збільшує число необхідних порівнянь при пошуку і розміщенні. Але навіть такий примітивний метод рехешування є досить ефективним засобом організації хеш-таблиць при неповному заповненні хеш-таблиці. Середній час на розміщення одного елемента в хеш-таблиці і на пошук елемента в хеш-таблиці можна знизити, якщо застосувати більш досконалий метод рехешування. Одним з таких методів є використання в якості p_i для функції h_і(key) = (h(key) + p_і) mod m послідовності псевдовипадкових цілих чисел p₁, р₂ , ... , р_k . При гарному виборі генератора псевдовипадкових чисел довжина послідовності k = m.

Існують і інші методи організації функцій рехешування основанні на квадратичних обчисленнях або, наприклад, на обчисленні добутку по формулі:

h_і(key) = (h(key) · С · i) mod m^' ,

де С – константа, m^' - найближче просте число, менше за m.

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

При будь-якому методі вирішення колізій необхідно обмежити довжину пошуку елемента. Якщо для пошуку елемента необхідно більше 3 - 4 порівнянь, то ефективність використання такої хеш-таблиці значно погіршується і її треба реструктуризувати (тобто знайти іншу хеш-функцію), щоб мінімізувати кількість порівнянь для пошуку елемента.

2.5. Хеш-таблиця з використанням методу ланцюжків

Вимога неповного заповнення хеш-таблиці при застосуванні рехешування веде до неефективного використання доступного об'єму пам'яті. Причому об'єм невикористовуваної пам'яті буде тим вище, чим більше інформації зберігається для кожного елемента. Цього недоліку можна уникнути, якщо доповнити таблицю значень деякою проміжною хеш-таблицею.

В комірках проміжної хеш-таблиці може зберігатися або порожнє значення, або значення вказівника на деяку область пам'яті з основної таблиці значень. Тоді хеш-функція обчислює адресу, по якій відбувається звертання спочатку до проміжної хеш-таблиці, а потім вже через неї по знайденій адресі — до основної таблиці значень. Якщо відповідна комірка таблиці значень порожня, то комірка проміжної хеш-таблиці буде містити порожнє значення. Тоді зовсім не обов'язково мати в самій хеш-таблиці комірки для кожного можливого значення хеш-функції — хеш-таблицю можна зробити динамічною, так щоб її об'єм ріс по мірі заповнення. Такий підхід дозволяє домогтися двох позитивних результатів: по-перше, немає необхідності заповнювати таблицю порожніми значеннями — це можна зробити тільки для хеш-таблиці; по-друге, кожному елементу буде відповідати строго одна комірка у таблиці значень. Порожні комірки в такому випадку будуть тільки в хеш-таблиці, і об'єм невикористовуваної пам'яті не буде залежати від обсягу інформації, збереженої для кожного вхідного елемента, — для кожного значення хеш-функції буде витрачатися тільки пам'ять, необхідна для зберігання одного вказівника на основну таблицю значень. На основі цієї схеми можна реалізувати ще один спосіб організації хеш-таблиць за допомогою хеш-функції, що називається методом ланцюжків або методом роздільних ланцюжків. У цьому випадку таблиця значень представляється як набір лінійних зв'язаних однонаправлених списків.

Наприклад, нижче на малюнку зображена хеш-таблиця, як масив з 8 елементів:

Кожний елемент являє собою вказівник на лінійний список, що зберігає числа. Хеш-функція в цьому прикладі просто ділить ключ на 8 і використовує остачу як індекс в хеш-таблиці.

Більш детальна інформація про побудову і роботу з хеш-таблицями, а також про різновиди стратегій розв'язання колізій при хешуванні надається на лекційних заняттях.