Читайте также:
|
Пошук – це процес отримання (вилучення) інформації (даних) з деякого інформаційного простору з ціллю її обробки. Ефективність алгоритмів пошуку інформації залежить від впорядкованості і структурованості даних. Припускається, що дані зберігаються у вигляді записів, що мають ключ, який використовується під час пошуку. Пошук інформації базується на операції порівняння, результатом якої є повідомлення про вдалий (влучення) чи невдалий (промах) пошук.
Класифікація:
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. Зовнішній пошук.
Дата добавления: 2015-04-26; просмотров: 179 | Поможем написать вашу работу | Нарушение авторских прав |