Generally, data compression is the act of removing redundancy (a lack of distinction, also know as repetition or order), and as de Bruijn sequences are maximally disordered, it must be the task of data compressors to approximate de Bruijn sequences in their output. With sufficient understanding of such translation processes, we might the decode existing de Bruijn sequences, and observe the hidden order of their message, as interpreted by decompression software. The same goes for cryptographic processes.
Kevin:
I asked not if a de Bruijn sequence is compressible by LZW but rather if a de Bruijn sequence can be decompressed by LZW. My suggestion is that some de Bruijn sequences are indeed decompressible and that different decompression algorithms will yield different decompression results for such decompressible de Bruijn sequences.
LZW ingests a stream of data and produces a data structure consisting of a token dictionary and coefficients used to reconstruct the original ingested data from the series of dictionary tokens during decompression. In short, the compressed data is highly structured.
These data structure(s) are serialized into a LZW stream and then handed to a persistence layer ( e.g. a file ) or ingested by some other application for further processing, like an archiving utility which handles multiple files, preserving file metadata, folder structure and so on.
So you cannot, for example, take any old data stream and decompress it, as the data structure needs to be consistent. For example, suppose you have a set of 200 dictionary entries, these will be represented by ( for simplicities sake ) an 8-bit token. So possible values are 0-255 with only 0-199 actually used. So while the coefficients could be anything, like "This is a sequence of 792 'BOB' tokens" you are not assured some arbitrary token number is actually in the dictionary. So for your data where the token number byte happens to be 201 thru 255, the lookup fails and the LZW stream is inconsistent.
So no, generally you cannot take some arbitrary stream of gibberish ( with any degree of randomness ) and have LZW decompress it into a more enormous pile of more gibberish.. ( Like this reply for example? )
With that said, there are implementations of LZW which basically ignore all of the checking to allow for recovery of damaged archives - it will do a "best efforts" decompression which will basically trust all the data presented is consistent, and when lookup failures occur or out of bounds errors occur, it will generate NULL data. This is, technically, NOT LZW decompression.
-- Bob
Robert: It certainly must be the case that the function of data compression is to remove redundancy. By such removal, the yield must be an increase in disorder. It is clear that de Bruijn sequences are maximally disordered. Hence, it must be the case that either LZW does less than an optimal job of removing redundancy, or LZW can decompress de Bruijn sequences. If LZW is, in fact, less than optimal, then that demonstrates an opportunity to improve compression algorithms.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms