# LZ(W) compression

Page 1 of 1

## 0 Replies - 2066 Views - Last Post: 02 May 2005 - 05:40 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=11021&amp;s=6d6ce32efbbe239fca3098b87975d739&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 the_cpp_boi

Reputation: 0
• Posts: 1
• Joined: 02-May 05

# LZ(W) compression

Posted 02 May 2005 - 05:40 AM

Reference reading directly related to this post:
http://www.math.prin...rror/index.html
http://www.math.prin...Compressor.html

Hi all.

I've just started learning the ways of compression. I decided to start with the LZ algorithm. The resource I use is:
http://www.math.prin...rror/index.html
I understand the fundamentals of parsing the incoming text. Let's call the container that holds the unique sub-strings: a
dictionary.
On the page where one can play online with a fully implemented LZ compressor, they use a number of ASCII characters to indicate
the index of the unique sub-substring in the "dictionary". Index 1 is the ASCII character 33 ('!' = index 1, so 'SPACE' = not
encountered before). ASCII-char 127 (DEL) is the 95th index. To me, a few steps in this online tutorial went too fast, missing a
few steps.

Let's play with the online compression tool, I'll ask my questions along the way. I am accurate, so observe the spaces as well

I enter: "a"
output: "aa"
QUESTION: why the double a? I see only one letter, not encountered before, etcetera. So I expect to see a space then "a" => " a"

I enter: "aa"
output: "aa"
QUESTION: Why this output? To me the second "a" is a string in the dictionary on index 1. Since index 1 is ASCII-char 33, the
output to me should be: " a!".

I enter: "aaa"
output: " a!a!a"
QUESTION: this is how I think:
1) The dicitonary looks like this:
```index    substring    in_terms_of_index
"!"        "a"                NONE
""""        "aa"            !a
```

So the output must be (according to me): " a!a"

I enter: "aaaa"
output: " a!a a"
QUESTION: To my logic the output should be: " a!a!" . I'll show you my dictionary:
```index    substring    in_terms_of_index
"!"        "a"                NONE
""""        "aa"               !a
```

So the output must be (according to me): SPACE for 1st "a" + "!a" for double "aa" + "!" for first index "a" = " a!a!"

And so forth.

I have another important question:
Suppose my dictionary size exceeds 95? How would I code something with index 96 or higher? What is the trick?