Триграмний індекс або «Пошук з друкарськими помилками»
Якось за обов'язком служби з'явилася необхідність додати до пошуку на сайті всім відому фічу, сервіс «Можливо ви мали на увазі…» або «Пошук з друкарськими помилками». Почали думати як реалізовувати. Сторонні сервіси та api використовувати не хотілося, бо час до чужого сервера і назад, та й загалом не дуже добре. Якраз до речі припав модуль pg_trgm, який шукає близькі до запиту слову на основі триграмного індексу.
Реалізація
Спочатку – як це використовується. Щоб шукати схожі слова, потрібно створити список правильних варіантів. Створюємо таблицю з текстовим полем, яке пізніше повісимо триграмний індекс.
CREATE TABLE "public". "tbl_words" ( "word" VARCHAR (255) NOT NULL ) WITHOUT OIDS;
* Цей source code був highlighted with Source Code Highlighter.
Заповнити таблицю можна різними способами, ми вирішили це питання так: — Граматичний словник Залізняка (4)
90 тисяч слів), словник української літератури (
Далі додаємо індекс.
CREATE INDEX "tbl_words_trgm_ >ON "public"."tbl_words" USING gist ("word" "public"."gist_trgm_ops");
* Цей source code був highlighted with Source Code Highlighter.
Ось у такому вигляді схему вже можна використати.
select word, similarity(word, 'Пужкін' ) from tbl_words
* Цей source code був highlighted with Source Code Highlighter.
Подібний запит видасть нам схожі слова та rate, який показує на скільки слово схоже із запропонованим. Сортуючи за рейтингом «схожості» у зворотному порядку, отримаємо схожі слова.
select word from tbl_words where word % 'Пужкін' order by similarity(word, 'Пужкін' ) desc , word limit 5
* Цей source code був highlighted with Source Code Highlighter.
Далі належить визначити, коли все ж таки людина помилилася і їй треба запропонувати правильний варіант. Найочевидніший варіант - якщо користувач на свій запит нічого не знайшов, або, наприклад, знайшов мало результатів, перевіряємо схожі варіанти. Якщо пошук за схожими варіантами видав певну кількість результатів, показуємо підказку користувачеві. На даному етапі, щоб досягти правильного результату, можна підкручувати значення видавати/не видавати, скільки видав пошук за схожими словами та інші властивості. Варто встановити граничне значення «рейтингу схожості», до якого слова навіть не слід розглядати як схожі.
У цього способу, однак, є кілька великих мінусів: 1) Словник у нас складається з окремих слів, тоді як пошукові запити зазвичай бувають складними. Пошук схожих фраз доводиться здійснювати окремо за словами, потім їх комбінувати. Тобто, наприклад, маючи пошукову фразу «рагня поезія Пушкіна», яка не видасть результатів, доводиться шукати схожі слова, відповідно, для «рагня», «поезія», «пушкіна». Якщо взяти по 2 схожі слова, кількість варіацій дорівнюватиме 8. Це створює непогане навантаження на базу, що зазвичай не тішить. 2) Навіть при установці всіх потрібних параметрів, трапляються веселі курйози, коли пошук по слову, що не має відношення до запиту, видасть більше результатів, ніж оригінальний запит. Таким чином, виходять досить веселі підказки, наприклад при пошуку слова «Тіна», з'явиться пропозиція, «можливо ви мали на увазі Путіна», або, не дай Боже, навпаки)
Разом: Плюси – легка реалізація, багато варіантів підказок. Мінус - завантаження бази при великих запитах, періодично невірні підказки.
Якщо ви ведете статистику пошукових запитів, можнавикористовувати інший варіант. Створюється таблиця з унікальними пошуковими запитами, на полі із запитами за тим самим принципом додається триграмний індекс. І відповідність шукається не окремо за словами, а за повною пошуковою фразою у збережених запитах.
Разом: Плюси – фрази у підказках складені користувачами, менша ймовірність «дурних» підказок. Мінус – повнота бази залежить тільки від вашої статистики запитів.
Після неодноразового тестування, ми вирішили відмовитися від першого методу на користь другого, аж надто непередбачуваними були його результати) Результати роботи другого способу можна подивитися тут.
Як це працює.
Щоб до кінця стало зрозуміло, розповім як це працює. Все досить просто. Кожне слово ділиться на трилітерні поєднання - триграми. Наприклад:
При пошуку схожої фрази шукаються однакові триграми. Чим більше рівних триграм, тим більше фраза схожа на вихідну.
Схожі товари.
Триграмний індекс, встановлений на назви товарів, дав непогані релевантні результати) Приклад тут, або на будь-якій сторінці товару на сайті.
Якщо комусь буде цікаво, наступного разу викладу тести продуктивності та вихідники.