Метод быстрого таймерного кодирования текстов
Розроблено статистично-орієнтований метод стискання даних з застосуванням нетрадиційного таймерного шифрування, а також необхідні оцінки складності. Метод може застосовуватись для стискання SMS повідомлень. Зроблено ймовірнісно-статистичний аналіз та отримано оцінки його ефективності. Розрахована шв...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/86174 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод быстрого таймерного кодирования текстов / Р.В. Скуратовский // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 154-160. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860251379378946048 |
|---|---|
| author | Скуратовский, Р.В. |
| author_facet | Скуратовский, Р.В. |
| citation_txt | Метод быстрого таймерного кодирования текстов / Р.В. Скуратовский // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 154-160. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розроблено статистично-орієнтований метод стискання даних з застосуванням нетрадиційного таймерного шифрування, а також необхідні оцінки складності. Метод може застосовуватись для стискання SMS повідомлень. Зроблено ймовірнісно-статистичний аналіз та отримано оцінки його ефективності. Розрахована швидкість архівування даних є найбільшою серед світових аналогів. Отримано часову складність О(n²) , за допомогою якої з урахуванням частоти генератора тексту легко отримати час архівування.
A statistics-oriented data compression method based on unconventional timer encryption is developed. Necessary complexity estimates are made. The method can be used to compress sms messages. A probabilistic analysis is performed and its efficiency is evaluated. The theoretical data compression rate is the world’s highest. The time complexity O(n²) is determined, which can be used to find the archiving time taking into account the frequency of the text generator.
|
| first_indexed | 2025-12-07T18:43:29Z |
| format | Article |
| fulltext |
ÓÄÊ 521.1, 514.01
Ð.Â. ÑÊÓÐÀÒÎÂÑÊÈÉ
ÌÅÒÎÄ ÁÛÑÒÐÎÃÎ ÒÀÉÌÅÐÍÎÃÎ ÊÎÄÈÐÎÂÀÍÈß ÒÅÊÑÒÎÂ
Êëþ÷åâûå ñëîâà: áëî÷íîå êîäèðîâàíèå, àðõèâàöèÿ, àëãîðèòì ñæàòèÿ äàí-
íûõ, òàéìåðíîå êîäèðîâàíèå.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Âîçìîæíîñòè òàéìåðíîãî êîäèðîâàíèÿ èçó÷àëà öåëàÿ ïëåÿäà ó÷åíûõ. Áûëè
âûÿâëåíû âîçìîæíîñòè òàéìåðíîãî ìàñêèðîâàíèÿ èíôîðìàöè [1], ïîñòðîåíèÿ
êîðïîðàòèâíîé ñèñòåìû çàùèòû èíôîðìàöèè [2], øèôðîâàíèÿ [3, 6, 7]. Îäíà-
êî ãëàâíûì ïðåèìóùåñòâîì òàéìåðíîãî êîäèðîâàíèÿ ÿâëÿåòñÿ âîçìîæíîñòü
êîäèðîâàíèÿ è ñæàòèå èíôîðìàöèè. Ýòèì âîïðîñîì çàíèìàëèñü Â.Ô. Áàðäà-
÷åíêî è Å.Î. Îñàä÷èé [1, 5].
Èçâåñòíî, ÷òî ïðè àðõèâàöèè äàííûõ èíîãäà íåîáõîäèìî ïðèìåíÿòü àëãî-
ðèòìû ïîèñêà, ïîñêîëüêó ïðè ðàáîòå, â ÷àñòíîñòè, òàêîãî àðõèâàòîðà êàê RAR,
èñïîëüçóåòñÿ àëãîðèòì ïîèñêà ÂWT, îöåíêà ñëîæíîñòè êîòîðîãî ñîñòàâëÿåò
O n n( )log 2 . Âàæíîé õàðàêòåðèñòèêîé àëãîðèòìà àðõèâàöèè ÿâëÿåòñÿ êîýôôèöè-
åíò ñæàòèÿ èíôîðìàöèè. Åãî öåëåâàÿ ôóíêöèÿ îïðåäåëÿåòñÿ ôîðìóëîé
F k x k y� � �1 2 min ,
ãäå x — îáúåì, y — âðåìÿ ( àääèòèâíà ôîðìà), x Q y t� �1 1, (Q1 — êîíñòàí-
òà, çàäàþùàÿ ìàêñèìàëüíî äîïóñòèìûé îáúåì).
Öåëü íàñòîÿùåé ñòàòüè — äîñòè÷ü íàèáîëüøåãî ñæàòèÿ èíôîðìàöèè ñ íàè-
ìåíüøèìè çàòðàòàìè âðåìåíè. Ãðàíè÷íîé âåëè÷èíîé ñæàòèÿ ïðîèçâîëüíîãî òåê-
ñòîâîãî ôàéëà áóäåì ñ÷èòàòü 8 áèò. Íà ïðàêòèêå ïðè òàéìåðíîì êîäèðîâàíèè
èìååì ëèíåéíûé ðîñò îáúåìà âûäåëåííîé ïàìÿòè, êîòîðûé çàâèñèò îò êîëè÷å-
ñòâà ìåòîê. Äëÿ äàëüíåéøåãî èçëîæåíèÿ ìàòåðèàëà èñïîëüçóþòñÿ òåðìèíû èç ðà-
áîò [7–9]. Ïðåäëîæåíûé â ñòàòüå ìåòîä ñæàòèÿ ìîæíî ïðèìåíÿòü ïîñëå ñæàòèÿ
òåêñòà óæå èçâåñòíûì ðàíåå àðõèâàòîðîì, êîòîðûé èñïîëüçóåò ìåòîäû ñèìâîëü-
íîãî êîäèðîâàíèÿ. Îöåíêà åãî ñëîæíîñòè äëÿ ïðîöåññà ñæàòèÿ òåêñòà ñ n ñèìâî-
ëàìè ñîñòàâëÿåò âåëè÷èíó 3 2 1( | | ) ([ / ] )length A n n� � , êîòîðàÿ â îòëè÷èå îò ñóùå-
ñòâóþùèõ ìåòîäîâ òàéìåðíîãî êîäèðîâàíèÿ íàìíîãî ìåíüøå, ïîñêîëüêó ïîñëåä-
íèå èìåëè ýêñïîíåíöèàëüíóþ çàâèñèìîñòü âðåìåíè ðàáîòû îò n. Çäåñü A —
àëôàâèò âñåõ èñïîëüçóåìûõ â òåêñòå ñèìâîëîâ.
 ïðîöåññå ðàáîòû àëãîðèòìà äîëæíû áûòü ñîáëþäåíû ñëåäóþùèå îãðàíè-
÷åíèÿ. Îáúåäèíåííûå áëîêè òåêñòà, ñîîòâåòñòâóþùèå ðàñêîäèðîâàííûì ìåòêàì,
154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
© Ð.Â. Ñêóðàòîâñêèé, 2013
îòâå÷àþò âñåìó òåêñòó, ñêîðîñòü ðàçàðõèâèðîâàíèÿ êîòîðîãî íå ìåíåå ÷åì s0 .
Ïðè ñðàâíåíèè ãðàíèö ñæàòèÿ äàííîãî ìåòîäà ñ äðóãèìè ìåòîäàìè ñëåäóåò
ó÷èòûâàòü, ÷òî ïðè ñèìâîëüíîì êîäèðîâàíèè ñ îäíîçíà÷íûì äåêîäèðîâàíèåì,
ò.å. â ïðåôèêñíîì êîäèðîâàíèè [1], ñóùåñòâóåò êîä ñ íàèáîëüøåé äëèíîé ñèìâî-
ëà L c( , )� : H ( )� � L c H( , ) ( )� �� �1 , ãäå H ( )� — ýíòðîïèÿ èñòî÷íèêà, ò.å. åãî íèæ-
íÿÿ ãðàíü, H p pi
i
n
i( ) ( / )� �
�
�
1
2 1log , ïðåäñòàâëÿþùàÿ ñðåäíåå îæèäàåìîå êîëè-
÷åñòâî èíôîðìàöèè, êîòîðóþ ñîäåðæèò îäèí ñèìâîë. Î÷åâèäíî, ÷òî ïðè óâåëè-
÷åíèè äëèíû òåêñòà Ò äëèíà êîäà, â ÷àñòíîñòè àðèôìåòè÷åñêîãî, áóäåò ëèíåéíî
âîçðàñòàòü. Ïðåäëîæåííûé çäåñü ìåòîä ïðè èñïîëüçîâàíèè îäíîé ìåòêè äëÿ çà-
êîäèðîâàíèÿ òåêñòà òðåáóåò ïàìÿòü, íåîáõîäèìóþ äëÿ ñîõðàíåíèÿ ìåòêè è îïòè-
ìàëüíîãî ïîðÿäêà ñèìâîëîâ äëÿ òåêñòîâîãî ãåíåðàòîðà. Ýòîò ïîðÿäîê åäèíûé äëÿ
âñåãî òåêñòà, ïîýòîìó íå âëèÿåò íà ôóíêöèþ ðîñòà êîëè÷åñòâà îïåðàöèé. Ïðè
ýòîì äëèíà êîäà âîçðàñòàåò íå áîëåå ÷åì ëèíåéíî ñ óâåëè÷åíèåì äëèíû òåêñòà.
Îäíàêî êîãäà èñïîëüçóåòñÿ ñèñòåìà ìåòîê ñ äëèíîé áëîêà êîäèðóåìîãî òåêñòà
3 áàéòà, òî äàæå ïîñëå àðõèâèðîâàíèÿ ìåòîäîì ñèìâîëüíîãî êîäèðîâàíèÿ è äîñ-
òèæåíèÿ íèæíåé ãðàíèöû ñæàòèÿ ïî Øåííîíó ìîæíî äîñòè÷ü ñæàòèÿ, êàê ìàêñè-
ìóì, â 24 ðàçà ïîñëå ïðèìåíåíèÿ òàéìåðíîãî êîäèðîâàíèÿ. Íàïîìíèì, ÷òî íèæ-
íÿÿ ãðàíèöà ñæàòèÿ ïî Øåííîíó ïðè 32-ñèìâîëüíîì àëôàâèòå — ýòî 5 áèò íà
ñèìâîë (à ñ ó÷åòîì íåðàâíîìåðíîãî ðàñïðåäåëåíèÿ áóêâ è âçàèìîçàâèñèìîñòè
â ïîñëåäîâàòåëüíîñòè áóêâ — ýòî 2 áèòà). Â íàñòîÿùåé ñòàòüå âïåðâûå ïðåä-
ëîæåíû íîâûå ìåòîäû òàéìåðíîãî êîäèðîâàíèÿ, äîêàçàíà èõ ýôôåêòèâíîñòü, ðàçðà-
áîòàíî ñîîòâåòñòâóþùåå ìàòåìàòè÷åñêîå îáåñïå÷åíèå äëÿ åãî îïòèìèçàöèè.
ÎÑÍÎÂÍÛÅ ÌÀÒÅÌÀÒÈ×ÅÑÊÈÅ ÂÅËÈ×ÈÍÛ
È ÑÂÎÉÑÒÂÀ ÈÑÑËÅÄÓÅÌÎÃÎ ÌÅÒÎÄÀ
Cèìâîëû òåêñòà èìåþò îòíîñèòåëüíûå ÷àñòîòû f s As, � , ãäå A — àëôàâèò ñèì-
âîëîâ èç T , êîòîðûå óïîðÿäî÷èâàåì ïî óáûâàíèþ ÷àñòîò. Îòìåòèì, ÷òî ãåíåðàòîð
âûðàáàòûâàåò ñèìâîëû â çàäàííîì óáûâàþùåì ïîðÿäêå ïîñëåäîâàòåëüíî ïî ðàçðÿ-
äàì. Âðåìÿ è ðåçóëüòàò ðàáîòû îäíîçíà÷íî îïðåäåëÿþòñÿ òàéìåðíîé ìåòêîé.
Îïðåäåëåíèå 1. Ñòàòèñòè÷åñêè îðèåíòèðîâàííûé ãåíåðàòîð òåêñòîâ Gs
ïðåäñòàâëÿåò àëãîðèòì, êîòîðûé ðåàëèçóåò íåîáõîäèìûé ðÿä ðàñïðåäåëåíèÿ ÷à-
ñòîò f fi j ñèìâîëîâ n ni j
, ãäå ni , n j — íîìåðà i-ãî è j-ãî ñèìâîëîâ â ïîëó-
÷åííîì ïîðÿäêå �.
Îïðåäåëåíèå 2. Ãåíåðàòîð òåêñòîâ ñ àëôàâèòíûì óïîðÿäî÷åíèåì îáîçíà÷èì Gp.
Îí ïîñëåäîâàòåëüíî ðåàëèçóåò òåêñòû, ãåíåðèðóÿ ñèìâîëû â àëôàâèòíîì ïîðÿäêå, ò.å.
íå ó÷èòûâàåò ÷àñòîòû ïîÿâëåíèÿ ýòèõ ñèìâîëîâ â îïðåäåëåííîì âèäå òåêñòîâ.
Ìíîæåñòâî ìåòîê îáðàçóåò 1-ñäâèã (ñäâèã íà îäèí ñèìâîë) B [9], à íà ìíî-
æåñòâå áëîêîâ êîäèðóåìîãî (ñæèìàåìîãî) òåêñòà îïðåäëåí m-ñäâèã A. Îòîáðàæå-
íèå �: A B� ÿâëÿåòñÿ áëî÷íûì êîäèðîâàíèåì. Òåêñòîâûé ãåíåðàòîð ãåíåðèðóåò
ïîñëåäîâàòåëüíî âñå òåêñòû äëèíîé k, ðàññìàòðèâàÿ êàæäûé èç íèõ â îòäåëüíîì
îêíå (áëîêå äëèíîé k). Åñëè ïîñëå ãåíåðàöèè îäíîãî èç íèõ íà óïðàâëÿþùèé
âõîä íå ïîñòóïèë ñèãíàë ïðåðûâàíèÿ, òî ãåíåðàòîð íà÷èíàåò ãåíåðèðîâàòü âñå
òåêñòû äëèíîé k �1 è ò.ä. Ïî îêîí÷àíèè ýòîãî ïðîöåññà ïîëó÷àåì îäíîçíà÷íî
îïðåäåëåííûé ñèìâîëîì èç Y áëîê òåêñòà äëèíîé ò, ãäå Y — àëôàâèò ïðîñòðà-
íñòâà ñäâèãà Â. Òàêèì îáðàçîì, èìååì áèåêòèâíîå îòîáðàæåíèå �� �1: B A. Ïî-
ýòîìó äëÿ ñîêðàùåíèÿ ïåðåáîðà òåêñòîâ ïðè ðàçàðõèâàöèè äàííûõ â êîä ñæàòîãî
òåêñòà C öåëåñîîáðàçíî âêëþ÷àòü òàêæå è äëèíó èñõîäíîãî òåêñòà.
Îïðåäåëåíèå 3. Òàéìåðíàÿ ìåòêà ñîîòâåòñòâóåò íåîáõîäèìîìó ñîñòîÿíèþ
òåêñòîâîãî ãåíåðàòîðà.  îáùåì ñëó÷àå òàéìåðíûé ãåíåðàòîð — ýòî óñòðîéñòâî,
êîòîðîå ðåàëèçóåò îòñ÷åò (èíêðåìåíòàöèþ) â âûáðàííîé ñèñòåìå ñ÷èñëåíèÿ ñ ïî-
ñòîÿííîé ÷àñòîòîé è äèñêðåòèçàöèåé.  êà÷åñòâå ñèñòåìû ñ÷èñëåíèÿ ìîæåò áûòü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 155
âûáðàíà è âðåìåííàÿ ñèñòåìà îòñ÷åòà. Òàéìåðíûå ìåòêè ïðèíèìàþò çíà÷åíèÿ èç
äèñêðåòíîãî ìíîæåñòâà ñ îäèíàêîâûìè ðàññòîÿíèÿìè ìåæäó ñîñåäíèìè òî÷êà-
ìè. Ýòè ðàññòîÿíèÿ îáðàòíî ïðîïîðöèîíàëüíî çàâèñÿò îò ñêîðîñòè ðàáîòû Gs.
Îïðåäåëåíèå 4. Íîìåðîì ñèìâîëà s A� ïðè çàäàííîì ïîðÿäîêå � ÿâëÿåòñÿ
åãî ïîðÿäêîâûé íîìåð ns � � â ýòîì óïîðÿäî÷åíèè, êîòîðîå îñóùåñòâëÿåòñÿ äëÿ
ñòàòèñòè÷åñêîãî ãåíåðàòîðà Gs â ñîîòâåòñòâèè ñ âåðîÿòíîñòÿìè, õàðàêòåðíûìè
äëÿ ñèìâîëîâ âûáðàííîãî òåêñòà. Çàìåòèì, ÷òî âåñîì ñèìâîëà áóäåò èìåííî åãî
íîìåð ni â ÷àñòîòíîì óïîðÿäî÷åíèè òàêîì, ÷òî åñëè f fi j , òî n nj i .
Îïðåäåëåíèå 5. Âåñîì ñëîâà W èëè òåêñòà Ò à à à àn� 1 2 3 ... íàçîâåì âåëè÷èíó
Wh T n Ai
n i
i
n
( ) | |� �
�
�
1
,
ãäå ni — íîìåð ñèìâîëà, êîòîðûé íàõîäèòñÿ íà ³-ì ìåñòå òåêñòà â çàäàííîì
äëÿ ãåíåðàòîðà óïîðÿäî÷åíèè, n — äëèíà òåêñòà T , | |A N� — ìîùíîñòü ìíî-
æåñòâà ñèìâîëîâ.
Òåêñòîâûé ãåíåðàòîð, ïîñòàâèâ íåïðàâèëüíî ïåðâóþ áóêâó, âûíóæäåí ïîñëå
íåå ïîñëåäîâàòåëüíî ïåðåáèðàòü íà âñåõ ïîçèöèÿõ âñå áóêâû èç À — ìíîæåñòâà
ñèìâîëîâ, ïîêà íå äîéäåò äî âåëè÷èíû âðåìåíè, ðàâíîé òàéìåðíîé ìåòêå äëÿ T .
Íàïðèìåð, åñëè çàêîäèðîâàíî ÷èñëî T �1567, à ãåíåðàòîð ïîñòàâèë ïåðâóþ öèô-
ðó 2 (÷òî îòâå÷àåò óïîðÿäî÷åíèþ 2,3,4,5,6,7,8,9,0,1), òî îí áóäåò ïåðåáèðàòü âñå
öèôðû, óâåëè÷èâ ñíà÷àëà ñèìâîë âî âòîðîì ðàçðÿäå, çàòåì âñå êîìáèíàöèè â ñëå-
äóþùèõ ðàçðÿäàõ è òàê äàëåå âïëîòü äî íàáîðà a a a aN N N1 . Çàòåì îí âîçâðàòèò-
ñÿ ê ïåðâîé ïîçèöèè, ãäå çàìåíèò öèôðó 2 íà ñëåäóþùóþ ïî ïîðÿäêó öèôðó 3
(êîòîðàÿ òàêæå îøèáî÷íà) è ñíîâà íà÷íåò ãåíåðèðîâàòü ñèìâîëû â ìåíüøèõ ðàç-
ðÿäàõ. Ïåðåáîð ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà ãåíåðàòîð íå ïîñòàâèò â ïåðâîì
ðàçðÿäå öèôðó 1. Òàêèì îáðàçîì, â êàæäîì ðàçðÿäå îò âòîðîãî äî ÷åòâåðòîãî
áûëî èñïîëüçîâàíî äåâÿòü èëè äåñÿòü öèôð, à â ïåðâîì ðàçðÿäå áûëè ïåðåáðàíû
âñå äåñÿòü öèôð. Ïîýòîìó äëÿ äàííîãî T âåðõíÿÿ ãðàíèöà ïåðåáðàííûõ êîìáèíà-
öèé ïðè íåïðàâèëüíî âûáðàííîì ñèìâîëå a1 ðàâíà n1
310� , à ïðè íåïðàâèëüíî
âûáðàíîì ñèìâîëå a2 ýòîé îöåíêîé áóäåò n2
210� êîìáèíàöèé è ò.ä. Òîãäà âåñ
òåêñòà ñîñòàâëÿåò Wh n n n n( )1567 10 10 101
3
2
2
3 4� � � � � � � , ãäå n n1 210 4� �, ,
n n3 45 6� �, , à ïðè îïòèìàëüíîì óïîðÿäî÷åíèè n n n n1 2 3 41 2 3 4� � � �, , , .
Îöåíî÷íàÿ âåëè÷èíà ïåðåáîðà ïðè íåïðàâèëüíî ïîñòàâëåííîì ñèìâîëå a1
ñîñòàâëÿåò n A n
1
1� �| | .  ýòîì ñëó÷àå âåëè÷èíà | |A n�1 ÿâëÿåòñÿ âåñîì ïîçèöèè
ïåðâîãî ñèìâîëà èëè ïåðâîãî ðàçðÿäà.  îáùåì ñëó÷àå âåëè÷èíà | |A n i� ðàâíà
âåñó i-ãî ñèìâîëà.
Òàêèì îáðàçîì, Wh T( ) — ýòî ÷èñëî ïåðåáðàííûõ ãèïåðñëîâ ïðè âûáðàííîì
óïîðÿäî÷åíèè áóêâ, ïîñëå êîòîðîãî ñëåäóåò èñêîìûé òåêñò T .
Óòâåðæäåíèå 1. Çíàÿ âåñà ñèìâîëîâ, ìîæíî áûñòðî âû÷èñëèòü âåñ âñåãî òåêñòà.
Äåéñòâèòåëüíî, ïîñêîëüêó òåêñò èçâåñòåí, òî èìååì ñèìâîëüíîå óïîðÿäî÷å-
íèå � ñ âåñàìè ni ñèìâîëîâ èç T . Ïîýòîìó ìîæíî ïðèìåíèòü ôîðìóëó
Wh T n Ai
n i
i
n
( ) | |� �
�
�
1
.
Èññëåäóåì íåêîòîðûå ñâîéñòâà òàéìåðíûõ ìåòîê òåêñòà. Ïóñòü òåêñò ãåíå-
ðèðóåòñÿ ñ îäèíàêîâîé ñêîðîñòüþ è ôèêñèðîâàííûì ïîðÿäêîì.
Óòâåðæäåíèå 2. Ìåæäó ìíîæåñòâîì äâîè÷íûõ çàïèñåé ÷èñåë è ìíîæåñòâîì
òàéìåðíûõ ìåòîê ýòèõ ÷èñåë ñóùåñòâóåò áèåêòèâíîå îòîáðàæåíèå ïðè ôèêñèðî-
âàííîì�, ïðè÷åì äëÿ ïîñòðîåíèÿ îòîáðàæåíèÿ íå íóæíî ïîñëåäîâàòåëüíîãî ãå-
íåðèðîâàíèÿ âñåõ ïðåäøåñòâóþùèõ òåêñòîâ äàííîìó òåêñòó.
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
Äåéñòâèòåëüíî, òàéìåðíóþ ìåòêó äàííîãî äâîè÷íîãî ÷èñëà à, à çíà÷èò è ñî-
îòâåòñòâóþùåãî åìó òåêñòà, ìîæíî ïîëó÷èòü èç ôîðìóëû
t
N a
V
� 2 ( )
.
Çäåñü N a2 ( ) — äâîè÷íîå ÷èñëî, êîòîðîå îòâå÷àåò êîäó äàííîãî òåêñòà (âåñó
òåêñòà ïðè äàííîì ïîðÿäêå ãåíåðèðîâàíèÿ ñèìâîëîâ), V — ñêîðîñòü (÷àñòîòà)
ðàáîòû ãåíåðàòîðà. Ïðè ýòîì | ( )| ( )N a Wh Tp2 � , ãäå Wh Tp ( ) — ñëîæíîñòü ïî-
ðîæäåíèÿ (âåñà) òåêñòà Ò ïðè îïðåäåëåííîì ëèíåéíîì óïîðÿäî÷åíèè. Äëÿ ñòà-
òèñòè÷åñêè îðèåíòèðîâàííîãî ãåíåðàòîðà ñ ñèìâîëüíûì óïîðÿäî÷åíèåì � âå-
ëè÷èíà òàéìåðíîé ìåòêè îïðåäåëÿåòñÿ ôîðìóëîé
t
Wh T
V
s( )
( )
�0 � .
Çíàÿ âåñ òåêñòà, ìîæíî ðàçäåëèòü åãî íà k ÷àñòåé. Äëÿ êàæäîé ÷àñòè âû÷èñ-
ëèòü âåñ è âåëè÷èíó òàéìåðíîé ìåòêè t i( )� , 1 � �i k. Òàêèì îáðàçîì, ïîëó÷åíà
ñèñòåìà òàéìåðíûõ ìåòîê y t� ( )�
ïóòåì âû÷èñëåíèÿ ñóììû ðÿäà, à íå ãåíåðà-
òîðíîãî ïåðåáîðà ìíîæåñòâà ãèïåðñëîâ â ñîîòâåòñòâèè ñ ïîëó÷åííûì ëåêñèêî-
ãðàôè÷åñêèì óïîðÿäî÷åíèåì ñîãëàñíî �.
Ïîñëåäîâàòåëüíîñòü âåëè÷èí | |A n âû÷èñëÿåòñÿ ðåêóðñèâíî è èìååò âðåìåííóþ
ñëîæíîñòü length length(| | ) ([ / ] ) ( | | ) ([ / ] )A n A n2 2 1 2 2 1� � � � � � 2 2 12( )([ / ] )log A n �
ñîãëàñíî ìåòîäó áèíàðíîãî âîçâåäåíèÿ â ñòåïåíü «÷åòûðåõ ðóññêèõ» [8], à äëèíû
ñèìâîëîâ èç À îãðàíè÷åíû îäíèì áàéòîì. Ïîýòîìó óìíîæàÿ n T�| | íà íîìåð ni ,
ïîëó÷àåì òî÷íîå îáùåå âðåìÿ, ïðè ýòîì îöåíêà âðåìåííîé ñëîæíîñòè ñîñòàâëÿåò
3 2 1( | | ) ([ / ] )length A n n� � . Òàêèì îáðàçîì, èìååì âðåìÿ ïðîöåññà àðõèâàöèè —
òàéìåðíóþ ìåòêó ãåíåðàòîðà áåç çàïóñêà ïîñëåäîâàòåëüíîãî ïåðåáîðà òåêñòîâ
äëÿ ïîëó÷åíèÿ ìåòêè.
Îáúåì ñæàòîé èíôîðìàöèè âû÷èñëÿåòñÿ, èñõîäÿ èç ñóììû îáúåìîâ ìå-
òîê, êîòîðûå ñîîòâåòñòâóþò êàæäîìó áëîêó òåêñòà, ïðåäñòàâëåííîìó äâîè÷-
íûì ÷èñëîì N a2 ( ) . Êàæäîìó áëîêó ñîîòâåòñòâóåò òàéìåðíàÿ ìåòêà t. Åå îáú-
åì ðàâåí Q t( ) . Òîãäà îáúåì ïîñëå ñæàòèÿ âñåãî òåêñòà áóäåò Q T Q ti
i
k
( ) ( )�
�
�
1
, ãäå
ti — i-ÿ ìåòêà èç àëôàâèòà Y , k — êîëè÷åñòâî áëîêîâ.
Íàïîìíèì, ÷òî âåðîÿòíîñòü ïîÿâëåíèÿ Ò — ýòî êóìóëÿòèâíàÿ âåðîÿòíîñòü
P T p p pn( ) ...� 1 2 , ãäå pi — âåðîÿòíîñòü ïîÿâëåíèÿ i-é áóêâû â òåêñòå èç äàííîé
îáëàñòè çíàíèé. Íåïîñðåäñòâåííî ñàìè òåêñòû óïîðÿäî÷èâàþòñÿ ëåêñèêîãðàôè-
÷åñêè.  ýòîì ñëó÷àå ñðåäíåñòàòèñòè÷åñêèé âåñ òåêñòà ðàâåí ìàòåìàòè÷åñêîìó
îæèäàíèþ îò âñåõ âåñîâ ñëîâ
M Wh W P W Wi i
i
l
( ( )) ( )�
�
�
1
,
ãäå l — ÷èñëî ñëîâ â òåêñòå.
Äîêàæåì ýôôåêòèâíîñòü ñòàòèñòè÷åñêîãî ìåòîäà ãåíåðèðîâàíèÿ äëÿ ìíî-
æåñòâà ãèïåðñëîâ. Ãèïåðñëîâî w ïðè ëåêñèêîãðàôè÷åñêîì ïîðÿäêå, êîòîðûé èñ-
ïîëüçóåò àäàïòèâíûé ñòàòèñòè÷åñêèé ãåíåðàòîð Gs, èìååò ìåíüøèé íîìåð, ÷åì
ïðè èñïîëüçîâàíèè ëåêñèêîãðàôè÷åñêîãî óïîðÿäî÷åíèÿ ïåðåáèðàþùåãî ãåíåðà-
òîðà Gp. Äëÿ ïðåôèêñà ãèïåðñëîâà ââîäÿòñÿ îòäåëüíàÿ ñèñòåìà ÷àñòîò áóêâ è ñî-
îòâåòñòâóþùàÿ ñèñòåìà ìåòîê, à ïðè íåïðàâèëüíîì âûáîðå íà÷àëüíîé áóêâû, íà-
ïðèìåð èç i-é ïîçèöèè, ïðîèñõîäèò ãåíåðèðîâàíèå âñåõ ïîñëåäóþùèõ | |A n i� êîì-
áèíàöèé, ÷òî õàðàêòåðíî ïðè ðàáîòå Gp.
 ïðîöåññå ôîðìèðîâàíèÿ òåêñòà ãåíåðàòîð ïîëó÷àåò åãî äâîè÷íóþ ìåòêó
äëÿ êàæäîãî âàðèàíòà òåêñòà ñ öåëüþ ñðàâíåíèÿ ñãåíåðèðîâàííîãî ÷èñëà, êîòî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 157
ðîå, åñòåñòâåííî, îòâå÷àåò îïðåäåëåííîìó òåêñòó, ñ ìåòêîé îðèãèíàëüíîãî òåêñòà
(îáîçíà÷èì åå �0). Ìåòêà �0 , âû÷èñëåííàÿ ïðè ðàáîòå ñòàòèñòè÷åñêîãî ãåíåðà-
òîðà, ñîîòâåòñâóåò ìåíüøåìó äâîè÷íîìó ÷èñëó, ÷åì ìåòêà �1 äëÿ ãåíåðàòîðà,
äåéñòâóþùåãî ïðÿìûì ïåðåáîðîì. Ýòî îáóñëîâëåíî òåì, ÷òî áóêâû, êîòîðûå
èìåþò áîëüøóþ âåðîÿòíîñòü ïîÿâëåíèÿ, êîäèðóþòñÿ â ñðåäíåì ìåíüøèìè äâî-
è÷íûìè ÷èñëàìè â òàáëèöå ñèìâîëüíîãî ïîðÿäêà, ò.å. èìåþò ìåíüøèå äâîè÷íûå
çíà÷åíèÿ ni â ôîðìóëå Wh T n Ai
n i
i
n
( ) | |� �
�
�
1
, ÷åì íîìåðà ýòèõ æå áóêâ ïðè ðàáîòå
ïåðåáîðíîãî ãåíåðàòîðà. Ïîýòîìó ñèìâîëû ñëîâà è ñîîòâåòñòâóþùèå èì òåêñòû,
êîòîðûå áîëåå õàðàêòåðíû äëÿ äàííîé îòðàñëè çíàíèé, òàêæå ïîëó÷àò ìåíüøèå
íîìåðà è ìåíüøèå âåñà Wh TS ( ) ïðè ñîçäàííîì ñòàòèñòè÷åñêîì óïîðÿäî÷åíèè.
Ñîîòâåòñòâåííî â åäèíè÷íîé ñèñòåìå ñ÷èñëåíèÿ [6] èì ñîîòâåòñâóþò ìåíüøèå
òàéìåðíûå ìåòêè:
t
Wh T
V
( )
( )
�0 � .
Äëÿ ïåðåáîðíîãî ãåíåðàòîðà òåêñòà âåñ ñîâïàäàåò ñ äâîè÷íûì ÷èñëîì
N a2 ( ), òàê êàê t
N a
V
( )
( )
�1
2� . Îäíàêî N a Wh TS2 ( ) ( ) , ïîñêîëüêó äëÿ áîëü-
øèíñòâà çíà÷åíèé i äëÿ ni è mi èìååì m ni i , ãäå mi — íîìåð áóêâû, êîòîðàÿ
íàõîäèòñÿ â i-ì ìåñòå òåêñòà â ïîðÿäêå, èñïîëüçóåìîì Gp, îòñþäà t t( ) ( )� �0 1
.
Äëÿ àðõèâàöèè òåêñòà, ÷òî ðàâíîñèëüíî ñîçäàíèþ åãî ìåòêè èëè ñèñòåìû ìå-
òîê, äîñòàòî÷íî âû÷èñëèòü t
Wh T
V
S( )
( )
�0 � , à äëÿ ãåíåðàòîðà Gp — îïðåäåëèòü
t
N a
V
( )
( )
�1
2� . Äëÿ ýòîãî íóæíî ñäåëàòü ñ÷èòûâàíèå âñåõ ñèìâîëîâ èç T , ãäå
| |T N� , è âûïîëíèòü N �1 óìíîæåíèé íà âåñ ðàçðÿäà, ò.å. íà | | ,A k 0 1� � �k N .
Âðåìÿ âû÷èñëåíèÿ ïðîèçâåäåíèÿ ÷èñåë ðàâíî ïðîèçâåäåíèþ äëèí ýòèõ ÷èñåë.
Ïîñëåäîâàòåëüíîñòü âåëè÷èí | |A n âû÷èñëÿåòñÿ ðåêóðñèâíî (ñíà÷àëà âû÷èñëÿåòñÿ
À, à çàòåì åãî êðàòíûå ïðîèçâåäåíèÿ è ïðîèçâåäåíèå ñ A) è èìååò âðåìåííóþ
ñëîæíîñòü length length(| | ) ([ / ] ) ( | | ) ([ / ] )A n A n2 22 1 2 1� � � � � , ïðè ýòîì äëèíû
ñèìâîëîâ èç À îãðàíè÷åíû îäíèì áàéòîì. Ïîýòîìó ñîâðåìåííûé êîìïüþòåð òà-
êîå âû÷èñëåíèå-îïðåäåëåíèå t( )�0 âûïîëíèò çà äîëè ñåêóíäû, ïîñêîëüêó åãî
ñëîæíîñòü ðàâíà O n( )2 .  îòëè÷èå îò ýêñïîíåíöèàëüíîé çàâèñèìîñòè ïðè ðàíåå
èçâåñòíûõ ìåòîäàõ àðõèâàöèè, èñïîëüçóþùèõ ïîñèìâîëüíîå ãåíåðèðîâàíèå
òåêñòà ãåíåðàòîðîì Gp, êîòîðîå ïðåäóñìàòðèâàëî ïåðåáîð áîëüøîãî êîëè÷åñòâà
âàðèàíòîâ è çàâèñåëî îò ÷àñòîò ñèìâîëüíîãî è òàéìåðíîãî ãåíåðàòîðîâ, ðàññìîò-
ðåííûé çäåñü ìåòîä èìååò ïðèíöïèàëüíî ìåíüøóþ âðåìåííóþ îöåíêó. Íîâàÿ
îöåíêà ñëîæíîñòè ðàáîòû àëãîðèòìà ïðèíàäëåæèò êëàññó ñëîæíîñòè ìåòîäîâ
êëàññè÷åñêîãî ñèìâîëüíîãî êîäèðîâàíèÿ, íàïðèìåð ñ èñïîëüçîâàíèåì ìåòîäà
LamplZiv (îöåíêà åãî ñëîæíîñòè ðàâíàn nlog ) è âñïîìîãàòåëüíîãî ìåòîäà
Burrowse-Wheller transformation (ãäå èñïîëüçóþòñÿ öèêëè÷åñêèå ñäâèãè âñåõ ïîäñòðîê è
ïîäñëîâà, ïîëó÷åííûå â êîíöå ñòðîêè ïîñëå ñäâèãà), êîòîðûå èñïîëüçóþò àðõèâàòîð
RAR. Êàê èçâåñòíî, äëÿ òåêñòà ñ ðàâíîìåðíûì ðàñïðåäåëåíèåì âåðîÿòíîñòåé ñèìâîëîâ
(ïðåäïîëîæèì, ÷òî èõ 32, òîãäà H p pi
i
i( )� � �
�
��
1
32
2
1log 32 2 51
1
32
2
5�
�
� �
i
log ) íà îäèí
ñèìâîë òåêñòà íåîáõîäèìî, êàê ìèíèìóì, 5 áèò.
Ó÷èòûâàÿ âçàèìîçàâèñèìîñòü ñèìâîëîâ, ò.å. óñëîâíûå âåðîÿòíîñòè, à òàêæå
íåðàâíîìåðíîå ðàñïðåäåëåíèå âåðîÿòíîñòè ñèìâîëîâ, ïîëó÷àåì, ÷òî ýíòðîïèÿ
èñòî÷íèêà (íèæíèé ïðåäåë ñæàòèÿ) çíà÷èòåëüíî óìåíüøàåòñÿ (2 áèòà íà ñèìâîë
èç 32-áóêâåííîãî àëôàâèòà ïî èññëåäîâàíèÿì Øåííîíà).
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
Çàìåòèì, ÷òî åñëè ïðèìåíèòü ñíà÷àëà êëàññè÷åñêîå ñèìâîëüíîå êîäèðîâà-
íèå, à çàòåì òàéìåðíîå êîäèðîâàíèå, èìåþùåå ðàññòîÿíèå 3 áàéòà ìåæäó ìåòêà-
ìè, òî ïîëó÷èì ïîâòîðíîå ñæàòèå â 24 ðàçà. Äåéñòâèòåëüíî, ïîñêîëüêó â òðåõ
áàéòàõ ñîäåðæèòñÿ 24 áèòà, òî òåïåðü âìåñòî íèõ ñîõðàíÿåì âñåãî Q a( ) áèò íà
ìåòêó, ÷òî èìååò ìåíüøèé îáúåì [7].
Óòâåðæäåíèå 3. Åñëè ñîãëàñíî ëåêñèêîãðàôè÷åñêîìó óïîðÿäî÷åíèþ âûïîë-
íÿåòñÿ íåðàâåíñâî w w1 2
, òî Wh w Wh w( ) ( )1 2
è t w t w( ) ( )1 2
.
Äîêàçàòåëüñòâî. Óòâåðæäåíèå ñëåäóåò èç òîãî, ÷òî �
�i n m n mi i j j: , ,
j i
, ïîýòîìó Wh w Wh w( ) ( )1 2
. Ïîñêîëüêó ñèìâîëû ñ á�ëüøèì âåñîì ãåíåðèðó-
þòñÿ ïîñëå ñèìâîëîâ ñ ìåíüøèì âåñîì ñîãëàñíî ñòàòèñòè÷åñêîìó ïîðÿäêó ñèì-
âîëîâ, òî t w t w( ) ( )1 2
.
ÂÛ×ÈÑËÅÍÈÅ ÊÎÝÔÔÈÖÈÅÍÒÀ ÑÆÀÒÈß
Îïðåäåëåíèå 6. Äëèíà ïîòîêîâîãî êîäà íà âûõîäå Lout — ýòî ñóììà äëèí êî-
äîâ ñëîâ (èëè áëîêîâ ñëîâ) â íîâîì àëôàâèòå Y . Ñðåäíÿÿ äëèíà êîäà âû÷èñëÿ-
åòñÿ òàê: L l C w p wi
i
k
iout �
�
� ( ( )) ( )
1
, ãäå k — ÷èñëî áëîêîâ, íà êîòîðûå ðàçáèò
òåêñò; êàæäîìó èç íèõ ñîîòâåòñòâóåò ìåòêà — ñèìâîë èç Y .
Îïðåäåëåíèå 7. Äëèíà èñõîäíîãî ïîòîêîâîãî êîäà — ýòî ñóììà äëèí ñëîâ
L l win i
i
k
�
�
� ( )
1
, ñðåäíÿÿ äëèíà ñëîâà ñîñòàâëÿåò L l w p win i
i
k
i�
�
� ( ) ( )
1
, ãäå l wi( ) —
äëèíà ³-ãî áëîêà òåêñòà, p wi( ) — âåðîÿòíîñòü åãî ïîÿâëåíèÿ.
Ôîðìóëà êîýôôèöèåíòà ñæàòèÿ èìååò âèä
K
l C w p
l w p
k p
k m p m
i i
i
k
i i
i
k
i
i
� �
�
� �
��
�
�
�
( ( ))
( )
1
1
1
,
ïîñêîëüêó äëèíà ìåòêè ðàâíà 1 áàéòó (ïðè íàèëó÷øåì óïîðÿäî÷åíèè ñèìâî-
ëîâ). Áîëåå äåòàëüíî î äëèíå ìåòêè, ïðåäñòàâëåííîé â äðóãîé êîäèðîâêå, èç-
ëîæåíî â [1, 4, 7]. Îòñþäà ñëåäóåò, ÷òî êîýôôèöèåíò ñæàòèÿ ïðè òàêîì êîäå
îáðàòíî ïðîïîðöèîíàëåí äëèíå áëîêà wi , êîòîðûé îòîáðàæàåòñÿ â ñèìâîë èç
íîâîãî àëôàâèòà Y . Òàêèì îáðàçîì, ïðè m-ñäâèãå, ò.å. êîäèðîâàíèè áëîêàìè
äëèíîé m, êîýôôèöèåíò ñæàòèÿ ðàâåí
1
m
, à ýòî ìåíüøå, ÷åì ó àëãîðèòìà êî-
äèðîâàíèÿ LZW, èìåþùåãî K ìåæäó ãðàíèöàìè O
n
n
ln�
�
�
�
�
� è O( )1 , ãäå n — äëè-
íà òåêñòà, çíà÷èòåëüíî ïðåâûøàþùàÿ m — äëèíó áëîêà. Âåëè÷èíó m ìîæíî
óâåëè÷èòü äî n, ïîëó÷èâ K n n n�
1/ ln / . Çíà÷åíèå m çàâèñèò îò áûñòðîäåé-
ñòâèÿ òåêñòîâîãî ãåíåðàòîðà.
Òàêèì îáðàçîì, â íàñòîÿùåé ñòàòüå ïðåäëîæåí ìåòîä ïîñòðîåíèÿ ñòàòèñòè-
÷åñêè îðèåíòèðîâàííîãî òåêñòîâîãî ãåíåðàòîðà, áûñòðîäåéñòâèå êîòîðîãî âûøå,
÷òî ïîçâîëÿåò óìåíüøèòü K. Äëÿ äîñòèæåíèÿ ìàêñèìàëüíîãî óìåíüøåíèÿ îáúåìà
âñåãî òåêñòà ïîñëå åãî ñæàòèÿ ìîæíî èñïîëüçîâàòü òîëüêî îäíó ìåòêó, îáúåì êî-
òîðîé ïðåäñòàâëåí ñåðèåé íóëåé, åùå îäíèì áèòîì èëè ìåòêîé â äðóãîé êîäè-
ðîâêå â êîíöå ñåðèè ñèìâîëîâ, èìåþùåé íóæíóþ äëèíó, è ñîîòâåòñâóþùåé âå-
ëè÷èíå t( )�0 . Ñåðèþ íóëåé s ìîæíî óñëîâíî ðàçáèòü íà áëîêè b òàê, ÷òîáû âåëè-
÷èíà length( )b áûëà îäíîãî ïîðÿäêà ñ ýòîé ñåðèåé, è ñîõðàíèòü èõ êîëè÷åñòâî è
äëèíó òàêèõ áëîêîâ. Ïðè ýòîì ñóùåñòâóåò îñòàòîê îò äåëåíèÿ s íà length( )b . Äëè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 159
íó áëîêà length( )b öåëåñîîáðàçíî âûáðàòü, ðàâíóþ ÷èñëó 2 â íåêîòîðîé ñòåïåíè.
Åñëè ó ïîëüçîâàòåëÿ, êîòîðûé áóäåò îñóùåñòâëÿòü ðàçàðõèâèðîâàíèå, åñòü ñòàòèñòè-
åñêèé ïîðÿäîê ñèìâîëîâ äëÿ äàííîãî òèïà òåêñòîâ, òî îáúåì àðõèâèðîâàííîé èí-
ôîðìàöèè áóäåò ðàâåí îáúåìó çàïèñè îäíîé ìåòêè. Ïðè ýòîì âðåìÿ ðàçâîðà÷èâàíèÿ
òåêñòà íåçíà÷èòåëüíî ïðåâûøàåò âðåìÿ ðàçâîðà÷èâàíèÿ òåêñòà ïðè ìíîæåñòâåííîé ñèñ-
òåìå ìåòîê, íî åãî ìîæíî óìåíüøèòü íàðàùèâàíèåì ÷àñòîòû òàéìåðíîãî ñ÷åò÷èêà.
Îñíîâíîé ðåçóëüòàò ïðè èñïîëüçîâàíèè ïðåäëîæåííîãî ìåòîäà ñîñòîèò
â òîì, ÷òî âðåìÿ ñæàòèÿ òåêñòà íå çàâèñèò îò ÷àñòîò ñèìâîëüíîãî ãåíåðàòîðà è òàé-
ìåðíîãî ñ÷åò÷èêà è íå îïðåäåëÿåòñÿ â ïðîöåññå ñòàòèñòè÷åñêè-îðèåíòèðîâàíîãî
ïåðåáîðà èëè ïðîñòîãî ïåðåáîðà. Îíî âû÷èñëÿåòñÿ êàê ñóììà ñòåïåííîãî ðÿäà
ñ âåñîâûìè êîýôôèöèåíòàìè ñîîòâåòñòâóþùåãî ñèìâîëüíîãî óïîðÿäî÷åíèÿ � è
îáëàäàåò ëèøü êâàäðàòè÷íîé çàâèñèìîñòüþ ñëîæíîñòè îò äëèíû òåêñòà n,
à èìåííî 3 2 1( | | ) ([ / ] )length A n n� � , ÷òî â îòëè÷èå îò ýêñïîíåíöèàëüíîé çàâèñè-
ìîñòè ïðè ìåòîäå ñòàòèñòè÷åñêîãî ïåðåáîðà ÿâëÿåòñÿ ïðèíöèïèàëüíûì óìåíü-
øåíèåì ñëîæíîñòè ïðîöåññà àðõèâèðîâàíèÿ. Íà ïðàêòèêå äëÿ ñîâðåìåííîãî êîì-
ïüþòåðà ñ ðåñóðñàìè íîóòáóêà óäàëîñü ïðîãðàììíî ðåàëèçîâàòü òàéìåðíûå ñ÷åò-
÷èêè ñ ÷àñòîòîé, ïðèáëèçèòåëüíî ðàâíîé ïîëîâèíå òàêòîâîé ÷àñòîòû ïðîöåññîðà.
Ýòîò ñêîðîñòíîé ìåòîä ìîæíî óñïåøíî ïðèìåíÿòü äëÿ ñæàòèÿ SMS ñîîáùåíèé.
Ïðè ýòîì íåò íåîáõîäèìîñòè âñòðàèâàòü òàéìåðíûé ñ÷åò÷èê â ìîáèëüíûé òåëå-
ôîí, ïîñêîëüêó ìîæíî âîñïîëüçîâàòüñÿ ñèñòåìîé ñïóòíèêîâîé ñâÿçè JPRS äëÿ
ñîåäèíåíèÿ ñ ýòàëîííûìè àòîìíûìè ÷àñàìè è ñèíõðîíèçàòîðîì, êîòîðûé ìîæíî
ðåàëèçîâàòü íà áàçå òåëåôîííîé ñòàíöèè. À ïîñêîëüêó àòîìíûå ÷àñû îáëàäàþò
áîëüøåé âåëè÷èíîé äèñêðåòèçàöèè âðåìåíè, ÷åì òàéìåðíûé ñ÷åò÷èê, êîòîðûé
ìîæíî ðåàëèçîâàòü íà áàçå íîóòáóêà, òî ìîæíî èñïîëüçîâàòü ãåíåðàòîð òåêñòîâ ñ
áîëüøåé ÷àñòîòîé, ÷òî òàêæå óâåëè÷èâàåò ñêîðîñòü ðàáîòû.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Á à ð ä à ÷ å í ê î Â . Ô . , Ä æ ó í è í Å . Í . Àíàëèç õàðàêòåðèñòèê òàéìåðíûõ ìàñêðàòîðîâ
èíôîðìàöèè // Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. — 1994. — ¹ 3. — Ñ. 16–22.
2. Á à ð ä à ÷ å í ê î Â . Ô . , Ê è ø è í ñ ê è é Ñ . È . Ïîñòðîåíèå êîðïîðàòèâíîé ñèñòåìû ôîíäîâîé
áèðæè ñ èñïîëüçîâàíèåì òàéìåðíûõ òåõíîëîãèé îáðàáîòêè è çàùèòû èíôîðìàöèè // Òàì æå. — 2000.
— ¹ 5. — Ñ. 66–73.
3. Á à ð ä à ÷ å í ê î Â . Ô . , Ê î ë å ñ è ö ê è é Î . Ê . Àíàëèç ñîâðåìåííûõ ñðåäñòâ àóòåíòèôèêàöèè äëÿ
ñèñòåì çàùèòû èíôîðìàöèè // Òàì æå. — 2004. — ¹ 3. — Ñ. 81–92.
4. Î ñ à ä ÷ è é ª . Î . ϳäõ³ä äî ïîêðàùåííÿ òàéìåðíèõ ìåòîä³â çàõèñòó ³íôîðìàö³¿ // ³ñí. Òåðíîï.
àêàäå쳿 íàðîä. ãîñïîäàðñòâà. — 1999. — ¹ 1. — Ñ. 30–35.
5. Ï à ò . 2128878 Ðîññèéñêîé Ôåäåðàöèè, ÌÊÈ 6 Í 03 Ê 23/00. N-ðàçðÿäíûé ñ÷åò÷èê / Å.À. Îñàä÷èé,
À.Å. Îñàä÷èé, Îïóáë. 10.04.99; Áþë. ¹ 10. — 16 ñ.
6. À . ñ . 1 2 7 5 4 7 1 ÑÑÑÐ, ÌÊÈ G06F 15/38, 9/44. Óñòðîéñòâî äëÿ ïðåîáðàçîâàíèÿ êîäîâ ñ îäíîãî
ÿçûêà íà äðóãîé / Â.È. Êîðíåé÷óê, À.Ï. Ìàðêîâñêèé, Å.À. Îñàä÷èé, Â.Ñ. Áàáàê. — Îïóáë. 07.12.86,
Áþë. ¹ 45. — 8 ñ.
7. Î ñ à ä ÷ è é ª . Î . , Î ñ à ä ÷ è é Î . ª . , Ò ê à ÷ å í ê î Â . Â . , Ê ó ð ÷ å í ê î Â . Ä . Òàéìåðíå
êîäóâàííÿ â ïðîãðåñèâíèõ ³íôîðìàö³éíèõ òåõíîëîã³ÿõ // Òåç. äîïîâ. 12 ̳æíàð. êîíô. ç àâòîìà-
òèçàö³¿ êåðóâàííÿ «Àâòîìàòèêà 2005» ÍÒÓÓ «Êϲ». — 2005. — 3. — Ñ. 55–75.
8. K o b l i t z N . Algebraic aspects of cryptography / Algori thms and Computation in Mathematics. — Berlin:
Springer-Verlag, 2004. — 3. — 207 ð.
9. L i n d D . , M a r c u s B . An introduction to symbolic dynamics and coding. — Cambridge: Cambridge
University Press, 1995. — 490 p.
Ïîñòóïèëà 05.02.2012
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
|
| id | nasplib_isofts_kiev_ua-123456789-86174 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:43:29Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Скуратовский, Р.В. 2015-09-08T18:24:37Z 2015-09-08T18:24:37Z 2013 Метод быстрого таймерного кодирования текстов / Р.В. Скуратовский // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 154-160. — Бібліогр.: 9 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86174 521.1, 514.01 Розроблено статистично-орієнтований метод стискання даних з застосуванням нетрадиційного таймерного шифрування, а також необхідні оцінки складності. Метод може застосовуватись для стискання SMS повідомлень. Зроблено ймовірнісно-статистичний аналіз та отримано оцінки його ефективності. Розрахована швидкість архівування даних є найбільшою серед світових аналогів. Отримано часову складність О(n²) , за допомогою якої з урахуванням частоти генератора тексту легко отримати час архівування. A statistics-oriented data compression method based on unconventional timer encryption is developed. Necessary complexity estimates are made. The method can be used to compress sms messages. A probabilistic analysis is performed and its efficiency is evaluated. The theoretical data compression rate is the world’s highest. The time complexity O(n²) is determined, which can be used to find the archiving time taking into account the frequency of the text generator. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Метод быстрого таймерного кодирования текстов Метод швидкого таймерного кодування текстів Fast timer text coding method Article published earlier |
| spellingShingle | Метод быстрого таймерного кодирования текстов Скуратовский, Р.В. Программно-технические комплексы |
| title | Метод быстрого таймерного кодирования текстов |
| title_alt | Метод швидкого таймерного кодування текстів Fast timer text coding method |
| title_full | Метод быстрого таймерного кодирования текстов |
| title_fullStr | Метод быстрого таймерного кодирования текстов |
| title_full_unstemmed | Метод быстрого таймерного кодирования текстов |
| title_short | Метод быстрого таймерного кодирования текстов |
| title_sort | метод быстрого таймерного кодирования текстов |
| topic | Программно-технические комплексы |
| topic_facet | Программно-технические комплексы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86174 |
| work_keys_str_mv | AT skuratovskiirv metodbystrogotaimernogokodirovaniâtekstov AT skuratovskiirv metodšvidkogotaimernogokoduvannâtekstív AT skuratovskiirv fasttimertextcodingmethod |