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

Алгоритми порівняння тексту

Мета роботи

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

Обладнання

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

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

Порівняння текстів — це процес визначення схожості або відмінності між двома текстовими рядками.
Основна мета — знайти кількісну міру подібності між текстами.

Основні задачі порівняння текстів

• Визначення, наскільки два тексти однакові (ідентичність).
• Виявлення відмінностей між текстами.
• Вимірювання “відстані” між словами або реченнями.
• Пошук схожих документів, фрагментів, слів.
• Застосування у перевірці плагіату, пошуку помилок, машинному перекладі.

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

1. Символьні алгоритми — працюють з окремими літерами (Левенштейна, Дамерау–Левенштейна).
2. Множинні алгоритми — порівнюють набори слів (Jaccard Similarity).
3. Векторні алгоритми — використовують векторне подання текстів (косинусна подібність).
4. Гібридні методи — поєднують статистичні й символьні метрики.

---

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

1. Лінійне порівняння

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

2. Відстань Левенштейна

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

3. Відстань Дамерау–Левенштейна

• Модифікація Левенштейна, що враховує перестановку сусідніх символів.
• Краще відображає реальні помилки введення.

4. Jaccard Similarity

• Порівнює множини унікальних слів двох текстів.
• Обчислюється як:
  J(A, B) = |A ∩ B| / |A ∪ B|
• Використовується у задачах семантичної схожості.

5. Косинусна подібність

• Розглядає тексти як вектори частот слів.
• Обчислюється через косинус кута між двома векторами.
  cos(θ) = (A · B) / (‖A‖‖B‖)
• Дає значення від 0 (різні тексти) до 1 (ідентичні).

---

Хід роботи

1. Відкрити Visual Studio → створити новий проєкт типу Console Application (C++).
2. Реалізувати алгоритми порівняння текстів:
   1. Лінійне порівняння.
   2. Відстань Левенштейна.
   3. Jaccard Similarity.
3. Додати функції:
   • Завантаження двох текстів із файлів.
   • Вимірювання часу виконання алгоритмів.
   • Виведення результатів у консоль та у файл.
4. Формат вихідних даних:

file1: text1.txt
file2: text2.txt
levenshtein distance: 12
jaccard similarity: 0.73
cosine similarity: 0.82
time: 0.011s

1. Здійснити порівняння для кількох пар текстів різної довжини.
2. Створити таблицю з результатами часу виконання та значеннями подібності.
3. Реалізувати програму з використанням принципів ООП:
   • клас TextComparer (порівняння текстів),
   • клас FileLoader (читання файлів),
   • клас Timer (вимір часу).
4. Побудувати висновок щодо точності та ефективності алгоритмів.
5. Зберегти звіт у форматі PDF та передати викладачу.

---

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

1. У чому полягає різниця між точним і нечітким порівнянням текстів?
2. Які типи помилок враховує відстань Левенштейна?
3. Як реалізується алгоритм Дамерау–Левенштейна?
4. Як обчислюється Jaccard Similarity і коли її доцільно використовувати?
5. Як формується вектор частот слів для косинусної подібності?
6. Як можна оптимізувати обчислення для великих текстів?
7. Які структури даних зручно застосовувати для порівняння текстів?
8. Як вимірювати ефективність алгоритмів порівняння?
9. Які метрики використовуються у задачах пошуку плагіату?
10. У яких прикладних галузях використовуються алгоритми порівняння текстів?