Чем минхеш выгоднее симхэша?

Simhash быстрее и обычно требует меньше памяти, чем minhash, но он ограничен тем фактом, что может обнаруживать только очень близкие сходства. Если два элемента отличаются более чем на небольшую величину, их сходство не будет обнаружено. Minhash, с другой стороны, может использоваться для обнаружения даже очень отдаленных сходств, например, предметов, которые имеют только 5% сходства друг с другом. Simhash также немного сложнее понять.

Minhash полагается на создание нескольких хэшей для каждого элемента, например. обычно где-то между 20 и 400 64-битных хэшей. Все эти хэши необходимо хранить вместе с идентификатором элемента, которому они принадлежат, проиндексированным по хешу. Чтобы найти все элементы, которые имеют, например. 50% предполагаемого сходства с данным элементом, вы должны найти все другие элементы, которые имеют не менее 50% хэшей данного элемента. Это может потребовать перечисления довольно большого количества пар хэш-идентификатор элемента.

Simhash, с другой стороны, использует только один хеш для каждого элемента, например. 64-битный хэш; и этот хэш генерируется таким образом, что очень похожие элементы будут иметь хэши с очень похожими битовыми шаблонами. Этот хеш должен храниться (вместе с идентификатором элемента) в нескольких таблицах (например, в 8 разных таблицах), каждая таблица переставляет биты хеша по-разному, и каждая таблица сортирует переставленные хэши в числовом порядке. Использование нескольких таблиц дает возможность быстро найти все хэши, отличающиеся не более чем на k битов от заданного хеша; проблема в том, что k не может быть большим: в зависимости от того, сколько элементов вы собираетесь хранить, сколько битов содержится во всем хеше и сколько таблиц вы можете хранить в памяти, k< /em> может быть от 3 до 6 или 7. См. это объяснение simhash.