Пошук даних

Згадайте, як часто доводиться вам шукати якісь дані. Таких прикладів багато і в побутових ситуаціях, і в навчальному процесі. Наприклад, у програмі телепередач ви шукаєте час початку трансляції футбольного матчу; в розкладі поїздів – відомості про поїзді, що йде до потрібної вам станції. На уроці фізики, вирішуючи завдання, шукаєте в таблиці питома вага міді. На уроці англійської мови, читаючи іноземний текст, шукаєте в словнику переклад слова на російську мову. Працюючи за комп’ютером, вам нерідко доводиться шукати на його дисках файли з потрібними даними або програмами.
Постановка завдання пошуку даних
У всіх комп’ютерних інформаційних системах пошук даних є основним видом обробки інформації. При виконанні будь-якого пошуку даних є три складові, які ми назвемо атрибутами пошуку:
Перший атрибут: набір даних. Це вся сукупність даних, серед яких здійснюється пошук. Елементи набору даних називатимемо записами. Запис може складатися з одного або декількох полів. Наприклад, запис у записнику складається з полів: прізвище, адреса, телефон.
Другий атрибут: ключ пошуку. Це те поле записи, за значенням якого відбувається пошук. Наприклад, поле ПРІЗВИЩЕ, якщо ми шукаємо номер телефону певної людини.
Третій атрибут: критерій пошуку, або умову пошуку. Це умова, якому має задовольняти значення ключа пошуку в шуканої запису. Наприклад, якщо ви шукаєте телефон Сидорова, то критерій пошуку полягає в збігу прізвища Сидоров з прізвищем, зазначеної в черговий записи в книжці.
Зауважимо, що ключів пошуку може бути декілька, тоді й критерій пошуку буде складним, враховує значення відразу декількох ключів. Наприклад, якщо в довіднику є кілька записів з прізвищем Сидоров, але у них різні імена, то складовою критерій пошуку включатиме дві умови: ПРІЗВИЩЕ – Сидоров, ІМ’Я – Володимир.
Як при «ручному» пошуку, так і при автоматизованому найважливішим завданням є скорочення часу пошуку. Воно залежить від двох обставин:
1) як організований набір даних в інформаційному сховищі (в словнику, в довіднику, на дисках комп’ютера та ін.);
2) яким алгоритмом пошуку користується людина або комп’ютер.
Організація набору даних
Щодо першого пункту можуть бути дві ситуації: або дані ніяк не організовані (таку ситуацію інколи називають «купою»), або дані структуровані.
Під словами «дані структуровані» розуміється наявність якоїсь впорядкованості даних в їх сховище: у словнику, в розкладі, в комп’ютерній базі даних.
Говорячи про системи в § 5, ми виділяли найважливіша властивість усякої системи – наявність структури. Ця властивість властива як матеріальним системам, так і інформаційним системам. Названі вище приклади сховищ інформації, а також архіви, бібліотеки, каталоги, журнали успішності учнів і багато інших є системами даних з певною структурою.
Структуровані системи даних, що зберігаються на будь-яких носіях, називатимемо структурами даних.
Проте буває й так, що зберігається інформація не систематизована. Уявіть собі, що ви записували адреси і телефони своїх знайомих в записну книжку без алфавітного індексу («драбинки» з букв по краях аркушів). Записи вели в порядку надходження, а не в алфавітному порядку. А тепер вам потрібно знайти телефон певної людини. Що залишається робити? Переглядати всю книжку поспіль, поки не попадеться потрібна запис! Добре, якщо пощастить і запис виявиться на початку книжки. А якщо в кінці? І тут ви зрозумієте, що книжка з алфавітом набагато зручніше.
Послідовний пошук
Ситуацію, описану вище, назвемо пошуком в неструктурованому наборі. Розумний алгоритм для такого пошуку залишається один: послідовний перебір всіх елементів множини до знаходження потрібного. Звичайно, можна переглядати безліч у випадковому порядку (методом випадкового перебору), але це може виявитися ще гірше, оскільки неминучі повторні перегляди одних і тих же елементів, що тільки збільшить час пошуку.

В алгоритмі врахуємо два можливих варіанти результату: 1) шукані дані знайдені; і 2) шукані дані не знайдені. Результати пошуку нерідко виявляються негативними, якщо в наборі немає шуканих даних.
Символіка блок-схем повинна бути вам зрозуміла. Зі схеми видно, що якщо шуканий елемент знайдений, то пошук може закінчитися до закінчення перегляду всього набору даних. Якщо ж елемент невиявлений, то пошук закінчується тільки після перегляду всього набору даних.
Задамося питанням: яке середнє число переглядів доводиться виконувати при використанні методу послідовного перебору? Є два крайніх приватних випадку:
– Бажаємий елемент виявився першим серед переглядаються. Тоді перегляд всього один.
– Бажаємий елемент виявився останнім у порядку перебору. Тоді число переглядів одно N, де N – розмір набору даних. Те ж буде, якщо елемент взагалі не знайдений.
Всякі середні величини прийнято визначати по великому числу проведених дослідів. На цьому принципі заснована ціла наука по, д; назвою математична статистика. Неважко зрозуміти, що якщо число дослідів (пошуків) буде дуже великим, то середня кількість переглядів у всіх цих дослідах виявиться приблизно рівним N / 2. Ця величина визначає тривалість пошуку – головну характеристику процесу пошуку.
Пошук половинним діленням
Візьмемо для прикладу гру в вгадування цілого числа в певному діапазоні. Наприклад, від 1 до 128. Один граючий загадує число, другий намагається його вгадати, задаючи питання, на які відповіддю може бути «так» чи «ні». Ключем пошуку в цьому випадку є число, а критерієм пошуку – збіг числа, задуманого першим гравцем, з числом, званим другим гравцем.
Якщо питання задавати такі: «Число дорівнює одиниці?». Відповідь: «Ні». Питання: «Число дорівнює двом?» І т. Д., То це буде послідовний перебір. Середнє число питань при багаторазовому повторенні гри з загадуванням різних чисел з даного діапазону дорівнюватиме 128/2 = 64.
Проте пошук можна здійснити набагато швидше, якщо врахувати впорядкованість натурального ряду чисел, завдяки чому між числами діють відносини більше / менше. З подібною ситуацією ми з вами вже зустрічалися в § 4, говорячи про вимірі інформації. Там обговорювалося спосіб вгадування одного значення з чотирьох (приклад з оцінками за іспит) і одного з восьми (приклад з книжковими полицями). Застосовувався метод пошуку називається методом половинного ділення. Відповідно до цього методу, питання треба задавати так, щоб кожен відповідь зменшував число невідомих у два рази.
Так само треба шукати і одне число з 128. Перше питання: «Число менше 65?» – «Так!» – «Число більше 32?» – «Ні!» І т. Д. Будь-яке число вгадується максимум за 7 питань. Це пов’язано з тим, що 128 = 2 ‘. Знову працює головна формула інформатики.
Метод половинного ділення для впорядкованого набору даних працює набагато швидше (у середньому), ніж метод послідовного перебору.

Посилання на основну публікацію