femtozip

> Finding ways to have, say, 10 million blacklist elements with a small memory footprint is left as an exercise for the reader. In case the reader is interested (and this may not be what OP had in mind): In trading memory gains with computation, this is how I squeezed ~4M entries in less than 30 MiB: 1. Compress (reversed) individual entries using a dictionary or entropy encoder. I experimented with Shoco [0], Femto [1], and a modified LZ78 [2]. 2. Create a bloom filter for membership checks, [3] or any probabilistic structure for that matter, like the xor-filters [4]. This prevents expensive but unnecessary lookups. 3. Insert the compressed (reversed: google.com -> com.google) entries into a radix-tree [5]. You could use a directed-acyclic graph (DAG), if you don't need to store key-value pairs. 4. Compact [6][7] the radix-tree [8] (comp

Annoying detail for DEFLATE + dictionary is that the dictionary has to be provided within every reader (setDictionary in java). The output from the DEFLATE stream is not standalone, which makes it really hard to use - a more ideal approach would've been to provide training to the Huffman tree & guess best window sizing from a sample. But SDCH solves that problem by storing an external named dictionary - clients will read it off a common HTTP location if it's missing in the cache. Within that, there's a pretty neat standard which SDCH uses - RFC 3284. I ran into it trying to optimize holding a few billion serialized blogs within an in-memory store with transactional updates - the issue was mostly the in-memory sizes of serialized objects. I ended up using a versioned external dictionary for compression, which was an extension to VCDIFF wit