Êîìïðåññèÿ äàííûõ ïðè îðãàíèçàöèè óäàëåííîãî äîñòóïà ê êîìïüþòåðíûì ñåòÿì


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

Êîìïðåññèÿ äàííûõ ïðè îðãàíèçàöèè
óäàëåííîãî äîñòóïà ê êîìïüþòåðíûì ñåòÿì

Ââåäåíèå

×èñëî óäàëåííûõ ëîêàëüíûõ ñåòåé ïîäðàçäåëåíèé, ñâÿçàííûõ ïî ðàçëè÷íûì òåëåêîììóíèêàöèîííûì êàíàëàì ñ èíôîðìàöèîííî-âû÷èñëèòåëüíûìè ñåòÿìè öåíòðàëüíûõ îôèñîâ ñâîèõ êîðïîðàöèé, ðàñòåò áûñòðûìè òåìïàìè. Â ÑØÀ, ñîãëàñíî ïðîãíîçàì, â 1997 ã. 94% âñåõ ËÂÑ áóäóò îñíàùåíû ñðåäñòâàìè óäàëåííîãî äîñòóïà (â 1993 ã. ýòîò ïîêàçàòåëü ñîñòàâëÿë îêîëî 40%). Ñîîòâåòñòâåííî, áûñòðûìè òåìïàìè ðàñòåò è ðûíîê îáîðóäîâàíèÿ äëÿ îáåñïå÷åíèÿ ñâÿçè ëîêàëüíûõ (LAN) è òåððèòîðèàëüíî-ðàñïðåäåëåííûõ (WAN) ñåòåé: â 1994 ã. â ìèðå áûëî ïðîäàíî îêîëî 370 òûñÿ÷ ìàðøðóòèçàòîðîâ óäàëåííîãî äîñòóïà [1].

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

Óâåëè÷åíèå ïðîïóñêíîé ñïîñîáíîñòè êàíàëîâ óäàëåííîãî äîñòóïà íåîáõîäèìî äëÿ ñåòåâûõ ïðèëîæåíèé åùå è ïîòîìó, ÷òî ïðè îðãàíèçàöèè óäàëåííîãî óçëà ËÂÑ ÷àñòü ïîëîñû ïðîïóñêàíèÿ êàíàëà LAN-WAN îêàçûâàåòñÿ çàíÿòîé ïåðåñûëêîé ñëóæåáíûõ ïàêåòîâ. Òàê, íàïðèìåð, ïîñêîëüêó ïðè ðàçðàáîòêå ñåòåâîé ÎÑ NetWare ôèðìîé Novell, âîïðîñû ýêîíîìèè ïîëîñû ïðîïóñêàíèÿ ñòîÿëè äàëåêî íå íà ïåðâîì ìåñòå, òî èñïîëüçîâàíèå ñåìåéñòâà ïðîòîêîëîâ IPX/SPX îêàçàëîñü êðàéíå íåýôôåêòèâíûì ïðè îðãàíèçàöèè óäàëåííîãî äîñòóïà ïî ìåäëåííûì êàíàëàì ñâÿçè. Âûçâàíî ýòî òåì, ÷òî ñåðâåðû, ìàðøðóòèçàòîðû, ñåòåâûå ïðèíòåðû è äðóãèå îáúåêòû ËÂÑ ïîñòîÿííî "ñîîáùàþò" î ñâîåì ïðèñóòñòâèè â ñåòè, ãåíåðèðóÿ ïàêåòû ïðîòîêîëîâ SAP (Service Advertising Protocol) è RIP (Routing Informationàl Protocol) è, êðîìå òîãî, â ñåòÿõ, ðàáîòàþùèõ ïîä óïðàâëåíèåì ÎÑ NetWare, ñåðâåð ãåíåðèðóåò â ñåòü òàê íàçûâàåìûå "watchdog"-çàïðîñû, ÷òîáû îïðåäåëèòü, ïðîäîëæàåò ëè òîò èëè èíîé ïîëüçîâàòåëü ðàáîòàòü â ñåòè. Ïîëîæåíèå óñóãóáëÿåòñÿ åùå è òåì, ÷òî â ñåòÿõ Ethernet ñóùåñòâóþò îãðàíè÷åíèÿ íà ìèíèìàëüíóþ äëèíó ïàêåòà, ïîýòîìó äëÿ ïåðåäà÷è äàæå îäíîãî áàéòà èíôîðìàöèè äëèíà ñåòåâîãî ïàêåòà âñå ðàâíî ñîñòàâèò 64 áàéòà.

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

* öèôðîâûå ñåòè ñ èíòåãðàëüíûì ñåðâèñîì - ISDN, ñ ïðîïóñêíîé ñïîñîáíîñòüþ îò 64 Êáèò/ñ äî 1.5 Ìáèò/ñ;

* êàíàëû Ò1 è Å1 ïðîèçâîäèòåëüíîñòüþ 1.536 è 2 Ìáèò/ñ ñîîòâåòñòâåííî, à òàêæå ëèíèè Ò3, îáåñïå÷èâàþùèå ñêîðîñòü ïåðåäà÷è äàííûõ äî 44.736 Ìáèò/ñ;

* îïòîâîëîêîííûå ëèíèè ñâÿçè SONET (Synchronous Optical NETwork), ÷üÿ ïðîïóñêíàÿ ñïîñîáíîñòü ñîñòàâëÿåò îò 51.84 Ìáèò/ñ äî 13 Ãáèò/ñ.

Â òî æå âðåìÿ, íåñìîòðÿ íà òî, ÷òî ñòîèìîñòü óñëóã òåëåôîííûõ êîìïàíèé ïîñòîÿííî ñíèæàåòñÿ, öåíà èñïîëüçîâàíèÿ ñêîðîñòíûõ êàíàëîâ îñòàåòñÿ äîñòàòî÷íî âûñîêîé. Òàê, â ÑØÀ óñëóãè ïî àðåíäå ëèíèè Ò1 êîìïàíèè AT&T íà ðàññòîÿíèå â 225 ìèëü (îêîëî 365 êì) îáõîäÿòñÿ ïîëüçîâàòåëÿì â 4 159 äîëë. â ìåñÿö, à âî Ôðàíöèè, íàïðèìåð, åæåìåñÿ÷íàÿ ïëàòà çà ïîëüçîâàíèå ëèíèåé Å1 íà ðàññòîÿíèå â òå æå 225 ìèëü äîñòèãàåò 14 440 äîëë. ÑØÀ [2]. Ïðè ýòîì öåíà ïîëüçîâàíèÿ ñïåöèàëüíûìè ëèíèÿìè ñóùåñòâåííî âîçðàñòàåò ñ óâåëè÷åíèåì ðàññòîÿíèÿ ìåæäó óäàëåííûìè ñåãìåíòàìè ËÂÑ: àðåíäà ëèíèè Ò1 íà ðàññòîÿíèå ìåæäó âîñòî÷íûì è çàïàäíûì ïîáåðåæüÿìè ÑØÀ ñîñòàâëÿåò óæå îêîëî 14 000 äîëë. â ìåñÿö. Ñòîèìîñòü àðåíäû ëèíèé Ò3 â 6-10 ðàç âûøå, ÷åì ëèíèé Ò1.

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

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

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

Âèäû êîìïðåññèè äàííûõ

Ðàçíîîáðàçíûå ïðîäóêòû äëÿ ñæàòèÿ äàííûõ â ñèñòåìàõ êîììóíèêàöèé LAN-WAN ìîæíî ïîäðàçäåëèòü íà äâà áîëüøèõ êëàññà: ïðîãðàììíîå îáåñïå÷åíèå è àïïàðàòíûå ñðåäñòâà.

Îáúåì ïðîäàæ ïðîãðàììíûõ ïðîäóêòîâ ñæàòèÿ äàííûõ äî ïîñëåäíåãî âðåìåíè çíà÷èòåëüíî îòñòàâàë îò îáúåìà ïðîäàæ àïïàðàòíûõ ñðåäñòâ, îäíàêî, ïî ìåðå øèðîêîãî ðàñïðîñòðàíåíèÿ òàêèõ ïîïóëÿðíûõ ïðîãðàìì, êàê, íàïðèìåð, DoubleSpace, Stacker, à òàêæå óòèëèò ñåðèè PkZip, Arc, Arj è äð., íà ýòîì ñåãìåíòå ðûíêà íà÷àëñÿ íàñòîÿùèé áóì. Â ñâÿçè ñ ýòèì àíàëèòèêè ïðåäñêàçûâàþò ñóùåñòâåííûé ðîñò îáúåìîâ ïðîäàæ ïðîãðàììíûõ ñðåäñòâ ñæàòèÿ äàííûõ: ñ 25 ìëí.äîëë. â 1993 ã. äî 160 ìëí.äîëë. â 1997 ã. [3]. Â òî æå âðåìÿ, ïðîãðàììíûå ïðîäóêòû ñæàòèÿ äàííûõ èñïîëüçóþòñÿ â îñíîâíîì äëÿ ýêîíîìèè ìåñòà íà ìàãíèòíûõ íîñèòåëÿõ è íå ïðèãîäíû äëÿ ðàáîòû â ñåòè â ðåæèìå on-line. Òàêîå ïðîãðàììíîå îáåñïå÷åíèå èñïîëüçóåòñÿ â ðåæèìå off-line - ïî êàáåëüíûì ëèíèÿì ïåðåäàþòñÿ óæå ïðåäâàðèòåëüíî ñæàòûå äàííûå.

Àïïàðàòíûå óñòðîéñòâà ñæàòèÿ äàííûõ îáû÷íî îáåñïå÷èâàþò ìåíåå âûñîêóþ ñòåïåíü êîìïðåññèè, è èõ ñòîèìîñòü çà÷àñòóþ çíà÷èòåëüíî âûøå ñòîèìîñòè ïðîãðàììíûõ ïðîäóêòîâ. Êðîìå òîãî, ñóùåñòâåííûì íåäîñòàòêîì áîëüøèíñòâà àïïàðàòíûõ óñòðîéñòâ ÿâëÿåòñÿ èõ îðèåíòàöèÿ íà ðàáîòó òîëüêî ñ êàêèì-ëèáî îäíèì âèäîì ïðèëîæåíèé èëè òèïîì äàííûõ. Îäíàêî, íà ñåãîäíÿøíèé äåíü òîëüêî óñòðîéñòâà àïïàðàòíîãî ñæàòèÿ äàííûõ ìîãóò îáåñïå÷èòü ðàáîòó â ïðèëîæåíèÿõ ðåàëüíîãî âðåìåíè, êîãäà êîìïðåññèÿ è ïåðåäà÷à äàííûõ ïî ñåòè ïðîèñõîäèò ïðàêòè÷åñêè îäíîâðåìåííî. Øèðîêîå ïðèìåíåíèå àïïàðàòíûå ñðåäñòâà êîìïðåññèè íàõîäÿò òàêæå â îáëàñòè ïåðåäà÷è âèäåî- è àóäèîñèãíàëîâ (íàïðèìåð, ðàçëè÷íûå âèäû ïëàò îáðàáîòêè âèäåîèçîáðàæåíèÿ).

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

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

Äëÿ ñæàòèÿ àóäèîñèãíàëà, íàïðèìåð, êîìïàíèÿ Gandalf ðàçðàáîòàëà âûñîêîýôôåêòèâíûé àëãîðèòì CELP (Codebook Excited Linear Prediction), ÿâëÿþùèéñÿ êîìáèíàöèåé âîëíîâûõ (waveform) ìåòîäîâ è ìåòîäîâ êîäèðîâàíèÿ èñòî÷íèêà (source coding). Ñóòü âîëíîâûõ ìåòîäîâ ñîñòîèò â öèôðîâîì êîäèðîâàíèè àìïëèòóäû àíàëîãîâîãî ñèãíàëà, à êîäèðîâàíèå èñòî÷íèêà çàêëþ÷àåòñÿ â èñïîëüçîâàíèè äâóõ òèïîâ ãåíåðàòîðîâ çâóêîâûõ ñèãíàëîâ è ìåíÿþùåãîñÿ âî âðåìåíè ôèëüòðà. Çâóêîâîé ñèãíàë ðàçáèâàåòñÿ íà áëîêè, äëÿ êàæäîãî èç êîòîðûõ îïðåäåëÿåòñÿ íàáîð ïàðàìåòðîâ: óñòàíîâêè ôèëüòðà, àìïëèòóäà è ò.ä. ßâëÿÿñü äîñòàòî÷íî ýôôåêòèâíûì ñ òî÷êè çðåíèÿ ñòåïåíè ñæàòèÿ, êîäèðîâàíèå èñòî÷íèêà â òî æå âðåìÿ îáåñïå÷èâàåò õóäøåå êà÷åñòâî ñèãíàëà ïî ñðàâíåíèþ ñ âîëíîâûìè ìåòîäàìè. Àëãîðèòì CLEP, îáúåäèíÿÿ âîçìîæíîñòè îáîèõ ìåòîäîâ, ïîçâîëÿåò äîñòè÷ü âûñîêîé ïðîèçâîäèòåëüíîñòè ïðè ñîõðàíåíèè õîðîøåãî êà÷åñòâà ñèãíàëà. Â òåõíîëîãèè CLEP ïðèìåíÿåòñÿ òàêæå òàáëèöà îáðàçöîâ çâóêîâûõ ñèãíàëîâ (codebook), çàïèñàííûõ â öèôðîâîì âèäå, êîòîðûå ñðàâíèâàþòñÿ ñ âõîäÿùèì çâóêîâûì ñèãíàëîì. Íàèáîëåå ïîäõîäÿùèé îáðàçåö ñèãíàëà çàòåì è ïåðåñûëàåòñÿ íà óäàëåííûé óçåë ñåòè.

Äëÿ äîñòóïà â ðåæèìå on-line ïîòåðÿ èëè èçìåíåíèå â ïðîöåññå ñæàòèÿ äàæå îäíîãî áèòà èíôîðìàöèè ïðèâîäèò ê "ôàòàëüíûì" ïîñëåäñòâèÿì: íåâîçìîæíîñòè ïðî÷åñòü ôàéë, çàâèñàíèþ èëè íåêîððåêòíîé ðàáîòå ïðîãðàììíîãî îáåñïå÷åíèÿ è ò.ä. Â ñâÿçè ñ ýòèì â áîëüøèíñòâå ïðèëîæåíèé, â òîì ÷èñëå è â êîìïüþòåðíûõ ñåòÿõ, èñïîëüçóþòñÿ ìåòîäû êîìïðåññèè áåç ïîòåðè èíôîðìàöèè, êðàòêèé îáçîð êîòîðûõ ìû è äàäèì íèæå. (×èòàòåëþ, æåëàþùåìó ïîëó÷èòü áîëåå ôóíäàìåíòàëüíûå ïðåäñòàâëåíèÿ îá àëãîðèòìàõ ñæàòèÿ èíôîðìàöèè, ðåêîìåíäóåì îáðàòèòüñÿ ê ðàáîòàì [4, 5, 6]).

Îñíîâíûå ìåòîäû êîìïðåññèè

Òåîðåòè÷åñêèå îñíîâû ìåòîäîâ ñæàòèÿ èíôîðìàöèè áûëè çàëîæåíû â êîíöå ñîðîêîâûõ ãîäîâ, êîãäà áûëà îïóáëèêîâàíà ñòàòüÿ Êëîäà Øåííîíà (Claude Shannon) "Ìàòåìàòè÷åñêàÿ òåîðèÿ êîììóíèêàöèé". Â íåé âïåðâûå áûëî ñôîðìóëèðîâàíî ïîëîæåíèå î òîì, ÷òî ýíòðîïèÿ ëþáîãî áëîêà èíôîðìàöèè ðàâíà âåðîÿòíîñòè åãî ïîÿâëåíèÿ âî âñåì ìàññèâå äàííûõ. Ñîîòâåòñòâåííî, íàèáîëåå ÷àñòî ïîâòîðÿþùèåñÿ áëîêè ÿâëÿþòñÿ è íàèáîëåå "èçáûòî÷íûìè" (redundant) è ìîãóò áûòü ïðåäñòàâëåíû â áîëåå ñæàòîì âèäå. Íà ñåãîäíÿøíèé äåíü ñóùåñòâóåò ìíîæåñòâî ðàçëè÷íûõ àëãîðèòìîâ ñæàòèÿ äàííûõ, ïîäðàçäåëÿþùèõñÿ íà íåñêîëüêî îñíîâíûõ ãðóïï:

* àëãîðèòìû êîäèðîâàíèÿ ïîâòîðîâ;
* âåðîÿòíîñòíûå ìåòîäû;
* àðèôìåòè÷åñêèå ìåòîäû;
* "ìåòîä ñëîâàðåé" (dictionary).

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

Êîäèðîâàíèå ïîâòîðîâ (Run-Length Encoding)

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

"Êëàññè÷åñêèé" âàðèàíò ýòîãî ìåòîäà ïðåäóñìàòðèâàåò çàìåíó ïîñëåäîâàòåëüíîñòè ïîâòîðÿþùèõñÿ ñèìâîëîâ íà ñòðîêó, ñîäåðæàùóþ ñàì ýòîò ñèìâîë, è ÷èñëî, ïîêàçûâàþùåå, ñêîëüêî ðàç ýòîò ñèìâîë ïîâòîðÿåòñÿ. Íàïðèìåð, ñòðîêà 'AAAAAACCCCCEEEFFFFFF' áóäåò çàïèñàíà â âèäå: '6A5C3E6F'. Â òî æå âðåìÿ ïðèìåíåíèå ýòîãî ìåòîäà äëÿ ñæàòèÿ òåêñòîâûõ èëè èñïîëíÿåìûõ (EXE, COM) ôàéëîâ îêàçûâàåòñÿ íåýôôåêòèâíûì.

Âåðîÿòíîñòíûå ìåòîäû ñæàòèÿ

Ê âåðîÿòíîñòíûì ìåòîäàì îòíîñÿòñÿ àëãîðèòìû Øåííîíà-Ôýíî (Shannon-Fano) è Õàôôìàíà (Huffman). Â îñíîâå ýòèõ àëãîðèòìîâ ëåæèò èäåÿ ïîñòðîåíèÿ "äåðåâà", ïîëîæåíèå ñèìâîëà íà "âåòâÿõ" êîòîðîãî îïðåäåëÿåòñÿ ÷àñòîòîé åãî ïîÿâëåíèÿ â ôàéëå. Êàæäîìó ñèìâîëó ïðèñâàèâàåòñÿ êîä, äëèíà êîòîðîãî îáðàòíî ïðîïîðöèîíàëüíà ÷àñòîòå ïîÿâëåíèÿ ñèìâîëà â ôàéëå. Ðàññìîòðèì ïðèìåð èñïîëüçîâàíèÿ ìåòîäà Øýííîíà-Ôýíî:

Ïóñòü èìååòñÿ ñëîâî METHOD. Äîïóñòèì, ÷òî ÷àñòîòà ïîÿâëåíèÿ ñèìâîëîâ îïðåäåëÿåòñÿ â âèäå (òàáë. 1). Çäåñü ìû èñïîëüçóåì ïðîèçâîëüíûå çíà÷åíèÿ âåðîÿòíîñòè ïîÿâëåíèÿ ñèìâîëîâ èñõîäÿ èç òîãî, ÷òî íàèáîëåå ÷àñòî âñòðå÷àþùèåñÿ áóêâû àíãëèéñêîãî ÿçûêà - E, O, H. Â êàæäîì ðåàëüíîì ìàññèâå äàííûõ ÷àñòîòà ïîÿâëåíèÿ ñèìâîëîâ ìîæåò îòëè÷àòüñÿ îò ïðèâåäåííîé íàìè, îäíàêî ýòî íå âëèÿåò íà ïðèíöèï ðàáîòû ìåòîäà.

Ñèìâoë ×àñòîòà Êîä

M 2 011

E 8 00

T 3 010

H 4 110

O 6 10

D 1 111

Òàáëèöà. 1. Êîäû ñèìâîëîâ â ñòðîêå "METHOD" (àëãîðèòì Øåííîíà-Ôýíî).

Ðàçäåëèì ñòðîêó "METHOD" íà äâå ÷àñòè òàê, ÷òîáû ñóììû ÷àñòîò ïîÿâëåíèÿ ñèìâîëîâ â íèõ áûëè ïðèáëèçèòåëüíî ðàâíû:

2(M)+8(E)+3(T)*4(H)+6(O)+1(D). Òåïåðü íà÷íåì ñòðîèòü "äåðåâî" ïî ñõåìå: íà êàæäîé "âåòâè" ïîðöèè ñèìâîëîâ ñ áîëüøåé ÷àñòîòîé áóäåò ïðèñâàèâàòüñÿ äâîè÷íûé íîëü, à ñ ìåíüøåé - äâîè÷íàÿ åäèíèöà (ðèñ. 2). Â ðåçóëüòàòå, êàæäûé èç ñèìâîëîâ ïîëó÷àåò ñâîé êîä, ïî êîòîðîìó ê íåìó ìîæíî äîáðàòüñÿ ñ âåðøèíû "äåðåâà", ïðè ýòîì ÷åì ÷àùå âñòðå÷àåòñÿ ñèìâîë â ôàéëå, òåì áëèæå îí ê âåðøèíå äåðåâà è, çíà÷èò, òåì êîðî÷å åãî àäðåñíûé êîä.

Ìåòîä Õàôôìàíà î÷åíü ïîõîæ íà ìåòîä Øåííîíà-Ôýíî, íî ñòðîèòåëüñòâî "äåðåâà" â íåì íà÷èíàåòñÿ íå ñ "âåðøèíû", à ñ "êîðíåé" (ðèñ. 3). Ñóììà ÷àñòîò ïîÿâëåíèé äâóõ ñàìûõ ðåäêî âñòðå÷àþùèõñÿ ñèìâîëîâ (D è Ì) ðàâíà 3, ñèìâîëîâ Í è Ò - 7. Äàëåå, ïðèñâàèâàÿ âåòâÿì äåðåâà äâîè÷íûå íóëè è åäèíèöû, òàê æå, êàê è â ïðåäûäóùåì ìåòîäå, ïîäíèìàåìñÿ ê "âåðøèíå", ïîëó÷àÿ êîä äëÿ êàæäîãî ñèìâîëà.

Ñóùåñòâóþò äâå ðàçíîâèäíîñòè ñòàòèñòè÷åñêèõ ìåòîäîâ, ðàçëè÷àþùèõñÿ ñïîñîáîì îïðåäåëåíèÿ âåðîÿòíîñòè ïîÿâëåíèÿ êàæäîãî ñèìâîëà â ôàéëå:
- ñòàòè÷åñêèå (static), èñïîëüçóþùèå ôèêñèðîâàííóþ òàáëèöó ÷àñòîòû ïîÿâëåíèÿ ñèìâîëîâ â ôàéëå, ðàññ÷èòûâàåìóþ ïåðåä íà÷àëîì ïðîöåññà ñæàòèÿ;
- àäàïòèâíûå (adaptive), â êîòîðûõ ÷àñòîòà ïîÿâëåíèÿ ñèìâîëîâ âñå âðåìÿ ìåíÿåòñÿ - ïî ìåðå ñ÷èòûâàíèÿ íîâîãî áëîêà äàííûõ èç ôàéëà ïðîèñõîäèò ïåðåðàñ÷åò íà÷àëüíûõ çíà÷åíèé ÷àñòîò.

Ñòàòèñòè÷åñêèå ìåòîäû, õàðàêòåðèçóþùèåñÿ õîðîøèì áûñòðîäåéñòâèåì è íå òðåáóþùèå çíà÷èòåëüíûõ ðåñóðñîâ îïåðàòèâíîé ïàìÿòè, íàøëè øèðîêîå ïðèìåíåíèå â ìíîãî÷èñëåííûõ ïðîãðàììàõ-àðõèâàòîðàõ, íàïðèìåð, ARC, PkZip è äð.

Àðèôìåòè÷åñêèå ìåòîäû

Îñíîâíûå ïðèíöèïû àðèôìåòè÷åñêîãî êîäèðîâàíèÿ áûëè ðàçðàáîòàíû â êîíöå 70-õ ãîäîâ. Àðèôìåòè÷åñêîå êîäèðîâàíèå, òàê æå êàê è âåðîÿòíîñòíûå ìåòîäû, èñïîëüçóåò â êà÷åñòâå îñíîâû òåõíîëîãèè ñæàòèÿ âåðîÿòíîñòü ïîÿâëåíèÿ ñèìâîëà â ôàéëå, îäíàêî ñàì ïðîöåññ àðèôìåòè÷åñêîãî êîäèðîâàíèÿ èìååò ïðèíöèïèàëüíûå îòëè÷èÿ. Â ðåçóëüòàòå àðèôìåòè÷åñêîãî êîäèðîâàíèÿ ñèìâîëüíàÿ ïîñëåäîâàòåëüíîñòü (ñòðîêà) çàìåíÿåòñÿ äåéñòâèòåëüíûì ÷èñëîì áîëüøå íóëÿ è ìåíüøå åäèíèöû.

Ðàññìîòðèì ïðîöåññ àðèôìåòè÷åñêîãî êîäèðîâàíèÿ ñëîâà "REDUNDANCE" (èçáûòî÷íîñòü). ×àñòîòà ïîÿâëåíèÿ êàæäîé áóêâû â ýòîì ñëîâå ðàâíà 0.1 çà èñêëþ÷åíèåì áóêâ E, D è N, êîòîðûå âñòðå÷àþòñÿ äâàæäû, è, ñîîòâåòñòâåííî, âåðîÿòíîñòü èõ ïîÿâëåíèÿ ðàâíà 0.2. Äàëåå êàæäîé áóêâå ïðèñâàèâàåòñÿ èíòåðâàë âåðîÿòíîñòè (range), äëèíà êîòîðîãî ðàññ÷èòûâàåòñÿ èñõîäÿ èç âåðîÿòíîñòè èõ ïîÿâëåíèÿ â ñëîâå (òàáë. 2).

Áóêâà Âåðîÿòíîñòü Èíòåðâàë

A 0.1 0.0-0.1

C 0.1 0.1-0.2

D 0.2 0.2-0.4

E 0.2 0.4-0.6

N 0.2 0.6-0.8

R 0.1 0.8-0.9

U 0.1 0.9-1.0

Òàáëèöà 2. Èíòåðâàëû âåðîÿòíîñòè äëÿ ñèìâîëîâ â ñëîâå Redundance.

Äàëüíåéøóþ ïðîöåäóðó àðèôìåòè÷åñêîãî ñæàòèÿ ïîÿñíèì ñ ïîìîùüþ òàáë. 3. Ïåðâàÿ áóêâà ñëîâà - 'R' - ïîëó÷àåò èíòåðâàë ñ íèæíåé ãðàíèöåé 0.8 è ñ âåðõíåé - 0.9. Íèæíÿÿ ãðàíèöà èíòåðâàëà è ñòàíîâèòñÿ ïåðâîé çíà÷àùåé öèôðîé êîäà. Çàòåì ïðîèçâîäèòñÿ ðàñ÷åò ãðàíèö ïîäèíòåðâàëîâ äëÿ êàæäîé ïîñëåäóþùåé áóêâû ïî àëãîðèòìó: íèæíÿÿ ãðàíèöà íîâîãî èíòåðâàëà ðàâíà ïðåäûäóùåé íèæíåé ãðàíèöå (äëÿ áóêâû Å ýòî 0.8) ïëþñ ïðîèçâåäåíèå ïðåäûäóùåãî èíòåðâàëà (äëÿ áóêâû Å ýòî áóäåò èíòåðâàë 0.9-0.8=0.1) è íèæíåé (äëÿ ðàñ÷åòà âåðõíåé ãðàíèöû èíòåðâàëà - âåðõíåé) ãðàíèöû èíòåðâàëà äëÿ áóêâû Å (ýòè çíà÷åíèÿ ñîîòâåòñòâåííî ðàâíû 0.4 è 0.6; èõ áåðåì èç òàáë. 2). Â ðåçóëüòàòå, ïîñëåäîâàòåëüíîñòü ñèìâîëîâ 'REDUNDANCE' çàìåíÿåòñÿ ÷èñëîì 0.8478570048. Òàêèì îáðàçîì, âìåñòî 10 áàéò íåîáõîäèìûõ äëÿ õðàíåíèÿ ñèìâîëüíîé ñòðîêè íàì ïîòðåáóåòñÿ âñåãî 4 áàéòà äëÿ çàïèñè ÷èñëà.

Ñèìâîë Íèæíÿÿ ãðàíèöà Âåðõíÿÿ ãðàíèöà

R 0.8 0.9

E 0.84 0.86

D 0.844 0.848

U 0.8476 0.848

N 0.84784 0.84792

D 0.847856 0.847872

A 0.8478560 0.848

N 0.84785696 0.84785728

C 0.847856992 0.847857024

E 0.8478570048 0.8478570432

Òàáëèöà 3. Ïîøàãîâîå ïðåäñòàâëåíèå ñòðîêè REDUNDANCE ìåòîäîì àðèôìåòè÷åñêîãî êîäèðîâàíèÿ.

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

Ìåòîä ñëîâàðåé

Àëãîðèòì "ìåòîä ñëîâàðåé" áûë âïåðâûå îïèñàí â ðàáîòàõ À.Ëåìïåëÿ è Äæ. Çèâà (Abraham Lempel, Jacob Ziv) â 1977-78 ãã., ïîýòîìó ýòîò ìåòîä ÷àñòî íàçûâàåòñÿ Lempel-Ziv èëè ñîêðàùåííî LZ. Hà ñåãîäíÿøíèé äåíü LZ-àëãîðèòì è åãî ìîäèôèêàöèè ïîëó÷èëè íàèáîëåå øèðîêîå ðàñïðîñòðàíåíèå ïî ñðàâíåíèþ ñ äðóãèìè ìåòîäàìè êîìïðåññèè. Â åãî îñíîâå ëåæèò èäåÿ çàìåíû íàèáîëåå ÷àñòî âñòðå÷àþùèõñÿ ïîñëåäîâàòåëüíîñòåé ñèìâîëîâ (ñòðîê) â ôàéëå ññûëêàìè íà "îáðàçöû", õðàíÿùèåñÿ â ñïåöèàëüíî ñîçäàâàåìîé òàáëèöå (ñëîâàðå). Òàê, íàïðèìåð, ñîçäàâ ñëîâàðü, ñîäåðæàùèé 65536 íàèáîëåå óïîòðåáèòåëüíûõ ñëîâ, ìîæíî ïðåäñòàâèòü òåêñòîâûå ôàéëû â âèäå ïîñëåäîâàòåëüíîñòè 16-áèòîâûõ ññûëîê íà "ìåñòî" äàííîãî ñëîâà â ñëîâàðå.

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

Ìíîæåñòâî ìîäèôèêàöèé ìåòîäà LZ: LZW, LZ77, LZSS è äð., àêòèâíî èñïîëüçóåòñÿ â ðàçëè÷íûõ ïðèëîæåíèÿõ. Òàê, íàïðèìåð, ìåòîä LZW ïðèìåíÿåòñÿ äëÿ ñæàòèÿ äàííûõ â ìîäåìàõ êàòåãîðèè V.42bis; LZ77-â óòèëèòàõ PkZip, Stacker è DoubleSpace, à òàêæå âî ìíîãèõ ñèñòåìàõ àïïàðàòíîãî ñæàòèÿ äàííûõ.

Ïåðñïåêòèâû ïðåîäîëåíèÿ íåñîâìåñòèìîñòè

Ìíîãîîáðàçèå ìåòîäîâ (à òàêæå ðàçëè÷íûõ âàðèàíòîâ è ìîäèôèêàöèé êàæäîãî èç ìåòîäîâ) ïîçâîëÿåò ïðîèçâîäèòåëÿì àïïàðàòíûõ óñòðîéñòâ ñæàòèÿ äàííûõ âûáðàòü îïòèìàëüíûé, èñõîäÿ èç òðåáîâàíèé, ïðåäúÿâëÿåìûõ ê ðàáîòå â êîíêðåòíûõ ïðèëîæåíèÿõ.

Â òî æå âðåìÿ ñåðüåçíîé ïðîáëåìîé ñòàíîâèòñÿ îáåñïå÷åíèå ñîâìåñòèìîñòè ðàçëè÷íûõ ìîäåëåé êîììóíèêàöèîííîãî îáîðóäîâàíèÿ. Âî ìíîãèõ ñëó÷àÿõ, ïðèîáðåòÿ îäèí ðàç îáîðóäîâàíèå, ïîëüçîâàòåëü îêàçûâàåòñÿ "ïðèâÿçàííûì" ê ïðîäóêöèè èìåííî ýòîãî ïðîèçâîäèòåëÿ. Â ñâÿçè ñ ýòèì âîçíèêëà íåîáõîäèìîñòü âûðàáîòêè åäèíûõ ñòàíäàðòíûõ ïðîãðàììíûõ è àïïàðàòíûõ ìåòîäîâ ñæàòèÿ èíôîðìàöèè. Íà âûðàáîòêó ñòàíäàðòíûõ àëãîðèòìîâ êîìïðåññèè íàïðàâëåíû óñèëèÿ Êîíñîðöèóìà ïðîèçâîäèòåëåé óñòðîéñòâ CSU/DSU (Channel Service Unit/Data Service Unit).

----------------------------------------------------

Ïëàíèðóåòñÿ, ÷òî áóäóò ðàçðàáîòàíû äâà îñíîâíûõ ñòàíäàðòà:

Ñòàíäàðòíûé àëãîðèòì êîìïðåññèè äëÿ ñèíõðîííîé ïåðåäà÷è äàííûõ ïî êîììóòèðóåìûì èëè âûäåëåííûì ëèíèÿì ñî ñêîðîñòÿìè äî 64 Êáèò/ñ, â ÷àñòíîñòè, ïî ñåòÿì ïðîòîêîëîâ Õ25, System Network Architecture è äð.
Ñòàíäàðò ñæàòèÿ äàííûõ äëÿ ðàáîòû â ñåòÿõ ISDN, T1/E1, à òàêæå â ñåòÿõ ñ àñèíõðîííîé ïåðåäà÷åé äàííûõ.

Ëèòåðàòóðà

Remote Compression Bridges. A report from National Software Testing Laboratories Inc.//Communication Analyst. Datapro on CD-ROM, March, 1995
Peter Heywood Leased-Line Forecast: Deeper Price Cuts// Data Communications, February 1995, pp. 55-56D
M.K. Stillman - The market for Data Compression Products// San Jose: Electronic Trend Publications, 1994
Ä.Ìàñòðþêîâ - Ñæàòèå ïî Õàôôìåíó// "Ìîíèòîð", NN 7 - 8, 1993
Ä.Ìàñòðþêîâ - Àëãîðèòìû ñæàòèÿ èíôîðìàöèè. ×àñòè 2-5// "Ìîíèòîð", NN 1 - 4, 1994
Marc Nelson - The Data Compression Book// New York: M&T Books, 1992

Ïðè ïîäãîòîâêå ñòàòüè èñïîëüçîâàëñÿ ìàòåðèàë êîìïàíèè Gandalf "Data Compression. White paper"// Gandalf Technologies Inc., February 1995, 10 p.

Äìèòðèé Âåäåâ