Developers Notebook-LZ78

From WxWiki

Jump to: navigation, search

Contents

[edit] LZ78

Part of Developers_Notebook-LZ78-Compression Methods

<index, char to add>

[edit] LZAP

[edit] LZMW

[edit] LZW

Fill indexes 0 to 255 with normal byte values

<index>

MyHash is a 32-bit integer array/hash

[edit] Encoding

RN's Implementation w/Comments...

  • coded on the wiki.... be gentle :)

<code> 

 //
 //   wxLZWEncode() Implementation by Ryan Norton (RN)
 //   Prerequisites - 
 //   1. MyHash is a wxLZWStruct wxHashMap
 //   2. pInputStream points to a wxInputStream and pOutputStream points to a wxOutputStream
 //
 struct wxLZWStruct
 {
     wxLZWStruct() : pParent(NULL) {}
     wxLZWStruct(wxLZWStruct*& pParent, const wxUbyte& cValue) : pParent(pParent), cValue(cValue) {}
     wxLZWStruct(wxLZWStruct*& pParent, const wxUbyte& cValue, wxUint16& wIndex) : pParent(pParent), cValue(cValue), wIndex(wIndex) {}
 
     wxLZWStruct* pParent;
     wxUbyte cValue; 
     wxUint16 wIndex;
     inline int operator < (const wxLZWStruct& i) {return pParentNode < i.pParentNode || cValue < i.cValue;}
 };
 
 void wxLZWEncode(wxLZWHash& MyHash, wxInputStream*& pInputStream, wxOutputStream*& pOutputStream)
 {
 //
 //Step 1.  Fill 0-255 values with normal values
 //  
 wxUbyte i; //i is a general purpose variable holder - is a loop value and the input byte 
 for(i = 0;i != 255;++i)
 {
      wxLZWStruct& ref = MyHash[i];
      ref.nIndex = ref.cValue = i;
 }
 
 //
 //Step 2.  Read in an initial character
 //
 pInputStream->Read(&i, 1);
 wxLZWStruct *pCurrentNode; 
 MyHash::iterator it;
 
 //
 //Step 3.  Loop
 //
 //      Algorithm (From comp.compression FAQ) -
 //set w = NIL
 //loop
 //   read a character K
 //   if wK exists in dictionary
 //        w = wK
 //   else
 //        output the code for w
 //        add wK to the string table
 //        w = K
 //endloop
 //
 
 //while we haven't reached the end...
 while(!(pInputStream->Eof()))
 {
    //read in a character
    pInputStream->Read(&i, 1);
   
    //attempt to find a node of MyHash with parent pCurrentNode and cValue i
    it = MyHash.find(wxLZWStruct(pCurrentNode, i)); //wK
 
    if(it == MyHash.end() ||   //if at the end it wasn't found...
       pCurrentNode->pParent == NULL)  //if the parent of the last one was null, then there's no more :)
    {
         pOutputStream->Write(&pCurrentNode->wIndex, 2);  // output the code for w
         
         //add wK to the string table
         MyHash.insert(wxLZWStruct(pCurrentNode, i, MyHash.size())); 
         //w = K
         pCurrentNode = &MyHash[wxLZWStruct(NULL, i)];        
    }
    else //if it exists in dictionary...
    {
         pCurrentNode = *it; //point it to the proper node
    }
 }
 //If the last one was in the dictionary we need to output 
 //it's code
 if (pCurrentNode == *it)
 {
         pOutputStream->Write(&pCurrentNode->wIndex, 2);  // output the code for w
 }
 //WHEW!
 }

</code>


[edit] Decoding

<pre> //(From Y Coding) //0 - Map 0-255. I = "". p = readcode() //1 - I.append(p) //2 - c = Dictionary.Locate( prevcode = readcode() )[0]. //c = first char of corresponding string in the dictionary to readcode() //3 - Dictionary.Add(pc) //4 - p = Dictionary.Locate( prevcode ) //5 - Reapeat from step 1 until 2 fails Patented in Europe and Japan, but not in the USA </pre>

[edit] LZC 

Version of LZW That begins with a specified numer for the "code size"
      • I.E. number of bytes in the hash table. 255 - table clear

[edit] Y

LZ88 variant used by YabbaWhap...

[edit] Resources

Retrieved from "http://wiki.wxwindows.org/Developers_Notebook-LZ78"
Personal tools