1跳表和散列課件（SkipListandHashing）2本章內(nèi)容1.1

字典

dictionaries1.2線性表描述

LinearList1.3跳表描述

SkipList1.4散列表描述

Hashtable1.5應(yīng)用

Applications為什么學這章？若一維排序數(shù)組，我們可以用折半檢索在O(logn)時間內(nèi)找到表中的一個元素。本章將研究如何構(gòu)造排序的鏈表、如何維護（進行插入或刪除操作后），以及能否也能在O(logn)時間內(nèi)進行檢索。41.1字典字典（dictionary）是一些元素的集合。每個元素有一個稱作key的域，不同元素的key各不相同。有關(guān)字典的操作有：插入（Insert）具有給定關(guān)鍵字值的元素。在字典中尋找/搜索（Search）具有給定關(guān)鍵字值的元素。刪除（Delete）具有給定關(guān)鍵字值的元素例，班級的學生注冊表，key=學號有重復(fù)元素的字典AdictionarywithduplicatesMaybetherearemorethanoneelementshaveasamekey例，班級的學生考試報表，key=成績5AbstractDataType抽象數(shù)據(jù)類型

Dictionary{實例一組帶有關(guān)鍵詞（<=，>=關(guān)系）的元素集合操作empty()truewhenthedictionaryisemptysize()returnthenumberofelementsfind(k):搜索關(guān)鍵字為k的數(shù)對Insert(p):向字典中插入數(shù)對perase(k):刪除關(guān)鍵字為k的數(shù)對}6Template<classk,classE>Classdictionary(){Public:virtual~dictionary(){}virtualboolempty()const=0;virtualintsize()const=0;virtualpair<constK,E>*find(constK&)const=0;virtualvoiderase(constk&)=0;virtualvoidinsert(constpair<constK,E>&)=0;}71.2線性表描述有序線性表:L=(e1,e2,e3,…,en),關(guān)鍵字從左到右依次增大在計算機存儲器中的數(shù)據(jù)描述公式化描述鏈表描述8鏈表描述的有序線性表（字典）采用鏈表描述的有序線性表——有序鏈表類

SortedChain9類

SortedChaintemplate<classK,classE>structpairNode{typedefpair<constK,E>pairType;pairTypeelement;pairNode<K,E>*next;pairNode(constpairType&thePair):element(thePair){}pairNode(constpairType&thePair,pairNode<K,E>*theNext):element(thePair){next=theNext;}};firste1e20en…eiei-1…ei+110ClassSortedChaintemplate<classK,classE>classsortedChain:publicdictionary<K,E>{public:sortedChain(){firstNode=NULL;dSize=0;}~sortedChain();boolempty()const{returndSize==0;}intsize()const{returndSize;}pair<constK,E>*find(constK&)const;voiderase(constK&);voidinsert(constpair<constK,E>&);voidoutput(ostream&out)const;protected:pairNode<K,E>*firstNode;//pointertofirstnodeinchainintdSize;//numberofelementsindictionary};11操作‘find’template<classE,classK>pair<constK,E>*sortedChain<E,K>::find(constK&theKey)const{//搜索與k匹配的元素，

//如果沒有匹配的元素，則返回NULLpairNode<K,E>*currentNode=firstNode;while(currentNode!=NULL&¤tNode->element.first<theKey)currentNode=currentNode->next;if(currentNode!=NULL&¤t->element.first==theKey)return¤t->element;//與theKey相匹配

returnNULL;

//不存在相匹配的元素}12操作‘Insert’firste1e20en…eiei-1…ei+1p：從表頭開始第一個大于x的節(jié)點tpfirste1e20en…eiei-1…ei+1ptp=0eqeq13template<classE,classK>voidsortedChain<E,K>::insert(constpair<K,E>&thePair){//如果表中不存在關(guān)鍵值與e相同的元素，則插入e,否則替換pairNode<E,K>*p=firstNode,*tp=NULL;//p指向節(jié)點的前驅(qū)while(p!=NULL&&p->element.first<thePair.first){tp=p,p=p->next;}if(p!=NULL&&p->element.first==thePair){p->element.second=thePair.second;//替換舊值return；}

//若沒有出現(xiàn)重復(fù)關(guān)鍵值,則產(chǎn)生一個關(guān)鍵值為e的新節(jié)點pairNode<E,K>*newNode=newpairNode<E,K>(thePair,p);if(tp==NULL)firstNode=newNode;//新節(jié)點插入表頭elsetp->next=newNode;dSize++;return;}14操作

‘erasefirste1e20en…eiei-1…ei+1ptpfirste1e20en…eiei-1…ei+1ptp=0tp->link=p->linkfirst=p->link15template<classE,classK>voidsortedChain<E,K>::erase(constK&theKey){//刪除與theKey相匹配的元素，pairNode<K,E>*p=firstNode,tp=NULL；//p指向匹配的節(jié)點，tp指向p前面的節(jié)點。

while(p!=NULL&&p->element.first<theKey){tp=p,p=p->next;}//搜索與k相匹配的元素//驗證是否與k匹配if(p!=NULL)&&p->element.first==theKey){//找到一個相匹配的元素if（tp==NULL）firstNode=p->next;elsetp->next=p->next;是鏈首節(jié)點deletep;dSize--;

}

作業(yè)p2395171.4SkipList1.4.1理想情況1.4.2插入和刪除1.4.3級的分配1.4.4類SkipNode1.4.5類SkipList1.4.6復(fù)雜性187.3.1

idealcase20243040607580Search:

最壞情況下的比較次數(shù)f(n)=nSearch:

f(n)=n/2+1ifwekeepapointerinthemiddle.2024304060758020243040607580210191.3理想狀態(tài)的節(jié)點分布0級鏈上元素數(shù):n

1級鏈上元素數(shù):?n

2級鏈上元素數(shù)：?n

……i

級鏈上元素數(shù):n/2i

我們稱元素a是第i層元素，若它也是0~i-1層的元素，但a不是第i+1層元素。E.g.40是層2元素,而24和75是層1元素。20跳表(skiplist):在跳表結(jié)構(gòu)中，每個節(jié)點有一維數(shù)組表示層次的鏈。0級鏈是包含所有元素的有序鏈表，1級鏈是0級鏈的一個子集。i級鏈所包含的元素是i-1級鏈所有元素的子集.

插入和刪除和sortedChain一樣，插入和刪除要保持表仍然是排序的，同時要給鏈表組賦值，而新增節(jié)點的層次要動態(tài)確定。227.3.2插入和刪除i

級鏈上元素數(shù):n/2ii-1級元素屬于i級鏈的概率是：1/2一個元素屬于i級鏈概率是：1/2i=(1/2)i

鏈的級數(shù)：

log2n

+12102024304060758023insertanelementwithvalue77元素插入1)發(fā)現(xiàn)插入位置2)對新元素賦予層數(shù)值i;3)對新元素和其他在層數(shù)0~i的節(jié)點指針可能要更改。元素刪除1)從最高層逐次向下搜索該元素

i,2)刪除該元素并對原來想鄰接的節(jié)點的指針進行修改。新增節(jié)點的level確定我們假定每個節(jié)點在level0的概率為1，其他是獨立按概率p增加的，1層p2層p*p…d層pd

如何實現(xiàn)？用系統(tǒng)的隨機函數(shù)rand(),每次產(chǎn)生隨機數(shù)在0~RAND_MAX.267.3.3levelassignmentThentheprobabilitythatthenextrandomnumberisCutOff=p*RAND_MAXisp。Ifnextrandomnumberis

Cutoff,thenthenewelementshouldbeinlevel1,andcheckthenextrandomnumberGenerally,thefinallevelassignedtothenewelementis

intlev=0while(rand()<=CutOff)lev++;0cutoffRAND_MAX=p*RAND_MAX

277.3.3

級的分配缺點1：可能為某些元素分配特別大的級，從而導(dǎo)致一些元素的級遠遠超過log1/pN（N為字典中預(yù)期的最大數(shù)目,因此，在有N個元素的跳表中，級的最大值

MaxLevel=「log1/pN

-1，以此值作為上限。缺點2：可能存在下面的情況，如在插入一個新元素前有三條鏈，而在插入之后就有了10條鏈。這時，新插入元素的為9級，……。我們可以把新元素的級調(diào)整為3。即把新元素的級調(diào)整為最大級數(shù)+1。結(jié)構(gòu)SkipNode頭節(jié)點需要最大層數(shù)的指針;尾節(jié)點不需要指針;每個節(jié)點包含element部分、指針部分（比它level多1）29

7.3.4類SkipNodetemplate<classE,classK>structSkipNode

{{typedefpair<constK,E>pairType;pairTypeelement;skipNode<K,E>**next;//一維指針數(shù)組skipNode(constpairType&thePair,intsize):element(thePair){next=newskipNode<K,E>*[size];}};0

12…………size-1next2024304060758030#ifndefskipList_#defineskipList_#include<iostream>#include<math.h>#include<sstream>#include<string>#include"dictionary.h"#include"skipNode.h"#include"myExceptions.h"usingnamespacestd;template<classK,classE>classskipList:publicdictionary<K,E>{public:skipList(K,intmaxPairs=10000,floatprob=0.5);~skipList();31boolempty()const{returndSize==0;}intsize()const{returndSize;}pair<constK,E>*find(constK&)const;voiderase(constK&);voidinsert(constpair<constK,E>&);voidoutput(ostream&out)const;protected:floatcutOff;//usedtodecidelevelnumberintlevel()const;//generatearandomlevelnumberintlevels;//maxcurrentnonemptychainintdSize;//numberofpairsindictionaryintmaxLevel;//maxpermissiblechainlevelKtailKey;//alargekeyskipNode<K,E>*search(constK&)const;//searchsavinglastnodesseenskipNode<K,E>*headerNode;//headernodepointerskipNode<K,E>*tailNode;//tailnodepointerskipNode<K,E>**last;//last[i]=lastnodeseenonleveli};32template<classK,classE>skipList<K,E>::skipList(KlargeKey,intmaxPairs,floatprob){//ConstructorforskiplistswithkeyssmallerthanlargeKeyand//sizeatmostmaxPairs.0<prob<1.cutOff=prob*RAND_MAX;maxLevel=(int)ceil(logf((float)maxPairs)/logf(1/prob))-1;levels=0;//initialnumberoflevelsdSize=0;tailKey=largeKey;//createheader&tailnodesandlastarraypair<K,E>tailPair;//申請變量tailPair.first=tailKey;//賦值headerNode=newskipNode<K,E>(tailPair,maxLevel+1);tailNode=newskipNode<K,E>(tailPair,0);//建立尾結(jié)點last=newskipNode<K,E>*[maxLevel+1];//用于記錄指針的數(shù)組//headerpointstotailatalllevelsaslistsareemptyfor(inti=0;i<=maxLevel;i++)headerNode->next[i]=tailNode;//建立首尾兩個節(jié)點的鏈接}33template<classK,classE>skipList<K,E>::~skipList(){//Deleteallnodesandarraylast.skipNode<K,E>*nextNode;//deleteallnodesbyfollowinglevel0chainwhile(headerNode!=tailNode){nextNode=headerNode->next[0];//沿著0層刪除deleteheaderNode;headerNode=nextNode;}deletetailNode;delete[]last;}34template<classK,classE>pair<constK,E>*skipList<K,E>::find(constK&theKey)const{//fa//ReturnNULLifnomatchingpair.if(theKey>=tailKey)returnNULL;//超出合理關(guān)鍵詞的取值范圍了//positionbeforeNodejustbeforepossiblenodewiththeKeyskipNode<K,E>*beforeNode=headerNode;//要找的節(jié)點前驅(qū)節(jié)點for(inti=levels;i>=0;i--)//從上到下逐層尋找//followlevelipointerswhile(beforeNode->next[i]->element.first<theKey)beforeNode=beforeNode->next[i];//checkifnextnodehastheKeyif(beforeNode->next[0]->element.first==theKey)return&beforeNode->next[0]->element;returnNULL;//nomatchingpair}35template<classK,classE>intskipList<K,E>::level()const{//Returnarandomlevelnumber<=maxLevel.intlev=0;while(rand()<=cutOff)lev++;return(lev<=maxLevel)?lev:maxLevel;}36template<classK,classE>skipNode<K,E>*skipList<K,E>::search(constK&theKey)const{//Search作為一個輔助函數(shù)，找到含有theKey的節(jié)點，并且//為記錄level的數(shù)組last賦值

skipNode<K,E>*beforeNode=headerNode;for(inti=levels;i>=0;i--){while(beforeNode->next[i]->element.first<theKey)beforeNode=beforeNode->next[i];

last[i]=beforeNode;//last記錄了該插入或刪除節(jié)點每層的前驅(qū)節(jié)點}returnbeforeNode->next[0];//返回指向要找節(jié)點的指針}37template<classK,classE>voidskipList<K,E>::insert(constpair<constK,E>&thePair){//基于search的查找，插入新節(jié)點，或修改已有節(jié)點if(thePair.first>=tailKey)//keytoolarge{ostringstreams;s<<"Key="<<thePair.first<<"Mustbe<"<<tailKey;throwillegalParameterValue(s.str());}//seeifpairwiththeKeyalreadypresentskipNode<K,E>*theNode=search(thePair.first);if(theNode->element.first==thePair.first)//已經(jīng)存在只改值{//updatetheNode->element.secondtheNode->element.second=thePair.second;return;}38//增加新節(jié)點，首先計算該節(jié)點指針數(shù)組大大小，及所在層次inttheLevel=level();//levelofnewnode//fixtheLeveltobe<=levels+1if(theLevel>levels){

theLevel=++levels;last[theLevel]=headerNode;//因為新增加了一層，必須從頭開始}//getandinsertnewnodejustaftertheNode

skipNode<K,E>*newNode=newskipNode<K,E>(thePair,theLevel+1);for(inti=0;i<=theLevel;i++){//insertintolevelichainnewNode->next[i]=last[i]->next[i];last[i]->next[i]=newNode;}dSize++;return;}39emplate<classK,classE>voidskipList<K,E>::erase(constK&theKey){//Deletethepair,ifany,whosekeyequalstheKey.if(theKey>=tailKey)//toolargereturn;//seeifmatchingpairpresentskipNode<K,E>*theNode=search(theKey);if(theNode->element.first!=theKey)//notpresentreturn;//deletenodefromskiplistfor(inti=0;i<=levels&&last[i]->next[i]==theNode;i++)last[i]->next[i]=theNode->next[i];

40//updatelevelswhile(levels>0&&headerNode->next[levels]==tailNode)levels--;

deletetheNode;dSize--;}41template<classK,classE>voidskipList<K,E>::output(ostream&out)const{//Insertthedictionarypairsintothestreamout.//followlevel0chainfor(skipNode<K,E>*currentNode=headerNode->next[0];currentNode!=tailNode;currentNode=currentNode->next[0])out<<currentNode->element.first<<""<<currentNode->element.second<<"";}//overload<<template<classK,classE>ostream&operator<<(ostream&out,constskipList<K,E>&x){x.output(out);returnout;}421.3.5類SkipList20243040607580HeadTail43

操作‘Search’20243040607580HeadTailp<k44操作‘Insert’lastLevel012

20243040607580HeadTail20243040607580HeadTail77p210210457.3.6復(fù)雜性時間復(fù)雜性:最壞情況:可能只有一個MaxLevel級元素，且余下的所有元素均在0級鏈上.搜索(Search),插入(Insert),刪除(Delete):O(MaxLevel+n)平均復(fù)雜性:O(log2n)作業(yè):p2468471.5散列表hashtable1.1理想哈希1.2基于一維數(shù)組的哈希表1.3基于鏈式結(jié)構(gòu)的哈希表一般假定可以把字符串轉(zhuǎn)換為整數(shù)481.13把字符串轉(zhuǎn)換為整數(shù)intstringToLong(strings){intlength=(int)a.length;//假定3longanswer=s.at(0);answer=(answer<<8)+s.at(1)return(answer<<8)+s.at(2);}

49hash(<string>C++STLTemplate<>classhash<string>{public:size_toperator()(conststringtheKey)const{//把關(guān)鍵詞theKey轉(zhuǎn)換為非負的整數(shù)unsisgnedlonghashValue=0;intlength=(int)theKey.length();for(inti=0;i<length;i++)hashValue=5*hashValue+theKey.at(i);returnsize_t(hashValue);}}

501.4.1Idealhashing元素個數(shù)不多，可以建立一個1-1函數(shù)，把每個key映射到Hash表的一個位置。如元素e,k是其關(guān)鍵詞，我們查找時可以計算f(k),若hash表的f(k)位置不空，返回其值，否則說元素不在表中。E.g,學生的ID在951000~952000,f(k)=k-95100051Operations散列表操作:

搜索（Search）:計算出f(k)，然后看表中f(k)處是否有元素。插入（Insert）:計算出f(k)，把元素放在f(k)位置刪除（Delete）:計算出f(k)，把表中f(k)位置置為空在理想情況下,散列表操作時間復(fù)雜性：

(1)initialization:initializeanemptydictionarywithbposition,O(b)52更一般的情況元素集合要遠遠大于哈希表，函數(shù)f是多對一。關(guān)鍵詞為k1,k2,…,km,但f(k1)=f(k2)=…=f(km).53Hashingfunctions若key是正整數(shù)，f(K)=k%D

（%為求模操作符）

D:是散列表的大小(即位置數(shù))

散列表中的位置號:0~D-1每一個位置稱為桶(bucket)

f(K)存儲關(guān)鍵字為k的元素的起始桶（homebucket

）。若不是正整數(shù)，但可以通過轉(zhuǎn)換，轉(zhuǎn)為正整數(shù)，也可以用這種方法。54元素:22,33,3,72,85散列表：

ht[0:7]散列函數(shù):f(key)=key%8[0][1][2][3][4][5][6][7]723338522[0][1][2][3][4][5][6][7]例55

25放入什么地方?f(25)=125的起始桶已經(jīng)被另一個數(shù)占用

這種情況被稱為是碰撞（

collision）具有相同hash函數(shù)值的不同關(guān)鍵詞被稱為是同義詞(synonyms)25和33是同義詞

[0][1][2][3][4][5][6][7]723338522碰撞和同義詞56存儲桶中若沒有空間時就發(fā)生溢出（overflow）當每個桶只能存儲一個元素時，碰撞和溢出會同時發(fā)生.解決溢出的方法：線性開型尋址(Linearopenaddressing)鏈表散列/鏈地址散列（Chaining）[0][1][2][3][4][5][6][7]72

3338522溢出（overflow）577.4.2線性開型尋址散列當溢出發(fā)生時，將元素插入下一個可用桶中。在尋找下一個可用桶時，表被視為環(huán)形的。例散列表的大小b=11f(k)=k%b在插入

80,40,和65之后58線性開型尋址散列在插入

58和24之后

f(58)=3(碰撞);f(24)=2在插入

35之后f(35)=2(碰撞)59線性開型尋址散列在插入

98之后f(98)=10(碰撞)98(d)60線性開型尋址散列Search操作首先搜索關(guān)鍵字為K的起始桶f(k)

接著對表中后繼桶進行搜索，直到下面其中之一情況發(fā)生：(1)存有關(guān)鍵字為K的桶已找到，即找到了要搜索的元素。

(2)到達一個空桶；

(3)又回到起始桶f(k)。若發(fā)生情況(2)和

(3),，則說明表中沒有關(guān)鍵字為k的元素。61線性開型尋址散列Delete操作執(zhí)行搜索操作，找到關(guān)鍵字為K的桶.在完成一次刪除操作后，必須能保證上述的搜索過程仍能夠正常進行。不能僅僅把表中相應(yīng)位置置為空。

f(24)=f(35)=2,f(80)=f(58)=3,Delete:58;然后

search:35

（f(35)=2）

2480012345678910354065hashtable刪除方法1當一個桶的元素被刪除后，其后面的桶的元素要前移。

Method2:采用標記

NeverUsed，對每個桶設(shè)為初始值=

true。當有元素放入，改為false.63template<classK,classE>classhashTable{public:hashTable(inttheDivisor=11);~hashTable(){delete[]table;}boolempty()const{returndSize==0;}intsize()const{returndSize;}pair<constK,E>*find(constK&)const;voidinsert(constpair<constK,E>&);voidoutput(ostream&out)const;protected:intsearch(constK&)const;pair<constK,E>**table;//hashtablehash<K>hash;//mapsKtointegerintdSize;//numberofpairsindictionaryintdivisor;//hashfunctiondivisor};64template<classK,classE>hashTable<K,E>::hashTable(inttheDivisor){divisor=theDivisor;dSize=0;//allocateandinitializehashtablearraytable=newpair<constK,E>*[divisor];for(inti=0;i<divisor;i++)table[i]=NULL;}65template<classK,classE>inthashTable<K,E>::search(constK&theKey)const{//theKey是要檢索的元素關(guān)鍵詞，其實與theKey的哈希映射位置，遍歷整個表，若找到該元素或空置單元，則返回位置下標inti=(int)hash(theKey)%divisor;//homebucketintj=i;//startathomebucketdo{if(table[j]==NULL||table[j]->first==theKey)returnj;j=(j+1)%divisor;//nextbucket}while(j!=i);//returnedtohomebucket?returnj;//tablefull}66template<classK,classE>pair<constK,E>*hashTable<K,E>::find(constK&theKey)const{//查找是否含有theKey的元素在表中？在返回全部信息，否則//nullintb=search(theKey);//seeifamatchwasfoundattable[b]if(table[b]==NULL||table[b]->first!=theKey)returnNULL;//nomatchreturntable[b];//matchingpair}67template<classK,classE>voidhashTable<K,E>::insert(constpair<constK,E>&thePair){//插入對（K,E），若已經(jīng)存在，在把第二部分修改intb=search(thePair.first);//checkifmatchingpairfoundif(table[b]==NULL){//nomatchingpairandtablenotfulltable[b]=newpair<constK,E>(thePair);dSize++;}else

68{//checkifduplicateortablefullif(table[b]->first==thePair.first){//duplicate,changetable[b]->secondtable[b]->second=thePair.second;}else//tableisfullthrowhashTableFull();}}697.4.3鏈表散列在發(fā)生溢出時，采用鏈表（chaining）來進行解決。每個桶僅含有一個節(jié)點指針，所有的元素都存儲在該指針所指向的鏈表中。保持一個鏈表上的元素是具有同樣起始桶的元素。707.4.3鏈表散列（直接利用SortedChain實現(xiàn)）搜索（Search）:計算起始桶號為f(k)=k%D;然后搜索該桶所對應(yīng)的鏈表.插入（Insert）:

計算f(k);搜索;插入.由于每次插入都要首先進行一次搜索，因此把鏈表按照升序排列比無序排列會更有效。刪除（Delete）:計算f(k);搜索;刪除.71template<classE,classK>classchainHashTable{public:chainHashTable(intdivisor=11)//divisor(除數(shù)）{d=divisor;table=newSortedChain<E,K>[D];}//headpointerarray,eachtable[i]hasaSortedchain.~chainHashTable(){delete[]table;}boolsearch(constK&k,E&e)const{returntable[k%D].search(k,e);}chainHashTable<E,K>&insert(constE&e){table[e%d].insert(e);return*this;}chainHashTable<E,K>&erase(constK&k,E&e){table[k%d].erase(k,e);return*this;}voidOutput()const;//輸出散列表private:intd//位置數(shù)sortedChain<E,K>*table;//鏈表數(shù)組}72Animprovedimplementation∞0∞0∞0∞0∞0Addingatailnodetotheendofeachchain73ComparisonwithlinearOpenaddressing空間復(fù)雜性，設(shè)s是存放一個元素所需的bytes數(shù)，每個指針和整數(shù)用2bytes,b是哈希函數(shù)能映射bin的數(shù)量.線性開型尋址散列:b(s+2)(數(shù)組empty:2b)鏈表散列:2b+2n+ns當n<bs/(s+2),鏈表方法所占用的空間要比開型尋址少.74Comparisoninrunningtime線性開型尋址散列:最壞情況:

(n)

平均性能:UnandSnaretheaveragenumberofbucketsexaminedduringanunsuccessfulsearchandsuccessfulsearchrespectively,n/b=

Sn~?(1+1/(1-α))Un~?(1+1/(1-α)2)鏈表散列:最壞情況:O(n)平均性能:weexpectthelengthofachain

Sn~1+α/2Un~

(α+1)/2,1,superiortolineararray75練習P25817P25931,37文本壓縮的應(yīng)用PopulartextcompressorssuchaszipandUnix’scompressarebasedontheLZW(Lempel-Ziv-Welch)method.ideaWecanoftenreducethedeskstorageneededtostoreatextfilebystoringacodeversionofthefile,especiallywhenthefrequencyoftheappearanceofsub-stringsarehigh.E.g.1000x1000y,2002bytesareneededifusing“x”,”y”;10bytesareenoughif“1000x1000y”.TheLZWmethodsistomapalongsubstringtoafixlengthcode,andusingcodestodenotethetextfile.77LZWCompressionThelzwmapsstringsoftextcharactersintomembercodethataredynamicallydetermined.ThemethodscansthestringsfromlefttorightandthengeneratesatableconsistingcodeandkeybasedonLZWruleThenusecodeinthetabletodenotethestringinordertocompressedthetext.Filecodingisdonebycompressoranddecodingbyadecomporessor.LZWruleBeginningwiththedictionaryinitialized.TheLZWcompressorrepeatedlyfindsthelongestprefix,p,oftheunencodedpartoftheinputfilethatisinthedictionaryandoutputsitscode.Ifthereisanextcharactercintheinputfile,thenpcisassignedtothenextcodeandinsertedintothedictionary.79LZWCompressionexampleAssumethelettersinthetextarelimitedto{a,b}.Thecharactersinthealphabetareassignedcodenumbersbeginningat0.Theinitialcodetableis:codekey0a1bInitializeddictionaryLZWruleOriginaltext=abababbabaabbabbaabbaCompressionisdonebyscanningtheoriginaltextfromlefttoright.Findlongestprefixpforwhichthereisacodeinthecodetable,a.output0;c=bandassign(2,ab)todictionarycodekey0a1bLZWCompressionOriginaltext=abababbabaabbabbaabbaCompressedtext=“0”codekey0a1b2abLZWCompressionOriginaltext=abababbabaabbabbaabbaCompressedtext=0codekey0a1b2ab3bap=bpCode=1c=aRepresentbby1andenterpair(3,ba)intothecodetable.Compressedtext=“01”LZWCompressionOriginaltext=abababbabaabbabbaabbaCompressedtext=01codekey0a1b2ab3bap=abpCode=2c=aRepresentabby2andenter(4,aba)intothecodetable.Compressedtext=“012”4abaLZWCompressionOriginaltext=abababbabaabbabbaabbaCompressedtext=012codekey0a1b2ab3bap=abpCode=2c=bRepresentabby2andenter(5,abb)intothecodetable.Compressedtext=“0122”4aba5abbLZWCompressionOriginaltext=abababbabaabbabbaabbaCompressedtext=0122codekey0a1b2ab3bap=bapCode=3c=bRepresentbaby3andenter(6,bab)intothecodetable.Compressedtext=012234aba5abb6babLZWCompressionOriginaltext=abababbabaabbabbaabbaCompressedtext=01223codekey0a1b2ab3bap=bapCode=3c=aRepresentbaby3andenter(7,baa)intothecodetable.Compressedtext=0122334aba5abb6bab7baaLZWCompressionOriginaltext=abababbabaabbabbaabbaCompressedtext=012233codekey0a1b2ab3bap=abbpCode=5c=aRepresentabbby5andenter(8,abba)intothecodetable.Compressedtext=01223354aba5abb6bab