Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал
Рассмотрены компьютерные алгоритмы универсальной схемы сжатия (компрессии) и однозначного развертывания (декомпрессии) произвольной двоично-кодированной информации. Предложены методы сжатия, основанные на статистических данных с применением логических шкал позиционного кодирования, вносящих единообр...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2009
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101505 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал / А.Ш. Сулейманов // Электронное моделирование. — 2009. — Т. 31, № 4. — С. 67-78. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101505 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1015052025-02-23T20:23:25Z Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал Algorithms of Compression of Arbitrary Binary-Encoded Information Based on the Use of the Logical Scales Сулейманов, А.Ш. Точность, надежность, диагностика Рассмотрены компьютерные алгоритмы универсальной схемы сжатия (компрессии) и однозначного развертывания (декомпрессии) произвольной двоично-кодированной информации. Предложены методы сжатия, основанные на статистических данных с применением логических шкал позиционного кодирования, вносящих единообразие в процессы сжатия и развертывания, что позволяет разрабатывать относительно универсальные эффективные средства сжатия данных. Розглянуто комп’ютерні алгоритми універсальної схеми стискування (компресії) та однозначного розгортання (декомпресії) довільної двоічно-кодованої інформації. Запропоновано методи стискування, що базуються на статистичних даних з використанням логічних шкал позиційного кодування, які вносять однаковість у процеси стискування та розгортання, що дозволяє розроблювати відносно універсальні ефективні засоби стискування даних. Computer algorithms of the universal scheme of a compression and ambiguous decompression of arbitrary binary-coded information have been considered. Methods of compression based on the statistic data and application of logical scales of positional coding bringing uniformity in the processes of compression and decompression and allowing to develop relatively universal effective means for compression of the data are offered. 2009 Article Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал / А.Ш. Сулейманов // Электронное моделирование. — 2009. — Т. 31, № 4. — С. 67-78. — Бібліогр.: 12 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101505 681.324 ru Электронное моделирование application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Точность, надежность, диагностика Точность, надежность, диагностика |
| spellingShingle |
Точность, надежность, диагностика Точность, надежность, диагностика Сулейманов, А.Ш. Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал Электронное моделирование |
| description |
Рассмотрены компьютерные алгоритмы универсальной схемы сжатия (компрессии) и однозначного развертывания (декомпрессии) произвольной двоично-кодированной информации. Предложены методы сжатия, основанные на статистических данных с применением логических шкал позиционного кодирования, вносящих единообразие в процессы сжатия и развертывания, что позволяет разрабатывать относительно универсальные эффективные средства сжатия данных. |
| format |
Article |
| author |
Сулейманов, А.Ш. |
| author_facet |
Сулейманов, А.Ш. |
| author_sort |
Сулейманов, А.Ш. |
| title |
Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал |
| title_short |
Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал |
| title_full |
Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал |
| title_fullStr |
Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал |
| title_full_unstemmed |
Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал |
| title_sort |
алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2009 |
| topic_facet |
Точность, надежность, диагностика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101505 |
| citation_txt |
Алгоритмы компрессии произвольной двоично-кодированной информации, основанные на применении логических шкал / А.Ш. Сулейманов // Электронное моделирование. — 2009. — Т. 31, № 4. — С. 67-78. — Бібліогр.: 12 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT sulejmanovaš algoritmykompressiiproizvolʹnojdvoičnokodirovannojinformaciiosnovannyenaprimeneniilogičeskihškal AT sulejmanovaš algorithmsofcompressionofarbitrarybinaryencodedinformationbasedontheuseofthelogicalscales |
| first_indexed |
2025-11-25T04:16:46Z |
| last_indexed |
2025-11-25T04:16:46Z |
| _version_ |
1849734425521160192 |
| fulltext |
ÓÄÊ:681.324
À. Ø. Ñóëåéìàíîâ, êàíä. òåõí. íàóê
Àçåðáàéäæàíñêèé òåõíè÷åñêèé óíèâåðñèòåò
(Àçåðáàéäæàí, AZ1073, Áàêó, ïðîñï. Ã. Äæàâèäà, 25,
òåë.: (09412) 4383260, E-mail: akif@inbox.ru)
Àëãîðèòìû êîìïðåññèè ïðîèçâîëüíîé
äâîè÷íî-êîäèðîâàííîé èíôîðìàöèè, îñíîâàííûå
íà ïðèìåíåíèè ëîãè÷åñêèõ øêàë
(Ñòàòüþ ïðåäñòàâèë ä-ð òåõí. íàóê Þ. Ì. Êîðîñòèëü)
Ðàññìîòðåíû êîìïüþòåðíûå àëãîðèòìû óíèâåðñàëüíîé ñõåìû ñæàòèÿ (êîìïðåññèè) è îäíî-
çíà÷íîãî ðàçâåðòûâàíèÿ (äåêîìïðåññèè) ïðîèçâîëüíîé äâîè÷íî-êîäèðîâàííîé èíôîðìàöèè.
Ïðåäëîæåíû ìåòîäû ñæàòèÿ, îñíîâàííûå íà ñòàòèñòè÷åñêèõ äàííûõ ñ ïðèìåíåíèåì ëîãè-
÷åñêèõ øêàë ïîçèöèîííîãî êîäèðîâàíèÿ, âíîñÿùèõ åäèíîîáðàçèå â ïðîöåññû ñæàòèÿ è
ðàçâåðòûâàíèÿ, ÷òî ïîçâîëÿåò ðàçðàáàòûâàòü îòíîñèòåëüíî óíèâåðñàëüíûå ýôôåêòèâíûå
ñðåäñòâà ñæàòèÿ äàííûõ.
Ðîçãëÿíóòî êîìï’þòåðí³ àëãîðèòìè óí³âåðñàëüíî¿ ñõåìè ñòèñêóâàííÿ (êîìïðåñ³¿) òà îäíî-
çíà÷íîãî ðîçãîðòàííÿ (äåêîìïðåñ³¿) äîâ³ëüíî¿ äâî³÷íî-êîäîâàíî¿ ³íôîðìàö³¿. Çàïðîïîíîâàíî
ìåòîäè ñòèñêóâàííÿ, ùî áàçóþòüñÿ íà ñòàòèñòè÷íèõ äàíèõ ç âèêîðèñòàííÿì ëîã³÷íèõ øêàë
ïîçèö³éíîãî êîäóâàííÿ, ÿê³ âíîñÿòü îäíàêîâ³ñòü ó ïðîöåñè ñòèñêóâàííÿ òà ðîçãîðòàííÿ, ùî
äîçâîëÿº ðîçðîáëþâàòè â³äíîñíî óí³âåðñàëüí³ åôåêòèâí³ çàñîáè ñòèñêóâàííÿ äàíèõ.
Ê ë þ ÷ å â û å ñ ë î â à: ñæàòèå äàííûõ, êîìïðåññèÿ (äåêîìïðåññèÿ), êîäèðîâàíèå,
èçáûòî÷íîñòü.
Ñîãëàñíî áîëüøèíñòâó ïðîãíîçîâ â áëèæàéøåì áóäóùåì â òåõíè÷åñêè
ðàçâèòûõ ñòðàíàõ îñíîâíàÿ ìàññà èíôîðìàöèè â ïîëíîì îáúåìå áóäåò õðà-
íèòüñÿ â áåçáóìàæíîì âèäå — â ïàìÿòè êîìïüþòåðíûõ ñèñòåì è ñåòåé [1].
Ïîäîáíûå èçìåíåíèÿ ñïîñîáíû âûäâèíóòü íà ïåðåäíèé ïëàí òî èëè èíîå
íàó÷íîå íàïðàâëåíèå èëè òåõíè÷åñêîå ðåøåíèå. Îäíèì èç òàêèõ íàïðàâ-
ëåíèé ÿâëÿåòñÿ ñæàòèå äèñêðåòíûõ äàííûõ, êîòîðîå çàíèìàåò îäíó èç âåäó-
ùèõ ïîçèöèé â áåçáóìàæíîé èíôîðìàòèêå. Â íàñòîÿùåå âðåìÿ ýòî âåñüìà
àêòóàëüíî, òàê êàê èíôîðìàöèîííûå ðåñóðñû ñòàíîâÿòñÿ îñíîâíûì íàöèî-
íàëüíûì áîãàòñòâîì, à ýôôåêòèâíîñòü èõ ïðîìûøëåííîé ýêñïëóàòàöèè âñå
â áîëüøåé ñòåïåíè îïðåäåëÿåò ýêîíîìè÷åñêîå ðàçâèòèå â öåëîì.
 [1—5] ïîêàçàíî, ÷òî äàëüíåéøèå èññëåäîâàíèÿ â îáëàñòè êîìïðåñ-
ñèè äàííûõ äîëæíû êîíöåíòðèðîâàòüñÿ âîêðóã ñëåäóþùèõ íàïðàâëåíèé:
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 4 67
ïîâûøåíèå ýôôåêòèâíîñòè ñæàòèÿ;
óâåëè÷åíèå ñêîðîñòè ðàáîòû àëãîðèòìà;
îñóùåñòâëåíèå ñæàòèÿ íà îñíîâå íîâîé ñèñòåìû êîíòåêñòîâ.
Ïîñòàíîâêà çàäà÷è. Ñóùåñòâóþò äâà îñíîâíûõ ñïîñîáà ñæàòèÿ: ñòà-
òèñòè÷åñêèé è ñëîâàðíûé. Ìåòîäû Øåííîíà—Ôýíî, Õàôôìåíà è àðèôìå-
òè÷åñêîå êîäèðîâàíèå îòíîñÿòñÿ ê ñòàòèñòè÷åñêèì ìåòîäàì. Ïðåäëîæåííûå
àëãîðèòìû (RPOS è RGRUP) òàêæå îòíîñÿòñÿ ê ñòàòèñòè÷åñêèì ìåòîäàì. Â
ñòàòèñòè÷åñêîì ñæàòèè êàæäîìó ñèìâîëó ïðèñâàèâàåòñÿ êîä, îñíîâàííûé
íà âåðîÿòíîñòè åãî ïîÿâëåíèÿ â òåêñòå, êîòîðàÿ îïðåäåëÿåòñÿ ïî ïðåäâà-
ðèòåëüíîìó ñòàòèñòè÷åñêîìó àíàëèçó (ÑÒÀ).
Ëó÷øèå ñëîâàðíûå ìåòîäû èñïîëüçóþòñÿ â àëãîðèòìàõ Çèâà—Ëåìïåëà
(LZ-ñåìåéñòâî) LZ77 è LZ78. Ýòî aëãîðèòìû ñæàòèÿ áåç ïîòåðü, îïóáëè-
êîâàííûå â ðàáîòàõ [6, 7].
Ýòè äâà àëãîðèòìà ÿâëÿþòñÿ íàèáîëåå èçâåñòíûìè â ñåìåéñòâå LZ*,
êóäà òàêæå âêëþ÷åíû LZW, LZSS, LZMA è äðóãèå àëãîðèòìû (ïî÷òè âñå
ïðàêòè÷åñêèå ñëîâàðíûå êîäèðîâùèêè ïðèíàäëåæàò ñåìüå àëãîðèòìîâ,
ðàçðàáîòàííûõ ß. Çèâîì è À. Ëåìïåëîì.) Ýòè àëãîðèòìû ìîæíî áûñòðî
ðåàëèçîâàòü, íî îíè íå îáÿçàòåëüíî îïòèìàëüíû, ïîñêîëüêó íå âûïîëíÿþò
íèêàêîãî àíàëèçà âõîäíûõ äàííûõ. Â ñëîâàðíîì ìåòîäå ãðóïïû ïîñëåäî-
âàòåëüíûõ ñèìâîëîâ èëè «ôðàç» çàìåíÿþòñÿ êîäîì. Çàìåíåííàÿ ôðàçà
ìîæåò áûòü íàéäåíà â íåêîòîðîì «ñëîâàðå». Êàê âèäíî, ñëîâàðíûå ìåòîäû
îñíîâàíû íà ïðèìåíåíèè òîëüêî îïðåäåëåííûõ çàêîíîìåðíîñòåé ÿçûêà
ïåðâè÷íîãî ïðåäñòàâëåíèÿ èíôîðìàöèè.
Ñëîâàðíûå àëãîðèòìû áîëåå ïðàêòè÷íû. Èõ ïðåèìóùåñòâî ïåðåä ñòàòèñ-
òè÷åñêèìè ìåòîäàìè òåîðåòè÷åñêè îáúÿñíÿåòñÿ òåì, ÷òî îíè ïîçâîëÿþò êî-
äèðîâàòü ïîñëåäîâàòåëüíîñòè ñèìâîëîâ ðàçíîé äëèíû. Ñòàòèñòè÷åñêèå àëãî-
ðèòìû òîæå ìîæíî èñïîëüçîâàòü äëÿ òàêèõ ïîñëåäîâàòåëüíîñòåé, íî â ýòîì
ñëó÷àå èõ ðåàëèçàöèÿ ñòàíîâèòñÿ âåñüìà ðåñóðñîåìêîé.
Êëþ÷åâûì äëÿ ðàçìåðà ïîëó÷àåìûõ êîäîâ N ÿâëÿåòñÿ ðàçìåð ñëîâàðÿ K
âî ôðàçàõ, ïîòîìó ÷òî êàæäûé êîä ïðè êîäèðîâàíèè ïî ìåòîäó LZ78 ñîäåð-
æèò íîìåð ôðàçû â ñëîâàðå. Èç ïîñëåäíåãî ñëåäóåò, ÷òî ýòè êîäû èìåþò
ïîñòîÿííóþ äëèíó, ðàâíóþ îêðóãëåííîìó â áîëüøóþ ñòîðîíó äâîè÷íîìó
ëîãàðèôìó ðàçìåðà ñëîâàðÿ +8 (ýòî êîëè÷åñòâî áèò â áàéò-êîäå ðàñøèðåí-
íîãî ASCII) N = logK + 8.
 òàáë. 1 äëÿ ñðàâíåíèÿ ïðèâåäåíû äàííûå, ïîëó÷åííûå ñ ïîìîùüþ
ïðåäëîæåííîãî ìåòîäà è àëãîðèòìà LZ*.
Êàê âèäíî èç ñîïîñòàâèòåëüíîãî àíàëèçà LZ* ìåòîäîâ êîìïðåññèè
äàííûõ, îíè ÿâëÿþòñÿ â îïðåäåëåííîé ñòåïåíè ïðîáëåìíî-îðèåíòèðîâàí-
íûìè (ñïåöèàëèçèðîâàííûìè). Â îñíîâó àëãîðèòìîâ ðåàëèçàöèè ýòèõ ìå-
òîäîâ ïîëîæåíû ñåìàíòè÷åñêèå, ëèíãâèñòè÷åñêèå, ñòðóêòóðíûå, âåðîÿò-
À. Ø. Ñóëåéìàíîâ
68 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 4
íîñòíî-ñòàòèñòè÷åñêèå è èíûå õàðàêòåðèñòèêè ÿçûêà ïåðâè÷íîãî ïðåä-
ñòàâëåíèÿ èíôîðìàöèè (ñèñòåìû ðàáîòàþò ïîëíîñòüþ íà ëåêñè÷åñêîì
óðîâíå). Ïîýòîìó îíè íå îòâå÷àþò òðåáîâàíèÿì ñèñòåì îáðàáîòêè, õðàíå-
íèÿ è ïåðåäà÷è äàííûõ è óïðàâëåíèÿ. Êðîìå òîãî, îòñóòñòâóåò ÷åòêàÿ
òåîðåòè÷åñêàÿ áàçà ñèñòåìíîãî ðåøåíèÿ äàííîé çàäà÷è.
Ïðåäëîæåííûå ìåòîäû ñæàòèÿ èíôîðìàöèè, îñíîâàíû íà êîíöåïöèè
ïðèìåíåíèÿ àáñòðàêòíîãî ìíîæåñòâà (àëôàâèòà) äâîè÷íûõ êâàíòîâ îïðå-
äåëåííîé äëèíû (3, 4, 5, ..., 8 áèòîâ) è ëîãè÷åñêèõ øêàë ïîçèöèîííîãî
êîäèðîâàíèÿ. Ïðèìåíåíèå àëôàâèòà äâîè÷íûõ êâàíòîâ ñ ðàçëè÷íûìè äëè-
íàìè áåç ó÷åòà ñòðóêòóðû åãî ïîñòðîåíèÿ è ñåìàíòèêè, â îòëè÷èe îò
àëãîðèòìà Ëåìïåëÿ—Çèâà, äàåò âîçìîæíîñòü íàéòè îáùóþ òåîðåòè÷åñ-
êóþ áàçó êîìïðåññèè äàííûõ äëÿ èõ îòíîñèòåëüíîé óíèâåðñàëèçàöèè,
ôóíêöèîíàëüíîé ïîëíîòû è ïðàãìàòè÷åñêîé öåííîñòè.
Ïðåäëîæåííûé àëãîðèòì ìîæåò áûòü ïðèìåíåí ïîâòîðíî ïîñëå ïåð-
âè÷íîãî ñæàòèÿ ìåòîäîì LZ*. Âîçìîæíà òàêæå äåêîìïîçèöèÿ ôàéëîâ íà
îñíîâå åãî ñòàòèñòè÷åñêèõ äàííûõ íà áîëåå ýôôåêòèâíûå ñ òî÷êè çðåíèÿ
ñæàòèÿ ïîäôàéëû ñ ïðèìåíåíèåì ëîãè÷åñêîé øêàëû ïîçèöèîííîãî êîäè-
ðîâàíèÿ (ËØÏÊ). Êðîìå òîãî, ýòè àëãîðèòìû ìîæíî èñïîëüçîâàòü â ñèñòå-
ìàõ àíàëèçà òåêñòîâ äëÿ ñòðóêòóðíîãî ïðåäñòàâëåíèÿ [8, 9].
Àëãîðèòìû ñæàòèÿ è îäíîçíà÷íîãî ðàçâåðòûâàíèÿ äèñêðåòíûõ
äàííûõ. Èç ñîïîñòàâèòåëüíîãî àíàëèçà íàèáîëåå ðàñïðîñòðàíåííûõ ìåòî-
äîâ è àëãîðèòìîâ êîìïðåññèè ñëåäóåò, ÷òî äëÿ ñèñòåìíîãî ðåøåíèÿ çàäà÷è
Àëãîðèòìû êîìïðåññèè ïðîèçâîëüíîé äâîè÷íî-êîäèðîâàííîé èíôîðìàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 4 69
Ìåòîä ñæàòèÿ
(õàðàêòåðèñòèêà)
LZ* RPOS è RGRUP
Òèï àëãîðèòìà
Ïðåäâàðèòåëüíûé ÑÒÀ
Âõîäíûå ôàéëû
Âðåìÿ ðåàëèçàöèè
Îáëàñòü ïðèìåíåíèÿ
Äëèíà ñæàòûõ êîäîâ
Ñëîâåñíîå (áóêâåííîå)
ñæàòèå
Ìíîãîêðàòíîñòü
ñæàòèÿ
Ñëîâàðíûé
Îòñóòñòâóåò
ßçûê ïåðâè÷íîãî ïðåä-
ñòàâëåíèÿ èíôîðìàöèè
Ñðàâíèòåëüíî áûñòðîe
Îòíîñèòåëüíî ñïåöèàëè-
çèðîâàííûå
Ïîñòîÿííàÿ
Âîçìîæíî
Âîçìîæíîñòü îãðàíè÷åíà
Ñòàòèñòè÷åñêèé
Äëÿ ïðåäâàðèòåëüíîé îöåíêè âû-
ïîëíÿåòñÿ ÑÒÀ
Àáñòðàêòíûå ìíîæåñòâà (àëôàâèòû)
äâîè÷íûõ êâàíòîâ
Ìåäëåííîå (äëÿ óâåëè÷åíèÿ òðå-
áóþòñÿ àïïàðàòíûå ðàñõîäû è ïà-
ðàëëåëèçì îáðàáîòêè)
Èìååòñÿ âîçìîæíîñòü óíèâåðñàëè-
çàöèè
Ïåðåìåííàÿ
Âîçìîæíî (èñïîëüçîâàíèå â ñèñòå-
ìàõ àíàëèçà òåêñòîâ äëÿ ñòðóêòóð-
íîãî ïðåäñòàâëåíèÿ)
Âîçìîæíî
Òàáëèöà 1
ñæàòèÿ äàííûõ (äëÿ èõ îòíîñèòåëüíîé óíèâåðñàëèçàöèè) áîëåå ýôôåêòèâ-
íû ìåòîäû, îñíîâàííûå íà ïðèìåíåíèè ËØÏÊ [10, 11]. Ýòî îáúÿñíÿåòñÿ
èõ ñëåäóþùèìè õàðàêòåðíûìè îñîáåííîñòÿìè:
1. Ïðèìåíåíèå ñòàòèñòè÷åñêèõ õàðàêòåðèñòèê (÷àñòîòû âñòðå÷àå-
ìîñòè áóêâ) àëôàâèòîâ ñæàòèÿ ïîçâîëÿåò ïîëó÷èòü çíà÷èòåëüíûé ýôôåêò
îò ñæàòèÿ.
2. Âîçìîæíîñòü ïðèìåíåíèÿ â êà÷åñòâå àëôàâèòà ñæàòèÿ íå òîëüêî
ñèìâîëîâ (áóêâ àëôàâèòà) ÿçûêà ïåðâè÷íîãî ïðåäñòàâëåíèÿ èíôîðìàöèè,
íî è áèòîâûõ ãðóïï ðàçëè÷íîé äëèíû (êâàíòîâ).
3. Âîçìîæíîñòü ðàçáèòü ôàéë, ñîäåðæàùèé ëþáóþ èíôîðìàöèþ, íà
ïîäôàéëû äëÿ ýôôåêòèâíîãî ïðèìåíåíèÿ ìåòîäîâ ñæàòèÿ; äåêîìïîçèöèÿ
ôàéëà ïîâûøàåò âåðîÿòíîñòü ïîëó÷åíèÿ ýôôåêòà îò ñæàòèÿ è óâåëè÷èâàåò
ñòåïåíü ñåêðåòíîñòè åãî õðàíåíèÿ èëè ïåðåäà÷è ïî êîììóíèêàöèîííûì
êàíàëàì.
4. Âîçìîæíîñòü óíèôèöèðîâàòü îñíîâíûå ïðîöåäóðû îáðàáîòêè äàí-
íûõ äëÿ ðàçðàáîòêè ìîäóëüíûõ àëãîðèòìîâ è àïïàðàòíî-ïðîãðàììíûõ
ñðåäñòâ ñæàòèÿ è ðàçâåðòûâàíèÿ ñ âîçìîæíîé ïðîãðàììèðóåìîé êîììó-
òàöèåé ïîñëåäíèõ.
Ðàññìîòðèì äâà ìåòîäà ñæàòèÿ äàííûõ.
Ïåðâûé — ìåòîä ïîñëåäîâàòåëüíîãî èñêëþ÷åíèÿ áóêâ (RPOS-ïðå-
îáðàçîâàíèå) — îñíîâàí íà ïðèìåíåíèè ëîêàëüíûõ ñòàòèñòè÷åñêèõ õàðàê-
òåðèñòèê (÷àñòîòà âñòðå÷àåìîñòè êàæäîãî êâàíòà-áóêâû) ñåãìåíòà äàí-
íûõ, êîòîðûé ðàññìàòðèâàåòñÿ êàê ñòîõàñòè÷åñêàÿ ïîñëåäîâàòåëüíîñòü
áèòîâ, à ñæàòèå (ïðåîáðàçîâàíèå) ïðîâîäèòñÿ ïîñëåäîâàòåëüíûì èñêëþ÷å-
íèåì èç îáðàáàòûâàåìîãî ñåãìåíòà ñîîòâåòñòâóþùèõ áóêâ àëôàâèòà.
Âòîðîé — ìåòîä èñêëþ÷åíèÿ ãðóïïû áóêâ (RGRUP-ïðåîáðàçîâàíèå) —
òàêæå îñíîâàí íà ïðèìåíåíèè ëîêàëüíûõ ñòàòèñòè÷åñêèõ õàðàêòåðèñòèê
ñåãìåíòà äàííûõ.
Îäíàêî ñæàòèå ïðîèñõîäèò ïóòåì âûäåëåíèÿ è ôèêñàöèè ïîñðåäñòâîì
ËØÏÊ ãðóïïû áóêâ, îáëàäàþùèõ ñðàâíèòåëüíî áîëüøîé èçáûòî÷íîñòüþ.
Îáà ìåòîäà îñíîâàíû íà òåõíîëîãèè ïðèìåíåíèÿ ËØÏÊ, êîòîðàÿ
ïîçâîëÿåò ïðîâîäèòü ïîñëåäîâàòåëüíóþ äåêîìïîçèöèþ ôàéëà íà ýôôåê-
òèâíûå ïîäôàéëû è ñîçäàâàòü ïàðàëëåëüíûå àëãîðèòìû ñæàòèÿ (ðàçâåð-
òûâàíèÿ).
Ìàòåìàòè÷åñêàÿ ìîäåëü àëãîðèòìà. Ââåäåì íåêîòîðûå îñíîâíûå
ïîíÿòèÿ è îïðåäåëåíèÿ. Ñåãìåíò ñòîõàñòè÷åñêîé ïîñëåäîâàòåëüíîñòè áè-
òîâ íàçîâåì äâîè÷íûì êîðòåæåì è ïðåäñòàâèì â âèäå
M x x xq0 1 2
� ( , , ..., ) .
Çäåñü x Mq � , ãäå M = {0, 1}; q — êîëè÷åñòâî áèòîâ (ñèìâîëîâ) ñòîõàñòè-
÷åñêîé ïîñëåäîâàòåëüíîñòè.
À. Ø. Ñóëåéìàíîâ
70 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 4
Îáîçíà÷èì íåïðåðûâíóþ êîíå÷íóþ ïîñëåäîâàòåëüíîñòü áèòîâ äëè-
íîé z ÷åðåç mz è íàçîâåì ýòó âåëè÷èíó øàãîì êâàíòîâàíèÿ:
m y y yz z� ( , ,..., )
1 2
.
Çíà÷åíèÿ mz è q íåîáõîäèìî âûáðàòü òàê, ÷òîáû q mz/ áûëî öåëûì ÷èñëîì:
K q mz z� / ,
ãäå z —ìàêñèìàëüíàÿ äëèíà øàãà êâàíòîâàíèÿ â áèòàõ. Ïîñëå êâàíòîâàíèÿ
M
0
øàãîì êâàíòîâàíèÿ mz ïîëó÷èì K z -êîìïîíåíòíûé êîðòåæ
� �M m M M Mz
m m
K
m
z
z
0 1 2
2 2( ) ( , , ..., )
( ) ( ) ( )
.
Ïðåäïîëîæèì, ÷òî êàêèå-òî êîìïîíåíòû êîðòåæà �M mz0
( ) îòëè÷àþòñÿ
îïðåäåëåííûì ñâîéñòâîì. Ìíîæåñòâî ýòèõ êîìïîíåíòîâ îáîçíà÷èì ÷åðåç
A mz
�
( ). Òîãäà ËØÏÊ( )mz ìîæíî âûäåëèòü òå êîìïîíåíòû êîðòåæà �M mz0
( ),
êîòîðûå âõîäÿò â A mz
�
( ):
ËØÏÊ ( ) ( , , ..., )
( ) ( ) ( )mz Kz
� � � �
� � �
1 2
,
np M Mj j
mz
� �
0
( )
( )
, j K z�1 2, , ..., ,
�
�
���
�
j
j
m
z
j
m
M A m
M A
z
z
( )
( )
( ) (
( ),
�
�
1
0
, åñëè _
, åñëè _
�
( ).mz
�
�
�
Çäåñü � — íîìåð ýòàïà ðàçáèåíèÿ êîìïîíåíò êîðòåæà íà äâà íåïåðåñå-
êàþùèõñÿ õàðàêòåðèñòè÷åñêèõ ìíîæåñòâà. Åñòåñòâåííî, ÷òî ïðè êâàíòî-
âàíèè M
0
øàãîì êâàíòîâàíèÿ mz êîëè÷åñòâî ðàçëè÷íûõ mz -áèòíûõ áóêâ
(íàçîâåì ìíîæåñòâî ýòèõ áóêâ àëôàâèòîì ïðåîáðàçîâàíèÿ, â äàííîì ñëó-
÷àå — ñæàòèÿ) áóäåò2
mz . Òîãäà îäèí è òîò æå êîðòåæ M
0
ìîæíî êâàíòîâàòü
( )z �1 ðàçëè÷íûìè êâàíòàìè (ïîñêîëüêó ïîñëå êâàíòîâàíèÿ äâîè÷íîãî êîð-
òåæà øàãîì z �1 ïîëó÷àåì èñõîäíûé êîðòåæ M
0
, ýòà îïåðàöèÿ íå èìååò
ñìûñëà) è ïîëó÷èòü ( )z �1 ðàçëè÷íûõ ìíîæåñòâ àëôàâèòà ñæàòèÿ.
Îáîçíà÷èì êîíêðåòíóþ áóêâó îïðåäåëåííîãî àëôàâèòà ÷åðåç
� �j z j m zm m
z
*
( )
( ) { ( )}� , j m u j j mz
m
z
z( ) , , , ..., ( ) _ ( )
*
� � �0 1 2 2 1 .
Åñòåñòâåííî, ÷òî êîíêðåòíûé äâîè÷íûé êîðòåæ ïðè êâàíòîâàíèè
øàãîì êâàíòîâàíèÿ mz ìîæåò ñîäåðæàòü íå âñå ðàçíîîáðàçíûå áóêâû
�
j m z
z
m
( )
( ) â êîëè÷åñòâå 2
mz , è ëîêàëüíàÿ ÷àñòîòà èõ âñòðå÷àåìîñòè áóäåò
äëÿ êàæäîãî àëôàâèòà ðàçíîé. ×àñòîòó áóêâû � j zm*
( ) îáîçíà÷èì ÷åðåç
� j zm*
( ).Òîãäà ïîñëå êâàíòîâàíèÿ èñõîäíîãî êîðòåæà M
0
øàãîì êâàíòîâà-
Àëãîðèòìû êîìïðåññèè ïðîèçâîëüíîé äâîè÷íî-êîäèðîâàííîé èíôîðìàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 4 71
íèÿ mz îáðàçóåì äâå óïîðÿäî÷åííûå ïîñëåäîâàòåëüíîñòè (äëÿ ïðîñòîòû
çàïèñè íå áóäåì îòìå÷àòü øàã êâàíòîâàíèÿ mz ):
� � � �j j j jQ1 2 3
� � � �... , (1)
� � � �j j j jQ1 2 3
, , , ..., , (2)
ãäå j j j jQ
mz
1 2 3
0 1 2 2 1, , , ..., { , , , ..., ( )}� � .
Ñæàòèå äâîè÷íîãî êîðòåæà íàçîâåì R-ïðåîáðàçîâàíèåì. Áóäåì ïîëü-
çîâàòüñÿ îáîçíà÷åíèåì RX, ãäå X — îòîáðàæàåò ìíåìîíèêó êîíêðåòíîãî
ïðèìåíÿåìîãî ìåòîäà êîìïðåññèè äàííûõ. Îáà ðàññìàòðèâàåìûõ ìåòîäà
îñíîâàíû íà âåðîÿòíîñòíî-ñòàòèñòè÷åñêèõ õàðàêòåðèñòèêàõ áóêâ àëôà-
âèòà ñæàòèÿ. Îáùèì äëÿ îáîèõ ìåòîäîâ ÿâëÿåòñÿ ôîðìèðîâàíèå ïîñëåäîâà-
òåëüíîñòåé (1) è (2), ò. å. îïðåäåëåíèå ÷àñòîòû âñòðå÷àåìîñòè êàæäîé áóêâû
(� j zm*
( )) è óïîðÿäî÷åíèå, à òàêæå îïðåäåëåíèå áóêâû ñæàòèÿ � j zm*
( ).
Ýòà ïðîöåäóðà íàçûâàåòñÿ «ñòàòèñòè÷åñêèé àíàëèç ôàéëà è óïîðÿäî-
÷åíèå ÷àñòîòû âñòðå÷àåìîñòè áóêâ» è èìååò ñëåäóþùèå îñîáåííîñòè:
1. Ïåðåìåííàÿ äëèíà øàãà êâàíòîâàíèÿ îáóñëîâëèâàåò îñîáûå òðå-
áîâàíèÿ ê äëèíå èñõîäíîãî ôàéëà. Äëèíà ôàéëà â áèòàõ äîëæíà áûòü
íàöåëî äåëèìîé íà âñå ïðèíÿòûå çíà÷åíèÿ øàãà êâàíòîâàíèÿ mz .
2. Âåðîÿòíîñòü ïîëó÷åíèÿ ìàêñèìàëüíîé ýôôåêòèâíîñòè îò ñæàòèÿ
áîëåå çíà÷èòåëüíà ïðè âîçìîæíî áîëüøåé äëèíå øàãà êâàíòîâàíèÿ mz .
Îäíàêî ñ óâåëè÷åíèåì çíà÷åíèÿ mz óâåëè÷èâàåòñÿ è 2
mz , à ýòî îáñòîÿ-
òåëüñòâî, â ñâîþ î÷åðåäü, ïîðîæäàåò äðóãèå òðóäíîñòè (ïðè áîëüøèõ
çíà÷åíèÿõ mz óâåëè÷èâàåòñÿ îáùåå êîëè÷åñòâî ìíîæåñòâ àëôàâèòà ñæà-
òèÿ, â ðåçóëüòàòå ÷åãî óâåëè÷èâàåòñÿ òðåáóåìûé îáúåì ïàìÿòè äëÿ õðà-
íåíèÿ áóêâ).
3. Ïðè óâåëè÷åíèè çíà÷åíèÿ mz óâåëè÷èâàþòñÿ ïàðàìåòðû àëãîðèò-
ìîâ îáðàáîòêè.
Òàêèì îáðàçîì, äëÿ ïðèíÿòèÿ êîìïðîìèññíîãî ðåøåíèÿ íåîáõîäèìî
ðàññìàòðèâàòü âñå ïåðå÷èñëåííûå îñîáåííîñòè â êîìïëåêñå. Äëÿ ïðîãðàì-
ìíîé ðåàëèçàöèè àëãîðèòìîâ âûáðàííûõ ìåòîäîâ ìàêñèìàëüíàÿ äëèíà øàãà
êâàíòîâàíèÿ ïðèíÿòà mz �8, ò.å. z �8. Ïðè ýòîì mz �{ , , ,3 4 5 6 7 8, , }, òàê êàê ïðè
z �2 ñóùåñòâåííàÿ ýôôåêòèâíîñòü ïðåîáðàçîâàíèÿ ìàëîâåðîÿòíà.
RPOS-ïðåîáðàçîâàíèå. Èñõîäíûìè äàííûìè äëÿ ðàáîòû óêàçàííîãî
àëãîðèòìà ÿâëÿþòñÿ ïîñëåäîâàòåëüíîñòè (1) è (2), ïîëó÷åííûå â ðåçóëü-
òàòå ðàáîòû ïðîãðàììû ñòàòèñòè÷åñêîãî àíàëèçà ôàéëà è óïîðÿäî÷åíèÿ
÷àñòîòû âñòðå÷àåìîñòè áóêâ. Îñíîâíûå òèïîâûå ïðîöåäóðû ñëåäóþùèå:
âûáîðêà î÷åðåäíîãî êâàíòà èç ñåãìåíòà îáðàáîòêè;
ñðàâíåíèå âûáðàííîãî êâàíòà ñ ñîîòâåòñòâóþùèì ýòàëîííûì êâàíòîì;
ôîðìèðîâàíèå ËØÊÏ;
À. Ø. Ñóëåéìàíîâ
72 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 4
ôîðìèðîâàíèå âûõîäíûõ äàííûõ RPOS-ïðåîáðàçîâàíèÿ (òåãà, øêàë
è äð.).
Âðåìÿ ðàáîòû ïðîãðàììû â îñíîâíîì ëèíåéíî çàâèñèò îò äëèíû îáðà-
áàòûâàåìîãî ñåãìåíòà äàííûõ (è ñëåäîâàòåëüíî, îò ðàçìåðà ôàéëà îáðà-
áîòêè). Ïîýòîìó äëÿ äîñòèæåíèÿ âûñîêîé ïðîèçâîäèòåëüíîñòè íåîáõî-
äèìî ïðèìåíÿòü ìåòîäû ïàðàëëåëüíîé îáðàáîòêè èñõîäíûõ êâàíòîâ. Äëÿ
ýòîãî äîëæíû áûòü ðàçðàáîòàíû òèïîâûå ìîäóëè ïàðàëëåëüíîé îáðàáîòêè
êâàíòîâ.
Ïðèìåð. Ïóñòü çàäàíà òàêàÿ ïîñëåäîâàòåëüíîñòü áóêâ (èñõîäíûé ñåã-
ìåíò): «acbaaadbacabaabaaacaabae». Ïðîöåññ ñæàòèÿ äàííîé èíôîðìàöèè
ìåòîäîì RPOS-ïðåîáðàçîâàíèÿ ñîñòîèò â ñëåäóþùåì. Ïðîöåäóðà ôîð-
ìèðîâàíèÿ ËØÏÊ âûïîëíÿåòñÿ äëÿ êàæäîãî íåïîâòîðÿþùåãîñÿ êâàíòà
(áóêâû a, b, c, d, e) èñõîäíîãî ñåãìåíòà (ðèñ. 1) — ìàññèâ ËØÏÊ SG (I).
Äëèíà êàæäîé øêàëû è ïåðåìåííàÿ âåëè÷èíà çàâèñèò îò ÷àñòîòû âñòðå-
÷àåìîñòè áóêâû, äëÿ êîòîðîé ôîðìèðóåòñÿ ïðåäûäóùàÿ øêàëà. Ñëåäî-
âàòåëüíî, äëÿ îðãàíèçàöèè ïàðàëëåëüíîãî ôîðìèðîâàíèÿ ËØÏÊ íåîáõîäèìî
ó÷èòûâàòü, ÷òî ïðåäáëîêîì äëÿ ýòèõ áëîêîâ áóäåò ðàñ÷åòíûé áëîê îïðåäåëå-
íèÿ äëèí îòäåëüíûõ ËØÏÊ è ñîîòâåòñòâóþùèõ èñêëþ÷àåìûõ áóêâ. Îáùåå
êîëè÷åñòâî áëîêîâ (I) ôîðìèðîâàíèÿ ËØÏÊ äîëæíî áûòü (2 1
mz
� ).
Ïðè âûïîëíåíèè ïðîöåäóðû ôîðìèðîâàíèÿ âûõîäíûõ äàííûõ (<a, b,
c, d, e, ìàññèâ ËØÏÊ SG (I)>) ïðîãðàììû RPOS-ïðåîáðàçîâàíèÿ öåëåñî-
îáðàçíî ïðèìåíÿòü ñòåêîâûå ñòðóêòóðû îðãàíèçàöèè ïàìÿòè.
RGRUP-ïðåîáðàçîâàíèå. Èñõîäíûìè äàííûìè äëÿ ðàáîòû óêàçàí-
íîãî àëãîðèòìà òàêæå ÿâëÿþòñÿ ïîñëåäîâàòåëüíîñòè (1) è (2). Ñíà÷àëà èç
Àëãîðèòìû êîìïðåññèè ïðîèçâîëüíîé äâîè÷íî-êîäèðîâàííîé èíôîðìàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 4 73
Ìàññèâ ËØÏÊ
0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0
a(bcde)
I = 2:
0 1 0 1 0 1 1 0 1 0
b(cde)
I = 3:
1 0 1 1 0
c(de)
I = 4:
1 0
d(e)
I = 1
SG I( )
Ðèñ. 1. Ïðîöåññ ïîëó÷åíèÿ ËØÏÊ
óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè âûáèðàåì ãðóïïó áóêâ (íàèáîëåå ÷àñ-
òî âñòðå÷àþùèõñÿ) GRUP =2
k
(ãäå k mz� � 2), óäîâëåòâîðÿþùóþ óñëîâèÿì
ýôôåêòèâíîñòè ñæàòèÿ. Çàòåì ôîðìèðóåì ñëåäóþùèå êîìïîíåíòû ñæàòî-
ãî ñåãìåíòà:
ËØÏÊ (îñíîâíîå îòëè÷èå îò ïðåäûäóùåãî ìåòîäà ñîñòîèò â òîì, ÷òî â
äàííîì ñëó÷àå ôîðìèðóåòñÿ òîëüêî îäíà øêàëà, îáîçíà÷åííàÿ L(GRUP)) —
L(GRUP) � ( , , ..., )r r rKz1 2
;
r
m
m
i
i z
i z
�
�
�
1
0
, åñëè GRUP
, åñëè GRUP
�
�
( ) ,
( ) ;
êîðòåæ (ñæàòûé ñåãìåíò) —
s y y yKz0
1
1 2
( )
( , , ..., )� ;
y
m r
z r
i
i z i
i i
�
�
�
� ( ) ,
;
, åñëè = 0
Z , åñëè =1
0
Z b b b bk n0 1 2 3
�{( ... ) }, n kz
� �0 1 2 2 1, , , ..., ( ), bk �{ , }0 1 .
Çäåñü K z — îáùåå ÷èñëî êâàíòîâ (áóêâ); k — ðàçðÿäíîñòü ñæàòûõ êîäîâ.
Âûõîäíûå äàííûå ïðîãðàììû RGRUP ôîðìèðóþòñÿ â âèäå êîðòåæà
s L GRUP s
1
1
0
1( ) ( )
( , ( ), )� òåã .
Ñëåäóåò çàìåòèòü, ÷òî ïîñëå ïîëó÷åíèÿ ñòàòèñòè÷åñêèõ äàííûõ (î ÷àñ-
òîòå âñòðå÷àåìîñòè áóêâ) ôàéëà ïðåæäå âñåãî äîëæåí áûòü îïðåäåëåí ýôôåê-
òèâíûé äëÿ êîíêðåòíîãî ôàéëà àëãîðèòì ïðåîáðàçîâàíèÿ. Ýòà ïðîöåäóðà
ÿâëÿåòñÿ ïðîìåæóòî÷íîé ìåæäó ïðîöåäóðàìè ñòàòèñòè÷åñêîé îáðàáîòêè è
íåïîñðåäñòâåííî ïðåîáðàçîâàíèÿ. Ïðè ñðàâíåíèè äàííîãî àëãîðèòìà ñ ïðå-
äûäóùèì âèäíî, ÷òî îíè ñîñòîÿò ïðèáëèçèòåëüíî èç àíàëîãè÷íûõ ìîäóëåé
òèïîâûõ ïðîöåäóð.
À. Ø. Ñóëåéìàíîâ
74 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 4
Áóêâà ×àñòîòà âñòðå÷àåìîñòè Êîä
a
b
c
d
e
12
4
3
1
1
000
001
010
011
100
Ïðèìå÷àíèå: êîäû áóêâ óñëîâíûå
Òàáëèöà 2
Ïðèìåð. Ðàññìîòðèì òó æå ïîñëåäîâàòåëüíîñòü áóêâ «a c b a a a d b a c
a b a a a c a a b a e». Ïðîöåññ ñæàòèÿ âûïîëíÿåòñÿ â ñëåäóþùåì ïîðÿäêå.
Ñíà÷àëà âû÷èñëÿþòñÿ è óïîðÿäî÷èâàþòñÿ ÷àñòîòû âñòðå÷àåìîñòè êàæäîé
áóêâû (òàáë. 2.).
Ïðåäïîëîæèì, ÷òî mz = 3 (êâàíòû — äëèíà â áèòàõ êàæäîé áóêâû)
è k = 1 (äëèíà ñæàòûõ áóêâ). Òîãäà êîëè÷åñòâî âûáðàííûõ áóêâ, ïîäëå-
æàùèõ ñæàòèþ, ðàâíî 2
k
. Ýòî áóêâû «a» è «b». Íà îñíîâàíèè ýòîãî ôîðìè-
ðóåòñÿ ïîñëåäîâàòåëüíîñòü ïðåîáðàçîâàíèÿ.
Âûõîäíûå äàííûå ôîðìèðóþòñÿ â âèäå
S a b
1
1
1 0
( )
( , , , , )�
òåã
ËØÏÊ, ñæàòûé òåêñò
���
,
à ïîñëåäîâàòåëüíîñòè ËØÏÊ è ñæàòîãî òåêñòà — â âèäå, ïðåäñòàâëåííîì
íà ðèñ. 2.
 ñæàòîì òåêñòå âìåñòî òðåõðàçðÿäíîãî êîäà áóêâ (a = 000, b = 001)
èñïîëüçóåì îäíîðàçðÿäíûå êîäû añæ = 1 è bñæ = 0.
Ïðè ñðàâíåíèè äâóõ ñõåì ñæàòèÿ âèäíî, ÷òî êðîìå óñëîâèé ñæàòèÿ,
òàêèõ êàê âèä òåêñòà, àäàïòàöèÿ è ìíîãîñòîðîííîñòü ðàáîòû ñ ðàçíûìè
æàíðàìè, ñóùåñòâóåò ìíîãî äðóãèõ ôàêòîðîâ, íàïðèìåð êîëè÷åñòâî ïàìÿ-
òè è âðåìåíè, íåîáõîäèìîå äëÿ îñóùåñòâëåíèÿ ñæàòèÿ, êîòîðûå ñëåäóåò
ó÷èòûâàòü äëÿ êàæäîé ñõåìû.  òàáë. 3 äëÿ ñðàâíåíèÿ ïðèâåäåíû ðåçóëü-
òàòû ñæàòèÿ òåêñòà ñ ïîìîùüþ íàèáîëåå èçâåñòíûõ ìåòîäîâ ñæàòèÿ è ñ
èñïîëüçîâàíèåì ïðåäëîæåííûõ àëãîðèòìîâ, ïîëó÷åííûå íà îñíîâå ÷èñ-
ëåííîãî ýêñïåðèìåíòà.
Ñðåäñòâà ñæàòèÿ è ðàçâåðòûâàíèÿ ïî êðèòåðèþ ýôôåêòèâíîñòè ñæàòèÿ
ìîãóò áûòü ðàçäåëåíû íà äâà êëàññà. Ê ïåðâîìó êëàññó ìîæíî îòíåñòè ñðåäñò-
Àëãîðèòìû êîìïðåññèè ïðîèçâîëüíîé äâîè÷íî-êîäèðîâàííîé èíôîðìàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 4 75
Èñõîäíûé òåêñò
a C b a a a d b a c A b a a a c a b a e
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ËØÏÊ
1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .
Ñæàòûé òåêñò
1 010 0 1 1 1 011 0 1 010 1 0 1 1 1 010 1 1 0 1 100
a
Ðèñ. 2. Ïîñëåäîâàòåëüíîñòè ôîðìèðîâàíèÿ ËØÏÊ è ñæàòîãî òåêñòà
âà, îáåñïå÷èâàþùèå ìàêñèìàëüíóþ ñòåïåíü ñæàòèÿ ñ íàèáîëüøåé ïðîèç-
âîäèòåëüíîñòüþ. Åñëè ïðè ýòîì èñïîëüçóþòñÿ òîëüêî ïðîãðàììíûå
ñðåäñòâà, òî îíè çàíèìàþò áîëüøîé îáúåì ïàìÿòè, ñîñòîÿò èç áîëüøîãî ÷èñëà
ìîäóëåé è îòëè÷àþòñÿ ñëîæíûì àëãîðèòìîì îáìåíà ïðîãðàììíûìè ìîäó-
ëÿìè ìåæäó ðàçëè÷íûìè óðîâíÿìè ïàìÿòè.  ýòîì ñëó÷àå öåëåñîîáðàçíî
èñïîëüçîâàòü ïàðàëëåëüíûå àëãîðèòìû îáðàáîòêè äàííûõ [10]. Òîãäà èñ-
ñëåäîâàííûå ìåòîäû è àëãîðèòìû ñæàòèÿ è ðàçâåðòûâàíèÿ äàííûõ, îñíî-
âàííûå íà ïðèìåíåíèè ËØÏÊ, ÿâëÿþòñÿ íàèáîëåå ïîäõîäÿùèìè.
Êî âòîðîìó êëàññó îòíîñÿòñÿ èñïîëüçóåìûå äëÿ ñæàòèÿ ïðîãðàììíî-
àïïàðàòíûå ñðåäñòâà. Ïðè ýòîì àïïàðàòíûå ðàñõîäû ëèìèòèðóþòñÿ ïàðà-
ìåòðàìè ïðîèçâîäèòåëüíîñòè ñèñòåìû â öåëîì è ýôôåêòèâíîñòüþ ñæàòèÿ
äàííûõ. Òàêàÿ ñèñòåìà õàðàêòåðèçóåòñÿ íàëè÷èåì áîëüøîãî ÷èñëà ðàçíî-
îáðàçíûõ ñïåöèàëèçèðîâàííûõ ìîäóëåé ñæàòèÿ è ðàçâåðòûâàíèÿ äàííûõ
è äîñòàòî÷íî ñëîæíûì àëãîðèòìîì èõ êîììóòàöèè.
Íà îñíîâå ðàññìîòðåííûõ àëãîðèòìîâ ìîæíî ðàçðàáîòàòü ïðîãðàì-
ìíûå è ïðîãðàììíî-àïïàðàòíûå ñðåäñòâà, îòíîñÿùèåñÿ ê îáîèì óêàçàí-
íûì êëàññàì. Â ðåçóëüòàòå àíàëèçà ïðåäëîæåííûõ ìåòîäîâ êîìïðåññèè
âûäåëèì ñëåäóþùèå òèïîâûå óêðóïíåííûå ïðîöåäóðû:
1. Êâàíòîâàíèå äâîè÷íîé ñòîõàñòè÷åñêîé ïîñëåäîâàòåëüíîñòè ïåðå-
ìåííûì øàãîì êâàíòîâàíèÿ m �3 4 8, , ..., ïîëó÷åíèÿ ñòàòèñòè÷åñêèõ äàí-
íûõ è èõ óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè (áóêâ àëôàâèòîâ).
2. Ôîðìèðîâàíèå òåãà è ìàññèâà ËØÏÊ.
À. Ø. Ñóëåéìàíîâ
76 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 4
Âèä
èíôîðìàöèè
Òèï ôàéëà
Èñõîäíûé
ðàçìåð
ôàéëà
(áàéò)
Ðåçóëüòàò ñæàòèÿ ïî ïðîãðàììå
Arj.exe Lharc.exe Pkzip.exe
Cf.exe
RPOS
Ca.exe
RGRUP
Ìàøèííûå
êîäû
f1.exe 103189 61375
1,7
65149
1,6
65353
1,6
102873
1,0
93079
1,1
Àíãëèéñêèé
òåêñò
f2. Txt 8764 2525
3,5
2637
3,3
2675
3,3
6986
1,3
4287
2
Áàçà äàííûõ f3.dBf 362 200
1,8
135
2,7
236
1,5
165
2,2
138
2,6
Ðóññêèé
òåêñò
f4. Rtxt 26279 4343
6
4650
5,6
5863
4,4
11876
2,2
10461
2,5
×èñëîâàÿ
èíôîðìàöèÿ
f5.dt 269 236
1,1
199
1,4
278
0,96
164
1,6
181
1,5
Ïðèìå÷àíèå: ïîä ÷åðòîé óêàçàí êîýôôèöèåíò ñæàòèÿ
Òàáëèöà 3
3. Ôîðìèðîâàíèå ïðåîáðàçîâàíèÿ äàííûõ, ò.å. ñæàòèå.
4. Ðàçâåðòûâàíèå (êàæäûé ìåòîä êîìïðåññèè èìååò ñîîòâåòñòâóþùèé
ìåòîä îáðàòíîãî ïðåîáðàçîâàíèÿ).
5. Îïðåäåëåíèå ýôôåêòèâíîãî ìåòîäà (àëãîðèòìà) ïðåîáðàçîâàíèÿ
êîíêðåòíîãî ñåãìåíòà (àíàëèç ëîêàëüíûõ ñòàòèñòè÷åñêèõ äàííûõ).
Äëÿ ïîâûøåíèÿ ýôôåêòèâíîñòè ðàáîòû âñåé ñèñòåìû äàííûå ïðîöå-
äóðû äîëæíû âûïîëíÿòüñÿ ñ ìàêñèìàëüíî âîçìîæíûìè ñîâìåùåíèÿìè
ìèêðî- è ìàêðîîïåðàöèé. Â ïàñïîðòíûõ òåãàõ ôàéëîâ äîëæíû íàõîäèòüñÿ
íåîáõîäèìûå, çàðàíåå ïîëó÷åííûå, ñòàòèñòè÷åñêèå äàííûå [12]. Òîãäà
ïðîöåññû ñæàòèÿ áóäóò âûïîëíÿòüñÿ áîëåå ïðîèçâîäèòåëüíî, áåç ïðèâëå-
÷åíèÿ äîïîëíèòåëüíûõ ïðîãðàììíûõ ñðåäñòâ, à òèïîâûå ìîäóëè îáðà-
áîòêè äàííûõ äàäóò âîçìîæíîñòü êîììóòèðîâàòü áîëåå ýôôåêòèâíóþ ñèñ-
òåìó ñæàòèÿ è ðàçâåðòûâàíèÿ äàííûõ.
Âûâîäû. Ïðåäëîæåííûå ìåòîäû ñæàòèÿ èíôîðìàöèè, îñíîâàííûå íà
ïðèìåíåíèè àáñòðàêòíîãî ìíîæåñòâà (àëôàâèòà) äâîè÷íûõ êâàíòîâ áåç
ó÷åòà ñòðóêòóðû åãî ïîñòðîåíèÿ è ñåìàíòèêè ïîçâîëÿþò íàéòè ñèñòåìíîå
ðåøåíèå çàäà÷è êîìïðåññèè äàííûõ è äàþò âîçìîæíîñòü îñóùåñòâëÿòü èõ
ìíîãîêðàòíîå ñæàòèå, ò.å. ñæàòèå ñæàòûõ äàííûõ. Íåäîñòàòêîì äàííûõ
àëãîðèòìîâ ÿâëÿåòñÿ áûñòðîäåéñòâèå îïåðàöèé ñæàòèÿ âñëåäñòâèå ïðåäâà-
ðèòåëüíîãî ñòàòèñòè÷åñêîãî àíàëèçà âõîäíûõ ôàéëîâ. Äëÿ óñòðàíåíèÿ
ýòîãî íåäîñòàòêà èññëåäóþòñÿ âîçìîæíîñòè àïïàðàòíî-ïðîãðàììíîé ðåà-
ëèçàöèè è ðàñïàðàëëåëèâàíèå îáðàáîòêè äëÿ ðàçëè÷íûõ øàãîâ êâàíòî-
âàíèÿ ïðè îïðåäåëåíèè ýôôåêòèâíîñòè ñæàòèÿ.
Îäíèì èç ïðåèìóùåñòâ ïðåäëîæåííûõ àëãîðèòìîâ ÿâëÿåòñÿ âîçìîæ-
íîñòü èõ ïðèìåíåíèÿ ïðè çàùèòå èíôîðìàöèè (îíè íå ïîçâîëÿþò êðèïòî-
àíàëèòèêó óñòàíîâèòü ïðèñóùèé åñòåñòâåííîìó ÿçûêó ñòàòèñòè÷åñêèé ïî-
ðÿäîê) è â ñèñòåìàõ àíàëèçà òåêñòîâîé èíôîðìàöèè äëÿ ñòðóêòóðíîãî
ïðåäñòàâëåíèÿ.
Computer algorithms of the universal scheme of a compression and ambiguous decompression of
arbitrary binary-coded information have been considered. Methods of compression based on the
statistic data and application of logical scales of positional coding bringing uniformity in the pro-
cesses of compression and decompression and allowing to develop relatively universal effective
means for compression of the data are offered.
1. Ãëóøêîâ Â. Ì. Îñíîâû áåçáóìàæíîé èíôîðìàòèêè. «Íàóêà Ý». — Ì. : Ãë. ðåä.
ôèç.-ìàò. ëèòåðàòóðû, 1987. — Ñ. 552.
2. Ïåéñòðèê Ã. Êàê óäâîèòü, à òî è óòðîèòü, åìêîñòü æåñòêîãî äèñêà// ÐÑ Magazine (Rus-
sian Edition). — 1992. — ¹ 2. — Ñ. 15—26.
3. Chen Z., Gehrke J., Korn F. Query Optimization in Compressed Database Systems // Proc.
2001 ÀÑÌ-SIGMOD Int. Conf. Management. Santa Barbara. — ÑÀ. — 2001. — Ð. 271— 282.
Àëãîðèòìû êîìïðåññèè ïðîèçâîëüíîé äâîè÷íî-êîäèðîâàííîé èíôîðìàöèè
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 4 77
4. Ñóëåéìàíîâ À. Ø., Ïàøàåâ È. Ñ. è äð. Îáíàðóæåíèå îøèáîê ïðè ïåðåäà÷å ÷èñëîâûõ
ìàññèâîâ â ñåòè ÝÂÌ ñ èñïîëüçîâàíèåì óïîðÿäî÷åíèÿ // Èçâ. âóçîâ «Íåôòü è ãàç» .—
1997. — ¹ 3—4. — Ñ. 52—54.
5. Êóðáàêîâ Ê. È. Êîäèðîâàíèå è ïîèñê èíôîðìàöèè â àâòîìàòè÷åñêîì ñëîâàðå. — Ì. :
Ñîâ. ðàäèî, 1968. — Ñ. 246.
6. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression // IEEE Transac-
tions on Information Theory. — 1977. — Vol. IT-23, ¹ 3. — Ð. 337—343.
7. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding // Ibid.—
1978. — Vol. IT-24, ¹ 5. — P. 530—536.
8. Ñóëåéìàíîâ À. Ø. Ñòðóêòóðíîå ïðåäñòàâëåíèå òåêñòîâîé èíôîðìàöèè íà îñíîâå ìå-
òîäîâ ñæàòèÿ // Èíôîðìàöèîííûå òåõíîëîãèè ìîäåëèðîâàíèÿ è óïðàâëåíèÿ. — 2008. —
Âûï. 7 (50). — Ñ. 765—771.
9. Ñóëåéìàíîâ À. Ø. Ñåìàíòè÷åñêàÿ áëèçîñòü è ñåìàíòè÷åñêèå ðàññòîÿíèÿ ìåæäó òåêñ-
òàìè // Ìåæäóíàðîäíûé íàó÷íî-òåõíè÷åñêèé ñá. «Àäàïòèâíûå ñèñòåìû àâòîìàòè÷åñ-
êîãî óïðàâëåíèÿ» — Äíåïðîïåòðîâñê : Ñèñòåìíûå òåõíîëîãèè, 2007. — 164 ñ.
10. Ñóëåéìàíîâ À. Ø., Äàìàäàåâ Ì. Ì. Àïïàðàòíûå è ïðîãðàììíûå ñðåäñòâà äèíàìè-
÷åñêîãî ñæàòèÿ äàííûõ // Íàó÷. òð. Íàöèîíàëüíîé àêàäåìèè àâèàöèè. — 1999. — ¹ 1. —
Ñ. 169—174
11. Ñóëåéìàíîâ À. Ø., Êàñóìîâ Í. Ê. Îá îäíîì ìåòîäå êîìïðåññèè â ðåøåíèè ïðîáëåì ðå-
çåðâíîãî êîïèðîâàíèÿ è âîññòàíîâëåíèÿ äàííûõ íà ôîíå ñáëèæåíèÿ âîçìîæíîñòåé
SAN è NAS // Èçâ. ÍÀÍ Àçåðáàéäæàíà. Ñåð. ôèçèêî-òåõíè÷åñêèõ è ìàòåìàòè÷åñêèõ
íàóê. — 2004. — XXIV, ¹ 2. — Ñ. 35—39.
12. Ñóëåéìàíîâ À. Ø. Èíòåëëåêòóàëèçàöèÿ ñèñòåì îáðàáîòêè èíôîðìàöèè. — Áàêó :
«Ýëì», 2004. — 240 ñ.
Ïîñòóïèëà 18.02.09;
ïîñëå äîðàáîòêè 09.04.09
ÑÓËÅÉÌÀÍÎÂ Àêèô Øàìèë îãëû, êàíä. òåõí. íàóê, äîöåíò, çàâ. êàôåäðîé Àçåðáàéäæàíñ-
êîãî òåõíè÷åñêîãî óíèâåðñèòåòà.  1976 ã. îêîí÷èë Ìîñêîâñêèé ýíåðãåòè÷åñêèé èí-ò. Îá-
ëàñòü íàó÷íûõ èññëåäîâàíèé — èíòåëëåêòóàëèçàöèÿ ñèñòåìû îáðàáîòêè èíôîðìàöèè, ñæà-
òèå èíôîðìàöèè.
À. Ø. Ñóëåéìàíîâ
78 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 4
|