SimHash

SimHash — это техника хеширования, которая превращает любой текст в короткий битовый вектор, например, 64-битный. Главное свойство SimHash — семантическая чувствительность: похожие документы дают похожие хеши, отличающиеся всего в нескольких битах, а не полностью. Это отличает его от криптографических хешей, где малейшее изменение входа радикально меняет результат.

Зачем это важно? Поиск дубликатов, борьба со спамом, кластеризация новостей, проверка плагиата — всё это требует сравнения огромных объёмов текстов. Сравнивать каждый документ с каждым невозможно, а SimHash позволяет получить компактный отпечаток и быстро отыскать похожие, вычисляя расстояние Хэмминга между хешами.

Как это работает на интуитивном уровне? Представьте, что каждое слово в тексте взвешивается по значимости, например, по частоте. Алгоритм выдаёт каждому слову случайное число в том же битовом пространстве. Для каждой позиции бита он смотрит, сколько взвешенных слов имеют единицу в этой позиции и сколько — ноль. Если суммарный вес единиц больше, чем вес нулей, в итоговом хеше ставится единица, иначе ноль. Таким образом, если два документа содержат преимущественно одни и те же значимые слова, их хеши будут совпадать почти во всех битах.

Прикладной пример: онлайн-агрегатор новостей собирает статьи из тысяч источников. Одна и та же новость часто публикуется с незначительными правками. SimHash генерирует отпечаток каждой статьи. Расстояние Хэмминга между отпечатками оригинала и переработанной версии обычно равно одному-двум битам. Система легко группирует такие статьи в один сюжет.

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