Поиск статьи в БД и вычет % схожести

Question

[Степан]

Реально ли такое сделать?

Есть БД со статьями. При добавлении новой нужно искать в БД есть ли что то похожее на нее.
Читать все по очереди и сравнивать очень не выгодно со стороны нагрузки.
Возможно составить какой то хеш по которому и искать?

Answer 1

[sergeypid]

Для приблизительного сравнения текстов есть такой способ: составить нулевую матрицу 30х30, координаты матрицы — буквы алфавита. Пробегаемся по тексту и считаем, сколько раз в текста встречались последовательные пары букв. Например, если видим подряд буквы А и Б, прибавляем 1 к элементу [0, 1] матрицы. Потом нормируем — делим все элементы матрицы на общее число букв в тексте. В результате получится хэш-матрица, ее запоминаем для каждой статьи в БД.

Для проверяемой статьи строим такую же матрицу и вычитаем ее из хэш-матрицы каждой статьи в БД. Считаем сумму квадратов получившихся элементов. Исследуем на 20-40 типовых статьях и выводим пороговое значение. Для коротких текстов (порядка 100-500 букв) хорошо работало, попробуйте на ваших статьях!

В теории это имеет отношение к марковским цепям, n-граммам (2 граммам :)

Comments

[diger_74]

Какой интересный способ!
Получается, что мы проверяем среднеквадратичное отклонение по частоте последовательностей букв? В теории звучит очень даже заманчиво…

[FinDK]

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

[Степан]

Вроде и матфак заканчивал, и понимаю о чем вы говорите… 30х30 это еще только минимум. А учитывая латиницу? Составить мартицу не сложно, а вот упростить такой порядок наверное не смогу даже програмно:)

При вашем варианте все равно нужно читать хэш-матрицу каждой статьи и сравнивать с новой. Для сравнивания 2х стрингов есть готовые функции :)

Я что то более склонен к алгоритму Хаффмана или какому то другому методу сжатия (тут даже подойдет с потерями). Словарь у нас в принципе один. Нужно закодировать пару статей разными методами и посмотреть что из этого выйдет :)

[Степан]

Задание грубо говоря состоит в том, что бы упростить набор слов до одной строки. То есть если имеем две почти одинаковые статьи то и эти закодированная строки не будет сильно отличаться.

Answer 2

[TROODON]

Самое простое решение поднять поисковой движок sphinx/lucene(elasticsearch, Solr) и индексировать все статьи, при добавлении новой статьи отправить в поисковик запрос указав поля тело = тело, заголовок=заголовок и смотреть на размер вхождений.
Высокое значение вхождений — Статья похожа

Answer 3

[SergeiStartsev]

Можно при добавлении каждой статьи составлять (1 раз) ее карту, она может иметь различный вид, все зависит от того насколько релевантные должны быть результаты (как наиболее простой вариант — выбирать наиболее часто употребляемые слова), а затем уже производить анализ по этой карте.

Comments

[Степан]

По наиболее часто встречаемым словам и я думал. Но может есть решение проще а я его не вижу?
Сравнивать карты тоже не очень и просто. Хотя и реализуемо.

[SergeiStartsev]

Искать похожие результаты в плохо формализованных данных (которыми является человеческий язык) задача по умолчанию непростая, примерно тоже самое делает для вас гугл, когда ищет сайты, релевантные вашему запросу, так что вряд ли здесь есть простое решение в общем случае.

Answer 4

[gkirok]

алгоритм nilsimsa

поищите perl-Digest-Nilsimsa
создаете хэш для каждой статьи кладете в базку
сравнение кажется побитное непомню использовал давно
точный (если куски текста просто поменяны местами находит 100% идентичность)
относительно быстрый
не латиницу перед созданием хэша транслитеруйте