Сравнение текстов
Если абстрактно, то можно из этого "алгоритма шинглов" взять первые 2 этапа, положить шинглы в массив пар: [шингл, позиция первого слова]. И искать совпадения по шинглам тупым перебором (возможно, предварительно отсортировав массив по алфавиту). При канонизации можно ещё и синонимы пытаться заменять на один вариант.
Этого я не понял. Результаты хэш-функций для двух похожих кусков текста могут сильно отличаться. Надёжнее сравнивать шинглы без обработки.
Правда, если тупо сравнивать участки по 10 слов, то упустим участки по 9. А совпадения по 11 слов дадут 2 срабатывания.
Вероятно, нужен другой алгоритм.
Хэши сравнивать быстрее. А в надежности разницы на самом деле нет, ты если будешь сравнивать два куска текста без обработки, то все, чего ты добьешься - это выяснишь, одинаковы они или нет. То же самое будет с хэшами, я к тому же хэши хочу кэшировать в БД и в сл. раз их оттуда выцеплять. Должно быть быстро довольно так.
Вероятно, нужен другой алгоритм.
Чем меньше слов в шингле, тем выше точность, но и временные затраты. Я думаю, размер шингла будет подбираться опытным путем. Мне пока нравится вариант с шинглами размером в три слова, но не знаю, как там с производительностью будет.
Да... я поспешил и сказал не то, что думал. Хэши двух разных кусков текста могут совпадать, особенно, если применяем какую-нибудь простую CRC. Будет ложное срабатывание.
Плагиат в 3 слова - это сурово :)
Ну и в любом случае простой тест не пройдёт. Для двух одинаковых текстов в 100 слов должен быть один плагиат, а выйдет не менее 98.
Сфигали? Ты говоришь про коллизии в хэш-функциях, так такие хэш-функции зачем использовать? Мне кажется банального md5 хватит.
Ну и в любом случае простой тест не пройдёт. Для двух одинаковых текстов в 100 слов должен быть один плагиат, а выйдет не менее 98.
Плагиатность текста же не по одному куску будет рассчитываться, а по соотношению совпадений к длине текста. Просто трёхсловные шинглы позволяет выявить больше совпадений. Ну возможно с тремя - это перебор, допускаю, что правда где-то у цифры пять.
http://ru.wikipedia.org/wiki/Коллизия_хеш-функции
В общем, если хэш по длине будет не менее исходного текста, то коллизий не будет. Но в данной задаче такие хэши не нужны.
Отсюда вывод - надо разбить шинглы до одного слова... как пойдут адреса слов подряд - так будет выявляться плагиат.
Это только мне кажется, что в этом случае алгоритм вырождается в обычный diff? Или я чего-то не понимаю? Про шиндлы не смотрел, если честно.
Про diff подумал с самого начала, когда увидел тему. А поиск плагиата -- уже производная от работы diff -- как раз процент совпадений по отношению к тексту, не?
Да, только работать он должен наоборот.
Но тут, возможно, надо учесть, что плагиатор может переставить слова в предложениях или даже сами предложения переставить, может заменять слова на синонимы и т.п. И тут вывернутый diff может начать давать сбои. Однако, такие рассуждения бесполезны, ибо нету конкретного ТЗ.
Алгоритм с шиндлами используется для сбора статистики - поэтому там логика другая. Однако, интерес в нашем случае может представлять этап канонизации.
В общем, если хэш по длине будет не менее исходного текста, то коллизий не будет. Но в данной задаче такие хэши не нужны.
Ты выражаешься не совсем понятно. Ты говоришь о том, что результаты хэширования разных блоков текста будут одинаковы, что является коллизией хэш-функции, а ты мне еще и ссылку даешь? :) А про длину хэшей я и вовсе не понял. Выражай, пожалуйста чутка яснее свои мысли. :)
Это, имхо, перебор уже. Алгоритм шинглов годен, когда два слова и более. Хотя может я и не прав.
Я говорю, что с MD5 коллизии будут. А ссылку дал, потому что там написано:
На счёт длины. Я подозреваю, что хэш тогда не будет иметь коллизий, когда его длина будет не меньше, чем наибольшая длина входных данных. И статьи из Википедии косвенно это подтверждают.
Применение хэш-функций - это же не архивирование, смысл немного другой.
Я пытаюсь подвести к тому, что алгоритм шинглов не подходит тут.
Вот Der Meister привёл ссылку на интересную статью. Я только бегло просмотрел, но вроде бы это то, что требовалось. Уж если не всё использовать, то хоть идеи. Например, создание и использование словаря текста:
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.
Коллизии будут, но редко. Настолько редко, что можно их не брать в расчет. Оценка схожести по любому является приблизительной, поэтому потенциальные коллизии хэшей можно списать в погрешность.
Вот Der Meister привёл ссылку на интересную статью. Я только бегло просмотрел, но вроде бы это то, что требовалось. Уж если не всё использовать, то хоть идеи. Например, создание и использование словаря текста:
Пока ты внятно не объяснил, почему алгоритм шинглов не подходит.
А за текст Der Meister'у спасибо, я его чуть попозже буду читать. Мб в понедельник, сегодня неохота. Отдыхаю, чо. :)
Это дело твоё. Я же говорю, что конкретного ТЗ не знаю. Лишь бы ты ПО для самолётов и АЭС с таким же подходом не проектировал.
Ты сам в первом сообщении объяснил почему он не подходит в целом. Мне же не очевидно, зачем в твоём случае на каждое слово генерировать MD5 из 10 слов (или хотя бы трёх). Я не понимаю, что это даст.
Это правильно.
При всем моем уважении, что ты знаешь о подходе? Я должен на форум ТЗ выкладывать? Или тебе на почту высылать фконвертике?
Ты в алгоритм шинглов вообще вникал то? Речь зашла о том, что к каждому хэшу можно еще привязать его позицию, тогда он будет решать мои задачи. Такое ощущение, что ты о чем-то своем думаешь и что-то свое непонятное пишешь.
Не обязательно. Можно было привести несколько примеров, как программа работает. Может на самом деле тут элементарный diff подойдёт.
Заметь, что в алгоритме шинглов хэш составляется для каждого слова:
Необходимо из сравниваемых текстов выделить подпоследовательности слов, идущих друг за другом по 10 штук (длина шингла). Выборка происходит внахлест, а не встык.
Таким образом, разбивая текст на подпоследовательности, мы получим набор шинглов в количестве равному количеству слов минус длина шингла плюс один (кол_во_слов — длина_шингла + 1).
а ты говоришь: "Плагиатность текста же не по одному куску будет рассчитываться, а по соотношению совпадений к длине текста." Так ты получишь изуродованный diff, с ненужным этапом шифровки и ошибочными срабатываниями.
Мне это не нравится. Потому я и сказал, что нужен другой алгоритм. И вроде бы на него Der Meister дал ссылку. Зачем дальше спорить?
Я достаточно внятно изобразил задачу - вычислить процент плагиатности текста и подсветить совпадения. Точный процент плагиатности вычислить невозможно в принципе, поэтому достаточно приблизительных результатов. Я не пойму, что тебе еще надо? Дифф элементарно не подходит в силу своей медленности - один текст может быть размером с Войну и Мир, а таких текстов будет несколько десятков тысяч.
Не для каждого слова, а для каждого шингла.
Чем по твоему, алгоритм шинглов отличается от банального диффа?
Не надо попытку понять тебя воспринимать как спор. Ты пишешь обрывочные фразы, в которых лично мне крайне сложно проследить логику. Поэтому я пытаюсь дать тебе понять, чтобы ты как-то более внятно выражал свои мысли что-ли.
Примеры работы нужны. Что на входе (2 текста) и что на выходе. Желательно парочку примеров.
Во первых, дифф должен работать быстрее, чем хитрый алгоритм поиска плагиата, ибо его цель проще. А во вторых, в задаче не заданы ограничения по скорости.
Но ведь шингл составляется для каждого слова (я же привел цитату). Поэтому и хэш для каждого слова.
Назначением. Ты же сам об этом говорил в первом сообщении.