{"action":"created","issue":{"url":"https://api.github.com/repos/TheIronDeveloper/jenova/issues/1","labels_url":"https://api.github.com/repos/TheIronDeveloper/jenova/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/TheIronDeveloper/jenova/issues/1/comments","events_url":"https://api.github.com/repos/TheIronDeveloper/jenova/issues/1/events","html_url":"https://github.com/TheIronDeveloper/jenova/issues/1","id":95852326,"number":1,"title":"Possible alternative compression methods for the boards","user":{"login":"rotemdan","id":8589488,"avatar_url":"https://avatars.githubusercontent.com/u/8589488?v=3","gravatar_id":"","url":"https://api.github.com/users/rotemdan","html_url":"https://github.com/rotemdan","followers_url":"https://api.github.com/users/rotemdan/followers","following_url":"https://api.github.com/users/rotemdan/following{/other_user}","gists_url":"https://api.github.com/users/rotemdan/gists{/gist_id}","starred_url":"https://api.github.com/users/rotemdan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rotemdan/subscriptions","organizations_url":"https://api.github.com/users/rotemdan/orgs","repos_url":"https://api.github.com/users/rotemdan/repos","events_url":"https://api.github.com/users/rotemdan/events{/privacy}","received_events_url":"https://api.github.com/users/rotemdan/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/TheIronDeveloper/jenova/labels/enhancement","name":"enhancement","color":"84b6eb"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2015-07-18T19:23:25Z","updated_at":"2015-07-19T08:03:39Z","closed_at":null,"body":"If I understand this correctly, since the boards are essentially binary data (can only contain 0s and 1s), by encoding them to binary you could get a constant reduction in size by a factor of 8. To save them as LocalStorage compatible strings it would be possible to use `LZUTF8.encodeBinaryString()` on the resulting binary data (otherwise it might be possible to simply encode every 16 bits to a single character directly) - with some padding method - maybe just by storing the bit length along with the data.\r\n\r\nLooking at game-of-life boards it also seems that larger and relatively sparse boards might benefit from [run-length encoding](https://en.wikipedia.org/wiki/Run-length_encoding) which would be very fast and give good results in these cases (I mean after the data is already binary, it would have sequences of 0 and 255 for long runs of 0s and 1s respectively). Writing an RLE de/compressor is actually very easy (much simpler than Lempel-Ziv). [Modified huffman coding](https://en.wikipedia.org/wiki/Modified_Huffman_coding)  (which is a cross between [huffman coding](https://en.wikipedia.org/wiki/Huffman_coding) and RLE) will probably be more effective but isn't as easy to implement (though not that difficult). Line-by-line [delta encoding](https://en.wikipedia.org/wiki/Delta_encoding) before the entropy/RLE coding may also improve the compression rate if there are relatively solid two-dimensional structures invloved (solid squares/circles etc.) - this is used in [CCITT Group 3 compression](https://en.wikipedia.org/wiki/Fax#Modified_READ) - which is used in fax machines (using both line-by-line deltas and modified huffman would lead to something very similar to fax compression).\r\n\r\nEven better results could probably be achieved with more efficient [bitonal](https://en.wikipedia.org/wiki/Binary_image) (black and white) image compression algorithms such as [CCITT Group 4 compression](https://en.wikipedia.org/wiki/Group_4_compression), [JBIG](https://en.wikipedia.org/wiki/JBIG) or [Lossless JBIG2](https://en.wikipedia.org/wiki/JBIG2) (these compression methods are commonly used for fax, scanned documents [usually stored in TIFF files] and PDF files). Although I'm not very familiar with them it seems like they use similar methods, with some more advanced ones..\r\n\r\nThese methods could also be adapted for recording complete \"animations\" for sequences of successive boards. I don't really know of a lossless \"video\" compression algorithms optimized for bitonal images though, so some form of a delta encoding between the frames could be used. It would actually be cool to develop something like that, even if it does exists, it would probably be quite obscure (or I might be mistaken).\r\n\r\nAnyway, I'll try to think of a method to compress these efficiently. If I manage to come up with something simple and efficient, I'll publish it separately from LZ-UTF8 (though I have some code I could reuse from it).\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/TheIronDeveloper/jenova/issues/comments/122637754","html_url":"https://github.com/TheIronDeveloper/jenova/issues/1#issuecomment-122637754","issue_url":"https://api.github.com/repos/TheIronDeveloper/jenova/issues/1","id":122637754,"user":{"login":"rotemdan","id":8589488,"avatar_url":"https://avatars.githubusercontent.com/u/8589488?v=3","gravatar_id":"","url":"https://api.github.com/users/rotemdan","html_url":"https://github.com/rotemdan","followers_url":"https://api.github.com/users/rotemdan/followers","following_url":"https://api.github.com/users/rotemdan/following{/other_user}","gists_url":"https://api.github.com/users/rotemdan/gists{/gist_id}","starred_url":"https://api.github.com/users/rotemdan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rotemdan/subscriptions","organizations_url":"https://api.github.com/users/rotemdan/orgs","repos_url":"https://api.github.com/users/rotemdan/repos","events_url":"https://api.github.com/users/rotemdan/events{/privacy}","received_events_url":"https://api.github.com/users/rotemdan/received_events","type":"User","site_admin":false},"created_at":"2015-07-19T08:03:39Z","updated_at":"2015-07-19T08:03:39Z","body":"A further optimization (that could also be used with single frames) is to always assume the \"zeroeth\" frame (which doesn't actually need to be transmitted) is the \"blank\" frame, e.g.\r\n```\r\n0,0,0,0\r\n0,0,0,0\r\n0,0,0,0\r\n0,0,0,0\r\n```\r\nAnd then let the encoder decide whether to use a delta frame (P-frame), or just a plain representation of the board (I-frame) for the \"actual\" first frame, applying the same logic that's used for all other frames.\r\n\r\nSince the board is encoded in a simple (though somewhat inefficient) manner - with 1 and 0 characters, it would take, in this example, 16 UTF-8 bytes to represent the whole board.\r\nIn the case there are less than 8 (or `n/2`, where `n` is the total number of pixels.) \"1\" pixels in the board, for example:\r\n\r\n```\r\n0,0,1,0\r\n0,1,0,0\r\n0,0,0,0\r\n1,0,0,1\r\n```\r\n\r\nIt would be more efficient to represent the board as the delta from the \"blank\" one i.e.:\r\n```\r\n[1,3] [2,2] [4,1] [4,4] (8 bytes + terminator, using top-left coordinates)\r\n```\r\nInstead of:\r\n```\r\n0,0,1,0,0,1,0,0,0,0,0,0,1,0,0,1 (16 bytes + terminator)\r\n```\r\n\r\nDeltas may turn out to be less compressible than plain 0,1 character sequences though, so the threshold could be adjusted to a value less than `n/2`. Also, if the board is larger than 127 in width or height, the coordinates need to be individually weighted for the number of bytes they take in their UTF-8 representation (a multiplier of at least 2 for value > 127 and 3 for value > 2047)."}}