Monday, February 18, 2013

more on storing pixels

I recently thought about an extra possibility to reduce storage of tiles.

Since we directly store many strings in flash, and that we will store pointers to those strings, I will try to use "string tiling" (which is of course the same word as tiling but with a totally different meaning).

String tiling consists of detecting how to store efficiently N strings given pointers by taking advantage of overlaps.

By example, if you want to store AAAABBBBCCCC and BBBBCCCCDDDD and AABBB, you might as well store AAAABBBBCCCCDDDD only + pointers/length pairs (0,12), (4,12) and (2,4)

My current simple implementation detects for a string when a string begins by another (only partly match is needed, but only at beginning/end of strings respectively), or a string is included withing another (string must be completely included but place is free).

This leads to reduction of up to 17% with real life data, not bad for a free decompression !

No comments:

Post a Comment