Логика: лучший способ для выборки и подсчета байтов файла размером более 100 МБ

Question

Допустим, у меня есть этот файл 170 МБ (примерно 180 миллионов байт).Что мне нужно сделать, так это создать таблицу , в которой перечислены:

1. все найденные комбинации 4096 байтов [столбец 'bytes'] и
2. количество раз, которое каждая байтовая комбинация появилась в нем [столбец 'вхождения']

Допустим две вещи:

1. Я могу сохранитьданные очень быстро , но
2. Я могу обновить свои сохраненные данные очень медленно .

Как мне сэмплировать файли сохранить необходимую информацию?

Вот несколько советов, которые (чрезвычайно) медленны:

• Просмотрите все 4096 комбинаций байтов в файле, сохраните все данные,но сначала найдите в таблице существующие комбинации и обновите их значения. это невероятно медленно
• Просмотрите все 4096 байтовых комбинаций в файле, сохраните до 1 миллиона строк данных во временной таблице.Пройдите по этой таблице и исправьте записи (объедините повторяющиеся комбинации байтов), затем скопируйте в большую таблицу .Повторите, пройдя еще 1 миллион строк данных, и повторите процесс. это немного быстрее, но невероятно медленно

Это похоже на получение статистики файла.

ПРИМЕЧАНИЕ: я знаю, что выборка файла может генерировать тонны данных (около 22 Гб из опыта), и я знаю, что любое опубликованное решение заняло бы немного времени для завершения.Мне нужен самый эффективный процесс сохранения

Answer 1

Первое решение, которое вы предоставили, может быть значительно ускорено, если вы также хешируете данные и сохраняете хэш 4096-байтового сегмента в своей базе данных, а затем сравниваете его.Сравнение со строкой длиной 4096 байт потребовало бы вечности, но это было бы значительно быстрее:

For each 4096-byte segment in the file
    Hash the segment into something short (even MD5 is fine, and it's quick)
    Look up the hash in your database
        If it exists (segment may have already been found)
            Compare the actual segment to see if there's a match
        If it doesn't exist
            It's a new segment - save it to your database

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

Answer 2

Уже немного поздно, и я не могу думать прямо, поэтому мой расчет сложности алгоритма отчасти не верен :) Но если вам удастся поместить его в память, у вас может быть очень очень быстрая реализация с . Если вы можете оптимизировать каждый узел trie, чтобы он занимал как можно меньше памяти, он может просто работать.

Другое дело, по сути, предложение @ rwmnau, но не используйте предопределенные хеш-функции, такие как MD5 - используйте промежуточные итоги. В отличие от хэшей, это почти бесплатно, без каких-либо недостатков для такого большого размера блока (много случайностей в 4096 байтах). С каждым новым блоком вы получаете один байт и теряете один байт. Итак, вычислите сумму первых 4096 байтов; для каждого последующего просто вычтите потерянный байт и добавьте новый. В зависимости от размера целого числа, в которое вы вносите суммы, у вас будет много сегментов. Тогда у вас будет гораздо меньшее количество блоков для сравнения побайтно.