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