LZ(W) compression

[basics] 2 questions

Page 1 of 1

0 Replies - 2181 Views - Last Post: 02 May 2005 - 05:40 AM Rate Topic: -----

#1 the_cpp_boi   User is offline

  • New D.I.C Head

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

LZ(W) compression

Posted 02 May 2005 - 05:40 AM

Reference reading directly related to this post:

Hi all.

I've just started learning the ways of compression. I decided to start with the LZ algorithm. The resource I use is:
I understand the fundamentals of parsing the incoming text. Let's call the container that holds the unique sub-strings: a
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?

Thank your for your reading,

Is This A Good Question/Topic? 0
  • +

Page 1 of 1