Огромное спасибо за ваш проект. Жаль, что в 21 веке такой отчет до сих пор не обязателен. Я не ставлю под сомнение эффективность алгоритма, но если эта информация не является секретной было бы классно опубликовать чуть больше технических деталей.
Жадным называется алгоритм, принимающий локально оптимальные решения. В примере с поиском документов по запросу логично предположить, что такой алгоритм может снижать полноту выборки по документам. Поскольку большое количество хешей(не фрагментов) еще не гарантия того, что будут найдены все заимствования, то вроде как условия для жадности не выполняется.
Например, на основании 2х первых наборов хешей будет отброшен документ содержащий общий набор хешей, но в нем будет заимствование, которого может не оказаться в первых документах.
1: AAA 2:BBB 3:AB
Я понимаю, что с учетом перекрытия при шинглировании реальный пример будет сложнее, но потеря полноты на данном этапе может помешать установить наибольший заимствованный фрагмент например.
Если же вспомнить, что хеши имеют коллизии, то еще больше хочется увидеть конкретные цифры полноты и точности для данного алгоритма.
Пример того, как можно использовать MinHash:
Считаем MinHash для типичных фрагментов абзац/предложение, совпадение хешей в этом случае будет означать совпадение фрагментов с вероятностью, которой можно управлять количеством хеш-функций. В дальнейшем, при отборе документов мы имеем фрагменты текста, а нет хеши.
Жадным называется алгоритм, принимающий локально оптимальные решения. В примере с поиском документов по запросу логично предположить, что такой алгоритм может снижать полноту выборки по документам. Поскольку большое количество хешей(не фрагментов) еще не гарантия того, что будут найдены все заимствования, то вроде как условия для жадности не выполняется.
Например, на основании 2х первых наборов хешей будет отброшен документ содержащий общий набор хешей, но в нем будет заимствование, которого может не оказаться в первых документах.
1: AAA 2:BBB 3:AB
Я понимаю, что с учетом перекрытия при шинглировании реальный пример будет сложнее, но потеря полноты на данном этапе может помешать установить наибольший заимствованный фрагмент например.
Если же вспомнить, что хеши имеют коллизии, то еще больше хочется увидеть конкретные цифры полноты и точности для данного алгоритма.
Пример того, как можно использовать MinHash:
Считаем MinHash для типичных фрагментов абзац/предложение, совпадение хешей в этом случае будет означать совпадение фрагментов с вероятностью, которой можно управлять количеством хеш-функций. В дальнейшем, при отборе документов мы имеем фрагменты текста, а нет хеши.
Вы сравнивали его полноту с не жадным?
А с MinHash, Bloom filter, SimHash, w-shingling, Count-min sketch?