Original Post
Ok, so was pretty bored today after just stumbling a bit on my rendering engine and had a thought, it hurt :). Pure Text Compression ===================== And what a powerful way of doing it would be... So, i was thinking along the lines of a binary tree to compress a sentence. Supposing u have a sentence: Dave went to the market and bought a sheep. Now supposing each word became the bottom node on a single binary tree, so: / \ / \ / \ / \ / Dave went to the market and bought a sheep. (nil) If the compressor had a list of the most common words, like the top 1000 and also a list of say the top 100 word-pairs, in this case like 'to the', the word or pair of words could be replaced by a single or pair of ascii chars (depending on the index withing the list) each would have a possible value of 0-255. There fore this allows alot of scope for the list lengths since so many different ones can be represented by either 1 or 2 chars. Ok so compression, so far i have talked a bit about a simple conversion from the actual word to some sort of integer representing its position within a fixed list. If the word does not exist within the list, it could simply be left as it is and the rest of the file converted around it/them. Right so to further compress this file, once all the individual words are converted to the integers, you could look for the pairs of words as i mentioned earlier. If you come accross a pair of words that exist in the paired-word list you could simply move back up the binary tree position and replace the above node with the integer that represents this word pair. So assuming 'to the' is in the paired-words list you might have: (nil) 124 (nil) (nil) (nil) / \ / \ / \ / \ / Dave went to the market and bought a sheep. (nil) Ok so as u can see the 'to the' pairing might well be item 124 in the paired-words list so it would be place in the tree as so. I would then expect that the 'to' and 'the' nodes would be deleted and ofcourse by this stage we would actually be working entirely with numbers for efficiency so the tree might now look something like... (nil) 124 (nil) (nil) (nil) / \ / \ / \ / \ / \ 23 54 3 1 12 24 67 45 55 (nil) Now in order to store this representation you would have to keep track of what 'level' or generation within the binary tree the number is being stored on. Obviously otherwise each number could be on any level and you wouldn't know how to convert the number back to the words because you wouldn't know how many stages of compression it went through. Ok so thats basically it and i am aware it most likely has alot of flaws but it was only a thought. I'm sure some useful compressor could be derived from this theory and i already have an example on the way, but its a fair way off. I have no doubt that some other guy has thought of this. Any comments? EDIT: dammit the tree depictions are buggered, oh well, im hoping yu can still see what i mean although i will try and redraw them. ace
