Â. Â. Ñåìåíþê (e-mail: ecoding@mail.ru)
Âñå ïðàâà çàùèùåíû. Äîïóñêàåòñÿ èñïîëüçîâàíèå äàííîãî ìàòåðèàëà ñ îáÿçàòåëüíûì óêàçàíèåì àâòîðñòâà è ïðåäâàðèòåëüíûì óâåäîìëåíèåì àâòîðà. Îñîáî ïðèâåòñòâóþòñÿ âîïðîñû, çàìå÷àíèÿ è êîíñòðóêòèâíûå ïðåäëîæåíèÿ.
Àâòîð âûðàæàåò áëàãîäàðíîñòü Ìàêñèìó Çàõàðîâó,
ñâîåâðåìåííî ïðåäîñòàâèâøåìó íåêîòîðûå ìàòåðèàëû äëÿ äàííîé ðàáîòû.
1. Ñæàòèå ïðè ïåðåäà÷å èíôîðìàöèè: àëãîðèòìû, ïðîòîêîëû, ñòàíäàðòû
Ðàçäåë ïîñâÿùåí ðàññìîòðåíèþ îñíîâíûõ êîììóíèêàöèîííûõ ïðîòîêîëîâ è ñòàíäàðòîâ, îïèñûâàþùèõ èñïîëüçîâàíèå òåõ èëè èíûõ àëãîðèòìîâ ñæàòèÿ ïðè ïåðåäà÷å èíôîðìàöèè. Âíà÷àëå ðàññìàòðèâàþòñÿ ìîäåìíûå ïðîòîêîëû MNP, ñòàíäàðò V.42bis, ïðîòîêîë óïðàâëåíèÿ ñæàòèåì CCP, à òàêæå ìåòîäèêè ñæàòèÿ çàãîëîâêîâ ïàêåòîâ ïåðåäà÷è èíôîðìàöèè. Çàòåì âêðàòöå îïèñûâàåòñÿ ïðèíöèï äåéñòâèÿ ìåòîäà ADPCM, íàèáîëåå ÷àñòî èñïîëüçóåìîãî äëÿ ñæàòèÿ àóäèî ñèãíàëîâ.
1.1 Ïðîòîêîë MNP
Ïðîòîêîë MNP (Microcom Networking Protocol) áûë ðàçðàáîòàí Microcom Inc. äëÿ ìîäåìîâ, âûïóñêàåìûõ ôèðìîé.  íåì îïèñûâàþòñÿ ðàçëè÷íûå ïàðàìåòðû è ïðîöåäóðû ïåðåäà÷è èíôîðìàöèè, òàêèå êàê ôîðìàò ïåðåäà÷è áèòîâ, òèï ìîäóëÿöèè, ìåòîä êîððåêöèè îøèáîê è ò. ä. Âñå ñïåöèôèêàöèè ïðîòîêîëà ïîäðàçäåëÿþòñÿ íà êëàññû (óðîâíè). Êëàññû 5 è 7 (ñëåäóÿ òðàäèöèè, â äàëüíåéøåì èçëîæåíèè áóäåì íàçûâàòü èõ ïðîòîêîëàìè MNP5 è MNP7) èìåþò îòíîøåíèå ê ñæàòèþ èíôîðìàöèè. MNP îêàçàëñÿ äîñòàòî÷íî óäà÷íûì ïðîòîêîëîì è èñïîëüçóåòñÿ â áîëüøèíñòâå ñîâðåìåííûõ ìîäåìîâ.
Èç äâóõ óêàçàííûõ ïðîòîêîëîâ, ðåãëàìåíòèðóþùèõ ñïîñîáû ñæàòèÿ èíôîðìàöèè, íàèáîëüøåå ðàñïðîñòðàíåíèå ïîëó÷èë ïðîòîêîë MNP5. MNP5 ðåãëàìåíòèðóåò èñïîëüçîâàíèå äâóõóðîâíåâîé ñõåìû ñæàòèÿ, íà ïåðâîì óðîâíå êîòîðîé ïðèìåíÿåòñÿ ãðóïïîâîå êîäèðîâàíèå (RLE), à íà âòîðîì - àäàïòèâíîå ïðåôèêñíîå êîäèðîâàíèå. Îáðàáîòêà èíôîðìàöèè ïðîèçâîäèòñÿ â äâà ýòàïà: ñíà÷àëà èíôîðìàöèÿ ïîäâåðãàåòñÿ îáðàáîòêå ãðóïïîâûì êîäèðîâàíèåì, à çàòåì ïîëó÷åííàÿ êîäîâàÿ ïîñëåäîâàòåëüíîñòü “äîæèìàåòñÿ” ñ èñïîëüçîâàíèåì ïðåôèêñíîãî êîäèðîâàíèÿ. Ðàññìîòðèì äåòàëüíî êàæäûé àëãîðèòì.
Ðåàëèçàöèÿ ãðóïïîâîãî êîäèðîâàíèÿ â ïðîòîêîëå MNP5 âûãëÿäèò íåñêîëüêî íåñòàíäàðòíî. Åñëè â ïðîöåññå îáðàáîòêè èíôîðìàöèè âñòðåòèëèñü òðè è áîëåå èäóùèõ ïîäðÿä îäèíàêîâûõ ñèìâîëà, ïåðâûå òðè èç íèõ âûâîäÿòñÿ â èõ èñõîäíîì (íåçàêîäèðîâàííîì) âèäå, ïîñëå ÷åãî íà âûõîä ïîñòóïàåò ÷èñëî â âîñüìèáèòîâîì ïðåäñòàâëåíèè, îïðåäåëÿþùåå, ñêîëüêî åùå èäåíòè÷íûõ ñèìâîëîâ ñëåäóåò çà äàííûìè òðåìÿ. Ê ïðèìåðó, ïîñëåäîâàòåëüíîñòü “abaabaaabaaaaa” áóäåò çàêîäèðîâàíà íà âûõîäå àëãîðèòìà ãðóïïîâîãî êîäèðîâàíèÿ êàê “abaabaaa0baaa2”. Çàìåòèì, ÷òî â ñëó÷àå ñëåäîâàíèÿ ïîäðÿä òîëüêî òðåõ ñèìâîëîâ çà íèìè âñå ðàâíî äîëæíî âûâîäèòñÿ ÷èñëî ïîâòîðåíèé, äàæå íåñìîòðÿ íà òî, ÷òî îíî ðàâíî íóëþ. Ýòî íåîáõîäèìî äëÿ òîãî, ÷òîáû äåêîäåð â ïðîöåññå ðàáîòû ìîã ïðàâèëüíî èíòåðïðåòèðîâàòü êîäîâóþ ïîñëåäîâàòåëüíîñòü. Êàæäûé ðàç, êîãäà â ïðîöåññå äåêîäèðîâàíèÿ áóäåò âñòðå÷åíà ïîñëåäîâàòåëüíîñòü èç òðåõ îäèíàêîâûõ îêòåòîâ, î÷åðåäíîé îêòåò áóäåò ðàññìàòðèâàòüñÿ êàê ÷èñëî ïîâòîðåíèé.
 ïðîòîêîëå MNP5 ââîäèòñÿ îãðàíè÷åíèå íà êîëè÷åñòâî èäåíòè÷íûõ ñèìâîëîâ, îäíîâðåìåííî îáðàáàòûâàåìûõ ñ ïîìîùüþ ãðóïïîâîãî êîäèðîâàíèÿ. Êàê íè ñòðàííî, ýòî êîëè÷åñòâî îãðàíè÷èâàåòñÿ çíà÷åíèåì 250, à íå 255, ÷òî áîëåå ëîãè÷íî ñ ó÷åòîì òîãî, ÷òî äëÿ ïðåäñòàâëåíèÿ ÷èñëà ïîâòîðåíèé èñïîëüçóåòñÿ âîñüìèáèòîâîå êîäîâîå ïðîñòðàíñòâî. 5 íåèñïîëüçóåìûõ çíà÷åíèé çàðåçåðâèðîâàíû â ïðîòîêîëå äëÿ ñëóæåáíûõ öåëåé.
Àäàïòèâíîå ïðåôèêñíîå êîäèðîâàíèå, ïðèìåíÿåìîå íà âòîðîì óðîâíå ðàññìàòðèâàåìîé ñõåìû ñæàòèÿ, èñïîëüçóåò ñòàòè÷åñêóþ ñèñòåìó ïðåôèêñíûõ êîäîâ. Êàæäûé ïðåôèêñíûé êîä â ñèñòåìå ìîæåò áûòü óñëîâíî ðàçäåëåí íà ãîëîâíóþ ÷àñòü äëèíîé â òðè áèòà è îñòàòî÷íóþ ÷àñòü, äëèíà êîòîðîé ìîæåò âàðüèðîâàòüñÿ â èíòåðâàëå îò 1 áèòà äî 8 áèòîâ. Ãîëîâíàÿ ÷àñòü óêàçûâàåò îäíó èç âîñüìè ãðóïï, íà êîòîðûå ïîäðàçäåëÿþòñÿ âñå ïðåôèêñíûå êîäû â ñèñòåìå. Êîäû, ïðèíàäëåæàùèå îäíîé ãðóïïå, çà èñêëþ÷åíèåì ïîñëåäíåé ãðóïïû, èìåþò îäèíàêîâóþ äëèíó îñòàòî÷íîé ÷àñòè. Âîñåìü ãðóïï ñîäåðæàò ñîîòâåòñòâåííî 2, 2, 4, 8, 16, 32, 64, 129 êîäîâ. Ñèñòåìà ïðåôèêñíûõ êîäîâ âûãëÿäèò ñëåäóþùèì îáðàçîì (çíàê “|” äåëèò ïðåôèêñíûé êîä íà åãî ãîëîâíóþ è îñòàòî÷íóþ ÷àñòè; ãðóïïû çàêëþ÷åíû â ôèãóðíûå ñêîáêè): {“000|0”, “000|1”}, {“001|0”, “001|1”}, {“010|00”, ..., “010|11”}, {“011|000”, ... ,“011|111”}, {“100|0000”, ... ,“100|1111”}, {“101|00000”, ... , “101|11111”}, {“110|000000”, .... ,“110|111111”}, {“111|0000000”, ... ,“111|1111110”, “111|11111110”, “111|11111111”}.
Êàê âèäíî, ñèñòåìà ñîäåðæèò 257 ïðåôèêñíûõ êîäîâ. 256 èç íèõ ïðåäíàçíà÷åíû äëÿ êîäèðîâàíèÿ ñèìâîëîâ, à îñòàâøèéñÿ îäèí - “111|11111111” - çàðåçåðâèðîâàí äëÿ ñëóæåáíûõ öåëåé: îí âñåãäà ñòàâèòñÿ â êîíöå ïåðåäàâàåìîãî ñîîáùåíèÿ.
Àäàïòèâíîå êîäèðîâàíèå ñîïðÿæåíî ñî ñáîðîì ñòàòèñòèêè ïîÿâëåíèÿ ñèìâîëîâ â îáðàáîòàííîé ÷àñòè èíôîðìàöèè.  äàííîì ñëó÷àå ó÷èòûâàåòñÿ âñÿ îáðàáîòàííàÿ èíôîðìàöèÿ, à íå êàêîé-òî ôðàãìåíò. Äëÿ ýòîãî êàæäîìó èç 256 ñèìâîëîâ àëôàâèòà ñòàâèòñÿ â ñîîòâåòñòâèå ñ÷åò÷èê ÷àñòîòû ïîÿâëåíèÿ äàííîãî ñèìâîëà â îáðàáîòàííîé èíôîðìàöèè. Îñîáåííîñòü ñáîðà ñòàòèñòèêè ñîñòîèò â òîì, ÷òî ñ÷åò÷èê óâåëè÷èâàåòñÿ òîëüêî â ñëó÷àå, êîãäà îáðàáîòàííûé áàéò ïðåäñòàâëÿåò ñîáîé ñèìâîë â íåçàêîäèðîâàííîì ïðåäñòàâëåíèè. Òàêèì îáðàçîì, îêòåòû, ñîîòâåòñòâóþùèå ÷èñëó ïîâòîðåíèé, ïðè ñáîðå ñòàòèñòèêè íå ó÷èòûâàþòñÿ.
Ïðîáëåìà ïåðåïîëíåíèÿ ñ÷åò÷èêîâ â ðàññìàòðèâàåìîé ñõåìå ðåøàåòñÿ ñëåäóþùèì îáðàçîì: åñëè íåêîòîðûé ñ÷åò÷èê äîñòèãàåò ñâîåãî ïðåäåëüíîãî çíà÷åíèÿ, ðàâíîãî 255, ïðîèçâîäèòñÿ ìàñøòàáèðîâàíèå ñ÷åò÷èêîâ ñ êîýôôèöèåíòîì 2.
 ïðîöåññå îáðàáîòêè èíôîðìàöèè ñèìâîëàì àëôàâèòà äèíàìè÷åñêè ïðèñâàèâàþòñÿ ïðåôèêñíûå êîäû èç ïðèâåäåííîé âûøå ñèñòåìû. Ïðèñâîåíèå ïðîèñõîäèò ñ ó÷åòîì ÷àñòîòû ïîÿâëåíèÿ ñèìâîëà â îáðàáîòàííîé ÷àñòè èíôîðìàöèè, îïðåäåëÿåìîé ïî ñîîòâåòñòâóþùåìó çíà÷åíèþ ñ÷åò÷èêà - ñèìâîëàì, âñòðå÷àþùèìñÿ ðåæå ïî ñðàâíåíèþ ñ äðóãèìè ñèìâîëàìè, äîëæíû ñîîòâåòñòâîâàòü è áîëåå êîðîòêèå êîäû (ïðîöåäóðà äèíàìè÷åñêîãî ïðèñâàèâàíèÿ êîäîâ ñòðîãî ðåãëàìåíòèðóåòñÿ). Îáðàáîòêà êàæäîãî ñèìâîëà (â êà÷åñòâå ñèìâîëà ìîæåò âûñòóïàòü ÷èñëî ïîâòîðåíèé) âêëþ÷àåò â ñåáÿ òðè îïåðàöèè: çàìåíó ñèìâîëà ïðåôèêñíûì êîäîì ïðè êîäèðîâàíèè èëè èíòåðïðåòàöèþ ïðåôèêñíîãî êîäà ïðè äåêîäèðîâàíèè, îáíîâëåíèå ñ÷åò÷èêà, ñîîòâåòñòâóþùåãî äàííîìó ñèìâîëó è, â ñëó÷àå íåîáõîäèìîñòè, èçìåíåíèå ñîîòâåòñòâèÿ ìåæäó ñèìâîëàìè è ïðåôèêñíûìè êîäàìè.
Îïèñàííûé àëãîðèòì ñæàòèÿ îáëàäàåò ìàëîé ýôôåêòèâíîñòüþ. Ê ïðèìåðó, îáúåì îáû÷íîãî ïðåäñòàâëåíèÿ òåêñòîâîé èíôîðìàöèè, êàê ïðàâèëî, ìîæåò áûòü óìåíüøåí ñ ïðèìåíåíèåì äàííîãî àëãîðèòì íå áîëåå ÷åì â ïîëòîðà ðàçà. Áîëüøåé ýôôåêòèâíîñòüþ îáëàäàåò àëãîðèòì, ëåæàùèé â îñíîâå ïðîòîêîëà MNP7.
Ïðîòîêîë MNP7 ïðåäïèñûâàåò èñïîëüçîâàíèå íåñêîëüêî èíîé ñõåìû ñæàòèÿ, êîòîðàÿ òàêæå âêëþ÷àåò â ñåáÿ äâà óðîâíÿ îáðàáîòêè èíôîðìàöèè. Ïåðâûé óðîâåíü ïî÷òè ïîëíîñòüþ ïîâòîðÿåò ïåðâûé óðîâåíü ðàññìîòðåííîé âûøå ñõåìû ñæàòèÿ çà èñêëþ÷åíèåì òîãî, ÷òî äëÿ çàïèñè ÷èñëà ïîâòîðåíèé â ãðóïïîâîì êîäèðîâàíèè çäåñü èñïîëüçóåòñÿ íå 8, à 4 áèòà (ìàêñèìàëüíîå êîëè÷åñòâî ïîâòîðÿþùèõñÿ ñèìâîëîâ, îäíîâðåìåííî îáðàáàòûâàåìûõ ãðóïïîâûì êîäèðîâàíèåì, ðàâíî 18). Îäíàêî íà âòîðîì óðîâíå ñõåìû ïðèìåíÿåòñÿ àëãîðèòì, îòëè÷íûé îò àëãîðèòìà âòîðîãî óðîâíÿ ïðîòîêîëà MNP5.
Êîäèðîâàíèå êàæäîãî ñèìâîëà íà âòîðîì óðîâíå ñõåìû îñóùåñòâëÿåòñÿ ñ ó÷åòîì ïðåäûäóùåãî âñòðåòèâøåãîñÿ ñèìâîëà. Ïðè ýòîì èñïîëüçóåòñÿ ñòàòè÷åñêàÿ ñèñòåìà êîäîâ ïåðåìåííîé äëèíû, îòëè÷íàÿ îò òîé, êîòîðàÿ áûëà îïèñàíà âûøå. Âî âðåìÿ îáðàáîòêè èíôîðìàöèè ïðîèçâîäèòñÿ ñáîð ñòàòèñòèêè ïîÿâëåíèÿ ñèìâîëîâ â êîíòåêñòå ñèìâîëà, íåïîñðåäñòâåííî èì ïðåäøåñòâóþùåãî. Òàêèì îáðàçîì, êîëè÷åñòâî ñ÷åò÷èêîâ ïîÿâëåíèé ñèìâîëîâ ñîñòàâëÿåò óæå íå 256, à 256*256 = 65536 (÷èñëî âñåâîçìîæíûõ ïàð âèäà <ñèìâîë-ïðåäøåñòâåííèê, òåêóùèé ñèìâîë>). Ïðåôèêñíûå êîäû ðàñïðåäåëÿþòñÿ ñòðîãî ñ ó÷åòîì ÷àñòîòû ïîÿâëåíèÿ.  îòëè÷èå îò ïðåäûäóùåé ñõåìû, çäåñü ó÷èòûâàåòñÿ ÷àñòîòà ïîÿâëåíèÿ íå îäíîãî ñèìâîëà, à ñðàçó äâóõ (òî÷íåå, îäíîãî â êîíòåêñòå äðóãîãî).
Ðàññìîòðåííûé âêðàòöå àëãîðèòì ýôôåêòèâåí äëÿ èíôîðìàöèè, â êîòîðîé ÷àñòî âñòðå÷àþòñÿ îäèíàêîâûå ñèìâîëüíûå ñî÷åòàíèÿ (òàêèì ñâîéñòâîì, íàïðèìåð, îáëàäàåò òåêñòîâàÿ èíôîðìàöèÿ). Ýêñïåðèìåíòû ïîêàçûâàþò, ÷òî â íåêîòîðûõ ñëó÷àÿõ äàííûé àëãîðèòì â ïîëòîðà ðàçà îïåðåæàåò ïî ñòåïåíè ñæàòèÿ àëãîðèòì, ëåæàùèé â îñíîâå ïðîòîêîëà MNP5. Ê ñîæàëåíèþ, ïðîòîêîë MNP7 íå çàâîåâàë äîëæíîé ïîïóëÿðíîñòè, ÷òî, âåðîÿòíåå âñåãî, ïðîèçîøëî ïî ïðè÷èíå ïîâñåìåñòíîãî âíåäðåíèÿ âåñüìà ïåðñïåêòèâíîãî ñòàíäàðòà ñæàòèÿ èíôîðìàöèè V.42bis.
1.2 Ñòàíäàðò V.42bis
Ñòàíäàðò V.42bis ïðåäëîæåí ìåæäóíàðîäíûì êîíñóëüòàòèâíûì êîìèòåòîì ïî òåëåãðàôèè è òåëåôîíèè (CCITT) [23].  íåì îïèñûâàåòñÿ ïðîöåäóðà ñæàòèÿ èíôîðìàöèè, ðåêîìåíäóåìàÿ äëÿ èñïîëüçîâàíèÿ â îêîíå÷íîì ñåòåâîì îáîðóäîâàíèè òåëåôîííûõ ëèíèé ñâÿçè. Ñòàíäàðò V.42bis ÿâëÿåòñÿ íà ñåãîäíÿøíèé äåíü îäíèì èç íàèáîëåå ðàñïðîñòðàíåííûõ ñòàíäàðòîâ ñæàòèÿ èíôîðìàöèè ïðè åå ïåðåäà÷å ïî êîììóíèêàöèîííûì êàíàëàì.
Àëãîðèòì ñæàòèÿ, ïðåäëîæåííûé â ñòàíäàðòå V.42bis, îñíîâàí íà ñëîâàðíîì àëãîðèòìå LZW. Íåîáõîäèìî îòìåòèòü, ÷òî, âîïðåêè áûòóþùåìó ìíåíèþ î ïîëíîé èäåíòè÷íîñòè äàííûõ àëãîðèòìîâ, àëãîðèòì, ðåêîìåíäîâàííûé êîìèòåòîì CCITT, è àëãîðèòì LZW èìåþò ñóùåñòâåííûå îòëè÷èÿ.
Ñîãëàñíî ñòàíäàðòó V.42bis, âî âðåìÿ ðàáîòû àëãîðèòìà ñæàòèÿ ïîääåðæèâàåòñÿ ñëîâàðü, ïðåäñòàâëåííûé ñîâîêóïíîñòüþ èç 256 äåðåâüåâ (ëåñ), êàæäîå èç êîòîðûõ ñîîòâåòñòâóåò òîìó èëè èíîìó ñèìâîëó àëôàâèòà ñîîáùåíèé (ïîäðàçóìåâàåòñÿ, ÷òî èñïîëüçóåòñÿ âîñüìèáèòîâîå ïðåäñòàâëåíèå èñõîäíîé èíôîðìàöèè; âîîáùå ãîâîðÿ, ñòàíäàðò äîïóñêàåò èñïîëüçîâàíèå ïðîèçâîëüíîãî àëôàâèòà). Ïðè èíèöèàëèçàöèè ñëîâàðÿ êàæäîå äåðåâî ñîäåðæèò ðîâíî ïî îäíîìó êîðíåâîìó óçëó. Êàæäîìó óçëó â äåðåâå ïðèñâàèâàåòñÿ óíèêàëüíûé èíäåêñ. Êîëè÷åñòâî èíäåêñîâ íà íà÷àëüíîì ýòàïå êîäèðîâàíèÿ ðàâíî 259: 256 èíäåêñîâ ñîîòâåòñòâóþò 256 êîðíåâûì óçëàì äåðåâüåâ, à îñòàâøèåñÿ 3 çàðåçåðâèðîâàíû äëÿ ñëóæåáíûõ öåëåé (ñì. íèæå).
Ïðè îáðàáîòêå èíôîðìàöèîííîé ïîñëåäîâàòåëüíîñòè îñóùåñòâëÿåòñÿ ïîèñê ñòðîêè â ñëîâàðå, èìåþùåé íàèáîëüøåå ñîâïàäåíèå ñ íà÷àëîì êîäèðóåìîé ñèìâîëüíîé ïîñëåäîâàòåëüíîñòè. Ïðîöåäóðà ïîèñêà àíàëîãè÷íà ïðîöåäóðå ïîèñêà, èñïîëüçóåìîé â àëãîðèòìå LZW. Ïîèñê íà÷èíàåòñÿ ñ êîðíåâîãî óçëà è âåäåòñÿ ïîñëåäîâàòåëüíûì ñðàâíåíèåì ñèìâîëîâ, ñîîòâåòñòâóþùèõ óçëàì äåðåâà, ïðîõîäèìûì ïðè åãî îáõîäå ïî ìàðøðóòó, îïðåäåëÿåìîìó êîäèðóåìîé ñèìâîëüíîé ïîñëåäîâàòåëüíîñòüþ. Ïîèñê çàêàí÷èâàåòñÿ â îäíîì èç äâóõ ñëó÷àåâ:
1. íàéäåíî íàèáîëüøåå ñîâïàäåíèå;
2. ïðîèçîøëî ñëóæåáíîå ñîáûòèå.
Íàéäåííîé ñòðîêå â ñëîâàðå ñîîòâåòñòâóåò íåêîòîðûé èíäåêñ. Äàííûé èíäåêñ è âûñòóïàåò â êà÷åñòâå êîäà. Îáúåì êîäîâîãî ïðîñòðàíñòâà îïðåäåëÿåòñÿ îáùèì êîëè÷åñòâîì çàäåéñòâîâàííûõ èíäåêñîâ è, êàê ïðàâèëî, íàõîäèòñÿ â ëîãàðèôìè÷åñêîé çàâèñèìîñòè îò ýòîãî êîëè÷åñòâà.  ñîîòâåòñòâèè ñî ñòàíäàðòîì V.42bis, èçìåíåíèå äëèíû êîäîâîé êîìáèíàöèè â ïðîöåññå êîäèðîâàíèÿ äîëæíî ñîïðîâîæäàòüñÿ âûâîäîì â âûõîäíîé ïîòîê ñëóæåáíîãî èíäåêñà STEPUP. Ïîñëå èíòåðïðåòàöèè äàííîãî èíäåêñà â ïðîöåññå äåêîäèðîâàíèÿ ðàçìåð êîäîâîé êîìáèíàöèè äîëæåí áûòü óâåëè÷åí íà 1 áèò, ïðè÷åì âíå çàâèñèìîñòè îò òîãî, áûëî ëè ïîëíîñòüþ èñ÷åðïàíî ïðåäûäóùåå êîäîâîå ïðîñòðàíñòâî èëè íåò.
Ñóùåñòâóåò ñèòóàöèÿ, ïðè êîòîðîé, â ñîîòâåòñòâèè ñî ñòàíäàðòîì, íàéäåííàÿ ñòðîêà äîëæíà áûòü îòâåðãíóòà, è ïðè êîäèðîâàíèè äîëæåí áûòü çàäåéñòâîâàí èíäåêñ ñòðîêè, ïîëó÷åííîé óäàëåíèåì èç íàéäåííîé ñòðîêè êðàéíåãî ïðàâîãî ñèìâîëà (òàêàÿ "óðåçàííàÿ" ñòðîêà âñåãäà ïðèíàäëåæèò ñëîâàðþ, ÷òî îáóñëàâëèâàåòñÿ ñïîñîáîì âêëþ÷åíèÿ ñòðîê â ñëîâàðü). Ýòî ñëó÷àé, êîãäà íàéäåííàÿ ñòðîêà áûëà äîáàâëåíà â ñëîâàðü íà ýòàïå êîäèðîâàíèÿ, íåïîñðåäñòâåííî ïðåäøåñòâóþùåì òåêóùåìó. Äàííîå îãðàíè÷åíèå îáóñëîâëåíî ñòðåìëåíèåì óïðîñòèòü ïðîöåññ äåêîäèðîâàíèÿ (èíòåðïðåòàöèÿ èíäåêñà ñòðîêè, äîáàâëåííîé â ñëîâàðü íà ïðåäûäóùåì ýòàïå êîäèðîâàíèÿ, âûçûâàåò â ïðîöåññå äåêîäèðîâàíèÿ íåêîòîðûå çàòðóäíåíèÿ).
Ñëóæåáíîå ñîáûòèå èíèöèèðóåòñÿ èçâíå è ñâÿçàíî ñ íåîáõîäèìîñòüþ èçìåíåíèÿ ðåæèìà èëè ïàðàìåòðîâ êîäèðîâàíèÿ.  êà÷åñòâå ïðèìåðà ñëóæåáíîãî ñîáûòèÿ ìîæíî ïðèâåñòè çàïðîñ íà ðåèíèöèàëèçàöèþ ñëîâàðÿ (C-INIT), ïðè ïîñòóïëåíèè êîòîðîãî ñëîâàðü äîëæåí áûòü íåçàìåäëèòåëüíî ïðèâåäåí â ñâîå íà÷àëüíîå ñîñòîÿíèå.
Äîáàâëåíèå ñòðîê â ñëîâàðü ñâîäèòñÿ ê äîáàâëåíèþ î÷åðåäíîãî óçëà â äåðåâî è ïðèñâîåíèþ äàííîìó óçëó óíèêàëüíîãî èíäåêñà, ñîîòâåòñòâóþùåãî çíà÷åíèþ ñ÷åò÷èêà èíäåêñîâ, êîòîðîå ïîñëå äîáàâëåíèÿ ñòðîêè óâåëè÷èâàåòñÿ íà åäèíèöó (íà÷àëüíîå çíà÷åíèå ñ÷åò÷èêà ðàâíî 259). Ñòàíäàðò V.42bis ïðåäïèñûâàåò, ÷òî äîáàâëåíèå äîëæíî ïðîèçâîäèòüñÿ òîëüêî â òîì ñëó÷àå, êîãäà äëèíà äîáàâëÿåìîé ñòðîêè íå ïðåâûøàåò íåêîòîðîãî çàäàííîãî çíà÷åíèÿ (äàííîå çíà÷åíèå âûáèðàåòñÿ íåïîñðåäñòâåííî ïåðåä íà÷àëîì êîäèðîâàíèÿ).
Îäíî èç ãëàâíûõ ðàçëè÷èé ìåæäó ðàññìàòðèâàåìûì àëãîðèòìîì è àëãîðèòìîì LZW çàêëþ÷àåòñÿ â ðàçíîì ïîäõîäå ê ðåøåíèþ ïðîáëåìû ïåðåïîëíåíèÿ ñëîâàðÿ.  îòëè÷èå îò àëãîðèòìà LZW, â àëãîðèòìå, ðåêîìåíäóåìîì êîìèòåòîì CCITT, ïðè äîñòèæåíèè îáùèì êîëè÷åñòâîì óçëîâ íåêîòîðîãî ïðåäåëà ðåèíèöèàëèçàöèÿ äåðåâà íå ïðîèçâîäèòñÿ. Çäåñü äåéñòâóåò íåñêîëüêî èíîé ìåõàíèçì, ðàáîòà êîòîðîãî ñîñòîèò â ïðèñâîåíèè íîâîé ñòðîêå èíäåêñà óæå èìåþùåéñÿ â ñëîâàðå ñòðîêè ñ ïîñëåäóþùèì óäàëåíèåì ýòîé ñòàðîé ñòðîêè èç ñëîâàðÿ ïîèñêà. Äëÿ èçáåæàíèÿ çàòðóäíåíèé ñ îáíîâëåíèåì äåðåâà óäàëÿþòñÿ òîëüêî ñòðîêè, ñîîòâåòñòâóþùèå ëèñòîâûì óçëàì. Äåòàëüíî ìåõàíèçì ðàáîòàåò ñëåäóþùèì îáðàçîì.  ñëó÷àå, êîãäà çíà÷åíèå â ñ÷åò÷èêå èíäåêñîâ äîñòèãàåò ñâîåãî ïðåäåëüíîãî çíà÷åíèÿ, ñ÷åò÷èê ñáðàñûâàåòñÿ äî ñâîåãî íà÷àëüíîãî ñîñòîÿíèÿ (259) è óâåëè÷èâàåòñÿ äî òåõ ïîð, ïîêà óçåë, ñîîòâåòñòâóþùèé åãî òåêóùåìó ñîñòîÿíèþ, íå îêàæåòñÿ ëèñòîâûì (çàìåòèì, ÷òî êîðíåâûå óçëû â äàííîì ïðîöåññå íå ó÷àñòâóþò, òàê êàê çíà÷åíèå ñ÷åò÷èêà íèêîãäà íå ñîâïàäàåò ñ èíäåêñàìè ýòèõ óçëîâ). Èíäåêñ äàííîãî ëèñòîâîãî óçëà ïðèñâàèâàåòñÿ íîâîé ñòðîêå.  äàëüíåéøåì ïðè äîáàâëåíèè êàæäîé íîâîé ñòðîêè äîëæíà îñóùåñòâëÿòüñÿ âûøåîïèñàííàÿ ïðîöåäóðà.
Êàê èçâåñòíî, àëãîðèòì LZW â íåêîòîðûõ ñèòóàöèÿõ îêàçûâàåòñÿ êðàéíå íåýôôåêòèâíûì. Äàííàÿ îñîáåííîñòü áûëà ó÷òåíà ïðè ðàçðàáîòêå ñòàíäàðòà V.42bis. Ñòàíäàðò ïðåäóñìàòðèâàåò äâà ðåæèìà îáðàáîòêè èíôîðìàöèè: ðåæèì ñæàòèÿ (compressed mode) è ïðîçðà÷íûé ðåæèì (transparent mode).  ðåæèìå ñæàòèÿ èíôîðìàöèÿ êîäèðóåòñÿ ñ ïðèìåíåíèåì îïèñàííîãî âûøå àëãîðèòìà, à â ïðîçðà÷íîì ðåæèìå îíà ïîñòóïàåò íà âûõîä â èñõîäíîì (íåçàêîäèðîâàííîì) âèäå. Ïðîçðà÷íûé ðåæèì çàäåéñòâóåòñÿ â òîì ñëó÷àå, êîãäà êîäèðîâàíèå íà÷èíàåò ïðèâîäèòü ê óâåëè÷åíèþ îáúåìà èñõîäíîãî ïðåäñòàâëåíèÿ èíôîðìàöèîííîãî ïîòîêà. Âàæíî îòìåòèòü, ÷òî ïðè ðàáîòå â ïðîçðà÷íîì ðåæèìå èíôîðìàöèÿ ïî-ïðåæíåìó îáðàáàòûâàåòñÿ îïèñàííûì àëãîðèòìîì ñæàòèÿ, îäíàêî ïðè ýòîì íå ãåíåðèðóåòñÿ âûõîäíîé êîä. Òî æå ñàìîå ïðîèñõîäèò ïðè ðàáîòå â ïðîçðà÷íîì ðåæèìå íà ýòàïå äåêîäèðîâàíèÿ. Èñïîëüçîâàíèå “õîëîñòîãî õîäà” îáóñëàâëèâàåòñÿ íåîáõîäèìîñòüþ îïðåäåëåíèÿ ìîìåíòà âîçâðàùåíèÿ ñèñòåìû îáðàáîòêè èíôîðìàöèè îáðàòíî â ðåæèì ñæàòèÿ. Ðåøåíèå î ïåðåêëþ÷åíèè ìåæäó ðåæèìàìè äîëæíî îñóùåñòâëÿòüñÿ íà îñíîâå èíôîðìàöèè îá ýôôåêòèâíîñòè êîäèðîâàíèÿ â òåêóùèé ìîìåíò âðåìåíè. Ïðîöåäóðà ïðèíÿòèÿ òàêîãî ðåøåíèÿ ñïåöèàëüíî íå îãîâàðèâàåòñÿ â ñòàíäàðòå, ÷òî äàåò ðàçðàáîò÷èêàì àïïàðàòóðû íåêîòîðóþ ñâîáîäó ïðè åãî ðåàëèçàöèè.
Óïðàâëåíèå ñåàíñîì îáðàáîòêè èíôîðìàöèè â ðåàëèçàöèÿõ ðàññìàòðèâàåìîãî ñòàíäàðòà îñóùåñòâëÿåòñÿ ïîñðåäñòâàì ïåðåäà÷è ñëóæåáíîé èíôîðìàöèè. Äëÿ êàæäîãî ðåæèìà îáðàáîòêè èíôîðìàöèè ñòàíäàðòîì ïðåäóñìàòðèâàåòñÿ òðè ñëóæåáíûå êîäîâûå êîìáèíàöèè.  ðåæèìå ñæàòèÿ ýòî ñëóæåáíûå èíäåêñû ETM (èíôîðìèðóåò äåêîäåð î ïåðåõîäå â ïðîçðà÷íûé ðåæèì), FLUSH (èíôîðìèðóåò äåêîäåð î íåîáõîäèìîñòè âûðàâíèâàíèÿ êîäà ïî ãðàíèöå ñëåäóþùåãî îêòåòà) è STEPUP (èíôîðìèðóåò äåêîäåð î ðàñøèðåíèè êîäîâîãî ïðåäñòàâëåíèÿ èíäåêñîâ), à â ïðîçðà÷íîì ðåæèìå ýòî ñëóæåáíûå ñèìâîëû ECM (èíôîðìèðóåò äåêîäåð î ïåðåõîäå â ðåæèì ñæàòèÿ), EID (ñèìâîëèçèðóåò íàëè÷èå ñëóæåáíîãî ñèìâîëà â äàííûõ) è RESET (èíôîðìèðóåò äåêîäåð î íåîáõîäèìîñòè ðåèíèöèàëèçàöèè ñëîâàðÿ). Çäåñü ìîæåò âîçíèêíóòü âïîëíå çàêîííûé âîïðîñ: áëàãîäàðÿ ÷åìó ñòàíîâèòñÿ âîçìîæíîé ïåðåäà÷à ñëóæåáíûõ ñèìâîëîâ â ïðîçðà÷íîì ðåæèìå îáðàáîòêè èíôîðìàöèè? (Äåëî â òîì, ÷òî èñõîäíîå èíôîðìàöèîííîå ïðåäñòàâëåíèå îáû÷íî äîïóñêàåò èñïîëüçîâàíèå òîëüêî ñèìâîëîâ îáû÷íîãî àëôàâèòà ñîîáùåíèé.)  ñòàíäàðòå V.42bis äëÿ ýòîãî ïðåäëàãàåòñÿ ïðèìåíÿòü ýñêåéï-ñèìâîëû.  êà÷åñòâå ýñêåéï-ñèìâîëà âñåãäà âûñòóïàåò êàêîé-òî ñèìâîë èñõîäíîãî àëôàâèòà ñîîáùåíèé. Ïðè ïîñòóïëåíèè òàêîãî ñèìâîëà íà âõîä äåêîäåðà ñëåäóþùèé çà íèì ñèìâîë ðàññìàòðèâàåòñÿ êàê ñëóæåáíûé.  ñëó÷àå, êîãäà ñèìâîë, âûñòóïàþùèé â ðîëè ýñêåéï-ñèìâîëà, âñòðå÷àåòñÿ â îáðàáàòûâàåìîé èíôîðìàöèè, îí âûâîäèòñÿ â âûõîäíîé ïîòîê âñëåä çà ñëóæåáíûì ñèìâîëîì EID. Ïðè ýòîì ðîëü ýñêåéï-ñèìâîëà ïåðåäàåòñÿ äðóãîìó ñèìâîëó (ìåõàíèçì ïåðåäà÷è ñòðîãî ðåãëàìåíòèðîâàí). Ñëóæåáíûå ñèìâîëû, à òàêæå èíôîðìàöèîííûå ñèìâîëû çàïèñûâàþòñÿ â âîñüìèáèòîâîì ïðåäñòàâëåíèè. Íåèñïîëüçóåìûå çíà÷åíèÿ ñëóæåáíûõ ñèìâîëîâ (îò 3 äî 255) çàðåçåðâèðîâàíû äëÿ áóäóùåãî ïðèìåíåíèÿ.
Ïðèíÿòî ñ÷èòàòü, ÷òî
ðàññìîòðåííûé àëãîðèòì ñæàòèÿ ïî ýôôåêòèâíîñòè ïðåâîñõîäèò àëãîðèòìû, îïèñûâàåìûìè
â ïðîòîêîëàõ
MNP5
è MNP7.
Îäíàêî, â äåéñòâèòåëüíîñòè äåëî îáñòîèò íåñêîëüêî èíà÷å.  [25]
ïðèâîäÿòñÿ
ðåçóëüòàòû ñðàâíåíèÿ ýôôåêòèâíîñòè èñïîëüçîâàíèÿ ïðîòîêîëà MNP5
è
ðåàëèçàöèè ñòàíäàðòà V.42bis â ìîäåìå
AnCom-ST
2442. Íåêîòîðûå
èç íèõ ïðåäñòàâëåíû â ñëåäóþùåé òàáëèöå.
|
Ôàéë |
(áàéò) |
(áàéò/ñ) |
(áàéò/ñ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Êàê âèäíî èç ðåçóëüòàòîâ, àëãîðèòì, ïðåäëàãàåìûé â ñòàíäàðòå V.42bis, áîëüøå âñåãî ïîäõîäèò äëÿ ñæàòèÿ òåêñòîâîé èíôîðìàöèè. Ïðèìåíåíèå äàííîãî àëãîðèòìà ê äðóãèì òèïàì èíôîðìàöèè ÷àñòî îêàçûâàåòñÿ íåîïòèìàëüíûì ðåøåíèåì.
1.3 Óïðàâëåíèå ñæàòèåì â ïðîòîêîëå PPP
Ïðîòîêîë óïðàâëåíèÿ ñæàòèåì CCP (Compression Control Protocol) [14], âõîäÿùèé â ïðîòîêîë PPP (Point-to-Point Protocol), ðåãëàìåíòèðóåò èñïîëüçîâàíèå ðàçëè÷íûõ àëãîðèòìîâ ñæàòèÿ èíôîðìàöèè ïðè åå ïåðåäà÷å ìåæäó îêîíå÷íûìè óçëàìè ëèíèé ñâÿçè. Îí íåïîñðåäñòâåííî îòâå÷àåò çà âûáîð, íàñòðîéêó è óïðàâëåíèå ïðîöåññàìè ñæàòèÿ âî âðåìÿ ñîåäèíåíèÿ. Ïðîòîêîë äîïóñêàåò èñïîëüçîâàíèå ñëåäóþùèõ àëãîðèòìîâ ñæàòèÿ:
Îäèí èç ïðèâåäåííûõ àëãîðèòìîâ óæå áûë ïîäðîáíî îïèñàí âûøå. Äàííûé ïîäðàçäåë ïîñâÿùåí ðàññìîòðåíèþ àëãîðèòìîâ Predictor, Stac Electronics LZS è Microsoft PPC.OUI Predictor type 1 Predictor type 2 Puddle Jumper Hewlett-Packard PPC Stac Electronics LZS Microsoft PPC Gandalf FZA V.42bis compression BSD LZW Compress.
1.3.1 Àëãîðèòì Predictor
Àëãîðèòì Predictor [15] - îäèí èç íàèáîëåå áûñòðûõ àëãîðèòìîâ ñæàòèÿ. Îí îòíîñèòñÿ ê àëãîðèòìàì ñëîâàðíîé ãðóïïû è èñïîëüçóåò òàê íàçûâàåìîå êîíòåêñòíî-çàâèñèìîå êîäèðîâàíèå.
Âî âðåìÿ ðàáîòû àëãîðèòìà Predictor ïîääåðæèâàåòñÿ ñòðóêòóðà, èìåíóåìàÿ òàáëèöåé ïðåäñêàçàíèé (guess table). Ôèçè÷åñêè òàáëèöà ïðåäñêàçàíèé ïðåäñòàâëÿåò ñîáîé ìàññèâ èç 65536 ÿ÷ååê, êàæäàÿ èç êîòîðûõ ñîäåðæèò îäèí ñèìâîë 256-ñèìâîëüíîãî àëôàâèòà. Âî âðåìÿ ðàáîòû àëãîðèòìà ñîäåðæèìîå òàáëèöû ïðåäñêàçàíèé èñïîëüçóåòñÿ äëÿ ïðåäñêàçàíèÿ ïîÿâëåíèÿ î÷åðåäíîãî îáðàáàòûâàåìîãî ñèìâîëà ñ öåëüþ âûáîðà ñïîñîáà åãî êîäèðîâàíèÿ. Îáðàáîòêà ñèìâîëà ïðîèçâîäèòñÿ ñëåäóþùèì îáðàçîì. Ïî íåñêîëüêèì ñèìâîëàì, íåïîñðåäñòâåííî ïðåäøåñòâóþùèì êîäèðóåìîìó ñèìâîëó, âû÷èñëÿåòñÿ õýø-èíäåêñ - ÷èñëî â èíòåðâàëå îò 0 äî 65535. Ñîäåðæèìîå ñîîòâåòñòâóþùåé ÿ÷åéêè òàáëèöû ïðåäñêàçàíèé ñðàâíèâàåòñÿ ñ êîäèðóåìûì ñèìâîëîì.  ñëó÷àå ñîâïàäåíèÿ (âåðíîå ïðåäñêàçàíèå) ñèìâîë êîäèðóåòñÿ åäèíè÷íûì áèòîì; â ñëó÷àå æå îòñóòñòâèÿ ñîâïàäåíèÿ (îøèáî÷íîå ïðåäñêàçàíèå) êîä äëÿ ñèìâîëà ïðåäñòàâëÿåò ñîáîé ñîâîêóïíîñòü íóëåâîãî áèòà è èñõîäíîãî âîñüìèáèòîâîãî ïðåäñòàâëåíèÿ ñèìâîëà. Äëÿ óäîáñòâà áèòû, óêàçûâàþùèå íà íàëè÷èå èëè îòñóòñòâèå ñîâïàäåíèé, îáúåäèíÿþòñÿ â áëîêè ïî 8 áèòîâ (îêòåòû). Ïîñëåäíèì ýòàïîì îáðàáîòêè ÿâëÿåòñÿ çàïèñü îáðàáîòàííîãî ñèìâîëà â ÿ÷åéêó, ñèìâîë â êîòîðîé èñïîëüçîâàëñÿ äëÿ ïðåäñêàçàíèÿ (îáíîâëåíèå òàáëèöû ïðåäñêàçàíèé).
Äëÿ îñóùåñòâëåíèÿ êîððåêòíîé èíòåðïðåòàöèè ïîëó÷àåìîé êîäîâîé ïîñëåäîâàòåëüíîñòè òàáëèöà ïðåäñêàçàíèé äîëæíà ïîääåðæèâàòüñÿ è íà ýòàïå äåêîäèðîâàíèÿ, ïðè÷åì âñå èçìåíåíèÿ â òàáëèöå äîëæíû ïðîèçâîäèòüñÿ ñèíõðîííî íà îäíèõ è òåõ æå ýòàïàõ êîäèðîâàíèÿ è äåêîäèðîâàíèÿ. Ïðîöåññ äåêîäèðîâàíèÿ âåñüìà ïðîñò. Êîãäà âñòðå÷àåòñÿ áèò, óêàçûâàþùèé íà ñîâïàäåíèå, â âûõîäíîé ïîòîê âûâîäèòñÿ ñèìâîë, ïðèíàäëåæàùèé ÿ÷åéêå òàáëèöû, ñîîòâåòñòâóþùåé õýø-èíäåêñó, âû÷èñëÿåìîìó ïî íåñêîëüêèì ïîñëåäíèì äåêîäèðîâàííûì ñèìâîëàì. Åñëè áèò óêàçûâàåò íà îòñóòñòâèå ñîâïàäåíèÿ, äåêîäèðîâàíèå ñâîäèòñÿ ê ïðîñòîìó êîïèðîâàíèþ ñèìâîëà èç êîäîâîé ïîñëåäîâàòåëüíîñòè â âûõîäíóþ ïîñëåäîâàòåëüíîñòü. Ïîñëå äåêîäèðîâàíèÿ î÷åðåäíîãî ñèìâîëà çàïóñêàåòñÿ ïðîöåäóðà îáíîâëåíèÿ òàáëèöû ïðåäñêàçàíèé, ïîëíîñòüþ ýêâèâàëåíòíàÿ ïðîöåäóðå îáíîâëåíèÿ, ïðîèçâîäèìîé íà ýòàïå êîäèðîâàíèÿ.
Àëãîðèòì Predictor íå ïîëó÷èë øèðîêîãî ðàñïðîñòðàíåíèÿ íà ïðàêòèêå. Ïðè÷èíîé òîìó, ñêîðåå âñåãî, ïîñëóæèëà åãî íåäîñòàòî÷íàÿ ýôôåêòèâíîñòü.
1.3.2 Àëãîðèòì Stac Electronics LZS
Êàê ñëåäóåò èç íàçâàíèÿ, ïðàâàìè íà àëãîðèòì LZS [8] âëàäååò ôèðìà Stac Electronics. Àëãîðèòì ïðèíàäëåæèò ñåìåéñòâó LZ77 è ÿâëÿåòñÿ ïðîèçâîäíûì îò àëãîðèòìà LZSS.
 ïðîöåññå îáðàáîòêè èíôîðìàöèè àëãîðèòìîì LZS â ñëîâàðå, â ðîëè êîòîðîãî âûñòóïàþò 2 êèëîáàéòà îáðàáîòàííîé èíôîðìàöèè, êàæäûé ðàç ïðîèçâîäèòñÿ ïîèñê ñòðîêè, èìåþùåé äîñòàòî÷íî äëèííîå ñîâïàäåíèå ñ òåêóùåé êîäèðóåìîé ñèìâîëüíîé ïîñëåäîâàòåëüíîñòüþ. Ìèíèìàëüíàÿ äëèíà ñîâïàäåíèÿ ðàâíà äâóì áàéòàì.  ñëó÷àå îòñóòñòâèÿ ñîâïàäåíèé ïðèåìëåìîé äëèíû ïåðâûé ñèìâîë êîäèðóåìîé ïîñëåäîâàòåëüíîñòè âûâîäèòñÿ â åãî èñõîäíîì âîñüìèáèòîâîì ïðåäñòàâëåíèè (íåçàêîäèðîâàííûé ñèìâîë). Êîäîâûå êîìáèíàöèè, îïèñûâàþùèå ñîâïàäåíèÿ è íåçàêîäèðîâàííûå ñèìâîëû, ðàçëè÷àþòñÿ ñëóæåáíûìè áèòàìè: 0 îçíà÷àåò íåçàêîäèðîâàííûé ñèìâîë, à 1 - ñîâïàäåíèå.
Íàèáîëüøèé èíòåðåñ äëÿ ðàññìîòðåíèÿ â àëãîðèòìå LZS ïðåäñòàâëÿåò ñïîñîá êîäèðîâàíèÿ ñîâïàäåíèé. Êîäîâàÿ êîìáèíàöèÿ, îïèñûâàþùàÿ ñîâïàäåíèå, òàê æå, êàê è â àëãîðèòìå LZSS, ñîñòîèò èç äâóõ ÷àñòåé: ñìåùåíèÿ ïîçèöèè èäåíòè÷íîé ñòðîêè â áóôåðå ïîèñêà è äëèíû ñîâïàäåíèÿ. Ñìåùåíèå ìîæåò áûòü çàïèñàíî ñ èñïîëüçîâàíèåì 7 èëè 11 áèòîâ. Ñïîñîá çàïèñè ñìåùåíèÿ óêàçûâàåòñÿ ñ ïîìîùüþ ñëóæåáíîãî áèòà: 0 ñîîòâåòñòâóåò 11-áèòîâîìó ïðåäñòàâëåíèþ ñìåùåíèÿ, à 1 - 7-áèòîâîìó. Íóëåâîå ñìåùåíèå â 7-áèòîâîì ïðåäñòàâëåíèè çàðåçåðâèðîâàíî äëÿ óêàçàíèÿ êîíöà ôàéëà.
Äëèíà ñîâïàäåíèÿ çàïèñûâàåòñÿ
ïðåôèêñíûì êîäîì ïåðåìåííîé äëèíû. Íåáîëüøèì äëèíàì ñîâïàäåíèé ñòàâÿòñÿ
â ñîîòâåòñòâèå äëèííûå ïðåôèêñíûå êîäû. Ñîîòâåòñòâèå ìåæäó äëèíàìè ñîâïàäåíèé
è ïðåôèêñíûìè êîäàìè ïðåäñòàâëåíî â ñëåäóþùåé òàáëèöå:
| Äëèíà |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Àëãîðèòì LZS ÿâëÿåòñÿ àëãîðèòìîì, ðåàëüíî èñïîëüçóåìûì â êîììóíèêàöèîííûõ òåõíîëîãèÿõ. Äàííûé àëãîðèòì ÷àñòî ðåàëèçóåòñÿ íà àïïàðàòíîì óðîâíå â ìàðøðóòèçàòîðàõ.
1.3.3 Àëãîðèòì Microsoft PPC
Àëãîðèòì Microsoft PPC áûë ïðåäëîæåí ôèðìîé Microsoft êàê ÷àñòü îòäåëüíîãî ïðîòîêîëà ñæàòèÿ Microsoft PPCP (PPCP - Point-to-Point Compression Protocol) [12]. Äàííûé àëãîðèòì òàê æå, êàê è ïðåäûäóùèé àëãîðèòì, ÿâëÿåòñÿ ñëîâàðíûì àëãîðèòìîì ñåìåéñòâà LZ77.
Âî âðåìÿ ðàáîòû àëãîðèòìà ïðîèçâîäèòñÿ ïîèñê ñîâïàäåíèé â ÷àñòè îáðàáîòàííîé èíôîðìàöèè, íåïîñðåäñòâåííî ïðåäøåñòâóþùåé òåêóùåé îáðàáàòûâàåìîé ïîçèöèè. Ðàçìåð ñëîâàðÿ ðàâåí 8 êèëîáàéòàì. Êàê îáû÷íî, ïðè êîäèðîâàíèè èñïîëüçóþòñÿ êîäîâûå êîìáèíàöèè äâóõ òèïîâ: ïåðâûå îïèñûâàþò íåçàêîäèðîâàííûå ñèìâîëû, à âòîðûå ïðåäíàçíà÷åíû äëÿ îïèñàíèÿ ñîâïàäåíèé. Ìèíèìàëüíàÿ äëèíà ñîâïàäåíèÿ ðàâíà 3 áàéòàì.
Îñîáîãî âíèìàíèÿ çàñëóæèâàåò îðèãèíàëüíûé ñïîñîá êîäèðîâàíèÿ, èñïîëüçóåìûé â àëãîðèòìå Microsoft PPC. Íåçàêîäèðîâàííûå ñèìâîëû, ÷èñëîâîå ïðåäñòàâëåíèå êîòîðûõ íå ïðåâûøàåò 127, âûâîäÿòñÿ â âûõîäíîé ïîòîê â ñâîåì èñõîäíîì âèäå. Äëÿ êàæäîãî èç îñòàâøèõñÿ 128 ñèìâîëîâ êîäîâàÿ êîìáèíàöèÿ ïîëó÷àåòñÿ äîáàâëåíèåì ê 7 ìëàäøèì áèòàì èñõîäíîãî ïðåäñòàâëåíèÿ ñèìâîëà ïðåôèêñà “10”.
Êîä ñîâïàäåíèÿ ñòàíäàðòíûì îáðàçîì äåëèòñÿ íà êîä ñìåùåíèÿ ñîâïàäåíèÿ â ñëîâàðå ïîèñêà è êîä äëèíû ñîâïàäåíèÿ. Ñìåùåíèå ìîæåò áûòü çàêîäèðîâàíî îäíèì èç òðåõ ñïîñîáîâ. Åñëè ñìåùåíèå íå ïðåâîñõîäèò 63, êîä äëÿ ñìåùåíèÿ ïîëó÷àåòñÿ äîáàâëåíèåì ïðåôèêñà “1111” ê 6-áèòîâîìó ïðåäñòàâëåíèþ ñìåùåíèÿ.  ñëó÷àå, êîãäà ñìåùåíèå íàõîäèòñÿ â èíòåðâàëå îò 64 äî 320, êîä ïîëó÷àåòñÿ äîáàâëåíèåì ïðåôèêñà “1110” ê 8-áèòîâîìó ïðåäñòàâëåíèþ ðàçíîñòè ñìåùåíèå-64. Âî âñåõ îñòàëüíûõ ñëó÷àÿõ êîä ñìåùåíèÿ ïîëó÷àåòñÿ äîáàâëåíèåì ïðåôèêñà “110” ê 13-áèòîâîìó ïðåäñòàâëåíèþ ðàçíîñòè (ñìåùåíèå - 320).
Ñïîñîá êîäèðîâàíèÿ äëèí
ñîâïàäåíèé ïðåäñòàâëåí â ñëåäóþùåé òàáëèöå.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Áëàãîäàðÿ íàëè÷èþ ñëîâàðÿ ïîèñêà áîëüøåãî ðàçìåðà è áîëåå ýôôåêòèâíîãî ñïîñîáà êîäèðîâàíèÿ, àëãîðèòì Microsoft PPC, êàê ïðàâèëî, ïðåâîñõîäèò ïî ñòåïåíè ñæàòèÿ àëãîðèòì Stac Electronics LZS. Òåì íå ìåíåå, àëãîðèòì Microsoft PPC çíà÷èòåëüíî ðåæå ïðèìåíÿåòñÿ íà ïðàêòèêå, ÷òî, ñêîðåå âñåãî, îáóñëîâëåíî åãî ïîâûøåííîé ñëîæíîñòüþ.
1.4 Ñæàòèå çàãîëîâêîâ ïàêåòîâ ïåðåäà÷è èíôîðìàöèè
Ïðîáëåìà ñæàòèÿ çàãîëîâêîâ ïàêåòîâ ïåðåäà÷è èíôîðìàöèè ÿâëÿåòñÿ âåñüìà àêòóàëüíîé, èáî íåðåäêî âñòðå÷àþòñÿ ñèòóàöèè, êîãäà ðàçìåð çàãîëîâêà îêàçûâàåòñÿ ñðàâíèìûì ñ ðàçìåðîì âñåãî ïàêåòà. Ê ïðèìåðó, î÷åíü ÷àñòî ïðè ñîâìåñòíîì èñïîëüçîâàíèè èíòåðàêòèâíîé è ãðóïïîâîé ïåðåñûëêè äàííûõ äëÿ óìåíüøåíèÿ âðåìåíè îæèäàíèÿ èíòåðàêòèâíîãî ïàêåòà áîëüøîé ìàññèâ ïåðåäàåòñÿ ñ ïîìîùüþ ìàëåíüêèõ ïàêåòîâ. Òàê êàê êîëè÷åñòâî òàêèõ ïàêåòîâ îêàçûâàåòñÿ î÷åíü áîëüøèì, ýêîíîìè÷íîå ïðåäñòàâëåíèå èõ çàãîëîâêîâ ìîæåò ñóùåñòâåííî ïîâûñèòü ñêîðîñòü ïåðåäà÷è.  [10] áûëî ïîêàçàíî, ÷òî ïðèìåíåíèå ñòàíäàðòíûõ àëãîðèòìîâ â äàííîì ñëó÷àå íåîïòèìàëüíî, è áîëåå ýôôåêòèâíûé ïîäõîä ñâÿçàí ñ èñïîëüçîâàíèåì ñïåöèàëèçèðîâàííûõ àëãîðèòìîâ ñæàòèÿ.
Óìåíüøåíèå îáúåìà çàãîëîâêîâ ïàêåòîâ ïåðåäà÷è èíôîðìàöèè ñòàíîâèòñÿ âîçìîæíûì áëàãîäàðÿ òîìó, ÷òî ïàêåòû, ïðèíàäëåæàùèå åäèíîìó ïàêåòíîìó ïîòîêó, ÷àñòî ñîäåðæàò ñõîæèå çíà÷åíèÿ â íåêîòîðûõ ïîëÿõ çàãîëîâêà. Âñå ïîëÿ çàãîëîâêà ìîãóò áûòü óñëîâíî ðàçäåëåíû íà òðè òèïà: ïîëÿ ñ íåîïðåäåëåííûìè (ñëó÷àéíûìè) çíà÷åíèÿìè, ïîëÿ ñ ïîñòîÿííûìè çíà÷åíèÿìè è ïîëÿ ñ ïëàâíî ìåíÿþùèìèñÿ çíà÷åíèÿìè. Ñæàòèå çàãîëîâêîâ äîñòèãàåòñÿ çà ñ÷åò èñïîëüçîâàíèÿ ýêîíîìíûõ ñïîñîáîâ ïðåäñòàâëåíèÿ ïîëåé äâóõ ïîñëåäíèõ òèïîâ.
Áàçîâûì îáúåêòîì â òåõíîëîãèÿõ ñæàòèÿ çàãîëîâêîâ ïàêåòîâ ïåðåäà÷è èíôîðìàöèè ÿâëÿåòñÿ êîíòåêñò çàãîëîâêà ïàêåòà. Êîíòåêñòîì çàãîëîâêà ïàêåòà íàçûâàåòñÿ ñîâîêóïíîñòü çíà÷åíèé åãî ïîëåé, ïåðåäàâàåìûõ â îñîáîì ýêîíîìè÷íîì ôîðìàòå.  ïðîöåññå êîäèðîâàíèÿ è äåêîäèðîâàíèÿ îñóùåñòâëÿåòñÿ õðàíåíèå êîíòåêñòîâ îáðàáîòàííûõ (ïåðåäàííûõ èëè ïîëó÷åííûõ) ïàêåòîâ. Ïðè ýòîì êàæäîìó êîíòåêñòó ïðèñâàèâàåòñÿ åãî óíèêàëüíûé èäåíòèôèêàòîð.
Ðàññìîòðèì â îáùèõ ÷åðòàõ ïðîöåäóðó ýôôåêòèâíîé ïåðåäà÷è çàãîëîâêà êîììóíèêàöèîííîãî ïàêåòà. Ïîëÿ ñ ïîñòîÿííûìè èëè ïëàâíî ìåíÿþùèìèñÿ çíà÷åíèÿìè, êàê ïðàâèëî, íåïîñðåäñòâåííî íå ïåðåäàþòñÿ, à âìåñòî ýòîãî îñóùåñòâëÿåòñÿ ïåðåäà÷à íåêîòîðîé ñòðóêòóðû, ñîäåðæèìîå êîòîðîé ïîçâîëÿåò âîññòàíîâèòü èñêîìûå çíà÷åíèÿ ïîëåé. Äàííàÿ ñòðóêòóðà îáû÷íî âêëþ÷àåò â ñåáÿ èäåíòèôèêàòîð êîíòåêñòà íåêîòîðîãî îáðàáîòàííîãî ïàêåòà, ñîâîêóïíîñòü ôëàãîâ, óêàçûâàþùèõ íà õàðàêòåð ðàçëè÷èé ìåæäó çíà÷åíèÿìè òåõ èëè èíûõ ïîëåé çàãîëîâêîâ îáðàáîòàííîãî è òåêóùåãî ïåðåäàâàåìîãî ïàêåòîâ, è ïðåäñòàâëåíèå ýòèõ ðàçëè÷èé â îñîáîì ôîðìàòå. Ïîëÿ çàãîëîâêîâ, ñîäåðæàùèå íåîïðåäåëåííûå çíà÷åíèÿ, ïåðåäàþòñÿ â èõ èñõîäíîì ïðåäñòàâëåíèè â ñîñòàâå óêàçàííîé ñòðóêòóðû. Ýôôåêòèâíîñòü ïåðåäà÷è çàãîëîâêà çàâèñèò îò êîíêðåòíîãî ñïîñîáà ïðåäñòàâëåíèÿ ðàçëè÷èé ìåæäó ñîäåðæèìûì ïîëåé çàãîëîâêîâ òåêóùåãî ïåðåäàâàåìîãî ïàêåòà è îáðàáîòàííîãî ïàêåòà, êîíòåêñò êîòîðîãî óêàçûâàåòñÿ ñ èñïîëüçîâàíèåì èäåíòèôèêàòîðà. ×àùå âñåãî äëÿ ïðåäñòàâëåíèÿ ðàçëè÷èé ïðèìåíÿåòñÿ òàê íàçûâàåìîå äåëüòà êîäèðîâàíèå [10].
Àëãîðèòìû ñæàòèÿ ïàêåòîâ ïåðåäà÷è èíôîðìàöèè îáëàäàþò î÷åíü âûñîêîé ýôôåêòèâíîñòüþ. Òàê, îáúåì çàãîëîâêîâ ïàêåòîâ UDP è TCP ìîæåò áûòü óìåíüøåí äî 4-7 îêòåòîâ. (Çàìåòèì, ÷òî çàãîëîâêè ýòèõ ïàêåòîâ îáû÷íî âêëþ÷àþò â ñåáÿ äâóõîêòåòíóþ êîíòðîëüíóþ ñóììó.) Ïîäîáíàÿ ýôôåêòèâíîñòü ïîçâîëÿåò ñóùåñòâåííî ïîâûøàòü ñêîðîñòü ïåðåäà÷è èíôîðìàöèè ïî ìåäëåííûì ëèíèÿì ñâÿçè.
1.5 Ìåòîä ADPCM
Àäàïòèâíàÿ äèôôåðåíöèàëüíàÿ èìïóëüñíî-êîäîâàÿ ìîäóëÿöèÿ (ADPCM) ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì äèôôåðåíöèàëüíîãî êîäèðîâàíèÿ. Äàííûé ìåòîä ïðåäëîæåí â êà÷åñòâå ñòàíäàðòà êîìèòåòîì CCITT.
Ñîãëàñíî ðåêîìåíäàöèè
G.726
ê ñòàíäàðòó, ìåòîä ADPCM
ìîæåò áûòü
èñïîëüçîâàí äëÿ îñóùåñòâëåíèÿ äâóñòîðîííåãî ïðåîáðàçîâàíèÿ PCM-ñèãíàëà,
ïåðåäàâàåìîãî ïî êàíàëó ñ ïðîïóñêíîé ñïîñîáíîñòüþ 64 êáèò/c, â
PCM-ñèãíàë,
ïðåäíàçíà÷åííûé äëÿ ïåðåäà÷è ïî êàíàëàì ñ ìèíèìàëüíûìè ïðîïóñêíûìè ñïîñîáíîñòÿìè
40, 32, 24 èëè
16 êáèò/c. Ðàññìîòðèì âêðàòöå ïðîöåññ
êîäèðîâàíèÿ è äåêîäèðîâàíèÿ ìåòîäîì ADPCM.
Íà ïðèâåäåííîì âûøå ðèñóíêå èçîáðàæåíà ñòðóêòóðíàÿ ñõåìà ïðîöåññà êîäèðîâàíèÿ PCM-ñèãíàëà ìåòîäîì ADPCM. Âî âðåìÿ ðàáîòû ìåòîäà àäàïòèâíûé ïðåäñêàçàòåëü îñóùåñòâëÿåò ïðåäñêàçàíèå óðîâíÿ ïîñòóïàþùåãî ðàâíîìåðíî êâàíòîâàííîãî ñèãíàëà. Âõîäíîé ñèãíàë èìååò 256 óðîâíåé êâàíòîâàíèÿ è ÷àñòîòó äèñêðåòèçàöèè 8 êãö.  ñóììàòîðå ïðîèñõîäèò àëãåáðàè÷åñêîå ñëîæåíèå âõîäíîãî è ïðåäñêàçàííîãî ñèãíàëà. Ðàçíîñòíûé ñèãíàë ïîñòóïàåò â àäàïòèâíûé êâàíòîâàòåëü, ãäå ïðîèçâîäèòñÿ ëîãàðèôìè÷åñêîå êâàíòîâàíèå. ×èñëî óðîâíåé êâàíòîâàíèÿ, ñîãëàñíî ñòàíäàðòó, ìîæåò áûòü ðàâíî 16, 8, 4 èëè 2. (Ñîîòâåòñòâåííî ñèãíàë ìîæåò áûòü ïåðåäàí ïî êàíàëàì ñ ìèíèìàëüíûìè ïðîïóñêíûìè ñïîñîáíîñòÿìè 40, 32, 24 èëè 16 êáèò/c.) Äðóãèå ïàðàìåòðû êâàíòîâàíèÿ ÷àñòè÷íî îïðåäåëÿþòñÿ â ñòàíäàðòå, à ÷àñòè÷íî çàâèñÿò îò õàðàêòåðèñòèê îáðàáàòûâàåìîãî ñèãíàëà.
Ñ âûõîäà àäàïòèâíîãî êâàíòîâàòåëÿ ñèãíàë îäíîâðåìåííî ïîñòóïàåò â îáðàòíûé àäàïòèâíûé êâàíòîâàòåëü è â êàíàë ïåðåäà÷è. Îáðàòíûé àäàïòèâíûé êâàíòîâàòåëü ïðåäíàçíà÷åí äëÿ ïåðåâîäà ëîãàðèôìè÷åñêè êâàíòîâàííîãî PCM-ñèãíàëà â ðàâíîìåðíî êâàíòîâàííûé ðàçíîñòíûé ñèãíàë. Ïîëó÷àåìûé ðàçíîñòíûé ñèãíàë ìîæåò íå ñîâïàäàòü ñ èñõîäíûì ðàçíîñòíûì ñèãíàëîì. Îáðàòíîå ïðåîáðàçîâàíèå íåîáõîäèìî äëÿ òîãî, ÷òîáû îáåñïå÷èòü îäèíàêîâîå ïðåäñêàçàíèå íà ýòàïàõ êîäèðîâàíèÿ è äåêîäèðîâàíèÿ.
Ñ âûõîäà îáðàòíîãî àäàïòèâíîãî êâàíòîâàòåëÿ ðàâíîìåðíî êâàíòîâàííûé ðàçíîñòíûé ñèãíàë îäíîâðåìåííî ïîñòóïàåò íà âõîä àäàïòèâíîãî ïðåäñêàçàòåëÿ è íà âõîä ñóììàòîðà. Ïîñëåäíèé îñóùåñòâëÿåò ñóììèðîâàíèå äàííîãî ñèãíàëà ñ ïðåäñêàçàííûì ñèãíàëîì. Ïîëó÷åííûé â ðåçóëüòàòå ñóììèðîâàíèÿ ñèãíàë òàêæå ïîñòóïàåò íà âõîä àäàïòèâíîãî ïðåäñêàçàòåëÿ.
Àäàïòèâíûé ïðåäñêàçàòåëü îñóùåñòâëÿåò ïðåäñêàçàíèå íà îñíîâå 6 ïîñëåäíèõ âûáîðîê îáðàáàòûâàåìîãî ñèãíàëà. Ïðè ýòîì ó÷èòûâàþòñÿ îñîáåííîñòè äàííîãî ñèãíàëà. (Ó÷åò ïðîèçâîäèòñÿ ïîñðåäñòâàì àäàïòèâíîãî èçìåíåíèÿ ïàðàìåòðîâ ïðåäñêàçûâàþùåé ôóíêöèè.)
Íà ñëåäóþùåì ðèñóíêå ïðèâåäåíà ñòðóêòóðíàÿ ñõåìà ïðîöåññà äåêîäèðîâàíèÿ.
Ïðîöåññ äåêîäèðîâàíèÿ â ìåòîäå ADPCM ñõîæ ñ ïðîöåññîì êîäèðîâàíèÿ. ADPCM-ñèãíàë ïîñòóïàåò íà âõîä îáðàòíîãî àäàïòèâíîãî êâàíòîâàòåëÿ. Ðàâíîìåðíî êâàíòîâàííûé ðàçíîñòíûé ñèãíàë îäíîâðåìåííî ïîñòóïàåò íà ñóììàòîð è àäàïòèâíûé ïðåäñêàçàòåëü. Íà ñóììàòîð òàêæå ïîñòóïàåò ïðåäñêàçàííûé ñèãíàë. Ïîëó÷åííûé â ðåçóëüòàòå ñëîæåíèÿ âîññòàíîâëåííûé ñèãíàë îäíîâðåìåííî ïîñòóïàåò â àäàïòèâíûé ïðåäñêàçàòåëü è ñèíõðîíèçàòîð.  ñèíõðîíèçàòîð òàêæå ïîñòóïàåò âõîäíîé ADPCM-ñèãíàë. Ñèíõðîíèçàòîð ñëóæèò äëÿ óñòðàíåíèÿ íàêîïëåííîãî âðåìåííîãî èñêàæåíèÿ. Ñ âûõîäà ñèíõðîíèçàòîðà PCM-ñèãíàë ïîñòóïàåò â âûõîäíîé êàíàë ñ ïðîïóñêíîé ñïîñîáíîñòüþ 64 êáèò/c.
Ïðàâèëüíîå äåêîäèðîâàíèå ñèãíàëà ñòàíîâèòñÿ âîçìîæíûì áëàãîäàðÿ îäèíàêîâûì ïðåäñêàçàíèÿì, âû÷èñëÿåìûì àäàïòèâíûì ïðåäñêàçàòåëåì íà ýòàïàõ êîäèðîâàíèÿ è äåêîäèðîâàíèÿ. Îòìåòèì, ÷òî îäíèì èç âàæíûõ óñëîâèé êîððåêòíîãî äåêîäèðîâàíèÿ ÿâëÿåòñÿ îòñóòñòâèå îøèáîê â êàíàëå ïåðåäà÷è.
Ìåòîä ADPCM ÷àùå âñåãî ïðèìåíÿåòñÿ äëÿ ñæàòèÿ àóäèî ñèãíàëîâ è, â îñîáåííîñòè, ãîëîñîâûõ ñîîáùåíèé. Îí íàøåë ñâîå ïðèìåíåíèå âî ìíîãèõ óñòðîéñòâàõ ïåðåäà÷è çâóêîâîé èíôîðìàöèè, íà÷èíàÿ ñ ãîëîñîâûõ ìîäåìîâ è çàêàí÷èâàÿ ìîáèëüíûìè òåëåôîíàìè.
2. Ïåðñïåêòèâíûå òåõíîëîãèè ñæàòèÿ ïðè ïåðåäà÷å èíôîðìàöèè
Ïðîãðåññ âû÷èñëèòåëüíîé òåõíèêè ïîâñåìåñòíî ñòàâèò íà ïåðâûé ïëàí íîâûå ýôôåêòèâíûå òåõíîëîãèè. Ñàìûå ñîâðåìåííûå àëãîðèòìû è ìåòîäû ñæàòèÿ èíôîðìàöèè ñ ïîòåðÿìè è áåç ïîòåðü ïîñòîÿííî âíåäðÿþòñÿ â ïðàêòè÷åñêèå ïðèëîæåíèÿ. Ê îãðîìíîìó ñîæàëåíèþ, òåõíîëîãèè ñâÿçè îñòàëèñü íà ñåãîäíÿøíèé äåíü ÷óòü ëè íå åäèíñòâåííîé îáëàñòüþ, ãäå ñóùåñòâóþùèì ìåòîäèêàì ñæàòèÿ íå óäåëÿåòñÿ äîëæíîå âíèìàíèå.
Àâòîðîì áûëè ïðîâåäåíû èñïûòàíèÿ, öåëüþ êîòîðûõ áûëî âûÿñíåíèå òîãî, íàñêîëüêî ýôôåêòèâíî íàðàáîòàííûå òåõíîëîãèè ñæàòèÿ èñïîëüçóþòñÿ äëÿ óâåëè÷åíèÿ ñêîðîñòè ïåðåäà÷è èíôîðìàöèè. Âî âðåìÿ èñïûòàíèé íåñêîëüêî ôàéëîâ, ñîäåðæèìîå êîòîðûõ îòíîñèòñÿ ê íàèáîëåå ðàñïðîñòðàíåííûì òèïàì èíôîðìàöèè, ïåðåäàâàëèñü ìåæäó äâóìÿ äîñòàòî÷íî óäàëåííûìè ïóíêòàìè ëèíèè ñâÿçè. Èíôîðìàöèÿ ïîñòóïàëà ÷åðåç òåëåôîííóþ ëèíèþ â óçåë Internet-ïðîâàéäåðà, à çàòåì ÷åðåç ãëîáàëüíóþ ñåòü Internet îñóùåñòâëÿëàñü åå äàëüíåéøàÿ ïåðåäà÷à óäàëåííîìó àáîíåíòó. Âî âðåìÿ ïåðåäà÷è â îêîíå÷íûõ ïóíêòàõ ëèíèè ïðîèçâîäèëîñü êîäèðîâàíèå è äåêîäèðîâàíèå ïåðåäàâàåìîé èíôîðìàöèè ñ ïðèìåíåíèåì íàèáîëåå óäà÷íûõ íà ñåãîäíÿøíèé äåíü ðåàëèçàöèé ìåòîäîâ PPM, BW, à òàêæå äâóõóðîâíåâîé ñëîâàðíîé ñõåìû ñåìåéñòâà LZ77 (LZ). Äëÿ îñóùåñòâëåíèÿ îáðàáîòêè èíôîðìàöèè â îáîèõ ñëó÷àÿõ èñïîëüçîâàëñÿ êîìïüþòåð Pentium 166 (32 ìåãàáàéòà îïåðàòèâíîé ïàìÿòè) ïîä óïðàâëåíèåì îïåðàöèîííîé ñèñòåìû Windows 98. Îáðàáîò÷èêàì èíôîðìàöèè â ïðîöåññå êîäèðîâàíèÿ è äåêîäèðîâàíèÿ âûäåëÿëîñü ïî 5 ìåãàáàéò îïåðàòèâíîé ïàìÿòè. Äëÿ îñóùåñòâëåíèÿ ïåðåäà÷è èíôîðìàöèè ÷åðåç òåëåôîííóþ ëèíèþ èñïîëüçîâàëñÿ ìîäåì 3Com Sporster 56k V.90 (ìàêñèìàëüíàÿ ñêîðîñòü ïåðåäà÷è - 33600 áèò/ñ).
Íèæå ïðèâåäåíû ðåçóëüòàòû
ïðîâåäåííûõ èñïûòàíèé. Áûëî ó÷òåíî ñóììàðíîå âðåìÿ êîäèðîâàíèÿ, äåêîäèðîâàíèÿ
è ïåðåäà÷è. Êîýôôèöèåíòû â òàáëèöå ïîêàçûâàþò, âî ñêîëüêî ðàç ïðèìåíåíèå
òîé èëè èíîé ìåòîäèêè ñæàòèÿ ïîçâîëèëî óâåëè÷èòü ñêîðîñòü ïåðåäà÷è èíôîðìàöèè.
|
|
(êèëîáàéò) |
ïðîòîêîëû |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
×èñëà ãîâîðÿò ñàìè çà ñåáÿ: ñîâðåìåííûå ìåòîäû ñæàòèÿ îêàçûâàþòñÿ ñóùåñòâåííî áîëåå ýôôåêòèâíûìè â ñðàâíåíèè ñ ìåòîäàìè, ðåàëüíî ïðèìåíÿåìûìè íà ïðàêòèêå.  ñëó÷àå ñ ôàéëîì “oranges.jpg”, ñîäåðæàùèì ìàëîèçáûòî÷íûå äàííûå è ïðàêòè÷åñêè íå ïîääàþùèìñÿ ñæàòèþ, íåáîëüøîå ïàäåíèå ïðîèçâîäèòåëüíîñòè ïðè èñïîëüçîâàíèè íîâûõ ìåòîäèê ñæàòèÿ ñâÿçàíî ñ îòñóòñòâèåì â íèõ àëãîðèòìà ïðåäâàðèòåëüíîãî äåòåêòîðà, ôóíêöèåé êîòîðîãî ÿâëÿåòñÿ îïðåäåëåíèå âîçìîæíîñòè óìåíüøåíèÿ îáúåìà ïðåäñòàâëåíèÿ òîé èëè èíîé èíôîðìàöèè. Ïðè íàëè÷èè òàêîãî äåòåêòîðà ïàäåíèÿ ïðîèçâîäèòåëüíîñòè ìîæíî èçáåæàòü.
Íåîáõîäèìî ïðèçíàòü, ÷òî âî âðåìÿ èñïûòàíèé áûëè çàäåéñòâîâàíû ñåðüåçíûå âû÷èñëèòåëüíûå ðåñóðñû. Îäíàêî íà ñåãîäíÿøíèé äåíü áîëüøèíñòâî âû÷èñëèòåëüíûõ ñèñòåì îáëàäàþò ïðîèçâîäèòåëüíîñòüþ, ïðåâîñõîäÿùåé ïðîèçâîäèòåëüíîñòü ñèñòåìû, èñïîëüçîâàííîé äëÿ èñïûòàíèé.
Èñõîäÿ èç âûøåñêàçàííîãî,
ìîæíî ñäåëàòü âûâîä î íåîáõîäèìîñòè ïðèìåíåíèÿ â êîììóíèêàöèîííûõ òåõíîëîãèÿõ
ñîâðåìåííûõ âûñîêîýôôåêòèâíûõ àëãîðèòìîâ ñæàòèÿ.
Ëèòåðàòóðà
- Barbir A., Carr D., Simpson W. PPP Gandalf FZA Compression Protocol. - RFC1993. - August, 1996.
- Casner S., Jacobson V. Compressing IP/UDP/RTP Headers for Low-Speed Serial Links. - RFC2508. - February, 1999.
- Degermark M., Nordgren B., Pink S. IP Header Compression. - RFC2507. - February, 1999.
- Deutsch P. , Gailly J-L. ZLIB Compressed Data Format Specification version 3.3. - RFC1950. - May, 1996. - http://compression.ru/download/articles/lz/rfc1950_pdf.rar
- Deutsch P. DEFLATE Compressed Data Format Specification version 1.3. - RFC1951. - May, 1996. - http://compression.ru/download/articles/lz/rfc1951_pdf.rar
- Deutsch P. GZIP file format specification version 4.3. - RFC1952. - May, 1996.
- Engan M., Casner S., Bormann C. IP Header Compression over PPP. - RFC2509. - February, 1999.
- Friend R., Simpson W. PPP Stac LZS Compression Protocol. - RFC1974. - August, 1996.
- Friend R., Monsour R. IP Payload Compression Using LZS. - RFC2395. - December, 1998.
- Jacobson V. Compressing TCP/IP headers for low-speed serial links. - RFC1144. - February, 1990.
- Mathur S., Lewis M. Compressing IPX Headers Over WAN Media (CIPX). - RFC1553. - December, 1993.
- Pall G. Microsoft Point-To-Point Compression (MPPC) Protocol. - RFC2118. - March, 1997.
- Pereira R. IP Payload Compression Using DEFLATE. - RFC2394. - December, 1998.
- Rand D. The PPP Compression Control Protocol (CCP). - RFC1962. - June, 1996.
- Rand D. PPP Predictor Compression Protocol. - RFC1978. - August, 1996.
- Salomon D. Data compression. - Springer. - 1997. - P. 56-62.
- Schneider K., Friend R. PPP LZS-DCP Compression Protocol (LZS-DCP). - RFC1967. - August, 1996.
- Schneider K., Venters S. PPP for Data Compression in Data Circuit-Terminating Equipment (DCE). - RFC1976. - August, 1996.
- Schremp D., Black J., Weiss J. PPP Magnalink Variable Resource Compression. - RFC1975. - August, 1996.
- Schryver V. PPP BSD Compression Protocol. - RFC1977. - August, 1996.
- Woods J. PPP Deflate Protocol. - RFC1979. - August, 1996.
- Shacham A., Monsour R., Pereira R., Thomas M. IP Payload Compression Protocol (IPComp). - RFC2393. - December, 1998.
- CCITT Data Compression Procedures for Data Circuit Terminating Equipment (DCE) Using Error Correction Procedures. Recommendation V.42 bis. - CCITT. - January, 1990.
- The Implementation of G.726 Adaptive Differential Pulse Code Modulation (ADPCM) on TMS320C54x DSP // Texas Instruments Europe. - July, 1997.
-
Äóäîðîâ Þ. Ïðîòîêîë ñæàòèÿ äàííûõ
äëÿ ìîäåìîâ V.42bis. - http://www.modem.od.ua/lib/lib_protocol_v42bis.html èëè
http://compression.ru/download/
articles/lz/dudorov_v42bis_compression.htm
Posted in May 2000.
Òåêñò ñ "êîñìåòè÷åñêèìè" èñïðàâëåíèÿìè Ìàêñèìà Ñìèðíîâà, 28.05.2003