Комментарии 28
Не знаю, на сколько это все очевидно и банальные весчи, но прочитал с удовольствием. Я хоть PostgreSQL не знаю, но наслышан ее мощью. Спасибо. Держите плюс.
Большой минус триграмм — на коротких словах (5 символов) они работают неадекватно при такой популярной опечатке, как перепутанные символы, например:
Обычно в словаре находятся совершенно посторонние слова с большей сходимостью.
'table' % 'tbale' = 0.2. Обычно в словаре находятся совершенно посторонние слова с большей сходимостью.
Да, все верно. Результаты также бывают не очень, при пропущенной букве в маленьком слове.
Поэтому используем проверку по целым фразам, а не отдельно по словам. Вероятность получить глупую подсказку гораздо меньше.
Плюс значение имеет по какому принципу определяется верное слово. В нашем случае берем 5 самых схожих фраз — по какой из них нашлось больше упоминаний, там в большинстве случаев и оказывается верной.
Поэтому используем проверку по целым фразам, а не отдельно по словам. Вероятность получить глупую подсказку гораздо меньше.
Плюс значение имеет по какому принципу определяется верное слово. В нашем случае берем 5 самых схожих фраз — по какой из них нашлось больше упоминаний, там в большинстве случаев и оказывается верной.
суперска ,)
/me записал в книжечку ещё один модуль пг
/me записал в книжечку ещё один модуль пг
Да, триграммы вещь хорошая.
Скажите у вас в какой кодировке база? windows-1251?
Я когда-то давно пытался их использовать с UTF-8. Латиница обрабатывалась отлично, а вот с русскими символами были проблемы. Дело в том, что триграмма рубит слово не по буквам, а по байтам! Поэтому на выходе были обрубки букв:
Теретически, искать по такому можно — т.к. похожие байты все равно встречаются. Но качество такого поиска мне не понравилось.
Скажите у вас в какой кодировке база? 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)
Теретически, искать по такому можно — т.к. похожие байты все равно встречаются. Но качество такого поиска мне не понравилось.
Да, у нас win.
megadb=# SELECT show_trgm('Пушкин');
show_trgm
-------------------------------------
{"ин ",кин,пуш,ушк,шки," пу"," п"}
(1 row)
Я в итоге перешел на расстояние Левеншейна.
Но опять же его реализация в PG оставляла желать лучшего. При работе с русскими буквами в UTF-8 он их считал за 2 буквы, поэтому расстояние иногда удваивалось, а иногда нет.
Пришлось написать такую функцию на plpgsql — она корректно работала. Хотя и существенно медленнее.
Но опять же его реализация в PG оставляла желать лучшего. При работе с русскими буквами в UTF-8 он их считал за 2 буквы, поэтому расстояние иногда удваивалось, а иногда нет.
Пришлось написать такую функцию на plpgsql — она корректно работала. Хотя и существенно медленнее.
пушнин путин -> Возможно, Вы имели в виду «путин»
Всё правильно! ;)
Всё правильно! ;)
>>>ибо время до чужого сервера и назад, да и в целом не очень хорошо.
Тяга к техническому творчеству это хорошо, но на пользу ли это вашему проекту?
Не знаю какое получится время до чужого сервера, а вот пользователю сайта больше понравится результат сильного алгоритма автоисправления, например если вы воспользуетесь гугловским (или еще чьим проверенным) поиском внутри сайта, нежели результат от сделанного по-быстрому для «чтобы было своё».
Тяга к техническому творчеству это хорошо, но на пользу ли это вашему проекту?
Не знаю какое получится время до чужого сервера, а вот пользователю сайта больше понравится результат сильного алгоритма автоисправления, например если вы воспользуетесь гугловским (или еще чьим проверенным) поиском внутри сайта, нежели результат от сделанного по-быстрому для «чтобы было своё».
Это вопрос целесообразности. Никто не спорит о громадном преимуществе текстового поиска гугла, но искать товары в каталоге лучше по определенным параметрам, и те вещи, которые у нас есть в расширенном поиске, например, при всем желании не прикрутить к поиску гугла.
К тому же полнотекстовый поиск в базах данных — абсолютно нормальная вещь и используется повсеместно. Вас же не смущает что в углу страницы хабра есть поле поиска по сайту и реализован он не с помощью стороннего api, а с использованием sphinx))
А уж по поводу «сделанного по-быстрому» вообще нечего сказать. Если статья читается за 5 минут, это не значит, что придумывается и реализовывается все за то же время)
К тому же полнотекстовый поиск в базах данных — абсолютно нормальная вещь и используется повсеместно. Вас же не смущает что в углу страницы хабра есть поле поиска по сайту и реализован он не с помощью стороннего api, а с использованием sphinx))
А уж по поводу «сделанного по-быстрому» вообще нечего сказать. Если статья читается за 5 минут, это не значит, что придумывается и реализовывается все за то же время)
почему по ссылке _тут_(read.ru/id/442820/) «ушкин» не нашел «пушкин»?
read.ru/search/ушкин/
Тут уже нашлась книга, поэтому подсказок не выдаем. Пробовали разные значения, меньше 5-ти, меньше 10-ти найденных. Часто люди ищут по полному названию с автором, подсказки в этом случае бывают лишними.
Тут уже нашлась книга, поэтому подсказок не выдаем. Пробовали разные значения, меньше 5-ти, меньше 10-ти найденных. Часто люди ищут по полному названию с автором, подсказки в этом случае бывают лишними.
Когда то пытался решить похожую проблему через soundex функции. Смысл заключался в следующем: брался словарь русских слов и отдельной колонкой записывался SOUNDEX слов.
Далее если ispell говорил что слово неверно написано я сравнивал слово с похожими по произношению и пытался найти слова схожие по произношению.
Увы метод тоже оказался с весьма большой погрешностью.
Далее если ispell говорил что слово неверно написано я сравнивал слово с похожими по произношению и пытался найти слова схожие по произношению.
Увы метод тоже оказался с весьма большой погрешностью.
Когда-то писала бакалаврскую по сравнению методов нечеткого поиска, и у меня получилось, что как раз триграммный метод для русского и украинского языков дает далеко не лучшие результаты, да и SoundEx тоже — лучшими были «максимальная общая подстрока» и «расстояние Левенштейна». Приятно видеть, что где-то он все-таки используется.
А к MySQL это всё применимо? Или хотя бы второй вариант???
Вполне вероятно, что для MySql есть подобные модули, но я не встречал. Поверхностный поиск в сети тоже ничего не дал, хотя может нужно поискать тщательней.
а что мешает использовать второй способ — с триграммами?
разбить слово при помощи PHP на трехбуквенные кусочки и поискать их в мускуле…
или я ошибаюсь и второй вариант работает совсем по-другому?
разбить слово при помощи PHP на трехбуквенные кусочки и поискать их в мускуле…
или я ошибаюсь и второй вариант работает совсем по-другому?
Ну чисто теоретически наверно можно, но много сложностей. Например, вы же не знаете, какие триграммы будут в поле, какие нет — придется искать по условию «или», а в этом случае будет будет слишком много результатов даже на небольшой фразе.
Следующая проблема — рейтинг, придется писать какую-то функцию в MySql, которая будет считать количество вхождений, чтобы потом сортировать по ее результату.
И самое главное — производительность. Непонятно, насколько быстро это будет работать.
Хотя, если создать отдельное поле, сразу заполнить его триграммами и повесить полнотекстовый индекс, то можно попробовать) Если вдруг решитесь, напишите о результатах, интересно)
Следующая проблема — рейтинг, придется писать какую-то функцию в MySql, которая будет считать количество вхождений, чтобы потом сортировать по ее результату.
И самое главное — производительность. Непонятно, насколько быстро это будет работать.
Хотя, если создать отдельное поле, сразу заполнить его триграммами и повесить полнотекстовый индекс, то можно попробовать) Если вдруг решитесь, напишите о результатах, интересно)
Прошло почти 2 месяца…
Продолжил измышления. Прошу поправить, если я ошибаюсь.
Составим индекс. Если составлять его из триграмм — получится довольно большой индекс, т.к. кол-во вариаций с тремя символами в любом случае больше, чем с двумя. Поэтому решено сделать «стереограммы». Каждая статья разбивается на слова (за счет пробелов), а каждое слово — на стереограммы, которые прописываются в таблицу стереограмм в базе данных. Каждая статья имеет свой номер.
Пример таблицы:
_а — 234, 567, 234
_б — 432, 322, 234
пи — 324, 343, 244
Очевидные условия:
— при заполнении индекса — если стереограмма слова со страницы уже присутствует в таблице стереограмм — повторно не заносить, не дублировать
Далее — сам поиск.
Возьмем слово «Пужкин», разобъем его на стереограммы:
_п, пу, уж, жк, ки, ин, н_
ищем каждую стереограмму в таблице по отдельности, получая список номеров страниц, где она встречается.
На основании сравнения общих совпадений выдаем список страниц по рейтингу двух типов совпадений: полное и частичное (без одной стереограммы).
Идея не совсем полноценная, т.к. есть вероятность нахождения подобных стереограмм в тексте, в котором вообще нет ничего похожего на Пушкина. Но идею можно дополнить полнотекстовым поиском сочетаниц стереограмм по отобранным статьям, сначала из полного совпадения и, при нулевом результате — из частичного совпадения.
Надеюсь, что изложил доступно.
Продолжил измышления. Прошу поправить, если я ошибаюсь.
Составим индекс. Если составлять его из триграмм — получится довольно большой индекс, т.к. кол-во вариаций с тремя символами в любом случае больше, чем с двумя. Поэтому решено сделать «стереограммы». Каждая статья разбивается на слова (за счет пробелов), а каждое слово — на стереограммы, которые прописываются в таблицу стереограмм в базе данных. Каждая статья имеет свой номер.
Пример таблицы:
_а — 234, 567, 234
_б — 432, 322, 234
пи — 324, 343, 244
Очевидные условия:
— при заполнении индекса — если стереограмма слова со страницы уже присутствует в таблице стереограмм — повторно не заносить, не дублировать
Далее — сам поиск.
Возьмем слово «Пужкин», разобъем его на стереограммы:
_п, пу, уж, жк, ки, ин, н_
ищем каждую стереограмму в таблице по отдельности, получая список номеров страниц, где она встречается.
На основании сравнения общих совпадений выдаем список страниц по рейтингу двух типов совпадений: полное и частичное (без одной стереограммы).
Идея не совсем полноценная, т.к. есть вероятность нахождения подобных стереограмм в тексте, в котором вообще нет ничего похожего на Пушкина. Но идею можно дополнить полнотекстовым поиском сочетаниц стереограмм по отобранным статьям, сначала из полного совпадения и, при нулевом результате — из частичного совпадения.
Надеюсь, что изложил доступно.
Ну здесь несколько моментов:
1. Комбинаций по 2 буквы вообще не много, собственно примерно 33^2, можно и сразу заполнить.
2. Все-таки искать сразу в тексте ничего не даст. В любом случае надо сначала искать слова/фразы. То есть набор «стереограмм» или «триграмм» надо искать в пределах одного слова/фразы, а потом ссылать на статью. Во-первых, надо же показать правильное слово, а второе — уверен, что любой набор из 2-х букв будет встречаться практически в любом тексте. Если не все стереограммы, то большая часть из набора.
3. 3 буквы, а не 2, используются для того, чтобы была большая определенность, больший процент вероятности совпадения. Мне кажется, лучше пробовать с 3-мя.
Интересно, что получилось в результате? Или это еще пока идея?
1. Комбинаций по 2 буквы вообще не много, собственно примерно 33^2, можно и сразу заполнить.
2. Все-таки искать сразу в тексте ничего не даст. В любом случае надо сначала искать слова/фразы. То есть набор «стереограмм» или «триграмм» надо искать в пределах одного слова/фразы, а потом ссылать на статью. Во-первых, надо же показать правильное слово, а второе — уверен, что любой набор из 2-х букв будет встречаться практически в любом тексте. Если не все стереограммы, то большая часть из набора.
3. 3 буквы, а не 2, используются для того, чтобы была большая определенность, больший процент вероятности совпадения. Мне кажется, лучше пробовать с 3-мя.
Интересно, что получилось в результате? Или это еще пока идея?
1. Точнее 34^2…
2. Проверил. Действительно почти в любом мало-мальски нормальном тексте (1-2 «страницы»).
3. Пришлось нехотя согласиться с тремя буквами, хоть это и получается 34 в третьей степени (добавляется символ «пробел» или заменяющее его «подчеркивание»). В общем около 40 тысяч строк получится в таблице. Первая ячейка — varchar (3), вторая — text.
4. Для экономии места стоит ли автоматически сокращать запись во второй ячейке при перечислении номеров страниц типа «34,35,36,37,38,39» до «34-39»?
5. Для ускорения работы поиска можно сначала поискать обычным методом (полнотекстовый поиск) и если результат будет равен 0 — искать с опечатками, а если результат будет положительным — предложить пользователю также возможность поискать с опечатками… Это спорный вопрос, готов выслушать ваше мнение.
2. Проверил. Действительно почти в любом мало-мальски нормальном тексте (1-2 «страницы»).
3. Пришлось нехотя согласиться с тремя буквами, хоть это и получается 34 в третьей степени (добавляется символ «пробел» или заменяющее его «подчеркивание»). В общем около 40 тысяч строк получится в таблице. Первая ячейка — varchar (3), вторая — text.
4. Для экономии места стоит ли автоматически сокращать запись во второй ячейке при перечислении номеров страниц типа «34,35,36,37,38,39» до «34-39»?
5. Для ускорения работы поиска можно сначала поискать обычным методом (полнотекстовый поиск) и если результат будет равен 0 — искать с опечатками, а если результат будет положительным — предложить пользователю также возможность поискать с опечатками… Это спорный вопрос, готов выслушать ваше мнение.
Предположим, на сайте 1000 страниц.
Номера в основном трехзначные, т.е. 3 байта.
В среднем предположим, что под запись во вторую ячейку будут попадать 65% страниц, т.е. 650.
Умножим 650 на 3 = 1950, округлим до 2000 байт.
Умножим кол-во строк 40 тысяч на размер одной строки 2000 байт = 80 000 000 байт = 78125 Кбайт ≈ 76 Мбайт.
Округлим до максимума — 100 Мбайт с каждой тысячи страниц ради поиска с опечатками.
Стоит ли это результата? Думаю, стоит!
Номера в основном трехзначные, т.е. 3 байта.
В среднем предположим, что под запись во вторую ячейку будут попадать 65% страниц, т.е. 650.
Умножим 650 на 3 = 1950, округлим до 2000 байт.
Умножим кол-во строк 40 тысяч на размер одной строки 2000 байт = 80 000 000 байт = 78125 Кбайт ≈ 76 Мбайт.
Округлим до максимума — 100 Мбайт с каждой тысячи страниц ради поиска с опечатками.
Стоит ли это результата? Думаю, стоит!
Это конечно всё хорошо, но, думаю, надо еще отдать приоритет согласным и первым-последним буквам, т.к. их расположение является определяющим. Еще стоит учитывать раскладку клавиатуры и учитывать в первую очередь наиболее вероятные опечатки, ну и переводить в другую раскладку автоматически при необходимости, a-la Punto Switcher. Это решается более продвинутым индексом, который складывает очки для каждого варианта. То есть, для каждого слова генерируется набор условий и очки, а затем выполняется поиск и вычисление наиболее подходящих вариантов. Надо еще подумать о фразах, поскольку наиболее подходящий вариант можно подобрать по контексту.
Кстати говоря, зачем использовать толстые словари? Можно в качестве словаря использовать множество слов в собственной базе
Кстати говоря, зачем использовать толстые словари? Можно в качестве словаря использовать множество слов в собственной базе
Перевод в другую раскладку используем.
read.ru/search/geirby/
По поводу словарей, тоже так и делали. В посте было — словари, плюс собственная база, разбитая по словам.
read.ru/search/geirby/
По поводу словарей, тоже так и делали. В посте было — словари, плюс собственная база, разбитая по словам.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Триграммный индекс или «Поиск с опечатками»