ROM Shingler

Search for borrowings in files

Поиск заимствований в файлах с использованием алгоритма шинглов и коэффициента Жаккарда.

Идея этой утилиты следующая: она использует алгоритм шинглов для поиска схожих образов игр.

Для чего нужен поиск родственных игр

1. Для лучшего сжатия. Как известно, упаковка схожих файлов в одном архиве позволяет создавать архивы с очень крутым коэффициентом сжатия.
2. Для составления полного списка игр.
3. Для выборки уникальных игр.
4. Для изучения игр в широком смысле этого слова. Например, образ сборника игр не запускается но после изучения можно составить список игр, которые в него входят. Или можно находить игры, сделанные на одном движке. Применений много.

Для примера возьмём коллекцию игр GoodNES v2.32b. В ней 22094 образов игр, из которых уникальных до 3 тысяч. Перебрать такую груду вручную возможно, но времени это займёт немало.

Немного теории

Шинглы это набор хэшей. Используется CRC32, размер шингла: 8. Как они готовятся?

Берётся образ игры и аккуратно нарезается на кусочки размером в 8 байт. Нарезка идёт внахлёст, то есть, первый шингл начинается с индекса 0, второй с индекса 1, итд. Например, втором шингле 7 байт из первого и один новый.

Генерация шинглов для игр NES/Famicom длится около 5 часов.

С точки зрения дискового пространства это тоже дорого. 5637 Мб распакованных игр получают 49 279 Мб шинглов, то есть примерно в 10 раз больше! Естественно, в памяти такое не удержать, приходится сохранять на диск.

Далее идёт сравнение коллекций шинглов.

Поскольку эта операция займёт несколько недель (22094 * 22094 / 2), приходится идти на оптимизации.

Перебираем коллекции шинглов, оставляя те контрольные суммы, которые делятся по модуля на 16. Таким образом, последний этап ускорится в 128 раз. Остаётся только понять, насколько при этом пострадает точность сравнения...

Из коллекций шинглов для двух игр получается две другие коллекции: их пересечение и их объединение. Естественно, во всех коллекциях хранятся уникальные значения, дубликатов нет.

Set<Long> s1intersect = new HashSet<>(s1Set);
Set<Long> s1union = new HashSet<>(s1Set);

s1intersect.retainAll(s2Set);
s1union.addAll(s2Set);
double relative = s1intersect.size() * 1.0 / s1Set.size();
double jakkard = s1intersect.size() * 1.0 / s1union.size();

Вот результат сравнения 10-Yard Fight (J) (PRG0) [!].nes с несколькими играми. Первое число это разница в процентах, второе - коэффициент Жаккарда:

10-Yard Fight (J) (PRG0) [p1][o1].nes:
0.9975749661894324
0.9950227928179366

10-Yard Fight (J) (PRG1) [!].nes:
0.8302009979946836
0.7096954233774517

10-Yard Fight (U) [!].nes:
0.670195401762813
0.4609635617141391

1919 by Me_Dave (Hard version) (1942 Hack).nes:
0.007741454087581028
0.0028800444151427878

Хорошо видно не-родственную игру.

Что ещё можно сделать

1. Многопоточная обработка
2. Группировать игры по семействам, упаковывать
3. Выбирать уникальные игры
4. Упаковывать шинглы, хотя бы в ZIP, чтобы много не занимали
5. Привязывать шиндлы к хешу файла, где-то это помнить

Другие решения

1. Архивировать по 2 игры и изучать коэффициент сжатия. Возможно это решение работает быстрее шинглов
2. Продвинутые алгоритмы шинглов

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

Начинать с того, что собрать семьи из одноимённых файлов (1024), порог 20. Дальше посмотреть. Надо по шагам повышать точность и понижать порог. В конце слить родственные семьи.