Алгоритми пошуку

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

Класифікація:

1. Послідовний:

застосовується для набору даних, котрий організовано у вигляді масиву чи списку (впорядкованого чи ні); ключ нового елемента порівнюється з ключами існуючих елементів (послідовно елементи порівнюються, у зворотному порядку).

2. Бінарний пошук:

отримаємо його якщо до впорядкованого набору даних застосувати принцип «Р і П». Суть - після поділу набору даних на дві частини визначається частина, якій належать шукані дані, і потім пошук виконується у відповідній частині. Швидший за послідовний.

3. Інтерполяційний пошук:

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

m = (le+ri)/2 <-> m = le+(ri-le)* ; m = le+(ri-le)* .

4. Пошук індексуванням за ключем:

Виконується у два етапи – 1) обчислення адреси (виконується перетворення ключа у індекс масиву) -> 2) вирішення конфліктів (обробка елементів з однаковим індексом). + хешування – це компроміс між часом виконання і об’ємом пам’яті.

(приклад – хеш-таблиця з роздільним зв’язуванням - динамічна)

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

5. Дерево бінарного пошуку (binary search tree, BST):

ключ кожного вузла дерева має значення більше чи рівне значенню ключів його лівого під-дерева і менше або ж рівне – правого під-дерева. Рекурсивна реалізація пошуку для додавання вузла в дерево робить новий елемент зовнішнім вузлом («листочком» - бяднягою без посилань на діток); якщо значення ключа нового елемента відповідає якомусь ключу існуючого вузла, то новий вузол стає правим під-деревом цього вузла. BST – це вже відсортований набір даних.

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

а) якщо значення ключа нового вузла більше значення ключа кореня, то тоді старий корінь стає лівим під-деревом нового вузла, а праве під-дерево старого кореня – правим під-деревом нового;р

б) якщо значення ключа нового вузла менше значення ключа кореня, тоді старий корінь стає правим під-деревом нового вузла, а ліве під-дерево старого кореня – лівим під-деревом нового вузла.

в) ротація – перетворення дерева, основане на обміні кореня з його дочірнім вузлом із збереженням порядку слідування ключів у вузлах BST-дерева:

01. Ротація вправо – місцями міняються корінь та його лівий вузол = старий корінь стає правим під-деревом нового кореня + праве під-дерево нового кореня стає лівим під-деревом старого кореня;

02. Ротація вліво – місцями міняються корінь та його правий вузол = старий корінь стає лівим під-деревом нового кореня + ліве під-дерево нового кореня стає правим старого.

Одначе, пошук на BST-деревах працює з гарантованою продуктивністю лише за умови збалансованості дерева, тобто, коли всі зовнішні вузли знаходяться на одному рівні (висоті) або останньому чи передостанньому рівнях.

Методи його збалансування:

а) Рандомізація використовується під час побудови дерева в операції вставки нового вузла – його позиція обирається випадковим чином у процесі її пошуку: або в корінь дерева, або в корінь деякого під-дерева;

б) Амортизація використовується під час побудови дерева в операції вставки нового вузла – при переміщені доданого вузла у корінь виконується подвійна ротація, оскільки виконується оцінка двох зв’язків нового вузла з батьківським (дві ротації на одній ітерації);

в) Оптимізація полягає у використанні вузлів з декількома ключами і зв’язками: низхідні 2-3-4 дерева:

01. 2-вузол (один ключ і два посилання);

02. 3-вузол (два ключі і три посилання, тобто, ліве посилання на вузол із значенням ключа, меншим за поточний, праве – більшим за поточні, середнє – між значеннями поточного вузла);

03. 4-вузол (три ключі і чотири посилання, тобто, посилання визначають вузли за інтервалами ключів поточного вузла);

6. Порозрядний пошук:

Під час пошуку елементу значення ключа оцінюється порціями, а не повністю. Найпростіший порозрядний пошук оснований на використанні дерев цифрового пошуку (digital search trees, DST), яке є ефективним для дуже великих наборів даних з невеликими значеннями ключів, оскільки час пошуку обмежується лише довжиною ключа. Продуктивність можна істотно підвищити якщо одночасно розглядати більше одного розряду (основа системи числення не рівна двом). Наприклад, багато-шляхові дерева – значення ключів зберігаються у зовнішніх вузлах і кожен вузол має R-посилання (R - основа системи числення).

Якщо значенням ключа є рядок символів, тоді для порозрядного пошуку можна використовувати дерево тернарного пошуку (ternary search trees, TST) – дерево, кожен вузол якого містить один символ і три посилання (зв’язки), що відповідають ключам, поточні символи яких менші, рівні або більше символу вузла.

7. Зовнішній пошук.

Поиск по сайту: