Методи таймерного шифрування
Разработаны статистически ориентированные методы сжатия данных с применением нетрадиционного таймерного шифрования, используемые для текстов определенной отрасли знаний совместно со скоростными таймерными счетчиками. The statistically oriented methods of a data compression using a non-traditional ti...
Gespeichert in:
| Veröffentlicht in: | Управляющие системы и машины |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/83090 |
| 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: | Методи таймерного шифрування / Р.В. Скуратовський, Є.О. Осадчий // Управляющие системы и машины. — 2012. — № 5. — С. 16-26. — Бібліогр.: 11 назв. — укр., рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860103097599131648 |
|---|---|
| author | Скуратовський, Р.В. Осадчий, Є.О. |
| author_facet | Скуратовський, Р.В. Осадчий, Є.О. |
| citation_txt | Методи таймерного шифрування / Р.В. Скуратовський, Є.О. Осадчий // Управляющие системы и машины. — 2012. — № 5. — С. 16-26. — Бібліогр.: 11 назв. — укр., рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Разработаны статистически ориентированные методы сжатия данных с применением нетрадиционного таймерного шифрования, используемые для текстов определенной отрасли знаний совместно со скоростными таймерными счетчиками.
The statistically oriented methods of a data compression using a non-traditional timer encryption are developed. The methods are used for the texts of a particular branch of knowledges with speed timer counters.
Розроблено статистично орієнтовані методи стиснення даних із застосуванням нетрадиційного таймерного шифрування, які використовуються для текстів визначеної галузі знань сумісно з швидкісними таймерними лічильниками.
|
| first_indexed | 2025-12-07T17:29:45Z |
| format | Article |
| fulltext |
16 УСиМ, 2012, № 5
Новые методы в информатике
УДК 512.64
Р.В. Скуратовський, Є.О. Осадчий
Методи таймерного шифрування
Разработаны статистически ориентированные методы сжатия данных с применением нетрадиционного таймерного шифрова-
ния, используемые для текстов определенной отрасли знаний совместно со скоростными таймерными счетчиками.
The statistically oriented methods of a data compression using a non-traditional timer encryption are developed. The methods are used
for the texts of a particular branch of knowledges with speed timer counters.
Розроблено статистично орієнтовані методи стиснення даних із застосуванням нетрадиційного таймерного шифрування, які
використовуються для текстів визначеної галузі знань сумісно з швидкісними таймерними лічильниками.
Вступ. При архівуванні даних очікування ре-
зультату іноді затримується. Наприклад, якщо
обсяг даних перевищує 1 Гб, то методи стиснен-
ня, що застосовуються в програмі RAR, будуть
працювати на доступному персональному ком-
п'ютері не менш, ніж одну годину. Важливою
характеристикою архівування вважається обсяг
стислої інформації. Тому цільовою функцією
може бути F = k1x + k2y min, де Y – час, X –
обсяг (адитивна форма) X Q1, Y t1.
Маємо лінійне зростання обсягу виділеної
пам'яті в залежності від кількості таймерних
(часових) міток x, оскільки кожній мітці відпо-
відає 8 біт пам'яті, а y = t() є системою міток
даного тексту.
Об'єднання текстів, які відповідають розко-
дованим міткам, ідентичним всьому тексту, дає
швидкість розархівування міток більше, ніж s0.
Для порівняння меж стиснення нагадаємо, що
при символьному кодуванні з однозначним де-
кодуванням, тобто в префіксному кодуванні, іс-
нує код з найменшою довжиною коду символу
,L c : , 1H L c H , де – H –
це ентропія джерела, тобто його нижня межа
стиснення. 2
1
1log
n
i
i i
H p p
, або середньо
очікувана кількість інформації, яку несе один
символ. Зрозуміло, що зі зростанням довжини
тексту Т довжина коду, наприклад арифметич-
ного, буде лінійно зростати. Метод, що пропо-
нується (у разі використання однієї мітки) ви-
користовує для неї 8 біт і пам'ять для зберіган-
ня алфавітного впорядкування символів відкри-
того тексту. При цьому довжина коду не росте
зі збільшенням довжини тексту, а коли вико-
ристовується система міток з періодом 3 Б, то
навіть після досягнення нижньої межі для сим-
вольного кодування стиснення за Шеноном,
можна досягти стиснення в 24 рази.
Саме тому в даній статті вперше запропоно-
вано нові методи таймерного кодування, дове-
дено їх ефективність, розроблено відповідне
математичне забезпечення для оптимізації.
Основи таймерного шифрування
Символи тексту є відносні частоти fi, за яки-
ми вони впорядковуються за спаданням часто-
ти, чим забезпечують лінійний порядок. Нага-
даємо, що генератор генерує символи в зада-
ному порядку послідовно за розрядами. Час і
результат його роботи однозначно визначають-
ся таймерною міткою.
Визначення. Номером символу при задано-
му впорядкуванні є його порядковий номер
ni в цьому впорядкуванні, здійснюваному для
статистичного генератора Gs згідно з ймовір-
ностями, характерними для символів виділено-
го тексту. Зауважимо, що вагою символу буде
саме його номер в частотному впорядкуванні,
такому, що коли, f i > f j, то ну n i < n j. Позначи-
мо символом А множисимволів с.
Визначення. Вагою слова W або тексту Т =
= а1, а2, а3, ..., аn назвемо величину
1
n
n i
i
i
Wh T n A
, (1)
УСиМ, 2012, № 5 17
де ni – номер символу, що знаходиться на i-му
місці тексту в заданому для генератора впоря-
дкуванні, N – довжина тексту.
Поставивши помилково першу літеру, гене-
ратор змушений ставити на всіх позиціях після
нього всі букви з А – множини символів, поки не
дійде до величини часу, більшої, ніж таймерна
мітка для Т. Наприклад, якщо мітка для числа
Т = 1567 і генератор поставив перший символ
2 (що відповідає впорядкуванню 2, 3, 4, 5, 6, 7,
8, 9, 0, 1), то він перебиратиме всі цифри, спо-
чатку послідовно збільшуючи символ у друго-
му розряді, потім всі комбінації в наступних
розрядах – так до набору a1 an anan, поки не
повернеться до першої позиції, де далі поста-
вить наступну за порядком цифру три (яка теж
помилкова) і знову почне послідовний перебір
в молодших розрядах. Так буде, поки він не
дійде в першому розряді до одиниці. Отже, в
кожному розряді від другого до четвертого
було використано від дев'яти до десяти цифр, а
в першому розряді – всі 10 цифр. Тому верхня
межа перебраних комбінацій при неправильно
вибраному а1 буде n1 103 для Т. Якщо непра-
вильно вибрано а2 n2 102, то це n2 102 комбі-
націй і т.д. В результаті, вага дорівнює
4
4
1
1 2 3 4
1567 ,
10, 4, 5, 6.
i
i
i
Wh n A
n n n n
Оцінна величина перебору в разі неправи-
льно поставленого а1 становить
1
1
N
n A
. При
цьому величина
1N
A
є вагою або розрядністю
позиції і-го символу. Взагалі величина
N i
A
дорівнює розрядності і-го символу. Відповідно
Wh T є комбінаторна складність гіперслова по
. Вона відповідає потужності множини гі-
перслів, що генеруються при обраному впоря-
дкуванні символів, після якої слідує шукане T.
А ймовірність виникнення слова Т – це куму-
лятивна ймовірність
1 2... nP T p p p , (2)
де pi – ймовірність появи i-го символу в дано-
му тексті з даної предметної галузі знань (ПГ).
Множинна система міток
Зрозуміло, що перші символи мають більшу
вагу. Саме тому доцільно сформувати окрему
мітку (мітки) для початку тексту, але якщо мі-
тки будуть розподілені нерівномірно, залишок
тексту буде довгим і його перші символи (пре-
фікс) матимуть ваги з високими ступенями. Са-
ме тому природною є гіпотеза про рівномірний
розподіл міток. Але спочатку доведемо ефектив-
ність використання множинної системи міток
за певних обмежень на їх кількість. Кожна міт-
ка займає 1 Б, а сукупна їх кількість може бути
обмежена потребами користувача. Підрахуємо
виграш в числі операцій від застосування двох
міток, відповідних префіксній множині з двох
гіперслів. Окремі мітки розділяють текст рівно-
мірно порівну. Нехай W= N. Якщо спочатку
знаходимо префікс Pr (W) = W1, де W1 – поча-
ток гіперслова W, довжини 1 2
NL w , від-
повідної таймерній мітці 0. Але якщо наступ-
на частина слова, що генерується, не збігається
з W, продовжимо генерувати її з L + 1-го місця
до кінця слова. Відповідно, наступну частину
W2 шукатимемо окремо, зафіксувавши вже знай-
дений префікс Pr (W) = w1. Для них частотні ваги
будуть наступні: Wh(w1) =
1
,
N L
n i
i
i
n A
-
-
=
å а для дру-
гої частини тексту Wh(w2) =
1
.
N L
N i
i
i L
n A
-
-
= +
å Тоді час-
тотна вага всього слова при використанні пе-
реборного генератора буде Wh(w) =
1
,
N
n i
i
i
n A
-
=
å
де w = Pr(w) w2. Це скоротить перебір як мі-
німум в
22
n
A
раз, оскільки ступінь знаменни-
ка менша в два рази
( )
( ) ( )
N n i
i
i
N
Nn i n i
i i
i Ni
n AWh W
k
Wh W Wh W
n A n A
1
21 2
1
2
-
=
- -
= =
= =
+
+
å
å å
.
Лінгвістична аналітика
Якщо для даної ПГ знань ввести статистику
не тільки частот символів, а ще й імовірностей
18 УСиМ, 2012, № 5
появи символу в слові, після того як визначено
вже I символів в цьому слові, будемо мати умов-
ні ймовірності. Саме ці ймовірності дозволять
зменшити перебір. Наприклад, є кілька прик-
метників з однаковими закінченнями: статис-
тичний, середньозважений, кореляційний, ма-
тематичний, інтегральний. Тому при l > 5, при
виникненні поєднання букв ні, логічно почати
підбір наступного символу з букви й, не врахо-
вуючи, що його частота порівняно мала. Також
при 3l доцільно враховувати можливість по-
яви не існуючих комбінацій символів у мові
даної галузі знань. Наприклад, не можуть з'яв-
лятися три голосних символи поспіль і інші по-
єднання. Це все формалізується за умовних імо-
вірнісних переходів до наступного символу.
Префіксно-таймерне кодування. Методи-
ка обчислення ймовірностей
Розглянемо ймовірності і швидкості поро-
дження текстів статистично налаштованим ге-
нератором. Нехай Gs – статистично навчений
генератор. Слід знайти ймовірність генеруван-
ня слова. Якщо aaa – потрібне слово раніше,
ніж abab – довільне слово. Розглянемо поміче-
ний граф виду, такого як на рис. 1 і 2 та відпо-
відні ймовірності переходів.
( ) ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
a aa aa
ab aba
aba aa abab abab
aa aaa ab aaa
x p a x a p b x
x p a x p a x
x p a x p b x
x p a x p b x x
x p a x p b x x
, 0
, 1
Æ Æ
Æ
ìï = +ïïïï = +ïïï = +íïïï = ⋅ + =ïïï = ⋅ + =ïïî
,
де xaa – ймовірність прийти з одного стану aa
шуканого слова aaa раніше, ніж до стану сло-
ва abab.
Визначення. Префікс-функцією по S від
рядка L назвемо найдовший префікс з Pr(S),
яким закінчується рядок L, L W. Позначимо
цю функцію як PrfS (L).
Якщо є заборонені слова (що не є початком
жодного з шуканих слів), то їх префікси дода-
ють у множину Pr(S). Потрапляння під заборо-
нене слово приводить до вершини . Наприк-
лад, в цьому ж наборі {ааа, abab} не має зу-
стрічатися bbb, оскільки воно не є початком
слів набору.
Якщо прийняти, що abab – текст з даної га-
лузі знань і має мітки в створеній префіксній
множині М, то є дійсним паралельне розархіву-
вання двох текстів. При цьому упорядкування
здійснюється за середньостатистичними дани-
ми для множини текстів з даної ПГ.
Метод обчислення ймовірності
Імовірність переходу до шуканого слова при
генеруванні дорівнює сумі добутків ймовірно-
стей шляхів, за якими можна прийти в стан
aaa з початкового стану Æ .
( )
1
,...,
k
aaa i
i
P p aaa
=
= Æå , де ( ),...,
i
p aaaÆ –
ймовірність переходу і-м шляхом з Æ вaaa .
Якщо abab – тестове середньостатистичне
слово, для якого немає спеціальних міток під-
слів, то статистичний порядок букв виконуєть-
ся не для шуканого гіперслова, а для ааа. За-
уважимо, що перехід з дописуванням букви a
відбувається частіше, оскільки він є більш прі-
оритетним, тому ймовірність отримання сло-
ва ааа раніше abab буде більше половини,
що доводить ефективність статистично зорі-
єнтованого генератора. Середній очікуваний
час M (t (aaa) ) < < M (t (abab) ).
За великої довжини тексту в такий спосіб
обчислювати ймовірність переходу нераціона-
льно. Але з системи (1), що відповідає марків-
ским ланцюгам, можна відносно легко обчис-
лити ліву частину передостаннього рівняння,
тобто xaba , оскільки в його правій частині xabab=
= 0 і xaa = p(a). Далі, підставляючи знайдене
xaba в інші рівняння, можна легко знайти ймо-
вірності у всіх станах.
Твердження. Нехай порядок символів зафі-
ксовано, тоді ймовірність генерації методом
спільного генерування одного з слів більше, ніж
методом роздільного генерування.
Це так тому, що кожне з w0, w1 має свою си-
стему міток дільників слова і в процесі генера-
ції більшого слова w0 виникатимуть підслова,
відповідні міткам для 1w і навпаки. Тому не-
доцільно генерувати окремо слова w1, оскільки
їх побудова відбуватиметься одночасно. При
цьому порядок букв для w0, w1 однаковий.
УСиМ, 2012, № 5 19
Архівування за множиною префіксів
Визначення. Дільником слова називається
підслово u : w p u r= ⋅ ⋅ , де ,p r - підслово
слова.
Таймерний лічильник запускається на поча-
тку генерації, але його значення, отримані в
процесі генерації фіксуються в ОЗУ після ко-
жної генерованої текстової одиниці дискрети-
зації, яка може бути словом або реченням. Це
необхідно для зіставлення з елементами мно-
жини Pr(S). Вони є не ті й не інші, а відпові-
дають префіксам і є дільниками тексту Т.
У даному дослідженні з метою архівування
методом таймерного кодування введемо спеці-
ально позначену таймерними мітками множи-
ну префіксів S, відповідну підсловам тексту W.
Серед цих міток обов'язково є повна мітка, від-
повідна всьому тексту.
Цілком природно, що закінчення гіперслова
(узагальнений суфікс) або довільний дільник цьо-
го гіперслова може збігатися з підсловом шука-
ного гіперслова W, а перевірити це можна порів-
нянням міток цих підтекстів. Тому, маючи мітки
певного набору дільників гіперслова W, можна
за їх появи в процесі статистично зорієнтованого
перебору істотно скоротити час роботи (кіль-
кість перебраних текстів до отримання закодо-
ваного тексту). Крім того, цілком природно для
архівування брати кілька текстів з родинних ПГ.
Доведемо, що їх спільне розархівування є
більш швидким. Нехай дано множину міток ар-
хівованого набору рядків S. Розглянемо мно-
жину можливих префіксів Pr(S) – множини по-
чатків деяких підрядків (виділені префікси) для
всіх рядків з S, включаючи власне рядки, а та-
кож префікс нульової довжини. Нехай кожному
префіксу відповідає деяка вершина кореневого
орієнтованого дерева, причому від вершини A
йде стрілка в вершину B, тоді і тільки тоді, коли
префікс, відповідний B, можна отримати з пре-
фікса, відповідного A, шляхом приписування
до нього одного символу. Наприклад, для слів
abb і abab можна взяти Pr(S) = {a, abb, abab}
(рис. 1). На дереві квадратами позначено пре-
фікси – члени Pr(S). Біля стрілок вказано сим-
воли, які потрібно додати, щоб перейти до за-
значеного префіксу. Тепер, якщо задано деяку
мітку, відповідну загальній частині двох архі-
вованих текстів, то слід окремо генерувати від-
повідне цій мітці гіперслово для обох текстів,
що пришвидшує спільне розархівування.
Рис. 1. Дерево пошуку префіксів
Якщо згенеровано гіперслово, то, щоб пере-
вірити його наявність в S, потрібно, починаю-
чи з мітки порожнього префікса, «пройти» по
дереву пошуку (це траєкторія паралельного ге-
нерування з таймерним пошуком), кожного ра-
зу рухаючись по ребру, позначеному символами
заданого набору S. Задане гіперслово буде час-
тиною S тоді і тільки тоді, коли знаходиться від-
повідне ребро. В результаті опинимося на пре-
фіксі, позначеному квадратиком. За наявності
набору S замість одного тексту, що генеруєть-
ся, можливих переходів по ребрам з тієї ж ве-
ршини (за умови, що ці переходи ведуть до од-
ного з елементів з Pr(S)), зрозуміло, буде не мен-
ше, тому швидкість спільного розархівування
буде більшою. Введемо наступну функцію.
Визначення. Префікс-функцією по S від ря-
дка L назвемо довгий префікс з Pr(S), яким за-
кінчується рядок L, L W. Позначимо цю функ-
цію як PrfS(L). Оскільки порожній префікс на-
лежить Pr(S), то для довільного рядка він буде
«кандидатом» на роль значення префікс-функції.
Тому для довільного рядка PrfS(L) визначена.
У загальному випадку міткам відповідають
довільні, заздалегідь обрані подільники гіпер-
слова W. Вони утворюють множину S. Тому в
процесі генерації, як тільки виникатиме підсло-
во, відповідне елементу з множини S, воно пе-
ретворюватиметься в двійковий запис підсло-
ва. Після цього здійснюватиметься пошук про-
довжень отриманого підслова шляхом такої ж
генерації символів і символів з урахуванням
20 УСиМ, 2012, № 5
ймовірності їх появи. Ці ймовірності врахова-
но при визначенні порядку генерації. За пода-
льшого дописування символів в PrfS(p) мож-
лива поява наступного префікса з S. Для цього
слід вирахувати PrfS(PС), який формально
буде суфіксом нового підслова pc. Максимум
PrfS(PС) = рс. Опишемо цей процес шляхом
побудови спеціального графа переходів по
префіксах p. У цьому графі стани – це множи-
на виявлених дільників гіперслова W і почат-
ковий стан Ø.
Граф переходів за префіксами. Дерево по-
шуку підслів можна розвинути в нову структу-
ру даних – граф переходів за префіксами з W,
що дозволяє швидко відповісти на питання: які
гіперслова з S входять в генерований G, на яких
місцях і скільки разів? Ця структура також са-
моконсолідована. Її перебудова відбувається
приблизно так, як і для дерева пошуку, та є
більш довготривалою. Щоб краще уявити собі
роботу з графом переходів за префіксами, нага-
даємо визначення. Будуємо граф всіх перехо-
дів між префіксами, тобто для кожного префі-
кса зазначаємо, яким він буде, коли до нього
приписати взятий символ. Під символом розу-
мітимемо дільник гіперслова, відповідний оди-
ниці дискретизації таймерного лічильника. Граф
будується так, щоб для довільного рядка L ви-
конувалося наступне: якщо починати маршрут
за графом від порожнього префікса і на кож-
ному кроці слідувати за стрілкою з черговим
символом з L, то в кінці маршруту отримаємо
префікс, рівний PrfS(L). Існування такого гра-
фа можливе, оскільки для довільних рядків x і
y виконується
Prfs(x) = Prs(y) Prfs(xc) = Prs(yc) (6)
для довільного символу c (або частини тексту,
відповідної одиниці дискретизації даного текс-
ту таймерним лічильником). Розглянутий сим-
вол приписано до рядків x і y. Для нашого на-
бору S зобразимо граф переходів за префікса-
ми (рис. 2).
Приймемо речення за одиницю дискретиза-
ції. На початку кожного з них запускається тай-
мерний лічильник, а в кінці – зчитуються зна-
чення часу і порівнюються зі значеннями міток
з Pr(S). У разі знаходження відповідної мітки
відшукується речення з тексту і запам'ятову-
ється адреса знайденої мітки в ОЗУ. Опишемо
процес побудови такого графа.
Рис. 2. Граф переходів за префіксами
Спочатку зафіксуємо на етапі, коли знайде-
но мітку для тексту довжиною n, дерево пере-
ходів або ж відзначимо його ребра як основні.
Далі в дереві переходів, що відповідає форму-
ванню тексту, з кожної знайденої вершини про-
довжимо визначати переходи по всіх можли-
вих символах, а не виконувати побудову цього
графа заново, як це було б у разі генератора з
однією міткою. При такому генеруванні пер-
шим буде виконуватися перехід, відповідний
більш пріоритетному символу.
Для довільного символу с і для довільного
префікса p з Pr(S) алгоритм шукає PrfS(pc) і з
префікса p направляє стрілку з символом c в пре-
фікс PrfS(pc). Напрямок стрілок визначається ди-
намічно, тобто з результатів для менших префік-
сів слідують результати для більших префіксів.
Індукція за довжиною префікса. Для поро-
жнього префікса переходи обчислюються на ос-
нові дерева пошуку. У разі успіху відповіддю
буде односимвольний префікс c, а в разі неус-
піху – порожній префікс.
Припустимо, що для префіксів, довжиною,
меншою, ніж визначена, всі переходи генеру-
ються і підраховуються. На цьому етапі можна
застосувати розпаралелювання після знаходжен-
ня префікса ( )p Pr S . Підрахуємо переходи
для всіх префіксів даної довжини. Перевіримо
присутність pc в Pr(S) за допомогою дерева
пошуку у тексті G. Для цього генератор допи-
сує символи c до наявного префіксу. Це можна
УСиМ, 2012, № 5 21
виконати за один крок, коли зберігається місце
знаходження таймерної мітки, що встановлю-
ється таймерним лічильником, який працює па-
ралельно початку префікса p в тексті. При па-
ралельній роботі кількох генераторів зберігає-
мо місце знаходження таймерних міток всіх
префіксів в дереві породжених послідовностей.
У разі успіху направляємо стрілку в pc. У разі
неуспіху, в силу (1) буде виконано Prfs(pc) =
= Prfs(pc), де p виходить з p відкиданням пер-
шого символу (далі використовується це позна-
чення і для інших рядків). Prfs(pc) може бути
отримано на основі вже частково побудовано-
го графа переходів. Якщо зберегти всі адреси
префіксів Prfs(pc) (їх число лінійно залежить від
обсягу S), то наступний Prfs(pc) можна отри-
мати за один крок, починаючи з Prfs(pc). Текст,
відповідний мітці Prfs(p′), буде збережений, ос-
кільки p' = q's, де q – префікс, попередній p в де-
реві пошуку, а s – останній символ префікса p.
І нарешті, щоб не пропустити жодного слова,
для кожного префікса p з Pr(S), необхідно вка-
зати LwS(p) – найбільш довге слово з S, яке не
збігається з p в разі його наявності. Це теж мож-
на зробити динамічно. Для порожнього префік-
са LwS – відсутня. Оскільки LwS(p) – кандидат
на роль PrfS(p'), то LwS(p) служить закінченням
останнього. Тому потрібно перевірити належ-
ність PrfS(p') множині S. Це виконується в один
крок, оскільки на попередньому етапі збере-
жено значення Prfs(p′). Якщо Prfs(p′) – в S, то
Lws(p) = Prfs(p′). В іншому випадку (див. рис. 2) –
перехід за стрілкою а з аba, тобто нове вкла-
дення префікса в отримане слово без допису-
вання нового символу Lws(p) = Lws(Prfs(p′)).
Останній вираз вже збережено, оскільки
Prfs(p′) коротший, ніж p. Алгоритм завершено.
Він виконується за кількість кроків, лінійно
залежних від обсягу S.
На рис. 3 в дужках для приставок вказані їх
значення Lws. Насправді, потрібно зберігати по-
силання на них в графі, оскільки за цими поси-
ланнями будуть здійснюватися переходи. Руха-
ючись графом, відзначаємо всі префікси, по-
значені квадратиками. При попаданні на пре-
фікси, які мають Lws, робимо перехід за поси-
ланнями на Lws, поки це можливо, кожного
разу відзначаючи нове входження деякого сло-
ва з S. Після переходу по таких посиланнях
повернемося до того префіксу, на який потра-
пили останнім переходом за символом, а не за
посиланнями LwS.
Побудова дерева
пошуку
Побудова
переходів за
символами
Знаходження
Lws(p)
Рис. 3. План побудови графа переходів за префіксами
Проілюструємо дію алгоритму на прикладі.
Нехай вводиться рядок ababb. Для неї черго-
вість операцій алгоритму буде наступна:
0. Знаходимося на порожньому префіксі.
1. Перехід по 'a' на "a"; фіксація входження
"a" з кінцем в п. 1.
2. Перехід по 'b' на "ab".
3. Перехід по 'a' на "aba". Для цього здійс-
нюється:
– перехід по Lws на "a", фіксація входження
"a" з кінцем в п. 3;
– повернення на "aba".
4. Перехід по 'a' на "abab", фіксація вхо-
дження "abab" з кінцем в п. 4.
5. Перехід по 'b' на "abb", фіксація вхо-
дження "abb" з кінцем в п. 5.
За великої кількості варіантів символів мо-
жна виконати перехід по меншій одиниці дис-
кретизації. Це дає зменшення необхідної пам'я-
ті і числа кроків приблизно в m/(2log2m) раз, де
m – кількість різних можливих підтекстів, які
мають таку ж довжину, що і одиниця дискре-
тизації d. Якщо взяти одиницю дискретизації
d = 3 Б, то навіть після застосування методів
символьного кодування отримаємо стиснення в
8*3 – 1 = 23 рази. Це так тому, що один біт, йде
власне на мітку. Але при цьому зі збільшенням
величини d зростає час роботи. Алгоритм, який
використовує граф переходів за префіксами,
виконує кількість кроків, лінійно пропорційниу
сумі розмірів введеного тексту. При цьому дося-
гається теоретично передбачена максимальна
ефективність таймерного кодування.
1. Осадчий Є., Осадчий О. Проблеми створення, інте-
грації і використання науково-технічної інформації
на сучасному етапі // Тез. доп. VІ міжнар. наук.-
практ. конф. – Київ, 16–17 груд. 1999. – С. 354–355.
22 УСиМ, 2012, № 5
2. Осадчий Є.О. Підхід до покращення таймерних
методів захисту інформації // Вісн. ТАНГ, Еконо-
міко-математичне моделювання. – 1999. – № 1. –
С. 30–35.
3. Осадчий Є., Осадчий О. Таймерні методи та засоби
захисту інформації // Тез. доп. Міжнар. наук.-практ.
конф. «Проблеми впровадження інформаційних тех-
нологій в економіці та бізнесі», Ірпінь, 2000. –
С. 354–355.
4. Методи та засоби захисту інформації в часі / Є. Осад-
чий, В. Курченко, Д. Гриценко та ін. // Правове, нор-
мативне та метрологічне забезпечення системи за-
хисту інформації в Україні: Зб. пр. – НТУУ «КПІ»,
2000. – С. 73–76.
5. Осадчий Є.О. Трансформерні технології побудови
машин та механізмів. – К.: Наук. світ, 2004. – 167 с.
6. Таймерне кодування в прогресивних інформаційних
технологіях / Є.О. Осадчий, О.Є. Осадчий, В.В. Тка-
ченко та ін. // Тез. доп. 12 міжнар. конф. з автома-
тизації керування «Автоматика 2005» – К.: НТУ
«КПІ», 2005. – Т. 3. – С. 55.
7. Патент Российской Федерации № 2128878, МКИ
6 Н 03 К 23/00. N-разрядный счетчик / Е.А. Осад-
чий, А.Е. Осадчий, (Украина), Опубл. 10.04.99;
Бюл. № 10. – 16 с.
8. Авт. свид. СССР № 1275471, НКИ G 06 F 15/38,
9/44. Устройство для преобразования кодов с одного
языка на другой / В.И. Корнейчук, А.П. Марковский,
Е.А. Осадчий, В.С. Бабак (СССР); НИИПиП (СССР). –
№ 3926126/24–24; Заяв. 05.07.85; Опубл. 07.12.86,
Бюл. № 45. – 8 с.
9. Осадчий Е.А. Об одном подходе к определению эф-
фективности методов формального сжатия инфор-
мации их информационной совместимости // УСиМ. –
1996. – № 5. – С. 43–56.
10. Осадчий Є.О., Осадчий В.Є. Трансформерна техно-
логія як приклад високої технології, що здатна
продукувати конкурентоздатну продукцію // Рынок
технологий, проблемы и пути решения: Тез. докл.
междунар. науч.-практ. конф. – К.: УкрИНТИ. –
2002. – С. 204–209.
11. Рішення про видачу патенту України на винахід по
заявці № 99095303 від 27.09.99, МКИ 6 Н 03 К
23/00. Асоціативний інерційний лічильник / Осад-
чий О.Є., Осадчий В.Є. – 14 с.
Поступила 07.02.2011
(после доработки 27.07.2012)
Тел. для справок: +380 63 203-1025, +380 99 327-0661,
+380 67 501-7213 (Киев)
E-mail: skeleton@unicyb.kiev.ua
© Р.В. Скуратовский, Е.А. Осадчий, 2012
Р.В. Скуратовский, Е.А. Осадчий
Методы таймерного шифрования
Введение. При архивировании данных ожидание резуль-
тата иногда затягивается. Например, если объем данных
превышает 1 Гб, то методы сжатия, применяемые в про-
грамме RAR, будут работать на доступном персональ-
ном компьютере не менее одного часа. Важной характе-
ристикой архивирования считается объем сжатой ин-
формации. Поэтому целевой функцией может быть
F = k1x + k2y min, где Y – время, X – объем (адди-
тивная форма) при X Q1, Y t1.
Имеем линейный рост объема выделенной памяти в
зависимости от количества таймерных (временных) ме-
ток x, так как каждой метке соответствует 8 бит памяти,
а y = t () – система меток данного текста. Объединение
текстов, соответствующее раскодированным меткам,
идентичным всему тексту, дает скорость разархивиро-
вания меток более чем s0. Для сравнения пределов сжа-
тия напомним, что при символьном кодировании с од-
нозначным декодированием, т.е. в префиксной кодиров-
ке, существует код с наименьшей длиной кода символа
L(c, ): H() L(c, ) H() + 1, где H() – энтропия ис-
точника, т.е. его нижняя граница сжатия.
2
1
1log
n
i
i i
H p p
, или среднее ожидаемое коли-
чество информации, которую несет один символ. По-
нятно, что с ростом длины текста Т длина кода, напри-
мер арифметического, будет линейно возрастать. Пред-
ложенный метод (в случае использования одной метки)
использует для нее 8 бит и память для хранения алфа-
витного упорядочивания символов открытого текста. При
этом длина кода не возрастает с увеличением длины текс-
та, а когда используется система меток с периодом 3 Б,
то даже после достижения нижней границы для сим-
вольного кодирования сжатия по Шеннону, можно дос-
тичь сжатия в 24 раза.
Именно поэтому в данной статье впервые предложе-
ны новые методы таймерного кодирования, доказана их
эффективность, разработано соответствующее матема-
тическое обеспечение для оптимизации.
Основы таймерного шифрования
Символы текста имеют относительные частоты fi, по
которым они упорядочиваются по убыванию частоты,
чем обеспечивают линейный порядок. Напомним, что
генератор генерирует символы в заданном порядке по-
следовательно по разрядам. Время и результат его рабо-
ты однозначно определяются таймерной меткой.
Определение. Номером символа при заданном упо-
рядочении есть его порядковый номер ni в этом упо-
рядочении, осуществляемом для статистического гене-
УСиМ, 2012, № 5 23
ратора Gs согласно вероятностям, характерным для сим-
волов выделенного текста. Заметим, что весом символа
будет именно его номер в частотном упорядочении, та-
ком, что если f i > f j, то n i > n j. Обозначим символом А
множество символов с T.
Определение. Весом слова W или текста Т = а1, а2,
а3, ..., аn назовем величину
1
n
n i
i
i
Wh T n A
, (1)
где ni – номер символа, который находится на i-м месте
текста и в заданном для генератора упорядочении, N –
длина текста.
Поставив ошибочно первую букву, генератор вынуж-
ден ставить на всех позициях после него все буквы с А –
множества символов, пока не дойдет до величины вре-
мени, большей, чем таймерная метка для Т. Например,
если метка для числа Т = 1567 и генератор поставил
первый символ 2 (что соответствует упорядочению 2, 3,
4, 5, 6, 7, 8, 9, 0, 1), то он будет перебирать все цифры,
сначала последовательно увеличивая символ во втором
разряде, потом все комбинации в следующих разрядах –
так до набора a1 an anan, пока не вернется к первой по-
зиции, где далее поставит следующую по порядку циф-
ру три (которая тоже ошибочна) и снова начнет после-
довательный перебор в младших разрядах. Так будет, пока
он не дойдет в первом разряде до единицы. Таким обра-
зом, в каждом разряде от второго до четвертого было
использовано от девяти до десяти цифр, а в первом раз-
ряде – все 10 цифр. Поэтому верхняя граница перебран-
ных комбинаций при неправильно выбранном a1 будет
n1 103 для Т. Если неправильно выбрано а2, n2 102, то
это n2 102 комбинаций и т.д. В итоге, вес равен
4
4
1 2 3 4
1
1567 , 10, 4, 5, 6.
i
i
i
Wh n A n n n n
Оценочная величина перебора в случае неправильно
поставленного a1 составляет n1 AN–1. При этом вели-
чина AN–1 будет весом или разрядностью позиции і-го
символа. Вообще, величина AN–i равна разрядности і-го
символа. Соответственно Wh(T) – комбинаторная слож-
ность гиперслова по . Она соответствует мощности мно-
жества генерируемых гиперслов при выбранном упоря-
дочении символов, после которой следует искомое T. А
вероятность возникновения слова Т есть кумулятивной
вероятностью
1 2 ... nP T p p p , (2)
где pi – вероятность появления i-го символа в данном
тексте по данной предметной области (ПО) знаний.
Множественная система меток
Понятно, что первые символы имеют больший вес,
именно поэтому целесообразно сформировать отдель-
ную метку (метки) для начала текста, но если метки бу-
дут распределены неравномерно, то остаток текста бу-
дет длинным и его первые символы (префикс) будут
иметь веса с высокими степенями. Именно поэтому ес-
тественна гипотеза о равномерном распределении ме-
ток. Но сначала докажем эффективность использования
множественной системы меток при определенных огра-
ничениях на их количество. Каждая метка занимает 1 Б, а
совокупное их количество может быть ограничено по-
требностями пользователя.
Подсчитаем выигрыш в числе операций от примене-
ния двух меток, соответствующих префиксному множе-
ству из двух гиперслов. Отдельные метки разделяют
текст равномерно и на равные части. Пусть W = N. Ес-
ли сначала находим префикс Pr(w) = w1, где w1 – начало
гиперслова w длины 1 2
N
L w
, соответствующей
таймерной метке 0. Но если следующая часть генери-
руемого слова не совпадает с W, продолжаем генериро-
вать ее с L + 1-го места до конца слова. Соответственно
следующую часть w2 ищем отдельно, зафиксировав уже
найденный префикс Pr(w) = w1. Для них частотные веса
будут следующие:
1
1
,
N L
n i
i
i
Wh w n A
а для второй части текста
Wh(w2)
1
N L
N i
i
i L
n A
. Тогда частотный вес всего слова
при использовании переборного генератора Wh w
1
,
N
n i
i
i
n A
где 2w Pr w w . Это сократит перебор
как минимум в
22
n
A
раз, поскольку степени знамена-
теля меньше в два раза
1
21 2
1
2
.
N
n i
i
i
N
N
n i n i
i i
Ni i
n A
Wh W
k
Wh W Wh W
n A n A
Лингвистическая аналитика
Если для данной ПО знаний ввести статистику не
только частот символов, а еще и вероятностей появления
символа в слове, после того как определены уже I сим-
волов в этом слове, то будем иметь условные вероятно-
сти. Именно эти вероятности позволят уменьшить пере-
бор. Например, есть ряд прилагательных с одинаковыми
окончаниями: статистический, средневзвешенный, корре-
ляционный, математический, интегральный.
Поэтому при I > 5, при возникновении сочетания букв
ни, логично начать подбор следующего символа с буквы
й, не учитывая, что его частота сравнительно мала. Так-
же при I > 3 целесообразно учитывать возможность по-
явления не существующих комбинаций символов в язы-
ке данной области знаний. Например, не могут появ-
ляться три гласных символа подряд и другие сочетания.
Это все формализуется в условных вероятностных пере-
ходов к следующему символу.
24 УСиМ, 2012, № 5
Префиксно-таймерное кодирование. Методика вы-
числения вероятностей
Рассмотрим вероятности и скорости порождения
текстов статистически настроенным генератором. Пусть
Gs – статистически обученный генератор. Следует най-
ти вероятность генерирования слова. Если aaa – нужное
слово раньше, чем abab – произвольное слово. Рассмот-
рим помеченный граф вида такого, как на рис. 1 и 2, и
соответствующие вероятности переходов.
, 0
, 1
a aa aa
ab aba
aba aa abab abab
aa aaa ab aaa
x p a x a p b x
x p a x p a x
x p a x p b x
x p a x p b x x
x p a x p b x x
,
где xaa – вероятность прийти из одного состояния aa
искомого слова aaa раньше, чем к состоянию слова abab.
Определение. Префикс-функцией по S от строки L
назовем самый длинный префикс с Pr(S), которым за-
канчивается строка L, L W . Обозначим эту функцию
как PrfS(L).
Если есть запрещенные слова (что не есть началом
ни одного из искомых слов), то их префиксы добавля-
ются в множество Pr(S). Попадание в запрещенное сло-
во приводит в вершину . Например, в этом же наборе
{ааа, abab} не должно встречаться bbb, так как оно не
есть началом слов набора.
Если положить, что abab – текст из данной области
знаний и имеет метки в созданном префиксном множе-
стве М, то будем иметь параллельное разархивирование
двух текстов. При этом упорядочение осуществляется
по среднестатистическим данным для множества тек-
стов из данной ПО.
Метод вычисления вероятности
Вероятность перехода к искомому слову при генери-
ровании равна сумме произведений вероятностей путей,
по которым можно прийти в состояние ааа из начально-
го состояния .
1
,...,
k
aaa i
i
P p aaa
,
где ,...,ip aaa – вероятность перехода по і-му пути
из Æ в ааа.
Если abab – тестовое среднестатистическое слово,
для которого нет специальных меток подслов, то стати-
стический порядок букв выполняется не для искомого
гиперслова, а для ааа. Заметим, что переход с дописыва-
нием буквы a происходит чаще, так как он более приори-
тетен, поэтому вероятность получения слова ааа раньше,
чем abab, будет больше половины, что доказывает эф-
фективность статистически ориентированного генератора.
Среднее ожидаемое время M (t (aaa) ) < M (t (abab) ).
При большой длине текста так вычислять вероят-
ность перехода нерационально. Но из системы (1), соот-
ветствующей марковским цепям, можно относительно
легко вычислить левую часть предпоследнего уравнения,
т.е. xaba, так как в его правой части xabab = 0 и xaa = p(a).
Далее, подставляя найденное xaba в другие уравнения,
можно легко найти вероятности во всех состояниях.
Утверждение. Пусть порядок символов зафиксиро-
ван, t(0) > t(1), тогда вероятность генерации методом
совместного генерирования одного из слов w0, w1 боль-
ше, чем методом раздельного генерирования.
Это так потому, что каждое из w0, w1 имеет свою
систему меток делителей слова, и в процессе генерации
большего слова w0 будут возникать подслова, соответ-
ствующие меткам для w1 и наоборот. Поэтому нецеле-
сообразно генерировать отдельно слова w1, так как по-
строение этих слов будет происходить одновременно.
При этом порядок букв для w0, w1 одинаков.
Архивирование по множеству префиксов
Определение. Делителем слова w называется под-
слово u: w p u r , где ,p r подслово слова.
Таймерный счетчик запускается в начале генерации,
но его значения, полученные в процессе генерации, фик-
сируются в ОЗУ после каждой сгенерированной тексто-
вой единицы дискретизации, которая может быть сло-
вом или предложением. Это необходимо для сопостав-
ления с элементами множества Pr(S). Они – не те и не
другие, а соответствуют префиксам и служат делителя-
ми текста Т.
В данном исследовании с целью архивирования ме-
тодом таймерного кодирования введем специально по-
меченное таймерными метками множество префиксов
S, соответствующее подсловам текста W. Среди этих
меток обязательно есть полная метка, соответствующая
всему тексту.
Вполне естественно, что окончание гиперслова
(обобщенный суффикс) или произвольный делитель этого
гиперслова может совпадать с подсловом искомого ги-
перслова W, а проверить это можно путем сравнения
меток этих подтекстов. Поэтому, имея метки некоторого
набора делителей гиперслова W, можно при их появле-
нии в процессе статистически ориентированного пере-
бора существенно сократить время работы (количество
перебранных текстов до получения закодированного
текста). Кроме того, вполне естественно для архивиро-
вания брать несколько текстов из родственных ПО.
Рис. 1. Дерево поиска префиксов
УСиМ, 2012, № 5 25
Докажем, что их совместное разархивирование будет
более быстрым. Пусть дано множество меток архивиро-
ванного набора строк S. Рассмотрим множество возмож-
ных префиксов Pr(S) – множества начал некоторых под-
строк (выделенные префиксы) для всех строк из S, вклю-
чая собственно строки, а также префикс нулевой длины.
Пусть каждому префиксу соответствует некоторая вер-
шина корневого ориентированного дерева, причем от вер-
шины A ведет стрелка в вершину B тогда и только тогда,
когда префикс, соответствующий B, можно получить из
префикса, соответствующего A, путем приписывания к
нему одного символа. Например, для слов abb и abab
можно взять Pr(S) = {a, abb, abab}. Дерево поиска для
них представлено на рис. 1. На дереве квадратами обо-
значены префиксы – члены Pr(S). Возле стрелок указа-
ны символы, которые нужно добавить, чтобы перейти к
указанному префиксу. Теперь, если задана некоторая
метка, соответствующая общей части двух архивиро-
ванных текстов, то следует отдельно генерировать соот-
ветствующее этой метке гиперслово для обоих текстов,
что повышает скорость совместного разархивирования.
Если сгенерировано гиперслово, то, чтобы проверить
его наличие в S, нужно, начиная с метки пустого пре-
фикса, «пройти» по дереву поиска (это траектория па-
раллельного генерирования с таймерным поиском), ка-
ждый раз двигаясь по ребру, помеченному символами
заданного набора S. Заданное гиперслово будет частью S
тогда и только тогда, когда находится соответствующее
ребро. В итоге, окажемся на префиксе, помеченном
квадратиком. При наличии набора S вместо одного ге-
нерируемого текста, возможных переходов по ребрам из
той же вершины (при условии, что эти переходы ведут к
одному из элементов с Pr(S)) понятно будет не меньше,
поэтому скорость совместного разархивирования боль-
ше. Введем следующую функцию.
Определение. Префикс-функцией по S от строки L
назовем длинный префикс с Pr(S), которым заканчивается
строка L, L W . Обозначим эту функцию как Prfs(L).
Так как пустой префикс принадлежит Pr(S), то для про-
извольной строки он будет «кандидатом» на роль значе-
ния префикс-функции. Поэтому для произвольной стро-
ки Prfs(L) определена.
В общем случае меткам соответствуют произвольные,
заранее выбранные делители гиперслова W. Они образу-
ют множество S. Поэтому в процессе генерации, как толь-
ко будет возникать подслово, соответствующее элемен-
ту из множества S, оно будет превращаться в двоичную
запись подслова. После этого будет осуществляться по-
иск продолжений полученного подслова путем такой же
генерации символов и символов с учетом вероятности их
появления. Эти вероятности учтены при определении
порядка генерации. При дальнейшем дописывания сим-
волов в Prfs(p) возможно появление следующего префикса
с S. Для этого следует вычислить Prfs(pс), который фор-
мально будет суффиксом нового подслова pc. Максимум
Prfs(pс) = рс.
Опишем этот процесс путем построения специально-
го графа переходов по префиксам p. В этом графе со-
стояния – множество выявленных делителей гиперслова
W и исходное состояние Ø.
Граф переходов по префиксам. Дерево поиска под-
слов можно развить в новую структуру данных – граф
переходов по префиксам с W, что позволяет быстро от-
ветить на вопрос: какие гиперслова с S входят в генери-
руемый G, на каких местах и сколько раз? Эта структу-
ра также самоконсолидируема. Ее перестройка происхо-
дит примерно так же, как для дерева поиска, но более
длительна. Чтобы лучше представить себе работу с гра-
фом переходов по префиксам, напомним определения.
Строим граф всех переходов между префиксами, т.е.
для каждого префикса указываем, каким он будет, если к
нему приписать взятый символ. Под символом будем по-
нимать делитель гиперслова, соответствующий единице
дискретизации таймерного счетчика. Граф строится так,
чтобы для произвольной строки L выполнялось следую-
щее. Если начинать маршрут по графу от пустого префик-
са и на каждом шаге следовать по стрелке с очередным
символом из L, то в конце маршрута получим префикс,
равный PrfS(L). Существование такого графа возможно,
так как для произвольных строк x и y выполняется
Prfs(x) = Prfs(y) Prfs(xc) = Prfs(yc) (6)
для произвольного символа c (или части текста, соот-
ветствующей единице дискретизации данного текста
таймерным счетчиком). Рассматриваемый символ при-
писан к строкам x и y. Для нашего набора S изобразим
граф переходов по префиксам (рис. 2).
Рис. 2. Граф переходов по префиксам
Примем предложение за единицу дискретизации. В
начале каждого из них запускается таймерный счетчик,
а в конце – считываются значения времени и сравнива-
ются со значениями меток с Pr(S). В случае нахождения
соответствующей метки отыскивается продолжение из
текста и запоминается адрес найденной метки в ОЗУ.
Опишем процесс построения такого графа.
Сначала зафиксируем на этапе, когда найдена метка
для текста длиной n, дерево переходов или же отметим
его ребра как основные. Далее в дереве переходов, что
соответствует формированию текста, с каждой найден-
ной вершины продолжим определять переходы по всем
возможным символам, а не выполнять построение этого
26 УСиМ, 2012, № 5
графа заново, как это было бы в случае генератора с од-
ной меткой. При таком генерировании, первым будет
выполняться переход, соответствующий более приори-
тетному символу.
Для произвольного символа с и для произвольного
префикса p с Pr(S) алгоритм ищет Prfs(pc) и с префикса
p направляет стрелку с символом c в префикс Prfs(pc).
Направление стрелок определяется динамически, т.е. из
результатов для меньших префиксов следуют результа-
ты для больших префиксов.
Индукция по длине префикса. Для пустого префикса
переходы вычисляются на основе дерева поиска. В слу-
чае успеха ответом будет односимвольный префикс c, а
в случае неуспеха – пустой префикс.
Предположим, что для префиксов длиной, меньшей,
чем данная, все переходы генерируются и подсчитыва-
ются. На этом этапе можно применить распараллелива-
ние после нахождения префикса p Pr(S). Подсчитаем
переходы для всех префиксов данной длины. Проверим
присутствие pc в Pr(S) с помощью дерева поиска по тек-
сту G. Для этого генератор дописывает символы c к
имеющемуся префиксу. Это можно выполнить за один
шаг, когда сохраняется место нахождения таймерной
метки, что устанавливается таймерным счетчиком, ра-
ботающим параллельно, начала префикса p в тексте.
При параллельной работе нескольких генераторов со-
храняем место нахождения таймерных меток всех пре-
фиксов в дереве порожденных последовательностей. В
случае успеха направляем стрелку в pc. В случае неус-
пеха, в силу (1) будет выполнено Prfs(pc) = Prfs(pc) где
p получается из p отбрасыванием первого символа
(дальше используется это обозначение и для других
строк). ( )sPrf p c может быть получено на основе уже
частично построенного графа переходов. Если сохра-
нить все адреса префиксов ( )sPrf p c (их число линейно
зависит от объема S), то следующий ( )sPrf p c можно
получить за один шаг, начиная с ( )sPrf p c . Текст, соот-
ветствующий метке Prfs(p′), будет сохранен, поскольку
p' = q's, где q – префикс, предыдущий p в дереве поиска,
а s – последний символ префикса p. И наконец, чтобы не
пропустить ни одного слова, для каждого префикса p из
Pr(S), необходимо указать LwS(p) – наиболее длинное
слово из S, не совпадающее с p в случае его наличия.
Это тоже можно выполнить динамически. Для пустого
префикса LwS отсутствует. Поскольку Lws(p) – кандидат
на роль Prfs(p′), то Lws(p) служит окончанием последне-
го. Поэтому нужно проверить принадлежность Prfs(p′)
множеству S. Это выполняется в один шаг, поскольку на
предварительном этапе сохранено значение Prfs(p′). Ес-
ли Prfs(p′) – в S, то Lws(p) = Prfs(p′). В противном случае
(см. рис. 2) – переход по стрелке а с аba, т.е. новое вло-
жение префикса в полученное слово без дописывания
нового символа: Lws(p) = Lws(Prfs(p′)).
Последнее выражение уже сохранено, так как PrfS(p′)
короче, чем p. Алгоритм завершен. Он выполняется за
количество шагов, линейно зависимых от объема S.
Рис. 3. План построения графа переходов по префиксам
На рис. 3 в скобках для приставок указаны их значе-
ния Lws. На самом деле, нужно хранить ссылки на них в
графе, так как по этим ссылкам будут осуществляться пе-
реходы. Двигаясь по графу, отмечаем все префиксы, обо-
значенные квадратиками. При попадании на префиксы,
имеющие Lws, переходим по ссылкам на Lws, пока это
возможно, каждый раз отмечая новое вхождение неко-
торого слова из S. После перехода по таким ссылкам
возвратимся к тому префиксу, на который попали по-
следним переходом по символу, а не по ссылкам Lws.
Проиллюстрируем действие алгоритма на примере.
Пусть вводится строка ababb. Для нее очередность опе-
раций алгоритма будет следующая:
0. Находимся на пустом префиксе.
1. Переход по 'a' на "a", фиксация вхождения "a" с
концом в п. 1.
2. Переход по 'b' на "ab".
3. Переход по 'a' на "aba", для чего осуществляется:
– переход по Lws на "a", фиксация вхождения "a" с
концом в п. 3;
– возвращение на "aba".
4. Переход по 'a' на "abab". Фиксация вхождения
"abab" с концом в п. 4.
5. Переход по 'b' на "abb". Фиксация вхождения
"abb" с концом в п. 5.
При большом количестве вариантов символов можно
выполнить переход по меньшей единице дискретизации.
Это дает уменьшение требуемой памяти и числа шагов
примерно в m/(2 2log m ) раз, где m – количество различ-
ных возможных подтекстов, имеющих такую же длину,
что и единица дискретизаций d. Если взять единицу
дискретизации d = 3 Б, то даже после применения ме-
тодов символьного кодирования получим сжатие в
8*3 – 1 = 23 раза. Это так потому, что один бит идет на
собственно метку. Но при этом с увеличением величины
d возрастает время работы. Алгоритм, использующий
граф переходов по префиксам, выполняет количество
шагов, линейно пропорциональное сумме размеров вве-
денного текста. При этом достигается теоретически пред-
сказанная максимальная эффективность таймерного ко-
дирования.
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-83090 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:29:45Z |
| publishDate | 2012 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Скуратовський, Р.В. Осадчий, Є.О. 2015-06-14T12:55:06Z 2015-06-14T12:55:06Z 2012 Методи таймерного шифрування / Р.В. Скуратовський, Є.О. Осадчий // Управляющие системы и машины. — 2012. — № 5. — С. 16-26. — Бібліогр.: 11 назв. — укр., рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/83090 512.64 Разработаны статистически ориентированные методы сжатия данных с применением нетрадиционного таймерного шифрования, используемые для текстов определенной отрасли знаний совместно со скоростными таймерными счетчиками. The statistically oriented methods of a data compression using a non-traditional timer encryption are developed. The methods are used for the texts of a particular branch of knowledges with speed timer counters. Розроблено статистично орієнтовані методи стиснення даних із застосуванням нетрадиційного таймерного шифрування, які використовуються для текстів визначеної галузі знань сумісно з швидкісними таймерними лічильниками. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Новые методы в информатике Методи таймерного шифрування Методы таймерного шифрования The methods of Timer Encryption Article published earlier |
| spellingShingle | Методи таймерного шифрування Скуратовський, Р.В. Осадчий, Є.О. Новые методы в информатике |
| title | Методи таймерного шифрування |
| title_alt | Методы таймерного шифрования The methods of Timer Encryption |
| title_full | Методи таймерного шифрування |
| title_fullStr | Методи таймерного шифрування |
| title_full_unstemmed | Методи таймерного шифрування |
| title_short | Методи таймерного шифрування |
| title_sort | методи таймерного шифрування |
| topic | Новые методы в информатике |
| topic_facet | Новые методы в информатике |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83090 |
| work_keys_str_mv | AT skuratovsʹkiirv metoditaimernogošifruvannâ AT osadčiiêo metoditaimernogošifruvannâ AT skuratovsʹkiirv metodytaimernogošifrovaniâ AT osadčiiêo metodytaimernogošifrovaniâ AT skuratovsʹkiirv themethodsoftimerencryption AT osadčiiêo themethodsoftimerencryption |