Поиск похожих файлов в большом архиве

Question

У меня есть архив около 100 миллионов двоичных файлов. Новые файлы регулярно добавляются. Размеры файлов варьируются от примерно 0,1 МБ до примерно 800 МБ.

Я могу легко определить, возможно ли, что файлы, вероятно, полностью идентичны, сравнивая их размеры и размеры совпадают, сравнивая хэши файлов.

Я хочу найти файлы с частично похожим контентом. Я имею в виду, что я считаю, что у них есть части, которые идентичны, и некоторые части, которые могут быть разными.

Какое лучшее или какой-либо реалистичный способ найти файлы, похожие на другие файлы, и, если возможно, получить какую-то информацию о том, насколько они похожи?

Редактировать: Файлы в основном исполняемые файлы. Они похожи, если, скажем, где-то между 10% и 100% их содержимого совпадают с содержимым другого файла. Нижний предел также может быть установлен на 50%. Точный нижний предел не важен. Я предполагаю, что для такого сравнения понадобится какая-то форма хэширования для такого сравнения.

Answer 1

Это зависит от того, как вы будете определять сходство, если, например, вы можете определить сходство, сравнив только первые 100 байт каждого файла, тогда я предполагаю, что это было бы осуществимо, но найти конкретное сравнение строк в 100 миллионах файлов, которые может быть 800 МБ большой, было бы совершенно неосуществимо.

Answer 2

Нелегкая проблема. Первым шагом является отображение каждого файла в набор хэшей, т. Е. Целых чисел. В идеале вы хотите сделать это, вычислив хэши набора подстрок в каждом файле, чтобы подстроки были равномерно распределены по всему файлу, но также вероятность того, что подстрока встречается в разных файлах, редка. Например, если файлы были английским текстом, вы могли бы разделить файл на подстроки на всех наиболее распространенных английских словах (the, to, be, of, and, ...). Чтобы сделать это с исполняемыми файлами, я сначала вычислил, какие наиболее частые пары или тройки всех файлов есть, и выберите верхний N, чтобы разделить файлы, которые, мы надеемся, сгенерируют подстроки, которые «не слишком длинны». Просто «недолго» с исполняемыми файлами - это то, о чем не имеет никакого представления.

Как только у вас есть эти подстроки, у вас есть проблема поиска похожих множеств, которая называется совокупностью сходств, соединяющей проблему в информатике. См. Мой пост here для методов/кода для решения этой проблемы. Удачи!