| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Как определить схожесть текстов? |
| Автор: Wowa 15.11.2006, 12:52 |
| Как определить схожесть текстов? Например, есть много записей в базе и при добавлении новой записи надо проверить, нет ли уже точно таких или схожих более, чем на 80%. |
| Автор: maxim1000 15.11.2006, 12:58 |
| а что за тексты? и в каком смысле схожесть? (по смыслу, по набору используемых слов) без этого вряд ли получится что-либо предложить... |
| Автор: Wowa 15.11.2006, 13:07 | ||||
статьи на разные тематики
По смыслу. Набор используемых слов обычно будет почти одинаков. |
| Автор: maxim1000 15.11.2006, 13:20 |
| по смыслу сложно... от copy-paste разных кусочков ещё можно пробовать защититься а от от переписывания своими словами (не просто синонимами, а нормальным пересказом) - сомнительно (хотя я этой областью особо не интересовался, может, что-то и придумали) |
| Автор: SoWa 16.11.2006, 20:41 | ||
| Придумал сегодня в трамвае. Метод таков, что без определенного словарика не обойтись. Разбираем все предложения в исходном тексте и в том, который сравниваем, по членам предложения(подлежащее, сказуемое, дополнение, обстоятельство, и др.). Составляем связную базу каждых членов(база подлежащих, сказуемых, где Бсказ(i)<->Бподл(i)). Затем гоним перебором сравнение по базам подлежащих, сказуемых, др. Причем, при сравнении могут работать логические структуры И, ИЛИ, НЕ. Например
Или можно какой-нибудь изоморфизм баз найти. PS Это только поверхностное представление решения проблеммы. К сожалению, на реализацию нету времени. Первый курс, как никак. СУВ, SoWa. |
| Автор: Wowa 17.11.2006, 22:58 | ||||
| Разбирать по словам конечно же наверно придется. Мало того, это просто необходимо ИМХО, чтобы обеспечить более быстрый поиск по базе. А текстов на самом деле будет не два, а много тысяч, часть из которых одинаковые или схожие будут. Вопрос в том, как это все записывать в таблицу. Или в таком виде:
Или в таком:
Как вы думаете лучше? |
| Автор: Medved 18.11.2006, 00:36 |
| Можно разбивать тексты на блоки определенной длины, и искать эти блоки в базе данных по like. Можно брать статистику слов. Ну к примеру если в статье встречается одинаковое кол-во одинаковых слов, тогда они похожи. Но тогда нужно сохранять кол-то слов в каждой статье. Что-то типа индекса делать. Пока вижу такие выходы. |
| Автор: Wowa 18.11.2006, 00:40 | ||
Да-да, именно так имхо лучше всего. |
| Автор: SoWa 19.11.2006, 19:41 | ||
Похожи?  ИМХО совершенно разный смысл. А вот разбор по членам предложения прокатит. PS Брутфорс никогда не рулил в подобных делах |
| Автор: Medved 19.11.2006, 21:38 | ||
эти два текста похожи на 50% |
| Автор: esperant0 19.11.2006, 21:40 | ||
Не верно. |
| Автор: Exception 19.11.2006, 22:11 | ||
ИМХО, даже на 90%. Потому что и там, и там говорится об одних и тех же вещах. |
| Автор: SoWa 20.11.2006, 14:35 |
| esperant0, сложность построения логической структуры будет в несколько раз меньше сложности сравнения перебором(Берем текст, считаем каждое слово, сравниваем еще , допустим с 1000 текстов...) Exception, А попробуй компу объясни. Нам понятно, что кто-то идет кушать кого-то. Вот и строим логическую структуру. Так схожесть будет определяться не только синтаксически, но и логически. |
| Автор: tab 21.11.2006, 00:42 |
| Есть замечательная програмка - "Антиплагиат". Я не уверен, что в сети есть подробное описание приципа работы - но что-то там точно должно быть- как минимум идеалогия. Цель она преследует по сути ту же. А подход очень интересен;) А вообще говоря вопрос не совсем корректен - 80% - это смотря как сравнивать. Разные критерии качества можно ввести;) |
| Автор: Fin 21.11.2006, 09:57 |
| Есть способ для быстрого определения 100 процентной схожести. Для каждого текста считаются контрольные суммы, например по методу CRC32. И затем по базе уже производить поиск всех текстов с равной контрольной суммой и равной длиной. И уже над этими записями делать дополнительную проверку. Для анализа текстов на процент меньшей схожести. Я думаю нужно разбивать текст на логические лексемы (слова) И делать словарь, в каких текстах в базе данные лексемы встречаются. Для английского языка это будет практически легко сделать. Для русского намного сложнее: так как иногда форма слова очень сильно изменяется в зависимости от склонений и т.п. |
| Автор: SoWa 21.11.2006, 11:32 |
За контрольные суммы не согласен  А вот далее у тебя написано мое мнение строгим языком. |
| Автор: esperant0 21.11.2006, 11:37 | ||
первый раз слышу про контрольную сумму процента схожести. |
| Автор: SoWa 21.11.2006, 11:45 |
| Fin Ага, а еще не будем забывать, что CRC для различных входных данных разная. И как сравнивать будем? С тем же успехом MD5 захешируем и будем довольны, а? |
| Автор: Fin 21.11.2006, 14:21 |
| SoWa и esperant0 иногда думать надо, прежде чем осуждать. Контрольная сумма это Хэш функция, по которой можно определить 100 процентно схожие тексты. Да бывают коллизии. Но уже не нужно просматривать полностью всю базу, а только те тексты, у которых совпали Хэш. Чтобы не было расхождений Хэшов, например из-за лишнего пробела. Можно текст приводить к единому стилю. Например 1 пробел между словами , все буквы заглавные, никаких переносов строк. Для этого приведенного текста считается Хэш. Но в базе можно хранить текст уже в произвольном виде. |
| Автор: SoWa 21.11.2006, 14:39 | ||
Но смотри, хеш двух таких текстов ведь будет разным:
А смысл разный: Сова кушает блюдо под названием "МЕДВЕД" А Медвед кушает блюдо под названием "СОВА" По количественной оцеке- текты одинаковы. По смысловой- разные. По хешу- черти-что вообще. PS Мы не осуждаем, мы опровергаем Кстати, esperant0, я был не прав, говоря о сложностях алгоритмов. У моего алгоритма сложность выше, чем у брутфорса. Ибо мой алгоритм- то же брутфорс, но не по тексту, а по логическим высказываниям. Т.е. я должен перебрать, а по мимо этого еще и высказывания построить(тем же брутфорсом). Но все равно останусь при мнении, что мой алгоритм определит схожесть точнее. |
| Автор: maxim1000 21.11.2006, 14:39 |
| кстати, хеш можно использовать и для того, чтобы определить, не "навыдирали" ли части анализируемой статьи из статей в базе - разделить статью на блоки (можно с перекрытием) выбранного размера и записать их хеши... а если по смыслу... можно ещё попробовать посмотреть статистику попарных (или более "арных") появлений слов в одном предложении - грубая аппроксимация (если вообще аппроксимация) связей между понятиями, используемыми в статье... |
| Автор: SoWa 21.11.2006, 14:48 |
| Я был бы благодарен, если бы ты объяснил, что такое аппроксимация. Я бы подумал над твоим предложением. Звучит дельно |
| Автор: maxim1000 21.11.2006, 15:26 | ||
приближение в данном случае я имел в виду, что эта статистика может нести полезную информацию о связях между понятиями и (если уж совсем оптимистами быть) всё это будет представлено в практически прямой форме: пара слов и степень связанности между ними |
| Автор: SoWa 21.11.2006, 16:07 |
| Ясно. Тогда мне кажется, что чем больше слов, тем меньше они связаны, если рассматривать аппроксимацию. Рассматривать пары или тройки- самый оптимальный вариант. |
| Автор: maxim1000 21.11.2006, 16:38 |
| хороший вариант был бы выделить тройку <понятие1> <тип связи> <понятие2> |
| Автор: SoWa 21.11.2006, 18:52 |
| Но опять без словарика никак. Чтобы определять, существительное это, глагол, или еще что. Вообще можно заняться. Что я и сделаю. Скоро статью выложу. А так, было предложение сделать неполный словарь и дополнять его во время работы. |
| Автор: maxim1000 21.11.2006, 19:51 |
| когда я предлагал, то имел в виду без словарика т.е., конечно, мысли о разделении слов по частям речи были, но в качестве предварительного варианта - можно без словаря вообще то, что я предложил, - не метод решения задачи это всего лишь какие-то характеристики, которые можно померять, и которые могут подсказать, в какую сторону двигаться Добавлено @ 19:53 что касается дополняемого словарика, возникнут проблемы с автоматическим отнесением нового слова к какой-либо части речи Добавлено @ 19:54 так что я бы сначала сделал "по-тупому" для всех слов без разбора (включая союзы ), а потом бы уже смотрел, в какую сторону двигаться, на основании экспериментальных данных |
| Автор: SoWa 21.11.2006, 20:04 | ||||||
Хм. Как без словарика можно определить такую структуру?
Не понимаю.
Это легко. Слово встретил незнакомое- выдаст запрос- это что: существительное, глагол, наречие, др... О! Кстати, можно попробовать научить прогу различать существительные и глаголы. Тогда как определить структуру- понятно.
Т.е. составлял бы структуры аппроксимации попарных и более "арных" слов и сравнивал? Для начала и это прокатит. Но уж совсем не оптимизировано. Во! Придумал. Берем такие структуры. Хешируем. Составляем текст из них. Гоним сравнение таких текстов брутфорсом. Так можно реализовать твое последнее предложение. А можно еще разок выделить структуры Но это я уже только мечтаю. Реализация- понятна. Вот только как работать будет- не знаю |
| Автор: podval 21.11.2006, 20:05 |
| Превед велосипедистам! Где научный подход? Wowa, Почитай здесь: http://www.smolensk.ru/user/sgma/MMORPH/N-9-html/andreev/andreev.htm У тебя подход, судя по задаче, должен быть похожим. Если, конечно, речь идет о текстах произвольного вида (т.е. пока не затрагиваются вопросы БД, где вид записей строго оговорен). Отталкиваемся от задачи классификации! |
| Автор: sergejzr 21.11.2006, 20:53 | ||
| Я бы упростил схему по стандартному методу, который уже много раз использовал в различных задачах. (Как уже писал в теме про антимат ) 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 Чем больше дистанция, тем больше тексты отличаются. Этим алгоритмом можно и два текста сравнивать. Если сравниваешь много - то получается почти алгоритм, предложенный подвалом. Как видим, даже при таком небольшом количестве слов, определяет неплохо. И, как видим, большая ответственность приходится на тезаури. Но тут ведь многое от контекста зависит. ("Ягуар" - машина, или "Ягуар" - животное)
ИМХО не совсем похож.. Кластеризация и классификация текстов это слишком круто здесь. Хотя статья интересная.Но тут текстов не так много и функции дискриминации попроще |
| Автор: maxim1000 21.11.2006, 21:35 | ||||||||
не, то я говорил как раз в продолжение мысли о словарике
ну, в принципе, можно конечно, возникнут трудности с омонимами, но наверное, их количество не так велико, чтобы сделать погоду...
ну... рановато оптимизировать... как при ускорении оптимизация должна отталкиваться от профайлера, так и здесь хорошо бы строить развитие на основании экспериментальных данных
хобби такое вот - велосипедизм во всех областях специалистом не станешь, а мозги разминки требуют |
| Автор: podval 22.11.2006, 10:20 | ||
Серж, ты именно здачу классификации и решил. Кстати, зачот |
| Автор: sergejzr 22.11.2006, 13:27 | ||
Почти там были авторы - центроиды по которым собственно тексты и классифицировались. А тут почти тоже самое, только центроидов для сравнения нет. |
| Автор: Levenson 28.11.2006, 20:27 |
| Релевантность (англ. relevant) — степень соответствия запроса и найденного, уместность результата. Основным методом для оценки релевантности является TF-IDF–метод, который используется в большинстве поисковых систем. Вот ссылочка: http://ru.wikipedia.org/wiki/TF-IDF |
| Автор: sergejzr 28.11.2006, 21:55 |
| Levenson, ну это релевантность документа к слову. Честно, ума не приложу, как её применить для сравнения документов. разве только каждое слово сравнивать. И потом, схема расчитана на относительную релевантность. Т.е зависит от самих документов в группе и их количества. К примеру два текста, не совпадающие на одно слово, будут считаться похожими, если в группе всего три документа и третий ещё больше отличается от тех двух. |
| Автор: SID_M 6.12.2006, 20:05 | ||||
Ты отчасти прав... сравнивать каждое слово, только по-умному. Я бы сделал так: 1) написал бы морфологический анализатор на словарной базе (словари уже готовы и бесплатны) для того чтобы по любому слову определять его начальную форму. Для начала рассматривал бы только существительные. 2) для каждого документа системы составил бы карту частоты встречаемости, используя подход "TF-IDF". Как показала практика в тексте достаточно большого размера слов, которые являются существительными не так уж и много. 3)далее я уже сравнивал бы такие карты для различных текстов Кстати, в чем проблема?
Они и так будут считаться похожими. Мож я не понял, чего ты хочешь сказать... |
| Автор: sergejzr 6.12.2006, 20:21 | ||
Нет, я конечно же совсем не то и не так хотел сказать  Спасибо за то, что заметил Это предложение наверное осталось случайно. можно его не считать.Имелось ввиду, что идея IDF в том, что если слово в документе встречается часто, а во всей группе - редко, то релевантность документа (по отношению к этому слову) будет расчитана как высокая. Таким образом она будет скакать в зависимости от количества документов. |
| Автор: SID_M 7.12.2006, 18:11 |
| Систему IDF я понял. Просто я предлагаю использовать только TF. А IDF оставить в покое. Т.е. анализировать схожесть текста только на основании словарей. Думаю, что такой подход имеет место быть. Еще одно предложение: Считать сочетания понятий в предложениях и составлять такие же словари для них. Не секрет, что сочетания слов в тексте точнее характеризует этот текст нежели просто вхождение слов. |
| Автор: sergejzr 7.12.2006, 18:25 | ||||
TF тоже относителен количеству слов в документе. Нет. ИМХО похожесть так не определишь..
Это да, но такой анализатор на 10000 текстах будет буксовать... Хотя можно конечно многое сделать. Я делал такую систему (как уже писал), но у меня были сочетания определены заранее. (Брал примеры и по ним сравнивал). Дело интересное, но опять же свои нюансы. Надо знать "о чём" документы. Добавлено @ 18:26 TF(А,Б) - сколько раз слово ""А находится в документе "Б". |
| Автор: SID_M 7.12.2006, 20:57 | ||
1) Зависит от текстов 2) А никто легкой жизни и не обещал Можно конечно сложность алгоритма посчитать, толтко лень как-то...  |
| Автор: Artemios 9.12.2006, 00:43 |
| Может быть пригодится: 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 человек решает аналогичную задачу. |
| Автор: kulibinka 9.12.2006, 12:50 | ||
| Ага, я решил аналогичную задачу методом шинглов. Теперь бьюсь над повышением ее быстродействия. Кстати, возник вопрос:
Не подскажете где можно получить словари синонимов русского языка? |
| Автор: sergejzr 9.12.2006, 19:12 | ||
Скорее всего надо будет писать самому. Стандартные словари мало чего дадут. (т.к у одного и тогоже слова бывает несколько значений.) |
| Автор: kulibinka 10.12.2006, 11:40 | ||
А что такое "стандарнтый словарь"? Я конечно понимаю как перелопатив горы текста правильным скриптом можно самому создать подобие словаря синонимов. Но зачем это еще раз делать, если в стандартных словарях типа http://www.trishin.ru/slovar.html это уже давно сделано и подчищено? Вот и хочется получить результат аналогичный http://www.trishin.ru/slovar.html, но не в виде программы, а в сыром (текстовом) виде для удобства встраивания в свои программы. |
| Автор: sergejzr 10.12.2006, 16:39 | ||||
Я давал пример слова "ягуар". Это может быть машина, а может быть животное. Зависит от типа текста и ещё кучи вещей.
Нет, всё же скриптом не получится. |
| Автор: kulibinka 10.12.2006, 17:29 | ||||
Категорично сказано Общие словари синонимов ("стандартные") именно скриптами и делаются, только потом вылизываются.
Нет никакой кучи вещей. Есть только текст который мы алгоритму подсовываем. И если мы хотим получить такой словарь, где ягуар должен определяться как зверь, то если попробовать напустить скрипт на тематические статьи о животных а не о всем подряд, то практически гарантированно получим только "животно-ягуарные" синонимы слова ягуар, потому как ничего другого в принципе там вылезти не может. Хотя обычно именно такие словари и надо... Тут проблемма в том где получить тематическую информацию, и побольше. А если есть большой обьем информации по теме то все можно сделать скриптом, который выдаст достаточно качественную информацию. По крайней мере тест toefl на то чтобы выбрать среди набора слов максимально близкое по смыслу с заданым словом в предложении он проходит с результатом выше средне-человеческого. А это я считаю очень сильным результатом. Детали реализации можно посмотреть тут http://acl.ldc.upenn.edu/C/C02/C02-1007.pdf. Причем заметьте - это довольно старые результаты. А люди на месте не стоят - они все думают и думают... |
| Автор: _Y_ 10.12.2006, 20:49 |
| ИМХО, имеется попытка изобрести велосипед. Но велосипед особенный, который еще никому до ума довести не удалось. Сколь знаю (сидел на паре семинаров на эту тему, но сам не специалист), сравнение текстов пока что делается не на уровне разработок, а на уровне научных исследований. Если не ошибаюсь, желающим недо копать по ключевым словам Text digging и Neural networks. Скорее всего такая область как Semantics тоже сюда относится. Практически я бы посоветовал сдалать что-то работающее интерактивно (может и не хорошо, но лучше чем программа неработающая). Сделал бы так: С начала:
1 Искать в БД идентичныую запись. Если найдена goto 9 2 Искать в новой записи слова из списка ключей. Находит, скажем x слов. 3 Если находится x >= n ключевых слов, goto 6 4 Показать диалог что мол только x слов найдено и просьба задать дополнительные ключевые слова или синонимы слов имеющихся в списке. 5 Если слова заданы - загнать их в список, если нет - это уже на усмотрение программиста (или пользователя) - либо искать по имеющимся, либо goto 8 6 Искать в БД записи с теми же ключевыми словами. Если x > n ищутся все сочетания из n. 7 Каждая найденная запись показывается в диалоге вместе со старой. Спрашивается: искать дальще или остановить ввод новой записи как дублирующей имеющуюся (это будет goto 9). Возможен и третий вариант - объединить записи и отредактировать результат (но это уже по вкусу) 8 Запись загоняется в БД 9 Дело сделано - бежим за пивом |
| Автор: SID_M 11.12.2006, 14:36 | ||
Можно выдрать тезаурус MS Word. Где-то в нете даже встречал статью по этой теме. |
| Автор: SoWa 11.12.2006, 14:55 |
| www.slovarik.ru Много словарей. _Y_, не велосипедист. Предлагалось всеми без исключения. Просьба читать тему с начала. В конце концов, решение найдено. Хватит обсуждать решенный вопрос. Все нюансы были описаны, а если чего то нет, то есть в инете. |
| Автор: kulibinka 11.12.2006, 16:04 | ||
Я не успел - к сожалению не открывается, а кеш гугля говорит "Site has been suspended" |
| Автор: kulibinka 11.12.2006, 16:27 | ||
А хотя бы приблизительно ориентиры статьи не помните? А то погуглил пол часа да так и не нашел... |
| Автор: SID_M 12.12.2006, 10:28 | ||
Посмотри здесь: http://www.rvb.ru/soft/catalogue/catalogue.html Там, возможно, не совсем то, что ты ищешь, но много интересного на эту тему. |
