суббота, 5 июля 2014 г.

Черновик. Поиск похожих документов

Я вам не рассказывал как устроен поиск похожих документов?

Линейное векторное пространство знаете что такое?
А евклидово?
Так вот набор документов представляется евклидовым пространством.

В котором введена метрика.

И собственно похожие документы это те у которых скалярное произведение стремится к нулю :-)

Всё дело лишь в том - как метрику определить :-)

Ну и не надо забывать про "нормированость" метрики.

Ну и "продолжеение" - http://programmingmindstream.blogspot.ru/2014/07/blog-post_7.html

25 комментариев:

  1. Этот комментарий был удален автором.

    ОтветитьУдалить
  2. Полнотекстовый поиск?
    Есть Oracle Text, Lucene, Sphinx наконец...
    Векторные пространства - это всё правильно конечно, но IMHO для того, чтобы воспользоваться холодильником не обязательно знать, как устроен компрессор...
    Впрочем, конечно же, всё зависит от задачи. И если требования - заоблачные, а бюджет - открытый, то вполне можно поэкспериментировать и на этом поприще... ;-)

    ОтветитьУдалить
    Ответы
    1. Вы к сожалению путаете "поиск похожих" и "полнотекстовый поиск".

      Про Lucene и Sphinx - мы конечно же в курсе.

      А что до "экспериментировать", то это не совсем верное слово.

      Удалить
    2. Вы к сожалению путаете "поиск похожих" и "полнотекстовый поиск".
      Немудрено спутать. Вы же не определили понятие похожести :-)
      Если речь идёт о сравнении документов, то есть вполне работающие решения на основе расчёта расстояния Левенштейна и аналогов.
      Боюсь соврать, но возможно, в Oracle даже есть решения на этот счёт. Кое-что мы сами применяем, но тут уверенно говорить не могу, поскольку не я курировал эту тему...

      Удалить
  3. Круто. Вот это мне нравится.

    ОтветитьУдалить
  4. Но ведь про самое интересное - саму метрику - ты ни слова не сказал.
    Остальное вроде и так понятно :)

    ОтветитьУдалить
    Ответы
    1. Ну, Ром. Главное - идея. :-) Привязанная к методике. А вот метрика это как раз то, что не рассказывается :-)

      Удалить
  5. Имхо, расстояние Левенштейна не годится для поиска похожих документов, а только для поиска похожих слов (даже не строк). Причем, сам алгоритм очень медленный, нормально работает только в узко очерченных рамках. Для одной задачки (поиск подобных коротких фраз) сначала использовал РС, а потом пришлось написать свой алгоритм, который выдавал результат намного чище и работал на порядок быстрее - потому что был заточен именно под эту задачу.

    Интересно, как была решена задача для поиска подобных текстов.

    ОтветитьУдалить
    Ответы
    1. «расстояние Левенштейна не годится для поиска похожих документов, а только для поиска похожих слов (даже не строк).»
      -- Для фраз подходит, и неплохо, но без модификации - будет давать нестабильные результаты. Например, перестановки слов приводят сразу к большим расстояниям.
      У себя использовали расстояние Джаро-Винклера.
      Сам алгоритм работает быстро (что Левенштейна, что аналоги, основанные на вычислении метрик), проблемы производительности обусловлены способом обработки: расстояние вычисляется для двух фрагментов текста, что не позволяет применять индексный поиск (ну точнее, я не знаю как :-) и вообще сомневаюсь, что это возможно).
      Но ускорить можно, и существенно, выполнив ограничение выборки по дополнительным критериям.

      Введение в тему нечёткого поиска (сопоставления) текстов неплохо обозначена в этой статье. Вот ещё неплохая подборка.

      Ну и, разумеется интересно, если Александр что-нибудь добавит...

      Удалить
  6. Этот комментарий был удален автором.

    ОтветитьУдалить
  7. "Например, перестановки слов приводят сразу к большим расстояниям".

    Именно так. Причем, если фраза короткая (2 - 5 слов), то можно, например, отсортировать слова по алфавиту, убрать предлоги и союзы, удалить окончания, а потом сравнить строки. В коротких фразах перестановка слов обычно большой роли не играет: "мама мыла раму", "мыла раму мама", "раму мыла мама" - смысл один и тот же. Но если фраза длинная (сложноподчиненное, сложносочиненное предложение), то сортировка слов просто искажает смысл и алгоритм будет находить "похожие" фразы, которые могут быть противоположными по смыслу.

    Вообще, нюансов нужно учитывать огромное количество. А то для документа, где много раз встречается слово "кубометр", программа будет находить подобный документ, где говорится об острове Куба. Это, кстати, реальный пример, из жизни ). Поэтому и интересны подробности алгоритма.

    ОтветитьУдалить
    Ответы
    1. "А то для документа, где много раз встречается слово "кубометр", программа будет находить подобный документ, где говорится об острове Куба"

      -- а вот тут мы наблюдаем "ошибку".

      "кубометр" не стоит приводить к "Кубе".

      Но это уже зависит от того, как построена "морфология" и/или нормализация.

      Удалить
    2. Интересно... Как Вы отличите собственное "Кубе", в смысле государства в дательном или предложном падеже от существительного "куб" в предложном?
      IMHO без контекста можно ориентироваться только на регистр первого символа, который может быть простой опечаткой или стремлением акцентировать внимание (Вы например, любите заглавные буквы), а это - очень ненадёжно.
      Спасёт то обстоятельство, что тексты, в которых встречаются словосочетания вида "оттянулся по полной на Кубе" нечасто содержат сентенции о геометрии и/или мерах объёма, тем более, в таких единицах измерения... :-)

      Удалить
    3. простите, о "кубе" и "Кубе" - я НИЧЕГО не говорил.. Я говорил о "кубометре" и "Кубе".. А ведь это "две большие разницы"... Понятное дело, что "в рамках предметной области"...

      Ну и потом - насчёт БОЛЬШИХ БУКВ - большие буквы и "маленькие" - сначала опускаются ВНИЗ, а потом капитализируются "для сравнения со словарём". Понятно?

      Удалить
    4. кпСС или КПсс или кПсС - становится КПСС, но не наоборот...

      Мысль понятна?

      И потом - СНАЧАЛА всё "нормализуется", а потом только считаются "нормы".

      Т.е. СНАЧАЛА текст становится НАБОРОМ НОРМ. Потом "канонизируется". А потом - "всё остальное".

      "Цепочки" или "словосочетания" или "устойчивые цепочки".

      Удалить
    5. Ну и понятно, что "нормализация" она - неоднозначна.

      "Суд" и "суда" - это норма от "судов".

      Т.е. текст ИЗНАЧАЛЬНО превращается в "список цепочек норм".

      А ПОТОМ - "канонизация" и выделение "словосочетаний".

      Удалить
    6. Ну и что касается "словосочетаний".

      "Верховный суд РФ" - это "нормально".
      А "Верховные суда РФ" - это НЕ "нормально".

      Учитывая нашу "предметную область".

      Удалить
    7. «Я говорил о "кубометре" и "Кубе".. А ведь это "две большие разницы"...»
      -- Разумеется. Но известно, что "кубометр" и "куб" часто используются как синонимы. В цитатах простой речи, в литературе например. Впрочем,если предметная область - правовая база, это не существенно и никакие это не синонимы.
      Но я совершенно не об этом. Конечно, это "две большие разницы", но в общем случае разница может быть выявлена только семантически, т.е. с учётом контекста, о чём я и говорил. Слова могут совпасть, если их нормализовать по реальным или возможным словоформам, но контекст - вряд ли.
      Соответственно, тексты с упоминанием государства Куба, будут сильно отличаться (в смысле расстояния) от текстов, в которых упоминаются кубы-кубометры.

      «Ну и потом - насчёт БОЛЬШИХ БУКВ - большие буквы и "маленькие" - сначала опускаются ВНИЗ, а потом капитализируются "для сравнения со словарём". Понятно?»
      -- Откровенно говоря - нет. Не понятно, что значит "опускаются ВНИЗ" (приводятся к нижнему регистру?) и зачем после этого их "капитализировать" (т.е. приводить к верхнему) - почему сразу не привести к верхнему регистру...
      То, что со словарём сравниваете - понятно, не понятно только зачем. Для нормализации? Но в таком случае операций с регистром символов недостаточно... Впрочем, всё зависит от способа поиска в словаре...
      В общем - непонятно.

      Удалить
    8. Пока я писал - Вы уже ответили. Спасибо.
      Много общего с алгоритмом, основанным на шинглах...

      Удалить
    9. "Много общего с алгоритмом, основанным на шинглах..."
      -- логично :-) "ничего нового"...

      Удалить
    10. "Соответственно, тексты с упоминанием государства Куба, будут сильно отличаться (в смысле расстояния) от текстов, в которых упоминаются кубы-кубометры."
      -- конечно! :-) За счёт того, что я описал выше.

      Удалить
    11. "То, что со словарём сравниваете - понятно, не понятно только зачем."
      -- как раз "понятно зачем" :-)
      Чтобы "суда" и "суд" отличить. И "куб" от "Куба".

      "Словарь" это ВАЖНЫЙ элемент "нормализации".

      Удалить
  8. «Причем, если фраза короткая (2 - 5 слов), то можно, например, отсортировать слова по алфавиту, убрать предлоги и союзы, удалить окончания, а потом поискать расстояние Левенштейна.»
    -- Есть модификации алгоритма, которые частично устраняют это свойство. Например, слова можно нормализовать (привести к канонической форме, т.е. без приставок-окончаний) и рассматривать как символы - в таком случае расстояние может существенно сократится...

    «Но если фраза длинная (сложноподчиненное, сложносочиненное предложение), то сортировка слов просто искажает смысл и алгоритм будет находить "похожие" фразы, которые могут быть противоположными по смыслу.»
    -- Сортировка - изначальное искажение смысла. Вряд ли это приемлемо в большинстве случаев...
    Алгоритмы основанные на вычислении расстояний неплохо работают и с документами. Только вместо в качестве символов нужно использовать слова (или, IMHO ещё лучше - нормализованные слова) и даже строки. Diff-ы всяческие, как следует из Википедии, работают именно так.
    Альтернативные подходы изложены по ссылкам которые я привёл выше. Разумеется - не все.
    У нас несколько иная предметная область, документы по подобию нам искать не приходится, а вот похожие фразы (в широком смысле) - очень даже. Модификация алгоритма Джаро-Винклера вполне устраивает в рамках той предметной области, где мы работаем.
    А для сопоставления именно документов (нормализованных текстов, в сущности) IMHO неплохо подходят те же шинглы.
    Критику последних очень хотелось бы услышать...

    ОтветитьУдалить
  9. Друзья мои... Мы про "расстояния" и "перестановки" не говорим.

    Вот это:
    "Только вместо в качестве символов нужно использовать слова (или, IMHO ещё лучше - нормализованные слова) и даже строки. "
    -- уже "ближе к истине".

    Просто "слова" или "цепочки слов" как раз в вычислении метрики и участвуют.

    ОтветитьУдалить
    Ответы
    1. «"слова" или "цепочки слов" как раз в вычислении метрики и участвуют.»
      -- Ну, где-то так и работают алгоритмы, основанные на шинглах.
      Там берутся равные последовательности канонизированных слов "в нахлёст", по ним считаются хэши.
      Имея последовательности хэшей шинглов для искомого документа и проверяемого, можно выполнить их сравнение. Вычислить расстояние того же Левенштейна, например. Проблема в количестве сравнений, поскольку понятно, что чем их больше - тем, вероятно, точнее результат...
      Вот здесь - простым языком...

      Удалить