Haja ya kuchunguza algorithm ya compression imepiga tena. Baada ya kucheza na LZSS (LZ77) nilidhani LZW (LZ78) ilikuwa kitu ambacho mwishowe nilipaswa kupata kusoma. Nimecheza na vitu vingine kadhaa tangu kuwa na wazo hilo, lakini hatimaye ilishikilia, na ikawa kitu ambacho kilitumia "wakati wa bure"
Kama ilivyo kwa utekelezaji wangu mwingine wa compression, kusudi langu ni kuchapisha rahisi kufuata utekelezaji wa ANSI C ya Lempel-Ziv-Welch (LZW) encoding/decoding algorithm. Mtu yeyote anayejua ANSI C na LZW au LZ78 anapaswa kuwa na uwezo wa kufuata na kujifunza kutoka kwa utekelezaji wangu. Nina hakika kuwa kuna nafasi ya uboreshaji wa uwiano wa compression, kasi, na utumiaji wa kumbukumbu, lakini mradi huu ni juu ya kujifunza na kushiriki, sio ukamilifu. Bonyeza hapa kwa kiunga cha chanzo changu cha LZW. Ukurasa huu wote unajadili LZW na utekelezaji wangu. Kama ni mtangulizi wa LZSS (LZ77), algorithm ya Lempel-Ziv-Welch hutumia kamusi iliyotengenezwa kwa nguvu na inashikilia kamba kwa kumbukumbu ya kamusi. Imekusudiwa kuwa kumbukumbu ya kamusi inapaswa kuwa fupi kuliko kamba inayochukua. Kama utaona, LZW inafikia lengo lake kwa kamba zote kubwa kuliko 1. Algorithm ya LZSS hutumia kamusi ya windows. Kila kiingilio katika kamusi ni tabia. Maneno ya nambari ya LZSS yanajumuisha kukabiliana na kamusi na idadi ya wahusika kufuatia kukabiliana na kujumuisha kwenye kamba iliyowekwa. Tofauti na LZSS, viingilio katika kamusi ya LZW ni kamba, na kila neno la nambari ya LZW ni kumbukumbu ya kamba kwenye kamusi. Sawa, kwa hivyo kamusi inatoka wapi, na kwa nini siwezi kupata kiingilio cha faili yangu yote ndani yake? Kamusi ya LZW sio kamusi ya nje ambayo inaorodhesha kamba zote zinazojulikana za alama. Badala yake, kamusi imeanzishwa na kiingilio kwa kila byte inayowezekana. Kamba zingine zinaongezwa kwani zinajengwa kutoka kwa mkondo wa pembejeo. Neno la nambari ya kamba ni thamani inayofuata wakati huo huongezwa kwenye kamusi. Kamba ya "encoded" hutumiwa kuongeza kamba mpya kwenye kamusi. Kamba iliyowekwa ndani imejengwa kutoka kwa mkondo wa pembejeo. Mtiririko wa pembejeo unasomwa 1 byte kwa wakati mmoja. Ikiwa kamba iliyoundwa kwa kushinikiza byte mpya kwa kamba iliyowekwa ndani iko kwenye kamusi, byte mpya imeongezwa hadi mwisho wa kamba iliyosimbwa. Vinginevyo kiingilio cha kamusi hufanywa kwa kamba mpya na neno la nambari ya kamba iliyo na alama imeandikwa kwa mkondo wa pato. Halafu byte ambayo ilisomwa tu inakuwa kamba iliyosimbwa. Hatua ya 1. Anzisha Kamusi ya kuwa na kiingilio kimoja kwa kila byte. Anzisha kamba iliyosimbwa na byte ya kwanza ya mkondo wa pembejeo. Hatua ya 2. Soma byte inayofuata kutoka kwa mkondo wa pembejeo. Hatua ya 3. Ikiwa Byte ni EOF goto Hatua ya 6.
Concatenate byte kwa kamba iliyosimbwa. Ongeza uchungu mpya kwenye kamusi. Andika nambari ya kamba iliyowekwa kwenye mkondo wa pato. Weka kamba iliyowekwa sawa na byte mpya. Hatua ya 6. Andika nambari ya kamba iliyosimbwa na exit. Katika mfano hapo juu, kamba ya tabia 17 inawakilishwa na maneno 13 ya nambari. Shindano lolote halisi ambalo lingetokea litatokana na saizi ya maneno ya msimbo. Katika mfano huu maneno maneno yanaweza kuwa mafupi kama biti 9. Kawaida maneno ya kanuni ni bits 12 hadi 16. Kwa kweli mkondo wa kawaida wa pembejeo pia ni mrefu kuliko herufi 17. Haipaswi kuwa mshangao mkubwa kuwa data ya LZW imeorodheshwa kabisa tofauti ya jinsi ilivyosimbwa. Kamusi imeanzishwa ili iwe na kiingilio kwa kila ka. Badala ya kudumisha kamba iliyosimbwa, algorithm ya decoding inashikilia neno la nambari ya mwisho na mhusika wa kwanza kwenye kamba ambayo hufunga. Maneno mapya ya nambari yanasomwa kutoka kwa mkondo wa pembejeo kwa wakati mmoja na kamba iliyowekwa na nambari mpya ni pato. Wakati wa mchakato wa usimbuaji, nambari kabla ya nambari ya sasa imeandikwa kwa sababu kubatilisha tabia ya kwanza ya nambari ya sasa na kamba iliyowekwa na nambari ya awali ilizalisha nambari ambayo haikuwa katika kamusi. Wakati hiyo ilifanyika kamba iliyoundwa na concatenation iliongezwa kwenye kamusi. Kamba hiyo hiyo inahitaji kuongezwa kwenye kamusi wakati wa kuorodhesha. Hatua ya 1. Anzisha Kamusi ya kuwa na kiingilio kimoja kwa kila byte. Hatua ya 2. Soma neno la kwanza la nambari kutoka kwa mkondo wa pembejeo na uandike byte encode. Hatua ya 3. Soma neno linalofuata kutoka kwa mkondo wa pembejeo. Hatua ya 4. Ikiwa neno la nambari ni exit ya EOF. Hatua ya 5. Andika kamba iliyowekwa na neno la nambari. Hatua ya 6. Concatenate mhusika wa kwanza katika neno la nambari mpya kwa kamba inayozalishwa na neno la msimbo uliopita na ongeza kamba inayosababishwa kwenye kamusi. Hatua ya 7. Nenda kwa hatua ya 3. Kamba ya Decode inalingana na kamba ya asili iliyowekwa, kwa hivyo lazima nimefanya kitu sawa. Moja ya mambo ninayopenda kuhusu LZW ni kwamba decoder haiitaji habari yoyote ya ziada kutoka kwa encoder. Hakuna haja ya kujumuisha habari ya ziada inayohitajika na algorithms ya takwimu kama nambari ya Huffman na nambari ya hesabu. Kwa hivyo uwiano wa compression haupunguzi kamwe na gharama ya ziada ya data. Yeyote aliyesema kwamba kuna ubaguzi kwa kila sheria lazima alisoma LZW. Inabadilika kuwa ubaguzi unaweza kutokea. Wakati wa kuamua mito fulani ya pembejeo inaweza kuona neno la nambari ambalo ni kubwa kuliko kitu chochote ambacho kina katika kamusi yake. Kwa bahati nzuri kwangu wengine wamefikiria wakati ubaguzi unatokea na jinsi ya kukabiliana nayo. Isipokuwa hufanyika ikiwa kam