Comp Sci Troubleshooting Index Error 7 in Decoding

[shivajikobardan]

Homework Statement

LZW decoding-:There is no entry for index 7 in the dictionary while decoding, how do I fix this issue?

Relevant Equations

N/A

Source of my knowledge-:

Encoding-:


Decoding-:


Other references-:


Question-: There is no entry for index 7 in the dictionary while decoding, how do I fix this issue?

 

[rcgldr]

The videos don't do a good job of explaining a LZW dictionary. Link to Wiki article:

https://en.wikipedia.org/wiki/Lempel–Ziv–Welch

Typically elements are not stored in the dictionary. For the OP's question the elements have values 1 (A) and 2(B). To keep things simple assume that elements and indexes are bytes with range 1 to 255.

The actual dictionary starts at index 3, since elements are usually not stored in the dictionary. Each dictionary entry consists of a prior index and an element, unless the prior index is less than 3, in which case its the first byte of a string. Each prior index represents a string. Note that decoding a dictionary entry will retrieve bytes in reverse order.

When the decoder encounters a code not yet in the dictionary, the last character for the new code equals the first character from the previous output. The decoder needs to save the first character of each output to implement this.

                 dictonary
rcvd decd     indx  code char string

   2    B
   1    A        3     2    1   BA
   1    A        4     1    1   AA
   3   BA        5     1    2   AB
   2    B        6     3    2  BAB
   7   BB        7     2    2   BB    new:  prior code = 2, prior first character = B = 2
   4   AA        8     7    1  BBA
   7   BB        9     4    2  AAB
   2    B       10     7    2  BBB

For a better example, string to be encoded: ABABABABABAB

    input   search  dictionary    output
    A        -
    B       A:B     d[3]=A:B       A
    A       B:A     d[4]=B:A       B
    B       A:B       3
    A       3:A     d[5]=3:A       3
    B       A:B       3
    A       3:A       5
    B       5:B     d[6]=5:B       5
    A       B:A       4
    B       4:B     d[7]=4:B       4
    A       B:A       4
    B       4:B       7
   eof                             7

Decoding:

input   dictionary    output
   A                  A
   B   d[3]=A:B=AB    B
   3   d[4]=B:A=BA    AB
   5   d[5]=3:A=ABA   ABA    last output first character = A
   4   d[6]=5:B=ABAB  BA
   7   d[7]=4:B=BAB   BAB    last output first character = B
 eof

 

[shivajikobardan]

The videos don't do a good job of explaining a LZW dictionary. Link to Wiki article:

https://en.wikipedia.org/wiki/Lempel–Ziv–Welch

Typically elements are not stored in the dictionary. For the OP's question the elements have values 1 (A) and 2(B). To keep things simple assume that elements and indexes are bytes with range 1 to 255.

The actual dictionary starts at index 3, since elements are usually not stored in the dictionary. Each dictionary entry consists of a prior index and an element, unless the prior index is less than 3, in which case its the first byte of a string. Each prior index represents a string. Note that decoding a dictionary entry will retrieve bytes in reverse order.

When the decoder encounters a code not yet in the dictionary, the last character for the new code equals the first character from the previous output. The decoder needs to save the first character of each output to implement this.

                 dictonary
rcvd decd     indx  code char string

   2    B
   1    A        3     2    1   BA
   1    A        4     1    1   AA
   3   BA        5     1    2   AB
   2    B        6     3    2  BAB
   7   BB        7     2    2   BB    new:  prior code = 2, prior first character = B = 2
   4   AA        8     7    1  BBA
   7   BB        9     4    2  AAB
   2    B       10     7    2  BBB

For a better example, string to be encoded: ABABABABABAB

    input   search  dictionary    output
    A        -
    B       A:B     d[3]=A:B       A
    A       B:A     d[4]=B:A       B
    B       A:B       3
    A       3:A     d[5]=3:A       3
    B       A:B       3
    A       3:A       5
    B       5:B     d[6]=5:B       5
    A       B:A       4
    B       4:B     d[7]=4:B       4
    A       B:A       4
    B       4:B       7
   eof                             7

Decoding:

input   dictionary    output
   A                  A
   B   d[3]=A:B=AB    B
   3   d[4]=B:A=BA    AB
   5   d[5]=3:A=ABA   ABA    last output first character = A
   4   d[6]=5:B=ABAB  BA
   7   d[7]=4:B=BAB   BAB    last output first character = B
 eof

thank you for writing this long answer for me but i could not get most things..

 

[rcgldr]

thank you for writing this long answer for me but i could not get most things..

Are you trying to create a program or just writing out the steps as you posted in your question?

Were you able to understand my encoding example?

Assuming a character is a byte, then each dictionary entry = {prior index : byte}.

Using my example, consider decoding d[6] onto a stack:

    d[6] = {5:B}      push B
    d[5] = {3:A}      push A
    d[3] = {A:B}      push B
    d[A] = {A}        push A
                      string = stack = ABAB

For the decoder. two arrays are used, one for dictionary entries, one for the first bytes of strings for those dictionary entries, a stack to store the bytes of a string in reverse order, a last_first variable that holds one byte, and J, an index into the dictionary, initialized to 3. The dictionary is initialized to the alphabet: d[A] = {A:}, d = {B:}. Instead of actually using dictionary entries for the alphabet, the code can just use the index if index is less than 3.

The first input is just a byte:

    last_first = input byte
    output input byte

After the first input, the dictionary is built on the fly and decoded to generate strings to output:

    decode dictionary[current input index] onto stack
    dictionary[J] = {prior input index : first_byte[current input index]}
    last_first = first_byte[J] = first byte of stack
    output the stack
    J++

If input == J, it's a special case:

    push last_first
    decode dictionary[prior input index] onto stack
    d[J] = {prior input index : last_first}
    last_first = first_byte[J] = first byte of stack
    output the stack
    J++