Реалізація Full Text Search зі Spell Checking на Microsoft SQL Server

Під час роботи над одним проєктом виникла потреба реалізувати пoшук за ключовими словами чи фразами у великому об’ємі тексту. Як це зазвичай буває, треба було все зробити на вчора, хоч дізналися ми про це рано вранці на дейліку. Рішення мало б бути простим, швидким в реалізації та використовувати готову інфраструктуру.

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

Обрані рішення

Врахочуючи те, що база даних де зберігалася потрібна інформація була Microsoft Sql Server, то ми вирішили використати її можливості пошуку.

Для Sql Server Microsoft пропонує розширення Full Text Search (FTS), яке власне і дозволяє виконувати різноманітні запити на пошук, такі як пошук повного тексту, пошук з використанням операторів логічного зв'язку (AND, OR, NOT), пошук з використанням фразового зв'язку та інші. Також FTS розпізнає відмінки слів, що несумнівно є плюсом.

Та лишалася проблема перевірки правопису. Рішення Microsoft з коробки не пропонує подібного механізму, то ж нам довелося чаклувати самотужки.

Першим кроком був пошук відповідного алгоритму знаходження подібних слів. Для англійської мови можна було б використати Soundex, який шукає слова за схожістю звучання і вже реалізований в більшості СУБД. Та в нас був польский клієнт та польска мова, то ж вибір пав на інший, більш простий алгоритм — Levenstein Distance.

Реалізація

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

CacheTable

Після підключення пошук вже працює. Та якщо ви спробуєте шукати за текстом в якому є помилки, то він вам нічого не знайде. Варто зазначити, що в нас вже був великий об’єм написаного тексту. Враховуючи те, що кількість слів у будь-якій мові обмежена, ми вирішили створити cache-табличку, де були б всі слова які використовувавись хоча б раз. Ми відкинули ті слова, що менші за три символи та мають в собі цифри та інші спеціальні знаки. Залишок зберегли у табличку. Звісно тільки унікальні значення. Самі слова ми брали з таблички вже проіндексованих слів FTS:

INSERT INTO CacheTable 
SELECT distinct display_term as Keyword 
FROM sys.dm_fts_index_keywords_by_document(db_id(), object_id('TableWithContent')) 
where display_term != 'END OF FILE' 
order by display_term;
WHERE display_term != 'END OF FILE' 
AND LEN(display_term) > 2 
AND display_term NOT LIKE '%[^a-z]%' 
ORDER BY display_term;

В сухому залишку вийшло приблизно 50 000 слів, що доволі багато. Важливо, що при збільшені кількості записів, 2, 5, 10 млн — кількість унікальних виразів буде приблизно на такому самому рівні. Та попри це, для пошуку всіх подібних виразів в мене виходило від 2-х до 10-ти! секунд. Але про це згодом.

Levenstein Distance

Наступним кроком було написання алгоритму Levenstein Distance (LD).

На щастя, його реалізація в мові T SQL легко гуглиться, та для зручності, вставляю код тут:

CREATE OR ALTER FUNCTION [dbo].[levenstein_distance](@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
 DECLARE @s1_len int, @s2_len int
 DECLARE @i int, @j int, @s1_char nchar, @c int, @c_temp int
 DECLARE @cv0 varbinary(8000), @cv1 varbinary(8000)

 SELECT
  @s1_len = LEN(@s1),
  @s2_len = LEN(@s2),
  @cv1 = 0x0000,
  @j = 1, @i = 1, @c = 0

 WHILE @j <= @s2_len
  SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1

 WHILE @i <= @s1_len
 BEGIN
  SELECT
   @s1_char = SUBSTRING(@s1, @i, 1),
   @c = @i,
   @cv0 = CAST(@i AS binary(2)),
   @j = 1

  WHILE @j <= @s2_len
  BEGIN
   SET @c = @c + 1
   SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
    CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
   IF @c > @c_temp SET @c = @c_temp
   SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
   IF @c > @c_temp SET @c = @c_temp
   SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
 END

 SELECT @cv1 = @cv0, @i = @i + 1
 END

 RETURN @c
END

Скорочення кількості слів

Наступним викликом було скорочення часу пошуку відповідних слів. Для цього нам треба було обмежити область пошуку та, перед застосуванням алгоритму LD, позбутись слів, які не підходять. Ми відкинули занадто короткі та занадто довгі слова (допускалася різниця максимально в 2 символи). Це дозволило скоротити область пошуку майже утричі. Далі ми брали під увагу лише ті вислови, які починаються на одну й ту ж саму літеру зі словом, яке шукають. У результаті кількість зменшилась до 500-та. Після цього, застосування алгоритму LD вже не займало так багато часу.

Отримані слова ми сортували за найбільшою подібністю та брали перші п’ять виразів, які не відрізнялися більше ніж на два символи. Пізніше з усіх слів ми формували список, який використовавали для пошуку в тексті. Приклад реалізації подібного механізму нижче (швидкість виконання менше 50 ms):

SELECT TOP (5) Keyword FROM CacheTable
WHERE LEN(Keyword) BETWEEN 2 AND 7
AND Keyword LIKE 'l%'
AND dbo.levenstein_distance('lista', Keyword) <= 2
ORDER BY dbo.levenstein_distance('lista', Keyword) 

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

Оновлення СacheTable.

Оновленням таблички займався ReccuringTask, який щоночі перезаписував слова. Враховуючи те, що в нас вже була велика база слів, то необхідності оновлювати таблицю після кожної зміни, чи додання нового тексту не було. Як я вже писав, кількість слів якою спілкуються люди — обмежена. То ж вірогідність того, що слова з нового тексту вже були у списку - висока! Навіть їх версії з помилками, яких теж було достатньо.

Мінуси

Хоч часу на виконання коду на реальних даних витрачалося небагато, варто зазначити що для великого об’єму даних та великої кількості користувачів, таке рішення не є ідеальним.

Іншим мінусом є сам алгоритм LD: для цього алгоритму слова taste i test будуть подібними, хоч і мають кардинально різне значення.

Висновки

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