Хабрахабр / Комментарии к посту «Триграммный индекс или «Поиск с опечатками»» в блоге «PostgreSQL»

16.02.2010 20:51:19 13i

13i — Tue, 16 Feb 2010 20:51:19 GMT

Несмотря на быстродопущенные ляпы (например 650 надо умножать на 4, т.к. еще разделитель нужен), результат примерно остается таким же — 100 Мбайт, а если применить описанное выше сжатие — около 60 Мбайт.

16.02.2010 20:47:25 13i

13i — Tue, 16 Feb 2010 20:47:25 GMT

Предположим, на сайте 1000 страниц.
Номера в основном трехзначные, т.е. 3 байта.
В среднем предположим, что под запись во вторую ячейку будут попадать 65% страниц, т.е. 650.
Умножим 650 на 3 = 1950, округлим до 2000 байт.
Умножим кол-во строк 40 тысяч на размер одной строки 2000 байт = 80 000 000 байт = 78125 Кбайт ≈ 76 Мбайт.

Округлим до максимума — 100 Мбайт с каждой тысячи страниц ради поиска с опечатками.
Стоит ли это результата? Думаю, стоит!

16.02.2010 20:38:35 13i

13i — Tue, 16 Feb 2010 20:38:35 GMT

1. Точнее 34^2…

2. Проверил. Действительно почти в любом мало-мальски нормальном тексте (1-2 «страницы»).

3. Пришлось нехотя согласиться с тремя буквами, хоть это и получается 34 в третьей степени (добавляется символ «пробел» или заменяющее его «подчеркивание»). В общем около 40 тысяч строк получится в таблице. Первая ячейка — varchar (3), вторая — text.

4. Для экономии места стоит ли автоматически сокращать запись во второй ячейке при перечислении номеров страниц типа «34,35,36,37,38,39» до «34-39»?

5. Для ускорения работы поиска можно сначала поискать обычным методом (полнотекстовый поиск) и если результат будет равен 0 — искать с опечатками, а если результат будет положительным — предложить пользователю также возможность поискать с опечатками… Это спорный вопрос, готов выслушать ваше мнение.

16.02.2010 20:16:01 sel

sel — Tue, 16 Feb 2010 20:16:01 GMT

Ну здесь несколько моментов:
1. Комбинаций по 2 буквы вообще не много, собственно примерно 33^2, можно и сразу заполнить.
2. Все-таки искать сразу в тексте ничего не даст. В любом случае надо сначала искать слова/фразы. То есть набор «стереограмм» или «триграмм» надо искать в пределах одного слова/фразы, а потом ссылать на статью. Во-первых, надо же показать правильное слово, а второе — уверен, что любой набор из 2-х букв будет встречаться практически в любом тексте. Если не все стереограммы, то большая часть из набора.
3. 3 буквы, а не 2, используются для того, чтобы была большая определенность, больший процент вероятности совпадения. Мне кажется, лучше пробовать с 3-мя.

Интересно, что получилось в результате? Или это еще пока идея?

16.02.2010 18:28:01 13i

13i — Tue, 16 Feb 2010 18:28:01 GMT

Прошло почти 2 месяца…
Продолжил измышления. Прошу поправить, если я ошибаюсь.

Составим индекс. Если составлять его из триграмм — получится довольно большой индекс, т.к. кол-во вариаций с тремя символами в любом случае больше, чем с двумя. Поэтому решено сделать «стереограммы». Каждая статья разбивается на слова (за счет пробелов), а каждое слово — на стереограммы, которые прописываются в таблицу стереограмм в базе данных. Каждая статья имеет свой номер.

Пример таблицы:
_а — 234, 567, 234
_б — 432, 322, 234
пи — 324, 343, 244

Очевидные условия:
— при заполнении индекса — если стереограмма слова со страницы уже присутствует в таблице стереограмм — повторно не заносить, не дублировать

Далее — сам поиск.
Возьмем слово «Пужкин», разобъем его на стереограммы:
_п, пу, уж, жк, ки, ин, н_
ищем каждую стереограмму в таблице по отдельности, получая список номеров страниц, где она встречается.
На основании сравнения общих совпадений выдаем список страниц по рейтингу двух типов совпадений: полное и частичное (без одной стереограммы).

Идея не совсем полноценная, т.к. есть вероятность нахождения подобных стереограмм в тексте, в котором вообще нет ничего похожего на Пушкина. Но идею можно дополнить полнотекстовым поиском сочетаниц стереограмм по отобранным статьям, сначала из полного совпадения и, при нулевом результате — из частичного совпадения.

Надеюсь, что изложил доступно.

20.12.2009 13:45:27 sel

sel — Sun, 20 Dec 2009 13:45:27 GMT

Ну чисто теоретически наверно можно, но много сложностей. Например, вы же не знаете, какие триграммы будут в поле, какие нет — придется искать по условию «или», а в этом случае будет будет слишком много результатов даже на небольшой фразе.
Следующая проблема — рейтинг, придется писать какую-то функцию в MySql, которая будет считать количество вхождений, чтобы потом сортировать по ее результату.
И самое главное — производительность. Непонятно, насколько быстро это будет работать.

Хотя, если создать отдельное поле, сразу заполнить его триграммами и повесить полнотекстовый индекс, то можно попробовать) Если вдруг решитесь, напишите о результатах, интересно)

19.12.2009 16:50:33 13i

13i — Sat, 19 Dec 2009 16:50:33 GMT

а что мешает использовать второй способ — с триграммами?
разбить слово при помощи PHP на трехбуквенные кусочки и поискать их в мускуле…

или я ошибаюсь и второй вариант работает совсем по-другому?

19.12.2009 10:47:13 sel

sel — Sat, 19 Dec 2009 10:47:13 GMT

Вполне вероятно, что для MySql есть подобные модули, но я не встречал. Поверхностный поиск в сети тоже ничего не дал, хотя может нужно поискать тщательней.

19.12.2009 10:41:38 sel

sel — Sat, 19 Dec 2009 10:41:38 GMT

Перевод в другую раскладку используем.
read.ru/search/geirby/

По поводу словарей, тоже так и делали. В посте было — словари, плюс собственная база, разбитая по словам.

19.12.2009 09:49:23 TravisBickle

TravisBickle — Sat, 19 Dec 2009 09:49:23 GMT

Это конечно всё хорошо, но, думаю, надо еще отдать приоритет согласным и первым-последним буквам, т.к. их расположение является определяющим. Еще стоит учитывать раскладку клавиатуры и учитывать в первую очередь наиболее вероятные опечатки, ну и переводить в другую раскладку автоматически при необходимости, a-la Punto Switcher. Это решается более продвинутым индексом, который складывает очки для каждого варианта. То есть, для каждого слова генерируется набор условий и очки, а затем выполняется поиск и вычисление наиболее подходящих вариантов. Надо еще подумать о фразах, поскольку наиболее подходящий вариант можно подобрать по контексту.
Кстати говоря, зачем использовать толстые словари? Можно в качестве словаря использовать множество слов в собственной базе

19.12.2009 09:17:22 13i

13i — Sat, 19 Dec 2009 09:17:22 GMT

А к MySQL это всё применимо? Или хотя бы второй вариант???

18.12.2009 14:09:57 el777

el777 — Fri, 18 Dec 2009 14:09:57 GMT

Я в итоге перешел на расстояние Левеншейна.
Но опять же его реализация в PG оставляла желать лучшего. При работе с русскими буквами в UTF-8 он их считал за 2 буквы, поэтому расстояние иногда удваивалось, а иногда нет.
Пришлось написать такую функцию на plpgsql — она корректно работала. Хотя и существенно медленнее.

18.12.2009 13:22:41 el777

el777 — Fri, 18 Dec 2009 13:22:41 GMT

Я в конечном итоге перешел на расстояние Левеншейна.

18.12.2009 13:17:37 Nicolette

Nicolette — Fri, 18 Dec 2009 13:17:37 GMT

Когда-то писала бакалаврскую по сравнению методов нечеткого поиска, и у меня получилось, что как раз триграммный метод для русского и украинского языков дает далеко не лучшие результаты, да и SoundEx тоже — лучшими были «максимальная общая подстрока» и «расстояние Левенштейна». Приятно видеть, что где-то он все-таки используется.

18.12.2009 10:44:52 sel

sel — Fri, 18 Dec 2009 10:44:52 GMT

read.ru/search/ушкин/

Тут уже нашлась книга, поэтому подсказок не выдаем. Пробовали разные значения, меньше 5-ти, меньше 10-ти найденных. Часто люди ищут по полному названию с автором, подсказки в этом случае бывают лишними.

18.12.2009 10:20:36 cat_crash

cat_crash — Fri, 18 Dec 2009 10:20:36 GMT

Когда то пытался решить похожую проблему через soundex функции. Смысл заключался в следующем: брался словарь русских слов и отдельной колонкой записывался SOUNDEX слов.
Далее если ispell говорил что слово неверно написано я сравнивал слово с похожими по произношению и пытался найти слова схожие по произношению.
Увы метод тоже оказался с весьма большой погрешностью.

18.12.2009 05:19:25 JackFrost

JackFrost — Fri, 18 Dec 2009 05:19:25 GMT

почему по ссылке _тут_(read.ru/id/442820/) «ушкин» не нашел «пушкин»?

17.12.2009 21:18:00 sel

sel — Thu, 17 Dec 2009 21:18:00 GMT

Это вопрос целесообразности. Никто не спорит о громадном преимуществе текстового поиска гугла, но искать товары в каталоге лучше по определенным параметрам, и те вещи, которые у нас есть в расширенном поиске, например, при всем желании не прикрутить к поиску гугла.

К тому же полнотекстовый поиск в базах данных — абсолютно нормальная вещь и используется повсеместно. Вас же не смущает что в углу страницы хабра есть поле поиска по сайту и реализован он не с помощью стороннего api, а с использованием sphinx))

А уж по поводу «сделанного по-быстрому» вообще нечего сказать. Если статья читается за 5 минут, это не значит, что придумывается и реализовывается все за то же время)

17.12.2009 20:32:33 Marsikus

Marsikus — Thu, 17 Dec 2009 20:32:33 GMT

>>>ибо время до чужого сервера и назад, да и в целом не очень хорошо.

Тяга к техническому творчеству это хорошо, но на пользу ли это вашему проекту?
Не знаю какое получится время до чужого сервера, а вот пользователю сайта больше понравится результат сильного алгоритма автоисправления, например если вы воспользуетесь гугловским (или еще чьим проверенным) поиском внутри сайта, нежели результат от сделанного по-быстрому для «чтобы было своё».

17.12.2009 18:26:04 sel

sel — Thu, 17 Dec 2009 18:26:04 GMT

Ну да, такие веселости встречаются.
Поиск основан на статистике, ничего не поделаешь, видимо пользователи не ищут «пушкин путин»)

Вот ближайшие варианты, которые искали:

phrase			similarity
путин			0,6
путилин			0,384615
плакат путин		0,375
владимир путин		0,315789
без путина		0,3125

17.12.2009 17:56:15 acy

acy — Thu, 17 Dec 2009 17:56:15 GMT

пушнин путин -> Возможно, Вы имели в виду «путин»

Всё правильно! ;)

17.12.2009 16:44:55 sel

sel — Thu, 17 Dec 2009 16:44:55 GMT

Да, у нас win.

megadb=# SELECT show_trgm('Пушкин');           
show_trgm              
-------------------------------------
 {"ин ",кин,пуш,ушк,шки," пу","  п"}
(1 row)

17.12.2009 16:14:17 el777

el777 — Thu, 17 Dec 2009 16:14:17 GMT

Да, триграммы вещь хорошая.
Скажите у вас в какой кодировке база? windows-1251?
Я когда-то давно пытался их использовать с UTF-8. Латиница обрабатывалась отлично, а вот с русскими символами были проблемы. Дело в том, что триграмма рубит слово не по буквам, а по байтам! Поэтому на выходе были обрубки букв:

postgres=# SELECT show_trgm('Pushkin');

 show_trgm 

-----------------------------------------

 {" p"," pu",hki,"in ",kin,pus,shk,ush}

(1 row)



postgres=# SELECT show_trgm('Пушкин');

 show_trgm 

------------------------------------------------------------------

 {0x8eb714,0x9092a3,0x922332,0xd19d23,0xfa46f0,0x38e3ee,0x5c1f41}

(1 row)



postgres=# SELECT show_trgm('Мушкин');

 show_trgm 

------------------------------------------------------------------

 {0x9092a3,0x922332,0xd19d23,0xffb97c,0x34e61d,0x38e3ee,0x7c7c68}

(1 row)

Теретически, искать по такому можно — т.к. похожие байты все равно встречаются. Но качество такого поиска мне не понравилось.

17.12.2009 15:12:14 habraname

habraname — Thu, 17 Dec 2009 15:12:14 GMT

суперска ,)
/me записал в книжечку ещё один модуль пг

17.12.2009 14:15:31 sel

sel — Thu, 17 Dec 2009 14:15:31 GMT

Да, все верно. Результаты также бывают не очень, при пропущенной букве в маленьком слове.
Поэтому используем проверку по целым фразам, а не отдельно по словам. Вероятность получить глупую подсказку гораздо меньше.

Плюс значение имеет по какому принципу определяется верное слово. В нашем случае берем 5 самых схожих фраз — по какой из них нашлось больше упоминаний, там в большинстве случаев и оказывается верной.

17.12.2009 14:06:00 deleted-user-afh

deleted-user-afh — Thu, 17 Dec 2009 14:06:00 GMT

Эх, вспоминаю давние времена, когда пытался при помощи триграмм определять язык на котором написан текст :-) Триграммы вообще полезная вещь.

17.12.2009 13:46:05 coldFlame

coldFlame — Thu, 17 Dec 2009 13:46:05 GMT

Большой минус триграмм — на коротких словах (5 символов) они работают неадекватно при такой популярной опечатке, как перепутанные символы, например: 'table' % 'tbale' = 0.2.

Обычно в словаре находятся совершенно посторонние слова с большей сходимостью.

17.12.2009 13:37:27 galkin

galkin — Thu, 17 Dec 2009 13:37:27 GMT

Не знаю, на сколько это все очевидно и банальные весчи, но прочитал с удовольствием. Я хоть PostgreSQL не знаю, но наслышан ее мощью. Спасибо. Держите плюс.