Релевантний пошук із морфологією (без індексації)

Часто перед веб-розробниками постає завдання пошуку по сайту. Спробуємо сконструювати «велосипед», який має такі характеристики:

Відсутність індексної таблиці (індекси – тема окремої статті);
Робота з кодуванням UTF-8;
Видалення коротких та стоп-слів;
Морфологічне перетворення українських словоформ;
Сортування результатів з урахуванням їхньої релевантності;
Посторінкова видача результатів.

Нам знадобиться робочий веб-сервер із підтримкою PHP. Для морфологічного аналізу ми використовуватимемо українськомовний стеммер Портера. Крім цього, нам знадобиться список стоп-слів та деякі функції з проекту PHP UTF-8. Оскільки ми домовилися, що не використовуватимемо індексування, то в базі даних достатньо однієї таблиці приблизно такого виду:

Шукати сторінки будемо за їх вмістом (content), а в сніпетах виводити назву (title) і опис (description). Однак за необхідності ви легко зможете розширити пошук до кількох полів і навіть враховувати це за підрахунку релевантності.

Попередня обробка рядка

Спочатку ініціалізуємо змінні з рядком запиту, номером поточної сторінки та кількістю записів, що відображається на одній сторінці. Останні дві змінні необхідні організації посторінкової видачі результатів із відповідною навігацією.

Скоротимо пошуковий запит до 64 символів (такої довжини цілком достатньо) і наведемо його до нижнього регістру. Для цього скористаємось функціями зі згаданого вище проекту PHP UTF-8, архів з яким ми розпакували в директорію utf8 . Якщо ваш робочий сервер підтримує mbstring, можна скористатися аналогічними функціями звідти.

Для коректної роботи стемера необхідно замінитилітери "е" на "е". Далі видаляємо з рядка всі HTML сутності і спеціальні символи, а пробіли, що йдуть поспіль, замінюємо одиничними екземплярами. Таким чином, отримуємо підготовлений рядок зі слів, розділених пробілами.

Морфологічний аналізатор

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

Існують два основних підходи до морфологічного аналізу. Перший і найточніший застосування алгоритмів з використанням словників. Як приклади можна навести Ispell і AOT. Мінусом такого підходу є більш високе навантаження на сервер, оскільки обсяг словників може сягати десятків мегабайт.

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

Як стеммер ми скористаємося реалізацією алгоритму Портера на PHP. Однак ви можете використовувати PECL::stem або будь-який інший на свій розсуд. Стеммер Портера виглядає так:

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

Побудова SQL-запиту

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

Звичайно, правильніше було б нормалізувати кількість входжень довжиною тексту, оскільки є різниця між десятьма повтореннями в цілій книзі і п'ятьма — в одному абзаці (другий випадок більш релевантний, незважаючи на меншу кількість збігів). Однак засобами SQL без застосування процедур, що зберігаються, неможливо визначити загальну кількість слів у рядку. Тому доведеться знехтувати амплітудою обсягу сторінок, вважаючи їх приблизно однаковими.

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

Попередньо відсіватимемо короткі і стоп-слова, а для тих, хто залишився, визначимо леми, які й шукатимемо. З метою додаткового захисту від надто «важких» запитів обмежимося п'ятьма першими словами.

Оскільки ми маємо намір отримувати результати посторінково, нам знадобляться два SQL-запити. З першого ми дізнаємося загальну кількість сторінок, що шукаються, а за допомогою другого виберемо необхідні для відображення(у кількості, вказаній в $rpp ), відсортувавши їх за спаданням релевантності.

Виведення результатів

Залишається лише відобразити форму введення запиту разом із результатами пошуку:

І, нарешті, додамо посилання для переміщення між сторінками результатів:

Виключення тегів та атрибутів

Серйозним мінусом безіндексної реалізації є пошук у всьому документі, включаючи теги та його атрибути. Наприклад, маючи намір знайти сторінки зі словом «article», ви знайдете також всі документи з однойменним тегом. Це не страшно, якщо у вас українськомовний сайт про квіти чи автомобілі. Гірше, якщо ваші користувачі дійсно часто шукають слова на кшталт «article», «section», «script» тощо. Виглядає вона так:

Збережені процедури підтримуються в системі InnoDB, але не MyISAM. Тому використання цієї можливості залишається на вашу думку. У наступній статті ми розглянемо пошук з індексацією, а також формування сніпетів на основі пошукового запиту з підсвічуванням знайдених слів.

Починаючи з 5.6, Mysql вміє використовувати FULLTEXT index для InnoDB.

Sphinx все ж таки найкращі рішення для пошуку по релевантності морфології ітд. Завдяки налаштуванню формул ранжирування

працює ось так return step4(step3(step2(step1($a[0])))));

Скажіть, будь ласка, що робить функція rv($word)? У ній змінна $flag == 1 тільки на останній літері слова, остання ітерація циклу, відповідно функція завжди повертає $rv = '' (порожньо)

Короткий курс HTML 5

Цей курс знайомить читача з основами мови HTML 5 і дозволяє розпочати його практичне застосування у найкоротший термін.