LZ78?
Part of Compression Methods
?
<index, char to add>
LZAP
LZMW
LZW
Fill indexes 0 to 255 with normal byte values
<index>
My Hash
? is a 32-bit integer array/hash
Encoding
RN
RN
?'s Implementation w/Comments...
- coded on the wiki.... be gentle :)
<code>
//
// wxLZWEncode() Implementation by Ryan Norton (RN?)
// Prerequisites -
// 1. My Hash? 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& My Hash
?, 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 = My Hash?[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 My Hash? with parent pCurrentNode and cValue i
it = My Hash?.find(wxLZWStruct(pCurrentNode, i)); //wK
if(it == My Hash?.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
My Hash?.insert(wxLZWStruct(pCurrentNode, i, My Hash?.size()));
//w = K
pCurrentNode = &My Hash?[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>
Decoding
//(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
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
Y
LZ88 variant used by Yabba Whap
?...
Resources