Вот моя проблема (я программирую на C):
У меня есть несколько огромных текстовых файлов, содержащих последовательности ДНК (каждый файл имеет примерно 65 миллионов строк и размер около 4 ~ 5 ГБ). В этих файлах много дубликатов (пока не знаю, сколько их, но их должно быть много миллионов), и я хочу вернуть на выходе файл только с различными значениями. Каждая строка имеет связанное значение качества, поэтому, если, например, у меня есть 5 одинаковых строк с разными значениями качества, я выберу лучшую и отброшу остальные 4.
Снижение требований к памяти и повышение эффективности скорости, насколько я могу, жизненно важно. Моя идея заключалась в том, чтобы создать массив JudyHS с использованием хэш-функции, чтобы преобразовать последовательность ДНК String (которая состоит из 76 букв и имеет 7 возможных символов) в целое число, чтобы уменьшить использование памяти (4 или 8 байтов вместо 76 байтов на многих миллионы записей должно быть настоящим достижением). Таким образом, я мог использовать целое число в качестве индекса и хранить только лучшее значение качества для этого индекса. Проблема в том, что я не могу найти хэш-функцию, которая УНИВЕРСАЛЬНО определяет такую длинную строку и выдает значение, которое может быть сохранено внутри целого числа или даже long long!
Моей первой идеей для хеш-функции было что-то вроде хеш-функции строки по умолчанию в Java: s [0] * 31 ^ (n-1) + s [1] * 31 ^ (n-2) + ... + s [ n-1], но я смог получить максимальное значение 8,52 * 10 ^ 59 .. слишком велико. Как насчет того, чтобы сделать то же самое и сохранить это в дубле? Становятся ли вычисления намного медленнее? Обратите внимание, что мне нужен способ УНИВОКАЛЬНО определить строку, избегая коллизий (или, по крайней мере, они должны быть крайне редкими, потому что мне пришлось бы обращаться к диску при каждом столкновении, довольно дорогостоящая операция ...)
