Мені здається, я почав розуміти, що ти мала на увазі!

Опечататися справа нехитра; опечататися в пошуковому запиті і подвійно. Почитай все більші веб-пошуковики сьогодні вміють коригувати помилки в ключових словах по-1х і підказувати запити по-2х; за ними так само хочеться пошукам поменше. Обидві штуки можна вправно реалізувати за допомогою відкритого пошуковика на прізвисько Sphinx; у цьому пості розповім, як саме.

Ну, за did you mean («що ти мала на увазі») та інший query completion («Чи не Васю ти шукаєш»).

Почнемо із простого, ті. query completion. Користувач починає вводити пошуковий рядок, у міру набору хочеться йому відразу показувати підказки (це щоб не шукав невідомо чого, а слухав «Валянки», як усі). Можливо, навіть із числом результатів. Як робити, звідки хоч брати дані?

Варіантів приблизно два: можна підказувати прямо запити користувача, а можна окремі ключові слова.

Ключові слова підказувати особливо нескладно. У програми індексування з несподіваним ім'ям indexer є два не менш раптові ключики:--buildstops, який змушує indexer замість звичайно індексування будувати список з N найпоширеніших слів (він же словник), і до нього--buildfreqs, який змушує ще й частоти при цьому рахувати (він же частотний словник). Беремо indexer, будуємо тисяч 10 (можна 100) найчастіших слів у нашій колекції документів:

Отримуємо приблизно такий файл:

Далі справа техніки. Створюємо SQL табличку, пишемо скрипт імпорту на десяток рядків, для підказки використовуємо звичайний LIKE, результати сортуємо за частотою слова. LIKE за індексом вийде цілком розумно швидкий, тк. шукаємо початок ключа. Для 1-літерних запитів результати непогано б відразу розрахувати та закешувати, щобне лопатити тисячі рядків на кожен чих. MySQL query cache, втім, за ідеєю врятує, якщо включений.

Запити підказуються майже так само. Ні табличка, ні LIKE нікуди не діваються; тільки замість окремих слів тепер хочеться повноцінні рядки. Взяти їх можна і потрібно у своєму лозі запитів, звідти й частоти порахувати. Лог доведеться трохи обробити напилком: рядок «vasya pupkin» з погляду пошуку збігається з «Vasya! Pupkin!», чому вважати їх різними запитами не дуже комільфо. Це забарвляється методом Sphinx API BuildKeywords(): беремо довільний рядок запиту, будуємо по ньому ключові слова (з наведенням регістру і всім таким), відновлюємо нормалізовану рядок запиту. Все це краще робити, попередньо встановивши персистентне з'єднання методом Open(), інакше працюватиме чимало разів повільніше. Ну, а далі вже за накатаною; лог, напильник, sort, uniq-c, скрипт імпорту, SQL табличка, LIKE, профіт. Напильник має виглядати приблизно так:

Скрипт імпорту з текстового файлу про два поля в SQL базу залишаємо як домашнє завдання для читачів.

Я зрозумів, що це натяк.

Зрозуміло, завжди є варіант вкрутити ispell, aspell, hunspell, або будь-модний-сьогодні-spell. Зрозуміло, завжди впирається або в якість xxxspell-словника, або тупо за його відсутності для потрібної мови. Зрозуміло, не допомагає з неологізмами (превед), спецтермінами (ацидіум ацетилосаліциліум), географічними назвами, тощо. Через це все одно хочеться більшого. Та й блог не про ispell, потрібно відповідати.

Знову знадобиться частотний словник. Щоправда, більше розміром, ніж 10K ключових слів — «виправляти» рідкісне правильне слово в часто-густе слово таки не варто. Словника на 1 мільйон слів зазвичай має вистачати, на 10 мільйонів зовсім повинно,ті. команда перетворюється на indexer --buildstops dict.txt 10000000 --buildfreqs MYINDEXNAME (працює зі швидкістю понад 20 MB/sec на C2D E8500, до речі). На відміну від підказок SQL шукати в такому словнику вже ніяк не допоможе; і даних більше, і вид запитів зовсім не той. Натомість допоможе Sphinx.

Основна ідея така. Генеруємо кожному за слова зі словниканабір триграм, ті. 3 символів, що послідовно йдуть. Індексуємо триграми Sphinx-ом. Для пошуку варіантів заміни, будуємо для слова-з помилкою триграми теж, шукаємо їх в індексі. Кандидатів знайдеться кілька. Чим більше триграм співпало, що менше відрізняється довжина слова, і що частіше зустрічається знайдений варіант, то краще. А тепер розберемо все це докладніше на живому прикладі.

Створений indexer --buildstops словник все ще виглядає ось так (я вибрав інший шматок, щоб слова були справжнішими, а приклад наочнішими):

Для кожного слова нам потрібно створити унікальний ID, зберегти саме слово та його частоту, побудувати триграми і все це зберегти в базу. Якщо в базі, що індексується, є помилки, дуже рідкісні слова має сенс відкинути, тк. з непоганим шансом це друкарські помилки і є.

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

Підозрювальні слова виявляємо з результатів пошукового запиту: якщо результатів пошуку занадто мало (або взагалі немає), аналізуємо секцію відповіді $result[«words»], дивимося на кількість документів для кожного слова. Якщо документів мало, пробуємо коригувати таке слово. Наприклад, для запиту "green liight" в моєму тестовому індексі кількість входжень для "green" дорівнює 34421, для "liight" тільки 2. Кого з них етапувати навиправні роботи, зрозуміло негайно. Конкретні пороги для мало дуже індивідуальні для різних колекцій документів і запитів. Дивіться у свій словник та лог запитів, підбирайте магічні константи.

Будуємо триграми, запускаємо запит за спеціндексом триграм. Оскільки слово набрано з помилками, товсетриграми навряд чи співпадуть. З іншого боку, якщо збігається лише одна триграма, такий кандидат теж малоцікавий: таке може статися, лише якщо збіглися три літери в середині слова (і більше нічого), або одна літера на початку (і більше нічого). Добре, використовуємо оператор кворуму, він саме так і шукає: видає всі документи, де збіглося не менше 2х триграм. Ще вводимо обмеження на довжину: припускаємо, що довжина правильного варіанта відрізняється не більше ніж на 2 символи.

Купу знайдених кандидатів необхідно відсортувати та вибрати з неї кращого. Згадуємо, які ми маємо чинники:

чим більше триграми збіглося, тим краще;
що менше відрізняється довжина слова, то краще;
що частіше зустрічається знайдений варіант, то краще.

Всі ці фактори свіжа версія Sphinx здатна порахувати та посортувати повністю на стороні сервера. Кількість триграм можна розрахувати ранкером SPH_RANK_WORDCOUNT (тк. в ході нашого спецпошуку кожна триграма і виступає окремим ключовим словом). Різниця у довжині слова дорівнює abs(len-$len), а частота зберігається в атрибуті freq. Розраховуємо фактори, збираємо деякі разом, і вибираємо найкращий:

Ура, працює! Для слова liight успішно перебуває виправлення light. (Точніше, Sphinx знаходить ID, яким потім з бази дістається рядок «light»).

Саме так влаштована прикладена до Sphinx 0.9.9-rc2 демка (див. директорію misc/suggest всередині архіву),яку можна негайно випробувати на своїх даних без написання додаткового коду :-)

Демка, відразу зрозуміло, неідеальна і підлягає доведенню напилком. (Вибачте, утриматися не зміг.) Є небезпека, що з коробки PHP частина не запрацює з українською мовою, тому що очікується UTF-8, використовується substr, і відповідно без mbstring.overload=7 нікуди. Майже, напевно, доведеться покрутити FREQ_THRESHOLD, ті. мінімальна кількість входжень, нижче якої слово вважається друкарською помилкою і в спеціндекс не потрапляє; для невеликих колекцій даних знизити, для великих збільшити. З тих же міркувань (щоб не ранжувало рідкісне сміття вище частого сміття) може статися необхідність покрутити формулу для розрахунку myrank. Наприклад, додати по зайвій одиниці до збіглися триграм для частот, що відрізняються в 1000 разів:

Крім того, фокус із триграмами дієвий, але дуже простий, і багато що не враховує. Не враховується порядок проходження триграм, хоча для слів розумної довжини це загалом не проблема. Що цікавіше, не враховуєтьсяяклюди помиляються: перестановка 2х сусідніх літер за кількістю триграм не відрізняється від заміни цих літер набудь-які(8) (!) інші (наприклад light/lihgt/limit); не враховується близькість букв на клавіатурі; Не враховується фонетична близькість (actually/akshully). Досить очевидна ідея для покращення якості виправлень малою кров'ю: замість 1 найкращого варіанта витягуємо штук 10-20, рахуємо на клієнті дистанцію Левенштейна, корегуємо результати розрахунків. Великою кров'ю можна так само «дорахувати» десяток-другий кандидатів будь-яким іншим самописним алгоритмом.

Загалом, демка працюватиме і з коробки. Але це таки демка, і маси простору для подальшого креативу ніхто не скасовував. Творіть,вигадуйте, пишіть блоги, засилайте патчі!