Выбор между SimHash и MinHash для производственной системы

Ответ 1

Simhash работает быстрее (очень быстро) и, как правило, требует меньше места для хранения, но накладывает строгое ограничение на то, насколько разнородными могут быть два документа, и при этом они могут быть обнаружены как дубликаты. Если вы используете 64-битный simhash (общий выбор) и в зависимости от того, сколько переставляемых таблиц вы можете хранить, вы можете ограничиться расстоянием Хэмминга, равным 3 или, возможно, 6 или 7. небольшие расстояния Хэмминга! Вы будете ограничены в обнаружении документов, которые в основном идентичны, и даже в этом случае вам может потребоваться выполнить тщательную настройку того, какие функции вы выбираете для добавления в simhash, и какие веса вы им предоставляете.

Генерирование симашей запатентовано Google, хотя на практике они позволяют по крайней мере некоммерческое использование.

Minhash использует больше памяти, поскольку вы, как правило, сохраняете 50-400 хешей для каждого документа, и это не так эффективно для процессора, как simhash, но это позволяет вам находить довольно отдаленные сходства, например, приблизительное сходство до 5%, если вы хочу. Это также немного легче понять, чем simhash, особенно с точки зрения работы таблиц. Это довольно просто реализовать, как правило, с использованием шинглинга, и не требует большой настройки, чтобы получить хорошие результаты. Он не (насколько мне известно) запатентован.

Если вы имеете дело с большими данными, наиболее ресурсоемкая часть подхода minhash, вероятно, будет после того, как вы сгенерировали minheshes для своего документа, когда вы просматриваете свою таблицу, чтобы найти другие документы, которые разделяют некоторые из ее хэши. Там могут быть десятки или сотни тысяч документов, которые разделяют по крайней мере один хэш, и вам нужно просмотреть все это, чтобы найти те немногие, которые разделяют, например, минимум половину его хэшей. Симхаш здесь намного быстрее.

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

Редактировать:

Я сейчас попробовал суперминхэш. Это довольно быстро, хотя моя реализация minhash, использующая одну хеш-функцию плюс битовые преобразования для получения всех остальных хешей, была быстрее для моих целей. Он предлагает более точные оценки jaccard, примерно на 15% лучше в некоторых ситуациях, которые я тестировал (хотя почти нет разницы в других). Это должно означать, что вам нужно примерно на треть меньше хешей для достижения той же точности. Хранение меньшего количества хэшей в вашей таблице означает, что для выявления почти дубликатов требуется меньше "прополки", что обеспечивает значительное ускорение. Я не знаю ни одного патента на суперминхэш. Спасибо, Отмар!

Ответ 2

Эта статья может дать вам несколько идей по двум алгоритмам.

http://jmlr.org/proceedings/papers/v33/shrivastava14.pdf