Ñàéò î ñæàòèè >> Íîâèíêè | Î ñåðâåðå (Compression Catalog! | ENGLISH) Êíèãà "Ìåòîäû ñæàòèÿ äàííûõ" >> Áåç ïîòåðü | Èçîáðàæåíèé | Âèäåî Ðàçäåëû >> Còàòüè | Âèäåî | Arctest | Ññûëêè | Ru.compress | Ôîðóì Ïðîåêòû >> Ä.Âàòîëèíà | À.Ðàòóøíÿêà | Ì.Ñìèðíîâà | Â.Þêèíà | Å.Øåëâèíà | Ä.Øêàðèíà

Ìåòîä LZW-ñæàòèÿ äàííûõ

Êàæäûé ïðîãðàììèñò èìååò õîòÿ áû íåêîòîðîå ïðåäñòàâëåíèå î ñæàòèè (óïàêîâêå) äàííûõ. Òàêèå ïðîãðàììû, êàê "ARC" (System Enhancement Associates, Wayne, N.J.) è "PkZip" (PKWARE, Glendale, Wisc.) âåçäåñóùè â ìèðå MS-DOS. "ARC", ê òîìó æå, èñïîëüçóåòñÿ â ðÿäå äðóãèõ îïåðàöèîííûõ ñèñòåì, òàêèõ êàê Unix, CP/M è ò.ä. Ïîëüçîâàòåëè CP/M äîëãîå âðåìÿ èñïîëüçîâàëè òàêæå "SQ" è "USQ" äëÿ ñæàòèÿ è ðàñïàêîâêè ïðîãðàìì. Ïîëüçîâàòåëè Unix èìåþò óòèëèòû "COMPRESS" è "COMPACK". Îäíàêî òåõíèêà ñæàòèÿ äàííûõ èñïîëüçóåòñÿ ýòèìè ïðîãðàììàìè òîëüêî äâóìÿ ñïîñîáàìè: ïåðåñûëêà ôàéëîâ ïî ëèíèÿì ñâÿçè è àðõèâàöèÿ. Ñæàòèå äàííûõ èìååò íåçàñëóæåííóþ ðåïóòàöèþ òðóäíîãî äëÿ îñâîåíèÿ, òÿæåëîãî â ðåàëèçàöèè è òåì íå ìåíåå ñóùåñòâóþùåãî ÿâëåíèÿ. Ôàêòè÷åñêè òåõíèêà, èñïîëüçîâàííàÿ â âûøå óïîìÿíóòûõ ïðîãðàììàõ, îòíîñèòåëüíî ïðîñòà è ìîæåò áûòü ðåàëèçîâàíà â âèäå ñòàíäàðòíûõ óòèëèò, ñîäåðæàùèõ äîâîëüíî ìàëî ñòðîê êîäà.  ýòîé ñòàòüå îáñóæäàåòñÿ Lempel-Ziv-Welch (LZW) ñæàòèå, õîðîøàÿ, ïîâñåìåñòíî èñïîëüçóåìàÿ òåõíèêà.

LZW, ê ïðèìåðó, ñæèìàÿ ýêðàííûå ôîðìû, ìîæåò ëåãêî "ñíÿòü" 50K áàéò ñ ïðîãðàììû, îñíîâíóþ ÷àñòü êîòîðîé ñîñòàâëÿþò õýëïîâûå ýêðàíû. Ïðè èñïîëüçîâàíèè LZW-ñæàòèÿ 500K áàéò ïðîãðàììíîãî îáåñïå÷åíèÿ ìîãóò áûòü ïîñòàâëåíû êîíå÷íîìó ïîëüçîâàòåëþ íà 360Ká äèñêåòå. ×ðåçìåðíî ðàçáóõøèå ôàéëû áàçû äàííûõ ìîãóò áûòü ñæàòû äî äåñÿòè ïðîöåíòîâ èõ èñõîäíîãî ðàçìåðà.

Îñíîâû LZW

Ñîáñòâåííî èñõîäíûé Lempel/Ziv ïîäõîä ê ñæàòèþ äàííûõ áûë âïåðâûå îáíàðîäîâàí â 1977ã., à óñîâåðøåíñòâîâàííûé (Terry Welch) âàðèàíò áûë îïóáëèêîâàí â 1984ã. Àëãîðèòì íà óäèâëåíèå ïðîñò. Åñëè â äâóõ ñëîâàõ, òî LZW-ñæàòèå çàìåíÿåò ñòðîêè ñèìâîëîâ íåêîòîðûìè êîäàìè. Ýòî äåëàåòñÿ áåç êàêîãî-ëèáî àíàëèçà âõîäíîãî òåêñòà. Âìåñòî ýòîãî ïðè äîáàâëåíèè êàæäîé íîâîé ñòðîêè ñèìâîëîâ ïðîñìàòðèâàåòñÿ òàáëèöà ñòðîê. Ñæàòèå ïðîèñõîäèò, êîãäà êîä çàìåíÿåò ñòðîêó ñèìâîëîâ. Êîäû, ãåíåðèðóåìûå LZW-àëãîðèòìîì, ìîãóò áûòü ëþáîé äëèíû, íî îíè äîëæíû ñîäåðæàòü áîëüøå áèò, ÷åì åäèíè÷íûé ñèìâîë. Ïåðâûå 256 êîäîâ (êîãäà èñïîëüçóþòñÿ 8-áèòíûå ñèìâîëû) ïî óìîë÷àíèþ ñîîòâåòñòâóþò ñòàíäàðòíîìó íàáîðó ñèìâîëîâ. Îñòàëüíûå êîäû ñîîòâåòñòâóþò îáðàáàòûâàåìûì àëãîðèòìîì ñòðîêàì.

Ïðîñòàÿ ïðîãðàììà, ïðèâåäåííàÿ íèæå, ðàáîòàåò ñ 12-áèòíûìè êîäàìè. Çíà÷åíèÿ êîäîâ 0 - 255 ñîîòâåòñòâóþò îòäåëüíûì áàéòàì, à êîäû 256 - 4095 ñîîòâåòñòâóþò ïîäñòðîêàì.

Ñæàòèå

Àëãîðèòì LZW-ñæàòèÿ â ïðîñòåéøåé ôîðìå ïðèâåäåí íà ðèñ.1. Êàæäûé ðàç, êîãäà ãåíåðèðóåòñÿ íîâûé êîä, íîâàÿ ñòðîêà äîáàâëÿåòñÿ â òàáëèöó ñòðîê. LZW ïîñòîÿííî ïðîâåðÿåò, ÿâëÿåòñÿ ëè ñòðîêà óæå èçâåñòíîé, è , åñëè òàê, âûâîäèò ñóùåñòâóþùèé êîä áåç ãåíåðàöèè íîâîãî.

Ïðîöåäóðà LZW-ñæàòèÿ:

ÑÒÐÎÊÀ = î÷åðåäíîé ñèìâîë èç âõîäíîãî ïîòîêà
WHILE âõîäíîé ïîòîê íå ïóñò DO
ÑÈÌÂÎË = î÷åðåäíîé ñèìâîë èç âõîäíîãî ïîòîêà
IF ÑÒÐÎÊÀ+ÑÈÌÂÎË â òàáëèöå ñòðîê THEN
ÑÒÐÎÊÀ = ÑÒÐÎÊÀ+ÑÈÌÂÎË
ELSE
âûâåñòè â âûõîäíîé ïîòîê êîä äëÿ ÑÒÐÎÊÀ
äîáàâèòü â òàáëèöó ñòðîê ÑÒÐÎÊÀ+ÑÈÌÂÎË
ÑÒÐÎÊÀ = ÑÈÌÂÎË
END of IF
END of WHILE
âûâåñòè â âûõîäíîé ïîòîê êîä äëÿ ÑÒÐÎÊÀ

Ðèñ. 1 Àëãîðèòì ñæàòèÿ

Ïðîñòàÿ ñòðîêà, èñïîëüçîâàííàÿ äëÿ äåìîíñòðàöèè àëãîðèòìà, ïðèâåäåíà íà ðèñ.2. Âõîäíàÿ ñòðîêà ÿâëÿåòñÿ êðàòêèì ñïèñêîì àíãëèéñêèõ ñëîâ, ðàçäåëåííûõ ñèìâîëîì "/". Êàê âû ìîæåòå çàìåòèòü, àíàëèçèðóÿ àëãîðèòì, åãî ðàáîòà íà÷èíàåòñÿ ñ òîãî, ÷òî íà ïåðâîì øàãå öèêëà îí âûïîëíÿåò ïðîâåðêó íà íàëè÷èå ñòðîêè "/W" â òàáëèöå. Êîãäà îí íå íàõîäèò ýòó ñòðîêó, òî ãåíåðèðóåò êîä äëÿ "/" è äîáàâëÿåò â òàáëèöó ñòðîêó "/W". Ò.ê. 256 ñèìâîëîâ óæå îïðåäåëåíû äëÿ êîäîâ 0 - 255, òî ïåðâîé îïðåäåëåííîé ñòðîêå ìîæåò áûòü ïîñòàâëåí â ñîîòâåòñòâèå êîä 256. Ïîñëå ýòîãî ñèñòåìà ÷èòàåò ñëåäóþùóþ áóêâó ("E"), äîáàâëÿåò âòîðóþ ïîäñòðîêó ("WE") â òàáëèöó è âûâîäèò êîä äëÿ áóêâû "W".

Ýòîò ïðîöåññ ïîâòîðÿåòñÿ äî òåõ ïîð, ïîêà âòîðàÿ ïîäñòðîêà, ñîñòîÿùàÿ èç ïðî÷èòàííûõ ñèìâîëîâ "/" è "W", íå ñîïîñòàâèòñÿ ñî ñòðîêîâûì íîìåðîì 256.  ýòîì ñëó÷àå ñèñòåìà âûâîäèò êîä 256 è äîáàâëÿåò òðåõñèìâîëüíóþ ïîäñòðîêó â òàáëèöó. Ýòîò ïðîöåññ ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íå èñ÷åðïàåòñÿ âõîäíîé ïîòîê è âñå êîäû íå áóäóò âûâåäåíû.

Âõîäíàÿ ñòðîêà : /WED/WE/WEE/WEB/WET

Ðèñ. 2 Ïðîöåññ ñæàòèÿ

Âûõîäíîé ïîòîê äëÿ çàäàííîé ñòðîêè ïîêàçàí íà ðèñ. 2, òàêæå êàê è ïîëó÷åííàÿ â ðåçóëüòàòå òàáëèöà ñòðîê. Êàê âû ìîæåòå çàìåòèòü, ýòà òàáëèöà áûñòðî çàïîëíÿåòñÿ, ò.ê. íîâàÿ ñòðîêà äîáàâëÿåòñÿ â òàáëèöó êàæäûé ðàç, êîãäà ãåíåðèðóåòñÿ êîä.  ýòîì ÿâíî âûðîæäåííîì ïðèìåðå áûëî âûâåäåíî ïÿòü çàêîäèðîâàííûõ ïîäñòðîê è ñåìü ñèìâîëîâ. Åñëè èñïîëüçîâàòü 9-áèòíûå êîäû äëÿ âûâîäà, òî 19-ñèìâîëüíàÿ âõîäíàÿ ñòðîêà áóäåò ïðåîáðàçîâàíà â 13.5-ñèìâîëüíàÿ âûõîäíóþ ñòðîêó. Êîíå÷íî, ýòîò ïðèìåð áûë âûáðàí òîëüêî äëÿ äåìîíñòðàöèè.  äåéñòâèòåëüíîñòè ñæàòèå îáû÷íî íå íà÷èíàåòñÿ äî òåõ ïîð, ïîêà íå áóäåò ïîñòðîåíà äîñòàòî÷íî áîëüøàÿ òàáëèöà, îáû÷íî ïîñëå ïðî÷òåíèÿ ïîðÿäêà 100 âõîäíûõ áàéò.

Ðàñïàêîâêà

Àëãîðèòìó ñæàòèÿ ñîîòâåòñòâóåò ñâîé àëãîðèòì ðàñïàêîâêè. Îí ïîëó÷àåò âûõîäíîé ïîòîê êîäîâ îò àëãîðèòìà ñæàòèÿ è èñïîëüçóåò åãî äëÿ òî÷íîãî âîññòàíîâëåíèÿ âõîäíîãî ïîòîêà. Îäíîé èç ïðè÷èí ýôôåêòèâíîñòè LZW-àëãîðèòìà ÿâëÿåòñÿ òî, ÷òî îí íå íóæäàåòñÿ â õðàíåíèè òàáëèöû ñòðîê, ïîëó÷åííîé ïðè ñæàòèè. Òàáëèöà ìîæåò áûòü òî÷íî âîññòàíîâëåíà ïðè ðàñïàêîâêå íà îñíîâå âûõîäíîãî ïîòîêà àëãîðèòìà ñæàòèÿ. Ýòî âîçìîæíî ïîòîìó, ÷òî àëãîðèòì ñæàòèÿ âûâîäèò ÑÒÐÎÊÎÂÓÞ è ÑÈÌÂÎËÜÍÓÞ êîìïîíåíòû êîäà ïðåæäå ÷åì îí ïîìåñòèò ýòîò êîä â âûõîäíîé ïîòîê. Ýòî îçíà÷àåò, ÷òî ñæàòûå äàííûå íå îáðåìåíåíû íåîáõîäèìîñòüþ òÿíóòü çà ñîáîé áîëüøóþ òàáëèöó ïåðåâîäà.

Àëãîðèòì ðàñïàêîâêè ïðåäñòàâëåí íà ðèñ. 3.  ñîîòâåòñòâèè ñ àëãîðèòìîì ñæàòèÿ, îí äîáàâëÿåò íîâóþ ñòðîêó â òàáëèöó ñòðîê êàæäûé ðàç, êîãäà ÷èòàåò èç âõîäíîãî ïîòîêà íîâûé êîä. Âñå, ÷òî åìó íåîáõîäèìî ñäåëàòü â äîáàâîê - ýòî ïåðåâåñòè êàæäûé âõîäíîé êîä â ñòðîêó è ïåðåñëàòü åå â âûõîäíîé ïîòîê.

Ïðîöåäóðà LZW-ðàñïàêîâêè:

÷èòàòü ÑÒÀÐÛÉ_ÊÎÄ
âûâåñòè ÑÒÀÐÛÉ_ÊÎÄ
WHILE âõîäíîé ïîòîê íå ïóñò DO
÷èòàòü ÍÎÂÛÉ_ÊÎÄ
ÑÒÐÎÊÀ = ïåðåâåñòè ÍÎÂÛÉ_ÊÎÄ
âûâåñòè ÑÒÐÎÊÓ
ÑÈÌÂÎË = ïåðâûé ñèìâîë ÑÒÐÎÊÈ
äîáàâèòü â òàáëèöó ïåðåâîäà ÑÒÀÐÛÉ_ÊÎÄ+ÑÈÌÂÎË
ÑÒÀÐÛÉ_ÊÎÄ = ÍÎÂÛÉ_ÊÎÄ
END of WHILE

Ðèñ. 3 Àëãîðèòì ðàñïàêîâêè

Íà ðèñ. 4 ïðèâåäåíà ñõåìà ðàáîòû àëãîðèòìà íà îñíîâå ñæàòûõ äàííûõ, ïîëó÷åííûõ â âûøå ïðèâåäåííîì ïðèìåðå. Âàæíî îòìåòèòü, ÷òî ïîñòðîåíèå òàáëèöû ñòðîê àëãîðèòìîì ðàñïàêîâêè çàêàí÷èâàåòñÿ êàê ðàç òîãäà, êîãäà ïîñòðîåíà òàáëèöà ñòðîê àëãîðèòìà ñæàòèÿ.

Âõîäíûå êîäû : / W E D 256 E 260 261 257 B 260 T

Ðèñ. 4 Ïðîöåññ ðàñïàêîâêè

Âûõîäíîé ïîòîê èäåíòè÷åí âõîäíîìó ïîòîêó àëãîðèòìà ñæàòèÿ. Îòìåòèì, ÷òî ïåðâûå 256 êîäîâ óæå îïðåäåëåíû äëÿ ïåðåâîäà îäèíî÷íûõ ñèìâîëîâ, òàêæå êàê è â àëãîðèòìå ñæàòèÿ.

Ëîâóøêà

Ê íåñ÷àñòüþ ïðåêðàñíûé , ïðîñòîé àëãîðèòì ðàñïàêîâêè, ïðèâåäåííûé íà ðèñ. 4, ÿâëÿåòñÿ âñå òàêèì ñëèøêîì ïðîñòûì.  àëãîðèòìå ñæàòèÿ ñóùåñòâóþò íåêîòîðûå èñêëþ÷èòåëüíûå ñèòóàöèè, êîòîðûå ñîçäàþò ïðîáëåìû ïðè ðàñïàêîâêå. Åñëè ñóùåñòâóåò ñòðîêà, ïðåäñòàâëÿþùàÿ ïàðó (ÑÒÐÎÊÀ ÑÈÌÂÎË) è óæå îïðåäåëåííóþ â òàáëèöå, à ïðîñìàòðèâàåìûé âõîäíîé ïîòîê ñîäåðæèò ïîñëåäîâàòåëüíîñòü ÑÒÐÎÊÀ ÑÈÌÂÎË ÑÒÐÎÊÀ ÑÈÌÂÎË ÑÒÐÎÊÀ, àëãîðèòì ñæàòèÿ âûâåäåò êîä ïðåæäå, ÷åì ðàñïàêîâùèê ïîëó÷èò âîçìîæíîñòü îïðåäåëèòü åãî.

Ïðîñòîé ïðèìåð èëëþñòðèðóåò ýòî. Ïðåäïîëîæèì, ñòðîêà "JOEYN" îïðåäåëåíà â òàáëèöå ñ êîäîì 300. Êîãäà ïîñëåäîâàòåëüíîñòü "JOEYNJOEYNJOEY" ïîÿâëÿåòñÿ â òàáëèöå, âûõîäíîé ïîòîê àëãîðèòìà ñæàòèÿ âûãëÿäèò ïîäîáíî òîìó, êàê ïîêàçàíî íà ðèñ. 5.

Âõîäíàÿ ñòðîêà : ...JOEYNJOEYNJOEY...

Ðèñ. 5 Íåêîòîðûå ïðîáëåìû

Êîãäà ðàñïàêîâùèê ïðîñìàòðèâàåò âõîäíîé ïîòîê, îí ñíà÷àëà äåêîäèðóåò êîä 300, çàòåì âûâîäèò ñòðîêó "JOEYN" è äîáàâëÿåò îïðåäåëåíèå äëÿ, ñêàæåì, êîäà 399 â òàáëèöó, õîòÿ îí óæå ìîã òàì áûòü. Çàòåì ÷èòàåò ñëåäóþùèé âõîäíîé êîä, 400, è îáíàðóæèâàåò, ÷òî åãî íåò â òàáëèöå. Ýòî óæå ïðîáëåìà. Ê ñ÷àñòüþ, ýòî ïðîèçîéäåò òîëüêî â òîì ñëó÷àå, åñëè ðàñïàêîâùèê âñòðåòèò íåèçâåñòíûé êîä. Òàê êàê ýòî ôàêòè÷åñêè åäèíñòâåííàÿ êîëëèçèÿ, òî ìîæíî áåç òðóäà óñîâåðøåíñòâîâàòü àëãîðèòì.

Ìîäèôèöèðîâàííûé àëãîðèòì ïðåäóñìàòðèâàåò ñïåöèàëüíûå äåéñòâèÿ äëÿ åùå íåîïðåäåëåííûõ êîäîâ.  ïðèìåðå íà ðèñ. 6 ðàñïàêîâùèê îáíàðóæèâàåò êîä 400, êîòîðûé åùå íå îïðåäåëåí. Òàê êàê ýòîò êîä íå èçâåñòåí, òî äåêîäèðóåòñÿ çíà÷åíèå ÑÒÀÐÎÃÎ_ÊÎÄÀ, ðàâíîå 300. Çàòåì ðàñïàêîâùèê äîáàâëÿåò çíà÷åíèå ÑÈÌÂÎËÀ, ðàâíîå "J", ê ñòðîêå. Ðåçóëüòàòîì ÿâëÿåòñÿ ïðàâèëüíûé ïåðåâîä êîäà 400 â ñòðîêó "JOEYNJ".

Ïðîöåäóðà LZW-ðàñïàêîâêè:

÷èòàòü ÑÒÀÐÛÉ_ÊÎÄ
âûâåñòè ÑÒÀÐÛÉ_ÊÎÄ
ÑÈÌÂÎË = ÑÒÀÐÛÉ_ÊÎÄ
WHILE âõîäíîé ïîòîê íå ïóñò DO
÷èòàòü ÍÎÂÛÉ_ÊÎÄ
IF NOT â òàáëèöå ïåðåâîäà ÍÎÂÛÉ_ÊÎÄ THEN
ÑÒÐÎÊÀ = ïåðåâåñòè ÑÒÀÐÛÉ_ÊÎÄ
ÑÒÐÎÊÀ = ÑÒÐÎÊÀ+ÑÈÌÂÎË
ELSE
ÑÒÐÎÊÀ = ïåðåâåñòè ÍÎÂÛÉ_ÊÎÄ
END of IF
âûâåñòè ÑÒÐÎÊÓ
ÑÈÌÂÎË = ïåðâûé ñèìâîë ÑÒÐÎÊÈ
äîáàâèòü â òàáëèöó ïåðåâîäà ÑÒÀÐÛÉ_ÊÎÄ+ÑÈÌÂÎË
ÑÒÀÐÛÉ_ÊÎÄ = ÍÎÂÛÉ_ÊÎÄ
END of WHILE

Ðèñ. 6 Ìîäèôèöèðîâàííûé àëãîðèòì ðàñïàêîâêè

Ðåàëèçàöèÿ

Êîíöåïöèè, èñïîëüçîâàííûå â àëãîðèòìå ñæàòèÿ, íàñòîëüêî ïðîñòû, ÷òî âåñü àëãîðèòì ìîæåò áûòü çàïèñàí â íåñêîëüêî ñòðîê. Íî òàê êàê óïðàâëåíèå ïîñòðîåíèåì òàáëèöû òðåáóåò íåêîòîðûõ ñïåöèàëüíûõ äåéñòâèé, ðåàëèçàöèÿ íåñêîëüêî áîëåå ñëîæíà.  äåìîíñòðàöèîííîé ïðîãðàììå, ïðèâåäåííîé íèæå, èñïîëüçîâàëèñü êîäû äëèíîé 12, 13 è 14 áèò. Ïðè äëèíå êîäà 12 áèò ïîòåíöèàëüíî âîçìîæíî õðàíèòü äî 4096 ñòðîê â òàáëèöå. Êàæäûé ðàç, êîãäà ÷èòàåòñÿ íîâûé ñèìâîë, òàáëèöà ñòðîê äîëæíà ïðîñìàòðèâàòüñÿ äëÿ ñîïîñòàâëåíèÿ. Åñëè ñîïîñòàâëåíèå íå íàéäåíî, íîâàÿ ñòðîêà äîëæíà áûòü äîáàâëåíà â òàáëèöó. Çäåñü âîçíèêàþò äâå ïðîáëåìû. Âî-ïåðâûõ, òàáëèöà ñòðîê ìîæåò äîñòàòî÷íî áûñòðî ñòàòü î÷åíü áîëüøîé. Äàæå åñëè äëèíà ñòðîê â ñðåäíåì îãðàíè÷èâàåòñÿ 3 èëè 4 ñèìâîëàìè êàæäàÿ, âåðõíèé ïðåäåë äëèí ñòðîê ìîæåò ëåãêî ïðåâûñèòü 7 èëè 8 áàéò íà êîä. Ê òîìó æå êîëè÷åñòâî ïàìÿòè, íåîáõîäèìîé äëÿ õðàíåíèÿ ñòðîê, çàðàíåå íå èçâåñòíî, òàê êàê îíî çàâèñèò îò îáùåé äëèíû ñòðîê.

Âòîðàÿ ïðîáëåìà çàêëþ÷àåòñÿ â îðãàíèçàöèè ïîèñêà ñòðîê. Êàæäûé ðàç, êîãäà ÷èòàåòñÿ íîâûé ñèìâîë, íåîáõîäèìî îðãàíèçîâàòü ïîèñê äëÿ íîâîé ñòðîêè âèäà ÑÒÐÎÊÀ+ÑÈÌÂÎË. Ýòî îçíà÷àåò ïîääåðæêó îòñîðòèðîâàííîãî ñïèñêà ñòðîê.  ýòîì ñëó÷àå ïîèñê äëÿ êàæäîé ñòðîêè âêëþ÷àåò ÷èñëî ñðàâíåíèé ïîðÿäêà log2 îò îáùåãî ÷èñëà ñòðîê. Èñïîëüçîâàíèå 12-áèòíûõ ñëîâ ïîòåíöèàëüíî ïîçâîëÿåò âûïîëíÿòü íå áîëåå 12 ñðàâíåíèé äëÿ êàæäîãî êîäà.

Ïåðâàÿ ïðîáëåìà ìîæåò áûòü ðåøåíà õðàíåíèåì ñòðîê êàê êîìáèíàöèé êîä/ñèìâîë. Òàê êàê êàæäàÿ ñòðîêà â äåéñòâèòåëüíîñòè ÿâëÿåòñÿ ïðåäñòàâëåíèåì êîìáèíàöèè óæå ñóùåñòâóþùåãî êîäà è äîáàâî÷íîãî ñèìâîëà, ìîæíî õðàíèòü êàæäóþ ñòðîêó êàê îòäåëüíûé êîä ïëþñ ñèìâîë. Íàïðèìåð â ðàçîáðàííîì âûøå ïðèìåðå ñòðîêà "/WEE" õðàíèòñÿ êàê êîä 260 è ñèìâîë "E". Ýòî ïîçâîëÿåò èñïîëüçîâàòü äëÿ õðàíåíèÿ òîëüêî 3 áàéòà âìåñòî 5 (âêëþ÷àþùèõ äîïîëíèòåëüíûé áàéò äëÿ êîíöà ñòðîêè). Èäÿ íàçàä, ìîæíî îïðåäåëèòü, ÷òî êîä 260 õðàíèòñÿ êàê êîä 256 ïëþñ äîáàâî÷íûé ñèìâîë "E". Íàêîíåö, êîä 256 õðàíèòñÿ êàê "/" ïëþñ "W".

Âûïîëíåíèå ñðàâíåíèÿ ñòðîê ÿâëÿåòñÿ íåìíîãî áîëåå òðóäíûì. Íîâûé ìåòîä õðàíåíèÿ óâåëè÷èâàåò âðåìÿ, íåîáõîäèìîå äëÿ ñðàâíåíèÿ ñòðîê, íî îí íå âëèÿåò íà ÷èñëî ñðàâíåíèé. Ýòà ïðîáëåìà ðåøàåòñÿ èñïîëüçîâàíèåì àëãîðèòìà õýøèðîâàíèÿ äëÿ õðàíåíèÿ ñòðîê. Ýòî îçíà÷àåò, ÷òî êîä 256 íå õðàíèòñÿ â êàêîì-ëèáî ìàññèâå ïî àäðåñó 256, à õðàíèòñÿ â ìàññèâå ïî àäðåñó, ñôîðìèðîâàííîìó íà îñíîâå ñàìîé ñòðîêè. Ïðè îïðåäåëåíèè ìåñòà õðàíåíèÿ äàííîé ñòðîêè ìîæíî èñïîëüçîâàòü òåñòîâóþ ñòðîêó äëÿ ãåíåðàöèè õýø-àäðåñà è çàòåì íàéòè öåëåâóþ ñòðîêó îäíîêðàòíûì ñðàâíåíèåì. Òàê êàê êîä äëÿ ëþáîé äàííîé ñòðîêè íåëüçÿ óçíàòü â äàëüíåéøåì èíà÷å êàê ïî åãî ïîçèöèè â ìàññèâå, íåîáõîäèìî õðàíèòü êîä äëÿ äàííîé ñòðîêè ñîâìåñòíî ñ äàííûìè ñòðîêè.  äåìîíñòðàöèîííîé ïðîãðàììå äëÿ ýòîãî èñïîëüçóþòñÿ ýëåìåíòû òðåõ ìàññèâîâ : code_value[i], prefix_code[i] è append_character[i].

Êîãäà íåîáõîäèìî äîáàâèòü íîâûé êîä â òàáëèöó, èñïîëüçóåòñÿ õýøôóíêöèÿ â ïðîöåäóðå find_match äëÿ ãåíåðàöèè êîððåêòíîãî i. Ïðîöåäóðà find_match ãåíåðèðóåò àäðåñ è çàòåì ïðîâåðÿåò, íå èñïîëüçîâàëñÿ ëè îí óæå. Åñëè ýòî òàê, òî find_match âûïîëíÿåò âòîðóþ ïðîáó è òàê äî òåõ ïîð, ïîêà íå íàéäåòñÿ ñâîáîäíîå ìåñòî.

Õýø-ôóíêöèÿ, èñïîëüçîâàííàÿ â ýòîé ïðîãðàììå - ïðîñòàÿ "xor"-òèïà õýø-ôóíêöèÿ. Ïðåôèêñ êîäà è äîáàâî÷íûé ñèìâîë êîìáèíèðóþòñÿ äëÿ ôîðìèðîâàíèÿ àäðåñà ìàññèâà. Åñëè ñîäåðæèìîå ïðåôèêñà êîäà è ñèìâîë â ìàññèâå ñîïîñòàâëÿþòñÿ èì, òî âîçâðàùàåòñÿ êîððåêòíûé àäðåñ. Åñëè ýëåìåíò ìàññèâà ïî ýòîìó àäðåñó óæå èñïîëüçîâàí, âûïîëíÿåòñÿ ôèêñèðîâàííîå ñìåùåíèå äëÿ ïîèñêà íîâîãî ìåñòà. Ýòî âûïîëíÿåòñÿ äî òåõ ïîð, ïîêà íå áóäåò íàéäåíî ñâîáîäíîå ìåñòî èëè íå ïðîèçîéäåò ñîïîñòàâëåíèå. Ñðåäíåå ÷èñëî ïîèñêîâ â òàêîé òàáëèöå - ìåíüøå 3, åñëè èñïîëüçóåòñÿ òàáëèöà íà 25% áîëüøåãî ðàçìåðà, ÷åì íåîáõîäèìî. Îíî ìîæåò áûòü óëó÷øåíî ïóòåì óâåëè÷åíèÿ ðàçìåðà òàáëèöû. Íåîáõîäèìî îòìåòèòü, ÷òî äëÿ òîãî, ÷òîáû ïîðÿäîê âòîðè÷íûõ ïðîá ðàáîòàë, ðàçìåð òàáëèöû äîëæåí áûòü ïðîñòûì ÷èñëîì. Ýòî îáúÿñíÿåòñÿ òåì, ÷òî ïðîáà ìîæåò áûòü ëþáûì öåëûì ìåæäó 1 è ðàçìåðîì òàáëèöû. Åñëè ïðîáà è ðàçìåð òàáëèöû íå ÿâëÿþòñÿ âçàèìíî ïðîñòûìè, ïîèñê ñâîáîäíûõ ìåñò ìîæåò çàêîí÷èòüñÿ íåóäà÷åé, äàæå åñëè îíè åñòü.

Ðåàëèçàöèÿ àëãîðèòìà ðàñïàêîâêè èìååò ñâîé íàáîð ïðîáëåì. Îäíà èç ïðîáëåì àëãîðèòìà ñæàòèÿ çäåñü èñ÷åçàåò. Êîãäà âûïîëíÿåòñÿ ñæàòèå, íåîáõîäèìî îðãàíèçîâàòü ïîèñê â òàáëèöå äëÿ äàííîé ñòðîêè. Ïðè ðàñïàêîâêå íåîáõîäèìî îðãàíèçîâàòü ïðîñìîòð äëÿ îòäåëüíîãî êîäà. Ýòî îçíà÷àåò, ÷òî ìîæíî õðàíèòü ïðåôèêñû êîäîâ è äîáàâî÷íûå ñèìâîëû, èíäåêñèðóÿñü ïî èõ ñòðîêîâîìó êîäó. Ýòî óñòðàíÿåò íåîáõîäèìîñòü â õýø-ôóíêöèè è îñâîáîæäàåò ìàññèâ, èñïîëüçîâàâøèéñÿ äëÿ õðàíåíèÿ çíà÷åíèé êîäîâ.

Ê ñîæàëåíèþ ìåòîä, èñïîëüçîâàííûé äëÿ õðàíåíèÿ ñòðîêîâûõ âåëè÷èí, ïðèâîäèò ê òîìó, ÷òî äåêîäèðîâêà ñòðîê äîëæíà âûïîëíÿòüñÿ â èíâåðñíîì ïîðÿäêå. Ýòî çíà÷èò, ÷òî âñå ñèìâîëû äëÿ äàííîé ñòðîêè ïðè äåêîäèðîâàíèè äîëæíû ïîìåùàòüñÿ â ñòåêîâûé áóôåð, à çàòåì âûâîäèòüñÿ â îáðàòíîì ïîðÿäêå.  ïðèâåäåííîé ïðîãðàììå ýòî âûïîëíÿåòñÿ ôóíêöèåé decode_string.

Ïðîáëåìà ïîÿâëÿåòñÿ, êîãäà ÷òåíèå âõîäíîãî ïîòîêà ïðåðûâàåòñÿ ïðè äîñòèæåíèè êîíöà ïîòîêà. Äëÿ ýòîãî ÷àñòíîãî ñëó÷àÿ â ïðîãðàììå çàðåçåðâèðîâàí ïîñëåäíèé îïðåäåëÿåìûé êîä MAX_VALUE êàê ïðèçíàê êîíöà äàííûõ. Ýòî íå ÿâëÿåòñÿ íåîáõîäèìûì ïðè ÷òåíèè ôàéëà, íî ìîæåò ïîìî÷ü ïðè ÷òåíèè áóôåðà ñæàòûõ äàííûõ èç ïàìÿòè. Çàòðàòû íà ïîòåðþ îäíîãî îïðåäåëÿåìîãî êîäà âåñüìà ìàëû ñðàâíèòåëüíî ñî âñåì ïðîöåññîì.

Ðåçóëüòàòû

Äîñòàòî÷íî òðóäíî îõàðàêòåðèçîâàòü ðåçóëüòàòèâíîñòü êàêîé-ëèáî òåõíèêè ñæàòèÿ äàííûõ. Ñòåïåíü ñæàòèÿ îïðåäåëÿåòñÿ ðàçëè÷íûìè ôàêòîðàìè. LZW-ñæàòèå âûäåëÿåòñÿ ñðåäè ïðî÷èõ, êîãäà âñòðå÷àåòñÿ ñ ïîòîêîì äàííûõ, ñîäåðæàùèì ïîâòîðÿþùèåñÿ ñòðîêè ëþáîé ñòðóêòóðû. Ïî ýòîé ïðè÷èíå îí ðàáîòàåò âåñüìà ýôôåêòèâíî, êîãäà âñòðå÷àåò àíãëèéñêèé òåêñò. Óðîâåíü ñæàòèÿ ìîæåò äîñòèãàòü 50% è âûøå. Ñîîòâåòñòâåííî, ñæàòèå âèäåîôîðì è êîïèé ýêðàíîâ ïîêàçûâàåò åùå áîëüøèå ðåçóëüòàòû.

Òðóäíîñòè ïðè ñæàòèè ôàéëîâ äàííûõ íåñêîëüêî áîëüøå.  çàâèñèìîñòè îò äàííûõ, ðåçóëüòàò ñæàòèÿ ìîæåò áûòü êàê õîðîøèì, òàê è íå î÷åíü óäîâëåòâîðèòåëüíûì.  íåêîòîðûõ ñëó÷àÿõ "ñæàòûé" ôàéë ìîæåò ïðåâîñõîäèòü ïî ñâîèì ðàçìåðàì èñõîäíûé òåêñò. Íåáîëüøîé ýêñïåðèìåíò äàñò Âàì ïðåäñòàâëåíèå î òîì, õîðîøî èëè ïëîõî óïàêîâûâàþòñÿ Âàøè äàííûå.

Âàøà ðåàëèçàöèÿ

Ïðîãðàììà, ïðèâåäåííàÿ â ñòàòüå, ÿâëÿåòñÿ ðàáî÷åé. Îíà áûëà íàïèñàíà, îäíàêî, ñ èëëþñòðàòèâíîé öåëüþ è íå î÷åíü ýôôåêòèâíà. Íàïðèìåð, ïðîöåäóðû, îðãàíèçóþùèå âõîäíûå è âûõîäíûå ïîòîêè, íåâåëèêè ïî ðàçìåðàì è ëåãêè äëÿ ïîíèìàíèÿ, íî óâåëè÷èâàþò íàêëàäíûå ðàñõîäû. Âû ìîæåòå ïîïðîáîâàòü óâåëè÷èòü ñêîðîñòü ïðîãðàììû, ñîâåðøåííî ïåðåïèñàâ ýòè ïðîöåäóðû ñ èñïîëüçîâàíèåì êîäîâ ôèêñèðîâàííîé äëèíû, ñêàæåì 12 áèò.

Îäíîé èç ïðîáëåì ÿâëÿåòñÿ òî, ÷òî ïðèâåäåííàÿ ïðîãðàììà íå àäàïòèðóåòñÿ ê ðàçëè÷íîé äëèíå ôàéëîâ. Èñïîëüçîâàíèå 14- èëè 15-áèòíûõ êîäîâ äàåò ëó÷øóþ ñòåïåíü ñæàòèÿ íà áîëüøèõ ôàéëàõ (ýòî îáúÿñíÿåòñÿ òåì, ÷òî äëÿ íèõ ñòðîÿòñÿ áîëüøèå òàáëèöû ñòðîê), íî õóæå ðàáîòàåò ñ ìàëåíüêèìè ôàéëàìè. Òàêèå ïðîãðàììû, êàê "ARC", ðåøàþò ýòó ïðîáëåìó èñïîëüçîâàíèåì êîäîâ ïåðåìåííîé äëèíû. Íàïðèìåð, êîãäà âåëè÷èíà next_code íàõîäèòñÿ ìåæäó 256 è 511, "ARC" ÷èòàåò è âûâîäèò 9-áèòíûå êîäû. Êîãäà âåëè÷èíà next_code ñòàíîâèòñÿ íàñòîëüêî áîëüøîé, ÷òî íåîáõîäèìû 10-áèòíûå êîäû, ïðîöåäóðû ñæàòèÿ è ðàñïàêîâêè óâåëè÷èâàþò ðàçìåð êîäà. Ýòî çíà÷èò, ÷òî 12- è 15-áèòíûå âàðèàíòû ïðîãðàììû ðàáîòàþò õîðîøî è íà ìàëåíüêèõ ôàéëàõ.

Äðóãîé ïðîáëåìîé áîëüøèõ ôàéëîâ ÿâëÿåòñÿ òî, ÷òî ñ óâåëè÷åíèåì ÷èñëà ïðî÷èòàííûõ áàéòîâ ñòåïåíü ñæàòèÿ ìîæåò íà÷àòü óõóäøàòüñÿ. Ïðè÷èíà ïðîñòà : òàê êàê ðàçìåð òàáëèöû ñòðîê ôèêñèðîâàí, ïîñëå çàíåñåíèÿ îïðåäåëåííîãî ÷èñëà ñòðîê èõ óæå ïðîñòî íåêóäà äîáàâèòü. Íî ïîñòðîåííàÿ òàáëèöà íóæíà òîëüêî äëÿ òîé ÷àñòè ôàéëà, ïî êîòîðîé îíà áûëà ïîñòðîåíà. Îñòàâøèåñÿ ÷àñòè ôàéëà ìîãóò èìåòü äðóãèå õàðàêòåðèñòèêè è â äåéñòâèòåëüíîñòè íóæíà óæå íåñêîëüêî îòëè÷íàÿ òàáëèöà.

Îáû÷íûì ñïîñîáîì ðåøåíèÿ ýòîé ïðîáëåìû ÿâëÿåòñÿ êîíòðîëü ñòåïåíè ñæàòèÿ. Ïîñëå òîãî, êàê òàáëèöà ñòðîê çàïîëíåíà, óïàêîâùèê ñëåäèò çà ïîâåäåíèåì êîýôôèöèåíòà ñæàòèÿ. Ïîñëå îïðåäåëåííîé  ñòåïåíè åãî óõóäøåíèÿ òàáëèöà ñòðîê î÷èùàåòñÿ è íà÷èíàåò ñòðîèòüñÿ çàíîâî.

Ïðîöåäóðà ðàñïàêîâêè îïðåäåëÿåò ýòîò ìîìåíò òåì, ÷òî óïàêîâùèê çàïèñûâàåò â ñâîé âûõîäíîé ïîòîê ñïåöèàëüíûé êîä. Àëüòåðíàòèâíûì ñïîñîáîì ÿâëÿåòñÿ îïðåäåëåíèå íàèáîëåå ÷àñòî âñòðå÷àþùèõñÿ ñòðîê è ÷èñòêà îñòàëüíûõ. Àäàïòèâíàÿ òåõíèêà, ïîäîáíàÿ ýòîé, ìîæåò, îäíàêî, âñòðåòèòü òðóäíîñòè ðåàëèçàöèè â ïðîãðàììàõ ðàçóìíîãî ðàçìåðà.

È, íàêîíåö, ìîæíî áðàòü âûðàáàòûâàåìûå LZW-ìåòîäîì êîäû è ïðîïóñêàòü èõ ÷åðåç àäàïòèðóþùèéñÿ êîäèðóþùèé ôèëüòð Õàôôìàíà. Ýòî äàåò íåñêîëüêî áîëüøóþ ñòåïåíü ñæàòèÿ, íî ñòîèìîñòü òàêîé ðàáîòû áîëåå âûñîêà, òàêæå êàê è âðåìÿ îáðàáîòêè.

Êîðîòêî

Ïðèâåäåííàÿ ïðîãðàììà áûëà íàïèñàíà è òåñòèðîâàíà íà MS-DOS ìàøèíå è óñïåøíî ñêîìïèëèðîâàíà è âûïîëíåíà ñ èñïîëüçîâàíèåì îáû÷íîãî êîìïèëÿòîðà "C". Îíà äîëæíà íîðìàëüíî ðàáîòàòü íà ëþáîé ìàøèíå, ïîääåðæèâàþùåé 16-áèòíûé öåëûå è 32-áèòíûå äëèííûå öåëûå ÿçûêà "C".

Ðåàëèçàöèÿ êîìïèëÿòîðîâ "C" äëÿ MS-DOS îáû÷íî ñîçäàåò ñëîæíîñòè ïðè èñïîëüçîâàíèè ìàññèâîâ áîëüøèõ, ÷åì 64Ê áàéò, íå ïîçâîëÿÿ èñïîëüçîâàòü 15- èëè 16-áèòíûå êîäû â ïðîãðàììå. Íà ìàøèíàõ ñ äðóãèìè ïðîöåññîðàìè, òàêèõ êàê VAX, ýòè ñëîæíîñòè ïðåîäîëåâàþòñÿ è îáëåã÷àåòñÿ èñïîëüçîâàíèå êîäîâ áîëüøåé äëèíû.

Îòìåòèì, ÷òî ïåðåâîä ýòîãî êîäà íà ÿçûê àññåìáëåðà ëþáîé ìàøèíû, ïîääåðæèâàþùåé 16- è 32-áèòíóþ ìàòåìàòèêó, íå âñòðåòèò çàòðóäíåíèé è ïîçâîëèò óëó÷øèòü íåêîòîðûå õàðàêòåðèñòèêè.

Áèáëèîãðàôèÿ

1. Terry Welch, "Technique for High-Performance Data Compression, "Computer, June 1984.
2. J. Ziv and A. Lempel, "A Universal Algorithm for Sequentia Data Compression, "IEEE Transactions on Information Theory, May 1977
3. Rudy Rucker, "Mind Tools, Houghton Miffilin Company, Boston, Mass.: 1987

/***************************************************************************
** Äåìîíñòðàöèîííàÿ ïðîãðàììà äëÿ LZW-àëãîðèòìà ñæàòèÿ/ðàñïàêîâêè äàííûõ.
** Mark R. Nelson
****************************************************************************/
#include <stdio.h>
#define BITS 12                      /* Óñòàíîâêà äëèíû êîäà ðàâíîé 12, 13   */
#define HASHING_SHIFT BITS-8         /* èëè 14 áèòàì.                        */
#define MAX_VALUE (1 << BITS) - 1    /* Îòìåòèì, ÷òî íà MS-DOS-ìàøèíå ïðè    */
#define MAX_CODE MAX_VALUE - 1       /* äëèíå êîäà 14 áèò íåîáõîäèìî êîìïè-  */
                                     /* ëèðîâàòü, èñïîëüçóÿ large-ìîäåëü.    */
#if BITS == 14
  #define TABLE_SIZE 18041           /* Ðàçìåð òàáëèöû ñòðîê äîëæåí áûòü     */
#endif                               /* ïðîñòûì ÷èñëîì, íåñêîëüêî áîëüøèì,   */
#if BITS == 13                       /* ÷åì 2**BITS.                         */
  #define TABLE_SIZE 9029
#endif
#if BITS <= 12
  #define TABLE_SIZE 5021
#endif

void *malloc();

int *code_value;                  /* Ýòî ìàññèâ äëÿ çíà÷åíèé êîäîâ            */
unsigned int *prefix_code;        /* Ýòîò ìàññèâ ñîäåðæèò ïðåôèêñû êîäîâ      */
unsigned char *append_character;  /* Ýòîò ìàññèâ ñîäåðæèò äîáàâî÷íûå ñèìâîëû  */
unsigned char decode_stack[4000]; /* Ýòîò ìàññèâ ñîäåðæèò äåêîäèðóåìûå ñòðîêè */

/***************************************************************************
** Ýòà ïðîãðàììà ïîëó÷àåò èìÿ ôàéëà èç êîìàíäíîé ñòðîêè. Îíà óïàêîâûâàåò
** ôàéë, ïîñûëàÿ âûõîäíîé ïîòîê â ôàéë test.lzw. Çàòåì ðàñïàêîâûâàåò
** test.lzw â test.out. Test.out äîëæåí áûòü òî÷íîé êîïèåé èñõîäíîãî ôàéëà.
****************************************************************************/

main(int argc, char *argv[])
{
FILE *input_file;
FILE *output_file;
FILE *lzw_file;
char input_file_name[81];
/*
**  Ýòè òðè áóôåðà íåîáõîäèìû íà ñòàäèè óïàêîâêè.
*/
    code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
    prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
    append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
    if (code_value==NULL || prefix_code==NULL || append_character==NULL)
    {
        printf("Fatal error allocating table space!\n");
        exit();
    }

/*
** Ïîëó÷èòü èìÿ ôàéëà, îòêðûòü åãî è îòêðûòü âûõîäíîé lzw-ôàéë.
*/
    if (argc>1)
        strcpy(input_file_name,argv[1]);
    else
    {
        printf("Input file name? ");
        scanf("%s",input_file_name);
    }
    input_file=fopen(input_file_name,"rb");
    lzw_file=fopen("test.lzw","wb");
    if (input_file==NULL || lzw_file==NULL)
    {
        printf("Fatal error opening files.\n");
        exit();
    };
/*
** Ñæàòèå ôàéëà.
*/
    compress(input_file,lzw_file);
    fclose(input_file);
    fclose(lzw_file);
    free(code_value);
/*
** Ñåé÷àñ îòêðûòü ôàéëû äëÿ ðàñïàêîâêè.
*/
    lzw_file=fopen("test.lzw","rb");
    output_file=fopen("test.out","wb");
    if (lzw_file==NULL || output_file==NULL)
    {
        printf("Fatal error opening files.\n");
        exit();
    };
/*
** Ðàñïàêîâêà ôàéëà.
*/
    expand(lzw_file,output_file);
    fclose(lzw_file);
    fclose(output_file);
    free(prefix_code);
    free(append_character);
}

/*
** Ïðîöåäóðà ñæàòèÿ.
*/
compress(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int character;
unsigned int string_code;
unsigned int index;
int i;
    next_code=256;         /* Next_code - ñëåäóþùèé äîñòóïíûé êîä ñòðîêè */
    for (i=0;i<TABLE_SIZE;i++)/* Î÷èñòêà òàáëèöû ñòðîê ïåðåä ñòàðòîì   */
        code_value[i]=-1;
    i=0;
    printf("Compressing...\n");
    string_code=getc(input);   /* Get the first code*/

/*
** Îñíîâíîé öèêë. Îí âûïîëíÿåòñÿ äî òåõ ïîð, ïîêà âîçìîæíî ÷òåíèå
** âõîäíîãî ïîòîêà.  Îòìåòèì, ÷òî îí ïðåêðàùàåò çàïîëíåíèå òàáëèöû
** ñòðîê ïîñëå òîãî, êàê âñå âîçìîæíûå êîäû áûëè èñïîëüçîâàíû.
*/
    while ((character=getc(input)) != (unsigned)EOF)
    {
        if (++i==1000)             /* Ïå÷àòàåò * ÷åðåç êàæäûå 1000  */
        {                          /* ÷òåíèé  âõîäíûõ ñèìâîëîâ (äëÿ */
            i=0;                   /* óìèðîòâîðåíèÿ çðèòåëÿ).       */
            printf("*");
        }
        index=find_match(string_code,character);/* Ñìîòðèò, åñòü ëè ñòðîêà */
        if (code_value[index] != -1)            /* â òàáëèöå.  Åñëè åñòü,  */
            string_code=code_value[index];      /* ïîëó÷àåò çíà÷åíèå êîäà. */
        else                                    /* Åñëè íåò, äîáàâëÿåò åå  */
        {                                       /* â òàáëèöó.              */
            if (next_code <= MAX_CODE)
            {
                code_value[index]=next_code++;
                prefix_code[index]=string_code;
                append_character[index]=character;
            }
            output_code(output,string_code); /* Êîãäà îáíàðóæèâàåòñÿ, ÷òî  */
            string_code=character;           /* ñòðîêè íåò â òàáëèöå,      */
        }                                    /* âûâîäèòñÿ ïîñëåäíÿÿ ñòðîêà */
    }                                        /* ïåðåä äîáàâëåíèåì íîâîé    */
/*
** End of the main loop.
*/
    output_code(output,string_code);  /* Âûâîä ïîñëåäíåãî êîäà       */
    output_code(output,MAX_VALUE);    /* Âûâîä ïðèçíàêà êîíöà ïîòîêà */
    output_code(output,0);            /* Î÷èñòêà áóôåðà âûâîäà       */
    printf("\n");
}
/*
** Ïðîöåäóðà õýøèðîâàíèÿ.  Îíà ïûòàåòñÿ íàéòè ñîïîñòàâëåíèå äëÿ ñòðîêè
** ïðåôèêñ+ñèìâîë â òàáëèöå ñòðîê. Åñëè íàéäåíî, âîçâðàùàåòñÿ èíäåêñ.
** Åñëè íåò, òî âîçâðàùàåòñÿ ïåðâûé äîñòóïíûé èíäåêñ.
*/
find_match(int hash_prefix,unsigned int hash_character)
{
int index;
int offset;

    index = (hash_character << HASHING_SHIFT) ^ hash_prefix;
    if (index == 0)
        offset = 1;
    else
        offset = TABLE_SIZE - index;
    while (1)
    {
if (code_value[index] == -1)
      return(index);
if (prefix_code[index] == hash_prefix && append_character[index] == hash_character)
      return(index);
  index -= offset;
  if (index < 0)
      index += TABLE_SIZE;
    }
}

/*
**  Ïðîöåäóðà ðàñïàêîâêè.  Îíà ÷èòàåò ôàéë LZW-ôîðìàòà è ðàñïàêîâûâàåò
**  åãî â âûõîäíîé ôàéë.
*/
expand(FILE *input,FILE *output)
{
unsigned int next_code;
unsigned int new_code;
unsigned int old_code;
int character;
int counter;
unsigned char *string;
char *decode_string(unsigned char *buffer,unsigned int code);
    next_code=256;            /* Ñëåäóþùèé äîñòóïíûé êîä.                */
    counter=0;                 /* Èñïîëüçóåòñÿ ïðè âûâîäå íà ýêðàí.      */
    printf("Expanding...\n");

    old_code=input_code(input); /* ×èòàåòñÿ ïåðâûé êîä, èíèöèàëèçèðóåòñÿ    */
    character=old_code;         /* ïåðåìåííàÿ character è ïîñûëàåòñÿ ïåðâûé */
    putc(old_code,output);      /* êîä â âûõîäíîé ôàéë.                     */
/*
**  Îñíîâíîé öèêë ðàñïàêîâêè.  ×èòàþòñÿ êîäû èç LZW-ôàéëà äî òåõ ïîð,
**  ïîêà íå âñòðåòèòñÿ ñïåöèàëüíûé êîä, óêàçûâàþùèé íà êîíåö äàííûõ.
*/
    while ((new_code=input_code(input)) != (MAX_VALUE))
    {
        if (++counter==1000) { counter=0; printf("*"); }
/*
** Ïðîâåðêà êîäà äëÿ ñïåöèàëüíîãî ñëó÷àÿ STRING+CHARACTER+STRING+CHARACTER+
** STRING, êîãäà ãåíåðèðóåòñÿ íåîïðåäåëåííûé êîä. Ýòî çàñòàâëÿåò åãî
** äåêîäèðîâàòü ïîñëåäíèé êîä, äîáàâèâ CHARACTER â êîíåö äåêîä. ñòðîêè.
*/
        if (new_code>=next_code)
        {
            *decode_stack=character;
            string=decode_string(decode_stack+1,old_code);
        }
/*
** Èíà÷å äåêîäèðóåòñÿ íîâûé êîä.
*/
        else
            string=decode_string(decode_stack,new_code);
/*
** Âûâîäèòñÿ äåêîäèðóåìàÿ ñòðîêà â îáðàòíîì ïîðÿäêå.
*/
        character=*string;
        while (string >= decode_stack)
            putc(*string--,output);
/*
** Íàêîíåö, åñëè âîçìîæíî, äîáàâëÿåòñÿ íîâûé êîä â òàáëèöó ñòðîê.
*/
        if (next_code <= MAX_CODE)
        {
            prefix_code[next_code]=old_code;
            append_character[next_code]=character;
            next_code++;
        }
        old_code=new_code;
    }
    printf("\n");
}

/*
** Ïðîöåäóðà ïðîñòîãî äåêîäèðîâàíèÿ ñòðîêè èç òàáëèöû ñòðîê, ñîõðàíÿþùàÿ
** ðåçóëüòàò â áóôåð.  Ýòîò áóôåð ïîòîì ìîæåò áûòü âûâåäåí â îáðàòíîì
** ïîðÿäêå ïðîãðàììîé ðàñïàêîâêè.
*/
char *decode_string(unsigned char *buffer,unsigned int code)
{
int i;

    i=0;
    while (code > 255)
    {
        *buffer++ = append_character[code];
        code=prefix_code[code];
        if (i++>=4094)
        {
            printf("Fatal error during code expansion.\n");
            exit();
        }
    }
    *buffer=code;
    return(buffer);
}
/*
** Ñëåäóþùèå äâå ïðîöåäóðû óïðàâëÿþò ââîäîì/âûâîäîì êîäîâ ïåðåìåííîé
** äëèíû.  Îíè äëÿ ÿñíîñòè íàïèñàíû ÷ðåçâû÷àéíî ïðîñòûìè è íå î÷åíü
** ýôôåêòèâíû.
*/
input_code(FILE *input)
{
unsigned int return_value;
static int input_bit_count=0;
static unsigned long input_bit_buffer=0L;
    while (input_bit_count <= 24)
    {
       input_bit_buffer |= (unsigned long) getc(input) << (24-input_bit_count);
       input_bit_count += 8;
    }
    return_value=input_bit_buffer >> (32-BITS);
    input_bit_buffer <<= BITS;
    input_bit_count -= BITS;
    return(return_value);
}
output_code(FILE *output,unsigned int code)
{
static int output_bit_count=0;
static unsigned long output_bit_buffer=0L;
    output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);
    output_bit_count += BITS;
    while (output_bit_count >= 8)
    {
        putc(output_bit_buffer >> 24,output);
        output_bit_buffer <<= 8;
        output_bit_count -= 8;
    }

Mark R. Nelson
Ïåðåâîä: Çàïîëüñêèé Ñ.À.

Ñàéò î ñæàòèè  >>  ARCTEST  >>  Ñðàâíèòåëüíûå òåñòû  |  Àëüòåðíàòèâíûå òåñòû  |  Ãðàôè÷åñêèå òåñòû  |  Íîâîñòè  |  Óòèëèòû  |  Ôàéë'ìåíåäæåðû  |  Îïèñàíèÿ  |  Ëèíêè  |  Necromancer's DN  |  Ïîääåðæêà

Ïîèñê: Ñïðàâêà Äåòàëüíûé çàïðîñ Ðàçìåð ñåðâåðà: 8069 ôàéëîâ 1215Ìá

Ñàéò î ñæàòèè >>
  Íîâèíêè | Î ñåðâåðå | Ñòàòèñòèêà

  Êíèãà "Ìåòîäû ñæàòèÿ äàííûõ" >>
     Óíèâåðñàëüíûå | Èçîáðàæåíèé | Âèäåî

  Ðàçäåëû >> Download (ñòàòüè+èñõîäíèêè) | Ññûëêè | Ru.compress | Arctest | Âèäåî | Êàòàëîã ññûëîê | Ôîðóì
  Ïðîåêòû >> Ä.Âàòîëèíà | À.Ðàòóøíÿêà | Ì.Ñìèðíîâà | Â.Þêèíà | Å.Øåëâèíà | À.Ôèëèíñêîãî | Ä.Øêàðèíà | Ñ.Îñíà÷à

Îñòàâüòå âàøè çàìå÷àíèÿ, ïðåäëîæåíèÿ, ìíåíèÿ!   Î íàéäåííûõ îøèáêàõ ïèøèòå íà compression_íà_graphicon.ru   © Ä.Âàòîëèí, À.Ðàòóøíÿê, Ì.Ñìèðíîâ, Â.Þêèí è äð., òåêñò, ñîñòàâ., 2001-2003     Project supported by Graphics & Media Lab    ÝÒÎÒ ÄÎÊÓÌÅÍÒ ÌÎÆÍÎ ÑÊÀ×ÀÒÜ C http://www.compression.ru/compression.ru/arctest/descript/lzwcomp.htm