Какой более выгодный минхаш по сравнению с симхашем?
Я работаю с simhash, но также вижу, что minhash более эффективен.
Но я не понимаю.
Пожалуйста, объясните мне: что более выгодно, чем симхаш?
2 ответа
Simhash быстрее и, как правило, имеет меньшие требования к памяти, чем minhash, но он ограничен тем фактом, что он может обнаруживать только очень близкие сходства. Если два элемента отличаются более чем на небольшое количество, их сходство не будет обнаружено. Minhash, с другой стороны, может использоваться для обнаружения даже довольно отдаленных сходств, таких как предметы, которые имеют только 5% сходство друг с другом. Симхаш также немного сложнее для понимания.
Minhash полагается на создание нескольких хешей для каждого элемента, например, где-то между 20 и 400 64-битными хешами. Все эти хеши должны храниться вместе с идентификатором элемента, которому они принадлежат, и проиндексированы по хешу. Чтобы найти все элементы, которые имеют, например, 50% приблизительное сходство с данным элементом, вы должны найти все другие элементы, которые имеют не менее 50% хеш-значений данного элемента. Это может включать перечисление довольно большого количества пар hash-itemID.
Simhash, с другой стороны, использует только один хеш для каждого элемента, например, 64-битный хеш; и этот хеш генерируется так, что очень похожие элементы будут иметь хеш с очень похожими битовыми шаблонами. Этот хэш должен храниться (вместе с идентификатором элемента) в нескольких таблицах (например, в 8 разных таблицах), каждая таблица переставляет биты хеша по-разному, и каждая таблица сортирует переставленные хеши в числовом порядке. Использование нескольких таблиц позволяет использовать хитрый трюк, благодаря которому вы можете быстро найти все хэши, которые отличаются не более чем на n битов от данного хэша; проблема в том, что n не может быть большим: в зависимости от того, сколько элементов вы ожидаете сохранить, сколько битов во всем хэше и сколько таблиц вы можете хранить в памяти, n может быть всего 3 или, возможно, столь же высоким, как и 6 или 7.
Minhash и simhash оба зависят от скорости хранения таблиц в основной памяти, хотя они могут быть разделены на несколько машин, если вам необходимо преодолеть ограничения памяти. Метод создания simhash защищен патентом, принадлежащим Google, хотя они, по-видимому, позволяют по крайней мере некоммерческое использование алгоритма.
В simhash нам не нужно хранить гиперплоскости. Он имеет немного худшие границы ошибок. Симхаш лекция