Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

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

6
28 июля 2011 года
George
4.1K / / 05.01.2007
Встала задача - сравнить тексты на схожесть (выявление плагиата). Сначала я хотел применить нагугленный мной алгоритм шинглов, но потом оказалось, что надо еще и подсвечивать схожие участки текста и генерировать по ним отчет, а проверка алгоритмом шинглов не выявляет похожих мест, она лишь вычисляет процент схожести. Есть какие-то другие решения или идеи, как это реализовать?
87
28 июля 2011 года
Kogrom
2.7K / / 02.02.2008
George, можешь привести конкретные примеры. Может хотя бы приемлемый "велосипед" кто-нибудь придумает.

Если абстрактно, то можно из этого "алгоритма шинглов" взять первые 2 этапа, положить шинглы в массив пар: [шингл, позиция первого слова]. И искать совпадения по шинглам тупым перебором (возможно, предварительно отсортировав массив по алфавиту). При канонизации можно ещё и синонимы пытаться заменять на один вариант.
6
28 июля 2011 года
George
4.1K / / 05.01.2007
Ну я пока думаю, что к шинглу буду присобачивать позицию оного, да, а от нее потом плясать. Канонизация в моей задаче уже не так важна, достаточно будет очистить текст от тэгов, пунктуации и предлогов с союзами и междометиями. Кстати, и 84 хэш-функции это слишком, возьму какую-нибудь одну.
87
28 июля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: George
Кстати, и 84 хэш-функции это слишком, возьму какую-нибудь одну.



Этого я не понял. Результаты хэш-функций для двух похожих кусков текста могут сильно отличаться. Надёжнее сравнивать шинглы без обработки.

Правда, если тупо сравнивать участки по 10 слов, то упустим участки по 9. А совпадения по 11 слов дадут 2 срабатывания.
Вероятно, нужен другой алгоритм.

6
28 июля 2011 года
George
4.1K / / 05.01.2007
Цитата: Kogrom
Этого я не понял. Результаты хэш-функций для двух похожих кусков текста могут сильно отличаться. Надёжнее сравнивать шинглы без обработки.


Хэши сравнивать быстрее. А в надежности разницы на самом деле нет, ты если будешь сравнивать два куска текста без обработки, то все, чего ты добьешься - это выяснишь, одинаковы они или нет. То же самое будет с хэшами, я к тому же хэши хочу кэшировать в БД и в сл. раз их оттуда выцеплять. Должно быть быстро довольно так.

Цитата: Kogrom
Правда, если тупо сравнивать участки по 10 слов, то упустим участки по 9. А совпадения по 11 слов дадут 2 срабатывания.
Вероятно, нужен другой алгоритм.

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

87
29 июля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: George
Хэши сравнивать быстрее. А в надежности разницы на самом деле нет, ты если будешь сравнивать два куска текста без обработки, то все, чего ты добьешься - это выяснишь, одинаковы они или нет.



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

Цитата: George
Чем меньше слов в шингле, тем выше точность, но и временные затраты. Я думаю, размер шингла будет подбираться опытным путем. Мне пока нравится вариант с шинглами размером в три слова, но не знаю, как там с производительностью будет.



Плагиат в 3 слова - это сурово :)
Ну и в любом случае простой тест не пройдёт. Для двух одинаковых текстов в 100 слов должен быть один плагиат, а выйдет не менее 98.

6
29 июля 2011 года
George
4.1K / / 05.01.2007
Цитата: Kogrom
Да... я поспешил и сказал не то, что думал. Хэши двух разных кусков текста могут совпадать, особенно, если применяем какую-нибудь простую CRC. Будет ложное срабатывание.


Сфигали? Ты говоришь про коллизии в хэш-функциях, так такие хэш-функции зачем использовать? Мне кажется банального md5 хватит.

Цитата: Kogrom
Плагиат в 3 слова - это сурово :)
Ну и в любом случае простой тест не пройдёт. Для двух одинаковых текстов в 100 слов должен быть один плагиат, а выйдет не менее 98.


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

87
29 июля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: George
Сфигали? Ты говоришь про коллизии в хэш-функциях, так такие хэш-функции зачем использовать? Мне кажется банального md5 хватит.



http://ru.wikipedia.org/wiki/Коллизия_хеш-функции

В общем, если хэш по длине будет не менее исходного текста, то коллизий не будет. Но в данной задаче такие хэши не нужны.

Цитата: George
Плагиатность текста же не по одному куску будет рассчитываться, а по соотношению совпадений к длине текста.



Отсюда вывод - надо разбить шинглы до одного слова... как пойдут адреса слов подряд - так будет выявляться плагиат.

10
29 июля 2011 года
Freeman
3.2K / / 06.03.2004
Цитата: Kogrom
надо разбить шинглы до одного слова... как пойдут адреса слов подряд


Это только мне кажется, что в этом случае алгоритм вырождается в обычный diff? Или я чего-то не понимаю? Про шиндлы не смотрел, если честно.

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

87
29 июля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: Freeman
Это только мне кажется, что в этом случае алгоритм вырождается в обычный diff? Или я чего-то не понимаю? Про шиндлы не смотрел, если честно.



Да, только работать он должен наоборот.

Но тут, возможно, надо учесть, что плагиатор может переставить слова в предложениях или даже сами предложения переставить, может заменять слова на синонимы и т.п. И тут вывернутый diff может начать давать сбои. Однако, такие рассуждения бесполезны, ибо нету конкретного ТЗ.

Алгоритм с шиндлами используется для сбора статистики - поэтому там логика другая. Однако, интерес в нашем случае может представлять этап канонизации.

341
29 июля 2011 года
Der Meister
874 / / 21.12.2007
Как насчёт адаптации Смита-Вотермана? Там и подсветка канает.
6
30 июля 2011 года
George
4.1K / / 05.01.2007
Цитата: Kogrom
http://ru.wikipedia.org/wiki/Коллизия_хеш-функции
В общем, если хэш по длине будет не менее исходного текста, то коллизий не будет. Но в данной задаче такие хэши не нужны.


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

Цитата: Kogrom
Отсюда вывод - надо разбить шинглы до одного слова... как пойдут адреса слов подряд - так будет выявляться плагиат.


Это, имхо, перебор уже. Алгоритм шинглов годен, когда два слова и более. Хотя может я и не прав.

87
30 июля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: George
А про длину хэшей я и вовсе не понял. Выражай, пожалуйста чутка яснее свои мысли.



Я говорю, что с MD5 коллизии будут. А ссылку дал, потому что там написано:

Цитата:
Однако для хеш-функций, принимающих вход переменной длины и возвращающих хеш постоянной длины (таких как MD5), коллизии обязаны существовать, поскольку хотя бы для одного значения хеш-функции соответствующее ему множество входных данных (полный прообраз) будет бесконечно — и любые два набора данных из этого множества образуют коллизию.



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

Цитата: George
Это, имхо, перебор уже. Алгоритм шинглов годен, когда два слова и более. Хотя может я и не прав.



Я пытаюсь подвести к тому, что алгоритм шинглов не подходит тут.
Вот Der Meister привёл ссылку на интересную статью. Я только бегло просмотрел, но вроде бы это то, что требовалось. Уж если не всё использовать, то хоть идеи. Например, создание и использование словаря текста:

Цитата:
So, for example, the text "A horse, a horse, my kingdom for a horse." might be
represented as the sequence < 1 2 1 2 3 4 5 1 2 >, with the correspondence
between lexemes and integer tokens as shown in Table 1.

6
30 июля 2011 года
George
4.1K / / 05.01.2007
Цитата: Kogrom
Я говорю, что с MD5 коллизии будут.


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

Цитата: Kogrom
Я пытаюсь подвести к тому, что алгоритм шинглов не подходит тут.
Вот Der Meister привёл ссылку на интересную статью. Я только бегло просмотрел, но вроде бы это то, что требовалось. Уж если не всё использовать, то хоть идеи. Например, создание и использование словаря текста:


Пока ты внятно не объяснил, почему алгоритм шинглов не подходит.
А за текст Der Meister'у спасибо, я его чуть попозже буду читать. Мб в понедельник, сегодня неохота. Отдыхаю, чо. :)

87
30 июля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: George
Коллизии будут, но редко. Настолько редко, что можно их не брать в расчет. Оценка схожести по любому является приблизительной, поэтому потенциальные коллизии хэшей можно списать в погрешность.



Это дело твоё. Я же говорю, что конкретного ТЗ не знаю. Лишь бы ты ПО для самолётов и АЭС с таким же подходом не проектировал.

Цитата: George
Пока ты внятно не объяснил, почему алгоритм шинглов не подходит.



Ты сам в первом сообщении объяснил почему он не подходит в целом. Мне же не очевидно, зачем в твоём случае на каждое слово генерировать MD5 из 10 слов (или хотя бы трёх). Я не понимаю, что это даст.

Цитата: George
А за текст Der Meister'у спасибо, я его чуть попозже буду читать. Мб в понедельник, сегодня неохота. Отдыхаю, чо. :)



Это правильно.

6
31 июля 2011 года
George
4.1K / / 05.01.2007
Цитата: Kogrom
Это дело твоё. Я же говорю, что конкретного ТЗ не знаю. Лишь бы ты ПО для самолётов и АЭС с таким же подходом не проектировал.


При всем моем уважении, что ты знаешь о подходе? Я должен на форум ТЗ выкладывать? Или тебе на почту высылать фконвертике?

Цитата: Kogrom
Ты сам в первом сообщении объяснил почему он не подходит в целом. Мне же не очевидно, зачем в твоём случае на каждое слово генерировать MD5 из 10 слов (или хотя бы трёх). Я не понимаю, что это даст.


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

87
31 июля 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: George
При всем моем уважении, что ты знаешь о подходе? Я должен на форум ТЗ выкладывать? Или тебе на почту высылать фконвертике?



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

Цитата: George
Речь зашла о том, что к каждому хэшу можно еще привязать его позицию, тогда он будет решать мои задачи.



Заметь, что в алгоритме шинглов хэш составляется для каждого слова:

Цитата:
Шинглы (англ) — чешуйки, выделенные из статьи подпоследовательности слов.
Необходимо из сравниваемых текстов выделить подпоследовательности слов, идущих друг за другом по 10 штук (длина шингла). Выборка происходит внахлест, а не встык.
Таким образом, разбивая текст на подпоследовательности, мы получим набор шинглов в количестве равному количеству слов минус длина шингла плюс один (кол_во_слов — длина_шингла + 1).



а ты говоришь: "Плагиатность текста же не по одному куску будет рассчитываться, а по соотношению совпадений к длине текста." Так ты получишь изуродованный diff, с ненужным этапом шифровки и ошибочными срабатываниями.

Мне это не нравится. Потому я и сказал, что нужен другой алгоритм. И вроде бы на него Der Meister дал ссылку. Зачем дальше спорить?

6
31 июля 2011 года
George
4.1K / / 05.01.2007
Цитата: Kogrom
Не обязательно. Можно было привести несколько примеров, как программа работает. Может на самом деле тут элементарный diff подойдёт.


Я достаточно внятно изобразил задачу - вычислить процент плагиатности текста и подсветить совпадения. Точный процент плагиатности вычислить невозможно в принципе, поэтому достаточно приблизительных результатов. Я не пойму, что тебе еще надо? Дифф элементарно не подходит в силу своей медленности - один текст может быть размером с Войну и Мир, а таких текстов будет несколько десятков тысяч.

Цитата: Kogrom
Заметь, что в алгоритме шинглов хэш составляется для каждого слова:


Не для каждого слова, а для каждого шингла.

Цитата: Kogrom
а ты говоришь: "Плагиатность текста же не по одному куску будет рассчитываться, а по соотношению совпадений к длине текста." Так ты получишь изуродованный diff, с ненужным этапом шифровки и ошибочными срабатываниями.


Чем по твоему, алгоритм шинглов отличается от банального диффа?

Цитата: Kogrom
Мне это не нравится. Потому я и сказал, что нужен другой алгоритм. И вроде бы на него Der Meister дал ссылку. Зачем дальше спорить?


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

87
01 августа 2011 года
Kogrom
2.7K / / 02.02.2008
Цитата: George
Я достаточно внятно изобразил задачу - вычислить процент плагиатности текста и подсветить совпадения. Точный процент плагиатности вычислить невозможно в принципе, поэтому достаточно приблизительных результатов. Я не пойму, что тебе еще надо?



Примеры работы нужны. Что на входе (2 текста) и что на выходе. Желательно парочку примеров.

Цитата: George
Дифф элементарно не подходит в силу своей медленности - один текст может быть размером с Войну и Мир, а таких текстов будет несколько десятков тысяч.



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

Цитата: George
Не для каждого слова, а для каждого шингла.



Но ведь шингл составляется для каждого слова (я же привел цитату). Поэтому и хэш для каждого слова.

Цитата: George
Чем по твоему, алгоритм шинглов отличается от банального диффа?



Назначением. Ты же сам об этом говорил в первом сообщении.

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог