Перелік усіх робіт

Пошук даних у тексті

Мета роботи

Навчитися використовувати алгоритми пошуку у тексах, створювати власні програмні реалізації даних алгоритмів та застосовувати їх на практиці.

Обладнання

Персональний комп’ютер, IDE Microsoft Visual Studio або інша середа розробки для мови C++

Теоретичні відомості

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

Основні задачі пошуку в тексті

• Знаходження першого входження підрядка у тексті.
• Знаходження всіх входжень підрядка.
• Підрахунок кількості входжень.
• Пошук декількох патернів одночасно.
• Пошук з урахуванням регістру, з урахуванням/без урахуванням пробілів тощо.

Класифікація алгоритмів пошуку

1. Прості (наївні) алгоритми — перебирають усі можливі позиції підрядка у тексті (лінійний пошук).
2. Алгоритми з попередньою обробкою патерну — використовують додаткову інформацію про патерн для прискорення пошуку (КМП, Бойера-Мура, Бойера-Мура-Хорспула).
3. Алгоритми з попередньою обробкою тексту — будують спеціальні структури для тексту (суфіксні дерева, масиви суфіксів, алгоритм Ахо-Корасик для множини патернів).
4. Алгоритми на основі хешування — використовують хеш-функції для швидкого порівняння підрядків (Рабіна-Карпа).

Огляд основних алгоритмів

1. Лінійний пошук (Brute Force)

• Перевіряє кожну позицію тексту, чи співпадає підрядок з патерном.
• Складність: O(n*m), де n — довжина тексту, m — довжина патерну.
• Простий у реалізації, але повільний для великих текстів.

2. Алгоритм Кнута-Морріса-Пратта (KMP)

• Використовує префікс-функцію для уникнення зайвих порівнянь.
• Префікс-функція показує, яку частину патерну можна використати повторно після невдачі.
• Складність: O(n + m).
• Ефективний для пошуку багатьох входжень одного патерну.

3. Алгоритм Бойера-Мура (BM)

• Порівнює патерн справа наліво, використовує таблиці зсувів (bad character, good suffix).
• Дозволяє робити великі зсуви патерну по тексту.
• Складність: у середньому швидше за КМП, у гіршому випадку O(n*m).
• Дуже ефективний для великих алфавітів і довгих патернів.

4. Алгоритм Рабіна-Карпа

• Використовує хеш-функцію для швидкого порівняння підрядків.
• Порівнює хеші підрядків тексту з хешем патерну, при збігу перевіряє символи.
• Складність: O(n) у середньому, O(n*m) у гіршому випадку (через колізії).
• Зручно для пошуку багатьох патернів одночасно.

5. Алгоритм Ахо-Корасик

• Дозволяє шукати багато патернів одночасно.
• Будує автомат (суфіксне дерево) для всіх патернів.
• Складність: O(n + k), де k — кількість входжень.

6. Алгоритм Бойера-Мура-Хорспула (BMH)

• Спрощений варіант Бойера-Мура, використовує лише таблицю “bad character”.
• Часто використовується на практиці через простоту та ефективність.

Додаткові поняття

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

Порівняння алгоритмів

Алгоритм	Складність (гірший випадок)	Складність (середній)	Підтримка множини патернів	Підготовка
Лінійний	O(n*m)	O(n*m)	Ні	Немає
КМП	O(n + m)	O(n + m)	Ні	O(m)
Бойера-Мура	O(n*m)	O(n/m)	Ні	O(m + k)
Рабіна-Карпа	O(n*m)	O(n)	Так	O(m)
Ахо-Корасик	O(n + k)	O(n + k)	Так	O(M)

n — довжина тексту, m — довжина патерну, k — кількість входжень, M — сумарна довжина всіх патернів.

Практичні аспекти

• Вибір алгоритму залежить від розміру тексту, довжини патерну, кількості патернів, алфавіту.
• Для пошуку одного короткого слова у невеликому тексті достатньо лінійного пошуку.
• Для пошуку багатьох слів або у великих текстах — КМП, Бойера-Мура, Ахо-Корасик.

Хід роботи

1. Завантажити Visual Studio. Знайдіть на робочому столі ярлик з Visual Studio або Пуск → Всі програми→ Microsoft → Microsoft Visual Studio.
2. Створити новий проект «Visual C++ (консольное приложение Win32)». Файл → Cтворити → Проект, тип проекту «Консольное приложение Win32».
3. Перевірити роботу програм, які вказані в прикладах до лабораторної роботи.
4. Оцініть складність реалізації наданих алгоритмів.
5. Модифікуйте програми наступним чином
   1. Додайте можливість завантаження тексту з файлу
   2. Створіть еталонний файл з кількома абзацами тексту англійською мовою в однобайтовому кодуванні
   3. Текст та слово для пошуку візьміть у генераторі тексту генераторі випадкових даних
   4. Додайте до програм можливіть пошуку всіх входжень шуканого слова, та запису позицій входження в окремий файл.
   5. Додайте можливіть обліку часу роботи програм. Зафіксуйте час роботи алгоритму для першого входження і для всіх входжень. Механізм обліку часу подано у прикладі 4
   6. Перетворіть програми з урахуванням основних концепцій ООП. Там де це необхадно, створіть окремі файли для класів.
   7. Вихідні файли повинні мати наступну структуру:

input file: C:\file.txt
search word: word
position: 15
time: 0.278s

input file: C:\file.txt
search word: word
positions: 15 89 245 764 801 903
time: 1.245s

1. Після аналізу файлів зробіть висновок про ефективність алгоритмів. Додайте в лабораторну роботу текст вхідного файлу, тексти вихідних файлів, порівняльну таблицю з часом виконання програм
2. Додайте програмний код завдання для самомтійного виконання
3. Дайте відповіді на контрольні запитання
4. Збережіть звіт у форматі PDF та надішліть викладачу

Контрольні запитання

1. Що таке задача пошуку підрядка у тексті? Які основні задачі вирішуються цими алгоритмами?
2. Які основні відмінності між лінійним пошуком, КМП, Бойера-Мура та Рабіна-Карпа?
3. Як працює префікс-функція у КМП і яку роль вона відіграє?
4. Які таблиці використовуються в алгоритмі Бойера-Мура і як вони впливають на ефективність пошуку?
5. Як працює алгоритм Рабіна-Карпа і в яких випадках його доцільно використовувати?
6. Які переваги та недоліки має кожен з основних алгоритмів пошуку у тексті?
7. Як організувати пошук усіх входжень підрядка у тексті?
8. Які структури даних використовуються для пошуку багатьох патернів одночасно?
9. Як виміряти ефективність алгоритму пошуку у тексті? Які метрики використовуються?
10. У яких практичних задачах застосовуються алгоритми пошуку у тексті?

Приклади

1. Лінійний пошук у тексті C++
2. КМП-пошук у тексті C++
3. БМ-пошук у тексті C++
4. Вимірювання часу роботи алгоритму C++

Довідники та додаткові матеріали

1. Лекція 15. Алгоритм прямого пошуку в тексті. Алгоритм Кнута-Морріса-Пратта. Алгоритм Бойера-Мура