Вы наверняка видели нечеткий текстовый поиск везде. Например, вы набираете «stck», но на самом деле вы имеете в виду «стек»! Когда-нибудь задумывались, как это работает?
Существует множество алгоритмов для нечеткого сопоставления текста, каждый со своими плюсами и минусами. Самые известные из них - это расстояние редактирования и qgram. Сегодня я хочу сосредоточиться на qgrams и реализовать пример.
В основном qgrams являются наиболее подходящим алгоритмом нечеткого сопоставления строк для реляционных баз данных. Это довольно просто. «q» в qgram будет заменено на число, такое как 2 грамма или 3 грамма или даже 4 грамма.
2 грамма означает, что каждое слово разбито на набор из двух символов. «Стек» будет разбит на набор {«st», «ta», «ac», «ck»} или «база данных» будет разбит на {«da», «at», «ta», «ba». », "как", "с"}.
Как только слова разбиты на 2 грамма, мы можем искать в базе данных набор значений вместо одной строки. Например, если пользователь неправильно набрал «stck», любой поиск по «stck» не будет соответствовать «стеку», потому что «a» отсутствует, но набор из 2 граммов {«st», «tc», «ck»} имеет 2 строки общего с 2-граммовым набором стека! Бинго мы нашли довольно близкий матч. Он не имеет ничего общего с 2-граммовым набором базы данных и только 1 имеет общие черты с 2-граммовым набором «stat», поэтому мы можем легко предложить пользователю, что он хотел напечатать: первый «стек» или второй, «звезда» ».
Теперь давайте реализуем это с помощью Sql Server: предположим, гипотетический набор данных слов. Вы должны иметь много-много отношений между 2 граммами и словами.
CREATE TABLE Grams(twog char(2), wordId int, PRIMARY KEY (twog, wordId))
Таблица граммов должна быть сгруппирована по первой ветке, а затем по слову WordId для производительности. Когда вы запрашиваете слово (например, стек), вы помещаете граммы во временную таблицу. Сначала давайте создадим несколько миллионов фиктивных записей.
--make millions of 2grams
DECLARE @i int =0
WHILE (@i<5000000)
BEGIN
-- a random 2gram
declare @rnum1 char = CHAR(CAST(RAND()*28 AS INT)+97)
declare @rnum2 char = CHAR(CAST(RAND()*28 AS INT)+97)
INS... INTO Grams (twog, wordId) VALUES ( @rnum1 + @rnum2, CAST(RAND()*100000 AS int))
END
Теперь давайте запросим слово «стек», которое будет разбито на: {'st', 'ta', 'ac', 'ck'} два грамма.
DECLARE @word TABLE(twog char(2)) -- 'stack'
INS... INTO @word VALUES ('st'), ('ta'), ('ac'), ('ck')
select wordId, count(*) from @word w inner join Grams g ON w.twog = g.twog
GROUP BY wordId
Вы должны убедиться, что Sql Server использует несколько запросов кластеризованного индекса (или циклов) для выполнения этого запроса. Это должен быть естественный выбор, но иногда статистика может быть повреждена или устарела, и SqlServer может решить, что полное сканирование дешевле. Обычно это происходит, если он не знает мощности левой таблицы, например, SqlServer может предположить, что таблица @word огромна и миллионы циклов будут дороже, чем полное сканирование индекса.