сравнение текстов

[folk]

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

P.S. Если мы в качестве хэша будем использовать сравнение с пустой строкой - то получим просто что то похожее на длину строки - то есть не очень катит. Если использовать слова с частотой по фиксированному словарю то в принципе можно получить число (сопоставляя каждому слову простое)- но большое оно будет и будет сильно плавать.

[Sonic86]

Source of the post мы хотим проверить не является ли новость старостью.

Предполагается точное совпадение новости и старости или нет? Если да, то почему бы и не взять длину? Если совпадение неточное, то надо описать, в чем состоит близость текстов и попытаться строить хэш, отталкиваясь от этого.

Source of the post Если использовать слова с частотой по фиксированному словарю то в принципе можно получить число (сопоставляя каждому слову простое)- но большое оно будет и будет сильно плавать.

Не, зачем Вам простые числа. Юзайте какие-нибудь естественные способы кодировки распределений. Пусть даже тупо XML-ка или там массивы.

[folk]

Новости одинаковые по смыслу - например про ураган катрина. Если уже было то выбрасываем.

[master]

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

Хотя особой уверенности в эффективности нет Тут надо пробовать.

[folk]

такой подход не зависит от порядка слов но с другой стороны может лажануться на тексте который является цитатой - вероятности слов даже относительные будут наверное прыгать - но уже получается здорово сократим объем сравнений.
----
C другой стороны можно наверное построить обратный индекс, тогда вопрос сводится к тому как искать в нем похожие тексты)
нумерация слов
1 2 3 4 5
текст#1: мама папа мама баба папа
текст#2: мама баба папа мама баба

индекс
мама #1(1,3) #2(1,4)
папа #1(2,5) #2(3)
баба #1(4) #2(2,5)

и всего то надо углядеть мама баба папа
----
Но можно наверное поступить по тупому - добавить в обратный индекс вообще все слова которые есть в тексте - все го то n+(n-1)+(n-2)+..+1 ~= n^2/2 слов для строки длины n
И тогда похоже вуаля при вставке в индекс построчек мы увидим есть ли они уже у нас в индексе.
(собственно тут можно и побайтово)

[qwertylol]

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

[folk]

Смысл понимать не надо конечно) По смыслу - борьба с повторным цитированием одной и той же новости. Вопрос был как сделать за один проход - похоже ответ найден - построение индекса (идея - суффиксное дерево)

[Soul]

Поищите "метод шинлов". Его какое-то время назад Яндекс использовал как раз для эти целей.

[folk]

Идея интересная но мне не шибко понравилась - по сути сравнивается сотня случайно выбранных подтекстов по 10 слов. Предложенный метод с индексом мне кажется получше будет)

[qwertylol]

Source of the post
Поищите "метод шинлов". Его какое-то время назад Яндекс использовал как раз для эти целей.

Любопытно, но смущает чувствительность к перестановке слов.