## Monday, December 22, 2008

### Compressed Vectors - Part 1

Normally for data that has a lot of repeating values, I use run-length encoding - it works particularly well when the data is accessed from start to end in forward order.  For example, the spot lighting masks for X-Plane's 2-d panels are RGBA image that are RLE compressed. Continuous scan lines of transparent window become a single RLE line segment.  This actually makes processing faster, because the decision to skip transparent areas is made once per scan line, not once per pixel.

Things get a little bit trickier if we need random access to the data.  The structure I am playing with now provides something similar to that.  It is a vector where continuous values are stored once in runs.  It has two parts:
• A run index (stored as a sorted vector of key-value pairs) maps the beginning of a run (in the virtual data) to the start of storage (in a real data vector).
• A real data vector contains each value as few times as possible.
We don't need to store "how long is this run" in the data vector - the index gives it to us.  We just look at the next index key-value pair and see (1) how long is our run and (2) how much data is behind it.  If only one value backs our 5-value run, we are run-length compressed.

Complexity properties: call N the number of items, U the number of unique items, and R the number of runs (that is, the number of times we change from RLE to non-RLE data.
• In the worst case (totally non-sequential data), the storage is the same as vector: O(N).  In the best case (all the same) we are O(1).  In both cases, R=1.
• Generally our storage is O(R+U), which should be less than O(N).
• Random access is O(log(R)) - not quite constant time, but pretty fast.  For the worst case random data, R is 1, so we can be fast that way.
• Pushing data onto the end is constant time plus any cost of memory reallocation; since the vector is compressed, hopefully that is less.
• Deleting data from the front is O(R+U) instead of O(N), which is a bit of an improvement.
At this point the unit tests work, but I don't have stats on real-world compression.
{"ft_lang_label":"__label__en","ft_lang_prob":0.93241584,"math_prob":0.97060555,"size":1247,"snap":"2021-43-2021-49","text_gpt3_token_len":306,"char_repetition_ratio":0.114239745,"word_repetition_ratio":0.0,"special_character_ratio":0.24939856,"punctuation_ratio":0.10948905,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9808112,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-26T11:53:00Z\",\"WARC-Record-ID\":\"<urn:uuid:8cc6da4b-c46e-40c5-a103-6cbf8ea9a99a>\",\"Content-Length\":\"92843\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ae1b4467-accb-4c2f-b584-86f428ce1e13>\",\"WARC-Concurrent-To\":\"<urn:uuid:ff2efc12-5da4-4aa6-ab22-710d3670dc03>\",\"WARC-IP-Address\":\"142.251.45.97\",\"WARC-Target-URI\":\"https://hacksoflife.blogspot.com/2008/12/compressed-vectors-part-1.html\",\"WARC-Payload-Digest\":\"sha1:G2C2C4UB3QARTYGLAZ5IA26IFFYV3QSG\",\"WARC-Block-Digest\":\"sha1:V3SGEJDJZMP2HBFPTV3WYJVDOM73OZRX\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323587877.85_warc_CC-MAIN-20211026103840-20211026133840-00557.warc.gz\"}"}