Как стать автором
Обновить

Комментарии 8

Многие вещи типа дедупликации или даже установления авторства можно сделать вот этим.

Собственно идея крайне проста, если слить два текста и упаковать, то коэффициент сжатия будет тем больше, чем больше одинаковых паттернов в обоих текстах.
Как ни странно — часто работает.
:-)

Правда при сколько-нибудь реальных объемах документов — процессор расплавится, т.к. расчет очень затратен, а для всей базы еще и квадратичен.

Я в похожих задачах вместо шинглов использовал bloom filter на случайных или на полных ngramm'ах.
Как-то работало, в сочетании с aNN методами, чтобы уйти от квадратичности.

У BF есть преимущество — все магические константы (типа 84) достаточно просто считаются под задачу и обоснованы теорвером и прочим матаном.
За «Normalized compression distance» спасибо. В любом случае интересно сравнить ресурсоемкость/качество работы алгоритма. А какие aNN методы вы использовали в паре с bloom filter?
Ну, по ресурсоемкости хуже чем NCD наверное и не найти, компрессия — штука тяжелая, и чем она тяжелее, тем точнее результат.

Я с Bloom filter использовал самописную версию LSH, думал перейти на более хитрые извращения, но потом задачу решил по другому, вообще без BF и дедупликации, т.е. саму постановку задачи перекрутил.

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

Для BF кстати лучше использовать Жаккардову метрику, не Хемминга — считается битовыми операциями и как-то «нативнее» для BF — показывает отношения в множестве.
Ну и она же и используется в известном MinHash — который тоже может быть применен для дедупликации.
Спасибо, разобрался с NCD.

Один на github, а второй на одном сайте по c# .

Если вкратце есть формула NCD(x,y) = C(xy) — min{C(x), C(y)} / max{C(x), C(y)}, где С возвращает длинну текста (строк, изображений и тд) после обработки алгоритмом архивации(например: «gzip», «bzip2», «PPMZ»). Причем xy — это два текста склеиных в одну переменную. Например xy = x + ' ' + y.

Выложил свой пример на github. Только не могу понять, почему для двух строк 'hello world' выводит резульат 0.09.
Так потому что архиватор — это приближение.
В точности должна быть т.н. «Колмоговровская сложность».
А архиватор дает очень приблизительную оценку.

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

И еще, на маленьких строках портит все заголовок архива.
Т.е. вот Hello world!\n
13 байт
А архив bzip2 — 53 байта — вот такая хреновая компрессия.
А двойной архив — 57 байт.

А с другой стороны — вот берем файл www.lib.ru/GIBSON/neuromancer.txt
485967 байт
Соответственно сжатый отдельно он — 152317
А сжатый с самим собой — 223390

Получаем дистанцию 0.467, что совершенно не похоже на ожидаемый 0.
Это уже артефакт блочной архивации.
Т.е. не все там так просто и не всякий архиватор пойдет.

А вот возьмем например архиватор xz
У него архивированный текст «Нейромантика» — 167532 байт (хуже чем у bzip2)
А архивированный сам с собой — 167680
Что дает дистанцию — 0.0008834

Совсем другое дело.

Для поиска дубликатов текста в одном из проектов использую алгоритм LSA (http://blog.netpeak.ru/algoritm-lsa-dlya-poiska-pohozhih-dokumentov/). Реализацию не проблема найти под требуемый язык программирования.
Можете более детально обьяснить, как расчитывать степень похожести 2-х документов после вычисления матрицы U, V, W?
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории