Searching a compressed, sorted fixed-width file
Suppose I have a constant fixed width file that is sorted into one of the fields. Given that I know the length of the records, I can use lseek to implement a binary search to find records with fields that match a given value, without having to read the entire file.
Now the difficulty is that the gzipped. Can this be done without completely bloating the file? If not with gzip. is there any compression that supports this behavior?
a source to share
This is not possible if the file is compressed using zip and derivatives. They are based on a sliding dictionary window, typically with some buffered compression of the most significant bits of the output codes on top of that. The bottom line is that a particular sequence of bytes in a zip file is meaningless without context.
If you want to be able to randomly read a specific record from a compressed file, you have to compress each record independently and then have an index in the file. Depending on your data, this will probably make the compression step useless.
a source to share
The bzip2 file format consists of several independently compressed blocks. If you want to maintain an index along with the bzip2 file, you might know where lseek to.
Note. This is a duplicate of the questions:
- Compression formats with good support for random access in archives?
- Random access gzip stream
- Random file access with multiple gzip files (in Java)
They answer the same question, but also that BGZF is a gzip-compatible output format with sync points inserted into the reset compression state.
a source to share
Almost all compressed algorithms I know operate in block mode , which means that random searches are not possible. Even LZMA, which does not use an initial dictionary, requires sequential decompression.
Stream compression means usually lossy adaptive compression with some key that is reset (or actually sliced into blocks). The details are more complex.
Now, here are some ideas for solving this problem:
- Create an index. Just like opening a ZIP, you can see all the files in it.
- Cut the compressed file into blocks and then use binary search on each block (same as the first)
- Decompress in memory, but actually discard any data until you find the start of the data you are looking for.
The latter method is good for small compressed files, and the block method is good for large compressed files. You can mix the two.
PS: Fixed with input does not mean the compressed file will be fixed. So this is pretty useless information.
a source to share
Based on what Wernight said , you can split your file into many fixed size subfiles before you gzip it. Your binary search might start by looking for a subfile that contains a range, then it only needs to decompress a small subfile, not the whole. You can optimize by creating a top-level file in the archive that contains the first line of each sub-file.
a source to share
Continuing what Ludvikas Bukis says: If your compressed blocks have a unique title, you don't need an index. This is similar to how some compressed video formats are searched. You aim for the point and look for the next heading. This requires reliable verification (using a checksum), though, as incorrect identification is possible.
a source to share
what you want is searchable compression; the dict server has dictzip, which format is gzip-compatible because it stores it in the gzip extension file in the header, and the chemistry kit has sgzip, which is not the one that stores the block lengths at the beginning of each block.
a source to share