Как обнаружить похожий текст на больших данных?
Как я только знаю, simhash и minhash доступны для этой задачи. Но все эти алгоритмы должны пересекать всю текстовую базу данных, что будет довольно ужасно. Есть ли оптимизация или другой алгоритм, который может решить задачу? Все, что я придумаю, - это нарезка текстовой базы данных на несколько частей и параллельное получение парного сходства. Моя текстовая база данных насчитывает около 1 миллиарда записей.
1 ответ
Вы должны пройти всю базу данных один раз (1 миллиард записей).
Преимущество minhash и simhash заключается в том, что вам не нужно отдельно сравнивать каждую возможную пару, чтобы увидеть, схожи ли они (примерно 500 квадриллионов возможных пар).
Разделение базы данных на несколько частей не поможет; вы просто упустите некоторые сходства. Разделение имеет смысл только в том случае, если записи естественным образом попадают в группы, которые, как вы знаете, не могут иметь никаких сходств между ними (например, если у вас есть два совершенно разных типа записей, которые никогда не похожи друг на друга, вы можете обрабатывать их отдельно для обнаружения сходства),
И simhash, и minhash могут извлечь выгоду из распределенных вычислений. Генерация хэшей может быть распределена столько, сколько вам нужно. При желании хранилище хешей можно разделить с помощью карты / уменьшить, хотя для simhash вам это, вероятно, не понадобится, поскольку он достаточно компактен, чтобы поместиться в достаточно стандартную основную память компьютера.
Simhash может находить только пары сходства, которые очень похожи, и для правильной работы часто требуется немало настроек. Если вы хотите найти более слабое сходство, используйте один из вариантов minhash, который более щадящий. Я рекомендую проверить superminhash, в сочетании с LSH. Superminhash быстро генерирует хэши, но, что еще важнее, он обеспечивает лучшую точность, поэтому необходимо хранить меньше хэшей. LSH группирует хэши в группы, чтобы вы не сравнивали отдельные хэши; Вы сравниваете всю группу за раз. Оба эти метода означают, что для поиска отдельных общих хэшей (или полос в последнем случае) требуется меньше запросов, а LSH, в частности, означает, что для каждого отдельного запроса потребуется меньше результатов. Это должно дать вам существенное ускорение.