Logic: Best way to sample & count bytes of a 100MB+ file

Question

Let's say I have this 170mb file (roughly 180 million bytes). What I need to do is to create a table that lists:

1. all 4096 byte combinations found [column 'bytes'], and
2. the number of times each byte combination appeared in it [column 'occurrences']

Assume two things:

1. I can save data very fast, but
2. I can update my saved data very slow.

How should I sample the file and save the needed information?

Here're some suggestions that are (extremely) slow:

• Go through each 4096 byte combinations in the file, save each data, but search the table first for existing combinations and update it's values. this is unbelievably slow
• Go through each 4096 byte combinations in the file, save until 1 million rows of data in a temporary table. Go through that table and fix the entries (combine repeating byte combinations), then copy to the big table. Repeat going through another 1 million rows of data and repeat the process. this is faster by a bit, but still unbelievably slow

This is kind of like taking the statistics of the file.

NOTE: I know that sampling the file can generate tons of data (around 22Gb from experience), and I know that any solution posted would take a bit of time to finish. I need the most efficient saving process

Answer 1

The first solution you've provided could be sped up significantly if you also hash the data and store the hash of the 4096-byte segment in your database, then compare to that. Comparing to a string that's 4096 bytes long would take forever, but this would be significantly faster:

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

Hashing the segment isn't free, but it's pretty cheap, and the comparisons between hashes will be orders of magnitude cheaper than comparing the full byte segments to each other repeatedly. Hashes are useful for a many applications - this is definitely one of them.

Answer 2

It's a bit late and I can't think straight, so my algorithm complexity calculation is kind of off :) But if you manage to fit it into memory, you might have a very very quick implementation with a trie. If you can optimize each trie node to take as little memory as possible, it just might work.

Another thing is basically @rwmnau's suggestion, but don't use predefined hash functions like MD5 - use running totals. Unlike hashes, this is almost free, without any downside for such a large block size (there's plenty of randomness in 4096 bytes). With each new block, you get one byte, and you lose one byte. So calculate a sum of the first 4096 bytes; for each subsequent ones, simply subtract the lost byte and add the new one. Depending on the size of the integer you do the sums in, you will have plenty of buckets. Then you will have much smaller number of blocks to compare byte-for-byte.