Почему пакет textreuse в R делает ведра LSH намного больше, чем исходные минхеши?
Насколько я понимаю, одна из основных функций метода LSH - это сокращение данных даже за пределами базовых хэшей (часто минхешей). Я использовал textreuseпакет в R и удивлен размером генерируемых им данных. textreuse- это проверенный экспертами пакет ROpenSci , поэтому я предполагаю, что он выполняет свою работу правильно, но мой вопрос остается.
Скажем, я использую 256 перестановок и 64 полосы для моих функций minhash и LSH соответственно - реалистичные значения, которые часто используются для обнаружения с относительной уверенностью (~ 98%) сходства всего на 50%.
Если я хеширую случайный текстовый файл с использованием TextReuseTextDocument(256 perms) и назначаю его trtd, у меня будет:
object.size(trtd$minhashes)
> 1072 bytes
Теперь создадим LSH-ведра для этого объекта (64 бэнда) и назначим его l, у меня будет:
object.size(l$buckets)
> 6704 bytes
Таким образом, оставшиеся хэши в бакетах LSH в шесть раз больше, чем исходные минхэши. Я понимаю, что это происходит потому, что для создания хэшей ведра textreuse используется дайджест md5 .
Но разве это не слишком расточительно / излишне, и нельзя ли это улучшить? Нормально ли, что наша техника обработки данных раздувается до такой степени? И разве не эффективнее сопоставить документы на основе исходных хэшей (аналогично perms = 256 и Band = 256), а затем использовать порог для отсеивания ложных срабатываний?
Обратите внимание, что я просмотрел типичные тексты, такие как Mining of Massive Datasets , но этот вопрос остается в отношении этой конкретной реализации. Также обратите внимание, что вопрос не только из любопытства, но и по необходимости. Когда у вас есть миллионы или миллиарды хэшей, эти различия становятся значительными.
Ответы
Автор пакета здесь. Да, было бы расточительно использовать больше хэшей / бэндов, чем вам нужно. (Хотя имейте в виду, что здесь речь идет о килобайтах, которые могут быть намного меньше, чем исходные документы.)
Вопрос в том, что вам нужно? Если вам нужно найти только совпадения, близкие к идентичным (например, с оценкой Жаккарда, близкой к 1,0), то вам не нужен особо чувствительный поиск. Если, однако, вам необходимо надежно обнаружить потенциальные совпадения, которые имеют только частичное перекрытие (т. Е. Со счетом Жаккарда, близким к 0), тогда вам нужно больше хэшей / полос.
Поскольку вы читали MMD, вы можете найти уравнение там. Но в пакете есть две функции, задокументированные здесь , которые могут помочь вам рассчитать, сколько хэшей / бэндов вам нужно. lsh_threshold()рассчитает пороговую оценку по Жаккару, которая будет обнаружена; while lsh_probability()покажет вам, насколько вероятно обнаружение пары документов с заданной оценкой Jaccard. Поиграйте с этими двумя функциями, пока не получите количество хэшей / бэндов, оптимальное для вашей задачи поиска.