Как определить схожесть текстов? Например, есть много записей в базе и при добавлении новой записи надо проверить, нет ли уже точно таких или схожих более, чем на 80%.

а что за тексты?
и в каком смысле схожесть? (по смыслу, по набору используемых слов)

без этого вряд ли получится что-либо предложить...

статьи на разные тематики



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

по смыслу сложно...
от copy-paste разных кусочков ещё можно пробовать защититься
а от от переписывания своими словами (не просто синонимами, а нормальным пересказом) - сомнительно
(хотя я этой областью особо не интересовался, может, что-то и придумали)

Придумал сегодня в трамвае.
Метод таков, что без определенного словарика не обойтись.
Разбираем все предложения в исходном тексте и в том, который сравниваем, по членам предложения(подлежащее, сказуемое, дополнение, обстоятельство, и др.). Составляем связную базу каждых членов(база подлежащих, сказуемых, где Бсказ(i)<->Бподл(i)).
Затем гоним перебором сравнение по базам подлежащих, сказуемых, др. Причем, при сравнении могут работать логические структуры И, ИЛИ, НЕ.
Например

Или можно какой-нибудь изоморфизм баз найти.

PS
Это только поверхностное представление решения проблеммы. К сожалению, на реализацию нету времени. Первый курс, как никак.
СУВ, SoWa.

Это сообщение отредактировал(а) SoWa - 16.11.2006, 20:43

Разбирать по словам конечно же наверно придется. Мало того, это просто необходимо ИМХО, чтобы обеспечить более быстрый поиск по базе.
А текстов на самом деле будет не два, а много тысяч, часть из которых одинаковые или схожие будут.

Вопрос в том, как это все записывать в таблицу. 
Или в таком виде:


Или в таком: 


Как вы думаете лучше?

Можно разбивать тексты на блоки определенной длины, и искать эти блоки в базе данных по like.
Можно брать статистику слов. Ну к примеру если в статье встречается одинаковое кол-во одинаковых слов, тогда они похожи. Но тогда нужно сохранять кол-то слов в каждой статье. Что-то типа индекса делать. 

Пока вижу такие выходы.

Да-да, именно так имхо лучше всего.

Похожи? 
ИМХО совершенно разный смысл. А вот разбор по членам предложения прокатит.

PS
Брутфорс никогда не рулил в подобных делах

Это сообщение отредактировал(а) SoWa - 19.11.2006, 19:42

эти два текста похожи на 50%

Не верно.

ИМХО, даже на 90%. Потому что и там, и там говорится об одних и тех же вещах.

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


Exception, А попробуй компу объясни. Нам понятно, что кто-то идет кушать кого-то. Вот и строим логическую структуру. Так схожесть будет определяться не только синтаксически, но и логически.

 Есть замечательная програмка - "Антиплагиат". Я не уверен, что в сети есть подробное описание приципа работы - но что-то там точно должно быть- как минимум идеалогия. Цель она преследует по сути ту же. А подход очень интересен;)

А вообще говоря вопрос не совсем корректен - 80% - это смотря как сравнивать. Разные критерии качества можно ввести;) 

Есть способ для быстрого определения 100 процентной схожести. Для каждого текста считаются контрольные суммы, например по методу CRC32. И затем по базе уже производить поиск всех текстов с равной контрольной суммой и равной длиной. И уже над этими записями делать дополнительную проверку.

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

За контрольные суммы не согласен   

А вот далее у тебя написано мое мнение строгим языком.

Это сообщение отредактировал(а) SoWa - 21.11.2006, 11:35

первый раз слышу про контрольную сумму процента схожести.

Fin
Ага, а еще не будем забывать, что CRC для различных входных данных разная. И как сравнивать будем?
С тем же успехом MD5 захешируем и будем довольны, а?

SoWa и esperant0 иногда думать надо, прежде чем осуждать. Контрольная сумма это  Хэш функция, по которой можно определить 100 процентно схожие тексты. Да бывают коллизии. Но уже не нужно просматривать полностью всю базу, а только те тексты, у которых совпали Хэш. Чтобы не было расхождений Хэшов, например из-за лишнего пробела. Можно текст приводить к единому стилю. Например 1 пробел между словами , все буквы заглавные, никаких переносов строк. Для этого приведенного текста считается Хэш. Но в базе можно хранить текст уже в произвольном виде. 

Но смотри, хеш двух таких текстов ведь будет разным:

А смысл разный: Сова кушает блюдо под названием "МЕДВЕД"
А Медвед кушает блюдо под названием "СОВА"
По количественной оцеке- текты одинаковы.
По смысловой- разные.
По хешу- черти-что вообще.

PS Мы не осуждаем, мы опровергаем 

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

Это сообщение отредактировал(а) SoWa - 21.11.2006, 14:46

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

а если по смыслу...

можно ещё попробовать посмотреть статистику попарных (или более "арных") появлений слов в одном предложении - грубая аппроксимация (если вообще аппроксимация) связей между понятиями, используемыми в статье...

Я был бы благодарен, если бы ты объяснил, что такое аппроксимация. Я бы подумал над твоим предложением.
Звучит дельно 

приближение
в данном случае я имел в виду, что эта статистика может нести полезную информацию о связях между понятиями и (если уж совсем оптимистами быть) всё это будет представлено в практически прямой форме: пара слов и степень связанности между ними

Это сообщение отредактировал(а) maxim1000 - 21.11.2006, 15:26

Ясно. Тогда мне кажется, что чем больше слов, тем меньше они связаны, если рассматривать аппроксимацию.
Рассматривать пары или тройки- самый оптимальный вариант.

хороший вариант был бы выделить тройку <понятие1> <тип связи> <понятие2>

Но опять без словарика никак. Чтобы определять, существительное это, глагол, или еще что.
Вообще можно заняться. Что я и сделаю. Скоро статью выложу.

А так, было предложение сделать неполный словарь и дополнять его во время работы.

когда я предлагал, то имел в виду без словарика
т.е., конечно, мысли о разделении слов по частям речи были, но в качестве предварительного варианта - можно без словаря вообще

то, что я предложил, - не метод решения задачи
это всего лишь какие-то характеристики, которые можно померять, и которые могут подсказать, в какую сторону двигаться

Добавлено @ 19:53 
что касается дополняемого словарика, возникнут проблемы с автоматическим отнесением нового слова к какой-либо части речи

Добавлено @ 19:54 
так что я бы сначала сделал "по-тупому" для всех слов без разбора (включая союзы ), а потом бы уже смотрел, в какую сторону двигаться, на основании экспериментальных данных

Хм. Как без словарика можно определить такую структуру?

Не понимаю.


Это легко. Слово встретил незнакомое- выдаст запрос- это что: существительное, глагол, наречие, др...
О! Кстати, можно попробовать научить прогу различать существительные и глаголы. Тогда как определить структуру- понятно.



Т.е. составлял бы структуры аппроксимации попарных и более "арных" слов и сравнивал?
Для начала и это прокатит. Но уж совсем не оптимизировано.

Во! Придумал. Берем такие структуры. Хешируем. Составляем текст из них. Гоним сравнение таких текстов брутфорсом. Так можно реализовать твое последнее предложение. А можно еще разок выделить структуры  Но это я уже только мечтаю. Реализация- понятна. Вот только как работать будет- не знаю 

Это сообщение отредактировал(а) SoWa - 21.11.2006, 20:07

Превед велосипедистам! 

Где научный подход?


Wowa, 
Почитай здесь: http://www.smolensk.ru/user/sgma/MMORPH/N-...eev/andreev.htm

У тебя подход, судя по задаче, должен быть похожим. Если, конечно, речь идет о текстах произвольного вида (т.е. пока не затрагиваются вопросы БД, где вид записей строго оговорен). Отталкиваемся от задачи классификации!

Я бы упростил схему по стандартному методу, который уже много раз использовал в различных задачах. (Как уже писал в теме про антимат  )

1) Нормализация текста
2) Сравнение

Теперь надо "развернуть" этото алгоритм по нашей задаче.
1а) Стеммер, в нижний регистр, елиминация всего, кроме слов, выкидываем предлоги итд.
1б)тезаури (маппинг синонимов);
1в) Создание общего вектора
2) Подсчёт дистанции Hamming'a

Этого должно хватить в 90% случаев. Я сам удивился, когда курсач писал и похожим методом практически точно классифицировал около 500 документов (кстати идея лично моя  )

Пример:
т1: Мама мыла раму.
т2: Маша мыла пол.
т3: Мама купила мыло.
т4: Папа чистил паркет.

1а)
мам мыл рам
маш мыл пол
мам куп мыл
пап чист паркет

1б)
паркет - пол
мыл - чист
род - мам,пап //родители

1в) //1, если слово присутствует в тексте, 0, если нет

      род мыл рам маш пол куп

т1: 1      1      1      0     0     0  //Мама мыла раму.
т2: 0      1      0      0     1     0  //Маша мыла пол.
т3: 1      1      0      0     0     1  //Мама купила мыло.
т4: 1      1      0      0     1     0  //Папа чистил паркет.

2) //Дистанция - количество позиций, где вектора не совпадают
Дистанция(т1,т2)=3
Дистанция(т1,т3)=2
Дистанция(т1,т4)=2
Дистанция(т2,т3)=3
Дистанция(т2,т4)=1
Дистанция(т3,т4)=2

Чем больше дистанция, тем больше тексты отличаются. 
Этим алгоритмом можно и два текста сравнивать. Если сравниваешь много - то получается почти алгоритм, предложенный подвалом.
Как видим, даже при таком небольшом количестве слов, определяет неплохо.
И, как видим, большая ответственность приходится на тезаури. Но тут ведь многое от контекста зависит. ("Ягуар" - машина, или "Ягуар" - животное)


ИМХО не совсем похож.. Кластеризация и классификация текстов это слишком круто здесь.  Хотя статья интересная.
Но тут текстов не так много и функции дискриминации попроще 

не, то я говорил как раз в продолжение мысли о словарике


ну, в принципе, можно
конечно, возникнут трудности с омонимами, но наверное, их количество не так велико, чтобы сделать погоду...


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



хобби такое вот - велосипедизм
во всех областях специалистом не станешь, а мозги разминки требуют 

Серж, ты именно здачу классификации и решил. 
Кстати, зачот 

Почти  там были авторы - центроиды по которым собственно тексты и классифицировались. А тут почти тоже самое, только центроидов для сравнения нет.

Релевантность (англ. relevant) — степень соответствия запроса и найденного, уместность результата.
Основным методом для оценки релевантности является TF-IDF–метод, который используется в большинстве поисковых систем.
Вот ссылочка: http://ru.wikipedia.org/wiki/TF-IDF 

Levenson, ну это релевантность документа к слову. Честно, ума не приложу, как её применить для сравнения документов. разве только каждое слово сравнивать. И потом, схема расчитана на относительную релевантность. Т.е зависит от самих документов в группе и их количества.
К примеру два текста, не совпадающие на одно слово, будут считаться похожими, если в группе всего три документа и третий ещё больше отличается от тех двух.

Ты отчасти прав... сравнивать каждое слово, только по-умному.

Я бы сделал так: 
1) написал бы морфологический анализатор на словарной базе (словари уже готовы и бесплатны) для того чтобы по любому слову определять его начальную форму. Для начала рассматривал бы только существительные.

2) для каждого документа системы составил бы карту частоты встречаемости, используя подход "TF-IDF". Как показала практика в тексте достаточно большого размера слов, которые являются существительными не так уж и много.

3)далее я уже сравнивал бы такие карты для различных текстов

Кстати, в чем проблема?

Они и так будут считаться похожими. Мож я не понял, чего ты хочешь сказать...

Нет, я конечно же совсем не то и не так хотел сказать         Спасибо за то, что заметил  Это предложение наверное осталось случайно. можно его не считать.

Имелось ввиду, что идея IDF в том, что если слово в документе встречается часто, а во всей группе - редко, то релевантность документа (по отношению к этому слову) будет расчитана как высокая. Таким образом она будет скакать в зависимости от количества документов.

Систему IDF я понял. Просто я предлагаю использовать только TF. А IDF оставить в покое. Т.е. анализировать схожесть текста только на основании словарей. Думаю, что такой подход имеет место быть.

Еще одно предложение: Считать сочетания понятий в предложениях и составлять такие же словари для них. Не секрет, что сочетания слов в тексте точнее характеризует этот текст нежели просто вхождение слов.

TF тоже относителен количеству слов в документе. Нет. ИМХО похожесть так не определишь..


Это да, но такой анализатор на 10000 текстах будет буксовать... Хотя можно конечно многое сделать.
Я делал такую систему (как уже писал), но у меня были сочетания определены заранее. (Брал примеры и по ним сравнивал). Дело интересное, но опять же свои нюансы. Надо знать "о чём" документы.

Добавлено @ 18:26 
TF(А,Б) - сколько раз слово ""А находится в документе "Б".

1) Зависит от текстов
2) А никто легкой жизни и не обещал   

Можно конечно сложность алгоритма посчитать, толтко лень как-то...   

Может быть пригодится:
http://company.yandex.ru/articles/spamooborona.html
http://company.yandex.ru/articles/article10.html

Добавлено @ 00:46 
P.S. Ссылки всплыли здесь:
http://forum.vingrad.ru/topic-125971.html
человек решает аналогичную задачу.

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

Кстати, возник вопрос:



Не подскажете где можно получить словари синонимов русского языка?

Скорее всего надо будет писать самому. Стандартные словари мало чего дадут. (т.к у одного и тогоже слова бывает несколько значений.)

А что такое "стандарнтый словарь"?

Я конечно понимаю как перелопатив горы текста правильным скриптом можно самому создать подобие словаря синонимов.

Но зачем это еще раз делать, если в стандартных словарях типа http://www.trishin.ru/slovar.html это уже давно сделано и подчищено?

Вот и хочется получить результат аналогичный http://www.trishin.ru/slovar.html, но не в виде программы, а в сыром (текстовом) виде для удобства встраивания в свои программы.

Это сообщение отредактировал(а) kulibinka - 10.12.2006, 13:00

Я давал пример слова "ягуар". Это может быть машина, а может быть животное. Зависит от типа текста и ещё кучи вещей. 

Нет, всё же скриптом не получится.

Категорично сказано 

Общие словари синонимов ("стандартные") именно скриптами и делаются, только потом вылизываются.


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

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

Детали реализации можно посмотреть тут http://acl.ldc.upenn.edu/C/C02/C02-1007.pdf. 
Причем заметьте - это довольно старые результаты. А люди на месте не стоят - они все думают и думают...

ИМХО, имеется попытка изобрести велосипед. Но велосипед особенный, который еще никому до ума довести не удалось. Сколь знаю (сидел на паре семинаров на эту тему, но сам не специалист), сравнение текстов пока что делается не на уровне разработок, а на уровне научных исследований. Если не ошибаюсь, желающим недо копать по ключевым словам Text digging и Neural networks. Скорее всего такая область как Semantics тоже сюда относится.

Практически я бы посоветовал сдалать что-то работающее интерактивно (может и не хорошо, но лучше чем программа неработающая). Сделал бы так:

С начала:

• Создать пустой список ключевых слов с синонимами. Он будет пополняться по ходу дела.
• Задать какое-то критическое количество ключевых слов n для поиска. Величина n 
  подбирается методом тыка и, возможно, разнится в зависимости от того, что за тексты лежат в базе.

При вводе новой записи в базу:
1 Искать в БД идентичныую запись. Если найдена goto 9
2 Искать в новой записи слова из списка ключей. Находит, скажем x слов.
3 Если находится x >= n  ключевых слов, goto 6
4 Показать диалог что мол только x слов найдено и просьба задать дополнительные ключевые слова или синонимы слов имеющихся в списке.
5 Если слова заданы - загнать их в список, если нет - это уже на усмотрение программиста (или пользователя) - либо искать по имеющимся, либо goto 8
6 Искать в БД записи с теми же ключевыми словами. Если x > n ищутся все сочетания из n. 
7 Каждая найденная запись показывается в диалоге вместе со старой. Спрашивается: искать дальще или остановить ввод новой записи как дублирующей имеющуюся (это будет goto 9). Возможен и третий вариант - объединить записи и отредактировать результат (но это уже по вкусу)
8 Запись загоняется в БД
9 Дело сделано - бежим за пивом

Это сообщение отредактировал(а) _Y_ - 11.12.2006, 13:52

Можно выдрать тезаурус MS Word. Где-то в нете даже встречал статью по этой теме.

www.slovarik.ru
Много словарей.
_Y_, не велосипедист. Предлагалось всеми без исключения. Просьба читать тему с начала.
В конце концов, решение найдено. Хватит обсуждать решенный вопрос. Все нюансы были описаны, а если чего то нет, то есть в инете.

Это сообщение отредактировал(а) SoWa - 11.12.2006, 14:57

Я не успел - к сожалению не открывается, а кеш гугля говорит "Site has been suspended"

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

Посмотри здесь: http://www.rvb.ru/soft/catalogue/catalogue.html
Там, возможно, не совсем то, что ты ищешь, но много интересного на эту тему.