Комментарии 16
Демо стенд быстроработает и на первый взгляд хорошо находит то что искали.
А опечатки вида перестановки букв местами не будет поддерживать?
Есть ли реализация которой уже можно воспользоваться?
Сколько занимают подготовленные матрицы?
А опечатки вида перестановки букв местами не будет поддерживать?
Есть ли реализация которой уже можно воспользоваться?
Сколько занимают подготовленные матрицы?
Демо стенд быстроработает и на первый взгляд хорошо находит то что искали.
Спасибо! Реализовано на C#, использован многопоточный цикл (Parallel.For). Хостинг – самый дешевый .NET на REG.RU, плюс сам поиск (по Войне и миру) организован в 2 этапа — сначала грубая оценка всего массива строк (1490 страниц) с ограничением по длине групп больше или равно 2, затем уточненная для первых 100 элементов грубой оценки с формированием данных для отображения, далее результаты отсекаются по порогу коэффициента > 0.5. И еще несколько моментов, позволяющих ускорить расчет. Есть возможности еще ускорить – не стал этого делать, чтобы не потерять «наглядность» алгоритма.
А опечатки вида перестановки букв местами не будет поддерживать?
Если не сложно, просьба прислать пример. Если я правильно понял, то видимо вопрос в отображении результатов. Перестановки букв находят отражение в коэффициенте. То есть в визуальном отображении результатов поиска рядом стоящие идущие подряд в строке поиска и переставленные местами символы строки данных будут отображаться одинаково, но коэффициент будет разным. Например «абв» с «абв» даст коэффициент 1, а «абв» и «вба» только 0.61. Но с отображением можно поработать, как и самим поиском – по конкретным кейсам.
Сейчас алгоритм стенда не содержит никаких изощренных особенностей и довольно легок для восприятия. Все практически как в описании, только немного более хитрый выбор лучшей группы и обработки пересечений.
Есть ли реализация которой уже можно воспользоваться?
реализация только та, что на демо-стенде (на C#, MVC).
Сколько занимают подготовленные матрицы?
Если я правильно понял вопрос. Никакой предварительной индексации текста не производится, все вычисления происходят «как в первый раз», в оперативной памяти находится только массив строк текста «Войны и мира» — не стал связываться с БД.
Пример с опечаткой поиск по «вйона» вместо «война».
С пропуском букв кстати хорошо работает, поиск по «голву» вместо «голову».
Я подумал, что матрицы предварительно сгенерированные берутся из БД, класно что на лету всё, т.е. ещё быстрее может всё работать?
C# не наша платформа, только если в виде сервиса с API на .NET Core в Docker, или консольной утилиты смогли бы к себе внедрить. На Python портировать смысла наверное нет, производительность упадёт.
А сравнивали с другими реализациями нечеткого поиска? Elastic и т.п.? По скорости и качеству.
Мы просто пользуемся в паре мест github.com/seatgeek/fuzzywuzzy (на левенштейне работает) для нечеткого поиска по небольшому сету строк (до 2000 строк, длина не более 100 символов), но он работает очень уж медленно.
С пропуском букв кстати хорошо работает, поиск по «голву» вместо «голову».
Я подумал, что матрицы предварительно сгенерированные берутся из БД, класно что на лету всё, т.е. ещё быстрее может всё работать?
C# не наша платформа, только если в виде сервиса с API на .NET Core в Docker, или консольной утилиты смогли бы к себе внедрить. На Python портировать смысла наверное нет, производительность упадёт.
А сравнивали с другими реализациями нечеткого поиска? Elastic и т.п.? По скорости и качеству.
Мы просто пользуемся в паре мест github.com/seatgeek/fuzzywuzzy (на левенштейне работает) для нечеткого поиска по небольшому сету строк (до 2000 строк, длина не более 100 символов), но он работает очень уж медленно.
Пример с опечаткой поиск по «вйона» вместо «война».Да, спасибо, хороший пример. Можно это решить. Плохой поиск по этой строке происходит вот почему. «вйона» и «война» дают 3 группы — «йна», «в» и «о». Сначала отбирается «йна», но она тут же отрбрасывается, так как группа, находящаяся внутри слова, подбирается в результат только в том случае, если у слова уже подобрана начальная часть. Если этого не делать, возникает некий мусор в результатах, но думаю результат из этого примера хуже, чем тот мусор. Это я сделал уже что называется «на закуску». Подумаю как лучше сделать.
C# не наша платформа, только если в виде сервиса с API на .NET Core в Docker, или консольной утилиты смогли бы к себе внедрить. На Python портировать смысла наверное нет, производительность упадёт.
Для меня этот проект скорее хобби и возможность поработать на других платформах, так как я на 1С специализируюсь (так исторически сложилось). Но можно решить я думаю. Есть старый вариант dll на С++, правда там без многопоточности.
Еще пример плохого поиска — "крове" (опечатка для поиска "кроме"). Не находит не одного релевантного совпадения в первой сотне. Если исправить опечатку (т.е. искать "кроме"), вся первая сотня содержит это слово.
Алгоритм с отсечением единичных букв для "крове" вообще находит только одну страницу и подсвечивает "кр" в "крикнул".
Кстати, вот не согласен, что в первую очередь важна скорость. В первую очередь важен результат. Лучше искать чуть медленнее, но более релевантно, особенно по "плохим" словам, чем совсем их отсекать.
За примеры спасибо!
На сайте tools41.ru кстати есть встроенный поиск по сайту от Яндекса, вот ссылка на него: tools41.ru/Home/Pagination?Length=0 Поиск установлен давно, уже год примерно.
Яндекс по умолчанию опечатки исправляет еще до старта поиска — думаю в этом есть смысл. По «крове» и по «вйона» тоже будет пусто (в кавычках если набирать, чтобы не исправил).
По поводу скорости, я согласен с Вами — приоритетно качество.
Имелось ввиду, что, например, зная эпизод сцены вызова Долохова Пьером на дуэль, и что в тексте вызов происходит на странице 378, я ввожу строку «пьер вызывает долохова на дуэль» — результат и в быстрой и в медленной версии меня устраивает, искомая страница на 2-м месте, остальные значимые страницы эпизода тоже в первой десятке. Тогда я предпочту быструю версию. То же самое по другим фрагментам — «вечер у анны павловны шерер», «самоуверенность немца, француза, русского» (интересное рассуждение на странице 782).
В случае опечаток да, медленная версия выигрывает, но тоже не самым лучшим образом.
На сайте tools41.ru кстати есть встроенный поиск по сайту от Яндекса, вот ссылка на него: tools41.ru/Home/Pagination?Length=0 Поиск установлен давно, уже год примерно.
Яндекс по умолчанию опечатки исправляет еще до старта поиска — думаю в этом есть смысл. По «крове» и по «вйона» тоже будет пусто (в кавычках если набирать, чтобы не исправил).
По поводу скорости, я согласен с Вами — приоритетно качество.
Имелось ввиду, что, например, зная эпизод сцены вызова Долохова Пьером на дуэль, и что в тексте вызов происходит на странице 378, я ввожу строку «пьер вызывает долохова на дуэль» — результат и в быстрой и в медленной версии меня устраивает, искомая страница на 2-м месте, остальные значимые страницы эпизода тоже в первой десятке. Тогда я предпочту быструю версию. То же самое по другим фрагментам — «вечер у анны павловны шерер», «самоуверенность немца, француза, русского» (интересное рассуждение на странице 782).
В случае опечаток да, медленная версия выигрывает, но тоже не самым лучшим образом.
Предложил бы посмотреть на fst
Поторопился, прошу прощения.
«вйона» и «война», группы «в», «й», «о» и «на». При грубом проходе группы единичной длины игнорируются, поэтому и результат такой плохой, так как остаются только страницы, содержащие «на», а эта группа есть почти везде. Причина в этом и только в этом.
Убрал отсечение групп единичной длины при грубом проходе. Скорость обработки снизилась, но зато качество выше. Но думаю все же в большинстве случаев скорость предпочтительней.
«вйона» и «война», группы «в», «й», «о» и «на». При грубом проходе группы единичной длины игнорируются, поэтому и результат такой плохой, так как остаются только страницы, содержащие «на», а эта группа есть почти везде. Причина в этом и только в этом.
Убрал отсечение групп единичной длины при грубом проходе. Скорость обработки снизилась, но зато качество выше. Но думаю все же в большинстве случаев скорость предпочтительней.
На сайте tools41.ru выложил предыдущий, быстрый вариант (с отсечением групп единичной длины), так что теперь можно сравнить результаты.
Поиск по фразам тоже приятные результаты выдаёт.
Напоминает метод N-грамм
Согласен, но я отталкивался от теоретических основ радиолокации и немного «шел своим путем». Фактически числитель формулы вычисления коэффициента состава групп
и есть вычисление ВКФ
только применительно к строкам. Группы пришлось ввести для повышения влияния на результат подряд совпадающих символов, что достигнуто возведением размеров групп в квадрат. Потом обнаружилась проблема пересечений, сначала в одной проекции, затем во второй.
и есть вычисление ВКФ
только применительно к строкам. Группы пришлось ввести для повышения влияния на результат подряд совпадающих символов, что достигнуто возведением размеров групп в квадрат. Потом обнаружилась проблема пересечений, сначала в одной проекции, затем во второй.
Скачал с Инфостарта Вашу обработку, попробую переделать для поиска дублей номенклатуры. Сам делал поиск методом N-грамм на встроенном языке 1С, но чуть-чуть не дошел до финала
Надеюсь дойдете еще. Версия этого алгоритма на языке 1С у меня тоже есть (изначально я на 1С алгоритм разрабатываю, потом переношу на C#), кстати время выполнения очень сильно различается. За то время, которое 1С тратит на вычисления только по одной странице текста, C# успевает обработать все 1490. На Инфостарте предыдущая версия алгоритма, на демо-стенде более продвинутая, но подход тот-же. Надеюсь пригодится. Если доберусь до ее переделки, как увидите на сайте новую версию, напишите — пришлю. Но не обещаю, что доберусь в ближайшее время.
у меня тоже был нечёткий поиск в 3д карте города — поиск заведений и магазинов по адресу, описанию и отзывам (одновременно), очень хорошо всё находилось. Алгоритм был простой — строку поиска разбиваем на слова и потом ищем каждое искомое слово в строке данных, если слово найдено, то вес результата увеличиваем на длину этого слова. Потом сортируем результаты по весам. Если в базе про одно здание написано «проспект Ленина дом 123 магазин Хозяин лаки краски инструменты и т.п.» то для поиска достаточно набрать в любом порядке слова такие например: «краски лаки Ленина». Хотел улучшить чтоб слова с опечатками искались, но не понадобилось, сначала и так было хорошо, а потом проект закрыл т.к. пришёл 2GIS в наш городок. С опечатками можно искать просто по наличию нужных букв в слове (это увеличивает вес результата), а если ещё и порядок букв совпадает — то вес каждой буквы можно умножать на 2
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм нечеткого поиска TextRadar. Основные подходы (ч. 1)