Хороший вопрос!
На третий взгляд, я бы поступил по следующему алгоритму.
Взял бы базу данных, ну например mysql.... Для хранения кешей и коллизий.
Итак, нам нужно пройтись по записям бигфайла, и сформировать новый бигфайл.
1) берем строчку файла, считаем от нее (или какой-то части), например sha1.
2) ищем по базе данных наш sha1
(таблица в "hashes" c полями "hash" и "offset", "count")
2.1) Если не нашли:
- копируем текущую строку в новый файл
- заносим наш sha1 и начало строки в базу (это нужно для коллизий)
2.2) Если нашли:
- из базы забираем смещение начала строки
- из старого файла вытягиваем всю строку по смещению и сравниваем
- если строки равны, то переходим на п1) (можно еще и обновить count этой записи)
- если строки не равны, у нас коллизия (!), обрабатываем ее
3) Обработка коллизии
(таблица в "collisions" c полями "hash" и "offset", "count")
- берем из collisions все записи по нашему хешу
- для каждой записи вынимаем строку из старого файла и сравниваем
- если строки равны, то переходим на п1) (можно еще и обновить count этой записи)
- если строки не равны, добавляем новую запись в таблицу collisions с новым смещением, текущюю строку пишем в новый файл
В принципе, этот процесс можно параллелить на бесконечное количество процессов. хотя, нужно бы еще над этим подумать.
PS. Можно еще дополнительное поле в каждой из таблиц сделать "count", обновлять его, если произошло сравнение записей, для статистики.
