Как детектить «похожие тексты»?

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

А так, ну убери все знаки препинания, сделай промежутки между словами везде ровно 1 пробел, бей по 20 слов например. Только если индексировать образцы можно по 20 отдельных слов, то проверять схожесть придётся скользящим окном по 20 слов на проверяемом тексте. Или наоборот - индексировать скользящим окном, проверять отдельными.

Для картинок перцептивный хэш (perceptual hash).

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

Для картинок перцептивный хэш (perceptual hash).

Этому термину сто лет, и он примерно столько же не очень полезен :). Хотелось бы скорее «методичку для чайников», с обзором всех алгоритмов (кроме совсем топовых) и возможностью выбрать уровень сложности.

Если надо искать просто глупо сделанные кросспосты и копипасты картинок - то то что я описал думаю вполне справится с задачей.

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

Ты понимаешь, что ответ «делай как я» ни при каких обстоятельствах не подойдет к вопросу «хочу увидеть всю картину возможных вариантов»?

У меня нет проблем сочинить за 5 минут очередную колхозную нормализацию. Я хочу сначала нормально в теме сориентироваться.

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

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

Так подумайте сначала, какой API для этого нужно разработать.
И сто пудов это будет лишь верхушка айсберга …

казнить нельзя помиловать

знаков насобираешь сам из того что выкинул. и мы решим что с тобой дальше делать :) мухаха

Смотри как всякие программы проверки на плагиат работают. Отсюда и копай.

spamassassin умеет это делать используя bayes-фильтр

Для картинок сам использую вот такой скрипт на Питон:

#!/usr/bin/python

from PIL import Image
import imagehash

import sys

hash = imagehash.phash(Image.open(sys.argv[1]), int(sys.argv[2]), 32)

print(hash)

Второй аргумент - размер хеша подбирается в зависимости от необходимой точности. Я использую 10. Замершие картинки на телевидении детектит.

Твой вариант по сути тоже «хеш всего сразу». А мне интересно, как народ мутит с фрагментами и поиском по многомерным хешам.

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

«похожие тексты»

Семантический поиск ©.

Где посмотреть готовые алгоритмы на эту тему?

Нейросети обычно оценивают расстояние Дамерау-Левенштейна ©.

Спасибо. Первая ссылка особенно толковая была.

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

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

Под «хорошим» я понимаю поиск по индексу, где сложность порядка O(1).

1. https://github.com/natasha/natasha - и привести оба текста к инфинитивам

2. Разбить на предложения, определить подлежащее, сказуемое, пару дополнений.

3. Закодировать и сделать частотное сравнение.

4. Дохрена процессорного времени и памяти надо.

Если я правильно понимаю ваш вопрос, то самое простое это мешок слов. Берёте текст. Оставляете в нём только слова больше 2 букв (3 буквы и выше). Сортируете, считаете. Или делаете хеш, если у вас голимый копипаст. Всё, затем сравниваете только этот массив слов или хеш. Копипасты ловятся на ура, если текст достаточно большой. Также есть не делимые паттерны ими ловят рерайт. То есть суть рерайта минимальными усилиями изменить текст, ради не делимых паттернов. Но это не ваш случай, вы же написали только про запятую. Упомянул, так как ловят то обычно рерайт.

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

Не, NLP это уже перебор наверное. Слишком жирно по затратам.

Мне хватит детектора «полной» копипасты, ну или если можно дешево сделать - детектор «значительной копипасты».

Люди они ж простые - посты по ctrl+a / ctrl+v копируют, и по ходу могут ошибки исправить. Это ж не дисер, кде более основательно над текстом измываются. Обычные форумные посты и объявления о продаже.

И как потом искать совпадения, без перебора хешей для каждой фразы? Или эта задача уже не имеет «хорошего» решения?

Неточные совпадения можно попытаться искать, например, на основе алгоритмов «нечёткого поиска» fuzzy-search-tools (исходники на Java) ©.

А что планируется делать с такой копипастой?

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

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

https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%88%D0%B8%D0%BD%D0%B3%D0%BB%D0%BE%D0%B2

Реализаций куча на любых языках, думаю.

https://github.com/leprosus/golang-shingles

https://github.com/mishra-sid/FirstStoryDetectionTwitter

Да, мельком посмотрел на гитхабе - куча всего есть, как пример тебе подойдёт. Не говоря уж о том, что всякие дорвейщики такое делали больше 10 лет назад на php.

Думаю, у тебя не составит труда запилить свою реализацию быстро и без напряга.

А что планируется делать с такой копипастой?

Репортить модераторам. Дальше вручную справятся.

А шинглы чем не подходят? Тем, что нет 10мб либы на js?:)

Ты не задачу решаешь, а пальцы гнешь.

Алсо, вы тут так рассуждаете про нагрузку, как будто у вас там на форум постят 100к тредов в секунду. Нет там никакой нагрузки, ну вы чего.

Тут вообще вопрос, зачем нужно чекать копипаст в комментариях на форуме (а не в стартовом посте).

Мне хватит детектора «полной» копипасты

По моему скромному мнению — бесполезен. Вот известный персонаж на ЛОРе, когда словосочетание «забанься, дебил» начали целенаправленно искать, стал писать «за6анься, дебiл». Всё, прицел сбит. Да, это грубый пример, кросспостер так делать не будет. Но, например, синонимов в краденый текст напихать может вполне.

ну или если можно дешево сделать - детектор «значительной копипасты».

А вот это, да, была бы бомба.

Еще интересно то же самое, но для картинок.

https://en.wikipedia.org/wiki/PhotoDNA – пока вроде бы ничего лучше не придумали. Ну и FPR не нулевой, понятное дело.

А вот это, да, была бы бомба.

«Это» сделано 25 лет назад и с тех пор обсосано как только можно. На этом строятся (строились, изначально) поисковики. «Бомба» это только для старичков, которые ничего кроме как клепать формы на qt не умеют и которые думают что у wifi какой то другой tcp/ip.

краденый текст

Серьезно?

По моему скромному мнению — бесполезен. Вот известный персонаж на ЛОРе, когда словосочетание «забанься, дебил» начали целенаправленно искать, стал писать «за6анься, дебiл». Всё, прицел сбит. Да, это грубый пример, кросспостер так делать не будет.

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

Но, например, синонимов в краденый текст напихать может вполне.

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

В общем, те кто специально хотят обходить детектор - не проблема.

Ответ лежит где-то в области полнотектсового поиска. Половина того, что нужно, уже реализовано в Elasticsearch. На ум приходит что-то вроде:

1. Каждый текст загоняется в эластик.

2. Каждый кандидат на добавление режется на кусочки, кусочки ищутся в эластике.

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

А, он анонимусов игнорит. Окей.

Ура, ты переизобрел шинглы.

Это НЕПРОСТО. Вот здесь Армстронг рассказывал про свои попытки создать что-то подобное: «The Mess We’re In» by Joe Armstrong +текстовая версия

То есть поставленная тобой задача - отфильтровать наиболее тупых, кто особо не заморачивается, получается?

Что именно я переизобрёл?

Цепи Маркова. Вроде так называется алгоритм, который вычисляет схожесть одного текста с другим. Более широкое название, наверное – алгоритмы нечеткого поиска.

https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%88%D0%B8%D0%BD%D0%B3%D0%BB%D0%BE%D0%B2 Это, но только там жырный эластик не нужен.

Цепи Маркова. Вроде так называется алгоритм, который вычисляет схожесть одного текста с другим.

Нет, Марков это больше про генерацию

Ну, как не нужен,

Канонизация текста приводит оригинальный текст к единой нормальной форме. Текст очищается от предлогов, союзов, знаков препинания, HTML тегов, и прочего ненужного «мусора», который не должен участвовать в сравнении. В большинстве случаев также предлагается удалять из текста прилагательные, так как они не несут смысловой нагрузки.

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

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

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

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

Можно сравнивать генерируемые цепочки

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

Одно это может занять просто кучу времени.

Да никакого времени оно не занимает, если у тебя форумный оп пост (а вопрос был о нем) не весит гигабайт.

Как вот сотни гигов текста чекать - это отдел ная история, но оно реалтайм не нужно.

Да, можно. Но причем тут вопрос, который задал автор треда?

Ну, я не понял до конца хочет ли автор искать кросспосты внутри только своего сайта, или сравнивать со всем инетом. Если второе

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

Вопрос схожий с детектом спама (кодовые слова / похожесть текста). Глянь посему на Bayesian filtering.

А ты, конечно же, понял, хотя там это не было уточнено. Видимо, дофантазировал.

Не сказал бы что схожий. Спам это не похожесть текста на текст.