Восстановление искаженных сжатых сообщений

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

1

http://naukovedenie.ru 86TVN114

УДК
004.627

Пронкин Алексей Александрович

ГКОУ ВПО «Академия Федеральной службы охраны Российской Федерации»

Россия, Орёл1

Адъюнкт

E-Mail: pron_rzhew@mail.ru

Восстановление искаженных сжатых сообщений

Аннотация: Проблема повышения достоверности приема информации на этапе 

декодирования кода источника является одной из наиболее важных в области проектирования 
телекоммуникационных систем. Однако в настоящее время указанная проблема не находит 
решений с требуемым качеством в силу ее сложности и многоаспектности. В статье 
рассматривается новый подход к проблеме декомпрессии поврежденных архивов. 
Использование предлагаемого подхода позволит определять местоположение искажений в 
коде источника. В статье выделены следующие этапы методики определения местоположения 
искажений в сжатых сообщениях: определение оптимального порядка и формирование 
контекстной модели формального языка (сообщения-эталона); формирование контекстной 
модели декодируемого сообщения; анализ совпадения контекстов модели декодируемого 
сообщения с контекстами модели сообщения-эталона. Вместе с тем рассмотрена структура 
наиболее распространенного на практике формата сжатия данных. Представлен алгоритм 
восстановления искаженных сжатых сообщений, который позволяет проводить декомпрессию 
сжатых цифровых потоков, сформированных согласно формату «Deflate», с коррекцией 
ошибок. Проведена проверка работоспособности предложенного алгоритма в ходе 
экспериментальной декомпрессии искаженных архивированных файлов.

Ключевые слова:
Kод источника;
местоположение искажения;
декодирование;

декомпрессор; сжатие; коррекция; избыточность.

Идентификационный номер статьи в журнале 86TVN114

1 302034, г. Орёл, ул. Приборостроительная, д. 35

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

2

http://naukovedenie.ru 86TVN114

Alexey Pronkin

The Academy of the Federal Guard Service of the Russian Federation

Russia, Orel

E-Mail: pron_rzhew@mail.ru

Restoration of distorted compressed messages

Abstract: The problem of information reception reliability increasing on the decoding of 

source code is one of the most important question in the field of telecommunication systems design. 
But this problem has not solved with requesting quality today due to its complexity and various 
aspects. The new approach to the problem of corrupted archives decompression is reviewed in this 
article. The proposed approach allows to determine the location of distortions in the source code. The 
article highlights the following steps of the method of distortions location determination in the 
compressed messages: definition of the optimal formation and forming of contextual model of 
formal language(template message); forming of contextual model of decoded message; analysis of 
comparison of decoded message model contexts and template message model contexts. At the same 
time the structure of the most widespread in practice data compression format is reviewed in this 
paper. An algorithm of the recovery of corrupted compressed message which allows to decompress 
with error correction the compressed digital flows generated according to the format «Deflate» is 
represented. Availability of the proposed algorithm is checking during the experimental 
decompression of distorted archived files.

Keywords: Source code;
distortion location;
decoding;
decompressor;
compression;

correction; redundancy.

Identification number of article 86TVN114

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

3

http://naukovedenie.ru 86TVN114

Введение

Характерной особенностью большинства типов данных является их избыточность. 

Степень избыточности данных зависит от типа данных. Например, для видеоданных степень 
избыточности в несколько раз больше чем для графических данных, а степень избыточности 
графических данных, в свою очередь, больше чем степень избыточности текстовых данных. 
Другим фактором, влияющим на степень избыточности, является используемая система 
кодирования. Примером систем кодирования могут быть обычные языки общения, которые 
являются ни чем другим, как системами кодирования понятий и идей для высказывания 
мыслей. Например, установлено, что кодирование текстовых данных с помощью средств 
русского языка характеризуется избыточностью в среднем на 20-25% большей, чем
кодирование аналогичных данных средствами английского языка. Следовательно, чтобы 
наиболее эффективно использовать ресурсы систем передачи данных, разрабатываются 
алгоритмы представления информации в «компактной» форме [1]. Вместе с тем, применение 
различных методов сокращения избыточности представления данных затрудняет процесс 
извлечения информации из архива из-за высокой чувствительности процесса декодирования 
кода источника к искажениям. При возникновении ошибок в коде источника прикладные 
программы не способны воспроизвести исходное сообщение без искажений, что приводит к 
частичной или полной потере информации.

1. Сжатие информации

В основе всех методов сжатия лежит простая идея: если представлять часто 

используемые элементы короткими кодами, а редко используемые − длинными, то для 
хранения блока данных требуется меньший объем памяти, чем при представлении всех 
элементов кодами одинаковой длины. Данный факт известен давно: например, в азбуке Морзе 
часто используемым символам поставлены в соответствие короткие последовательности 
точек и тире, а редко встречающимся – длинные [2].

Точная связь между вероятностями и кодами установлена в теореме Шеннона о 

кодировании источника, которая гласит, что элемент 
, вероятность появления которого 

равна 
, выгоднее всего представлять числом бит равным 
. Если при 

кодировании размер кодовых слов всегда в точности равен 
бит, то длина 

закодированной последовательности будет минимальной для всех возможных способов 
кодирования. Если распределение вероятностей 
неизменно, и элементы 

появляются независимо друг от друга, то можно найти среднюю длину кодов как среднее 
взвешенное:

.
(1.1)

Это значение также называется энтропией распределения вероятностей F или 

энтропией источника в заданный момент времени.

Обычно вероятность появления элемента является условной, т.е. зависит от какого-то 

события. В этом случае при кодировании очередного элемента 
распределение вероятностей 

F принимает одно из возможных значений Fk, то есть 
, и, соответственно, 
.

Можно сказать, что источник находится в состоянии k, которому соответствует набор 
вероятностей 
при генерации всех возможных элементов 
. Поэтому среднюю длину 

кодовых слов можно вычислить по формуле:

is

 
is
p
 


is
p
2
log


 


is
p
2
log


 


is
p
F 

 
 







i

i
i
s
p
s
p
H
2
log

is

k
F
F 
k
H
H 

 
i
k s
p
is

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

4

http://naukovedenie.ru 86TVN114

,
(1.2)

где 
− вероятность того, что F примет k-ое значение, или, иначе, вероятность 

нахождения источника в состоянии k. Итак, если известно распределение вероятностей 
элементов, генерируемых источником, то можно представить данные наиболее компактным 
образом, при этом средняя длина кодов может быть вычислена по формуле (1.2).

Но в большинстве случаев истинная структура источника не известна, поэтому 

необходимо строить модель источника, которая позволяет в каждой позиции входной 
последовательности оценить вероятность 
появления каждого элемента 
алфавита 

входной последовательности. В этом приходится оперировать оценкой 
вероятности 

появления элемента 
[3].

Методы сжатия могут использовать адаптивную модель источника, изменяющуюся по 

мере обработки потока данных, или фиксированную модель, созданную на основе априорных 
представлений о природе типовых данных, подвергающихся сжатию. Процесс моделирования 
может быть либо явным, либо скрытым, т.е. вероятности появления элементов могут 
использоваться в методе как явным, так и неявным образом, а сжатие всегда достигается за 
счет устранения статистической избыточности в представлении информации [4].

2. Контекстно-ограниченное моделирование источника информации

Наиболее изученным и распространенным типом моделей источника информации 

являются контекстные модели. В этих моделях оценка вероятности каждого символа 
сообщения осуществляется на основе контекста, в котором он появляется. Контекст − это 
последовательность символов сообщения, которая предшествует данному кодируемому 
символу. Количество символов в такой последовательности определяет порядок контекста и, 
соответственно, порядок модели. Если длина контекста равна m, то для алфавита источника 
объемом A возможно Am различных контекстов. Ясно, что вероятность появления отдельного 
символа сообщения зависит от вероятности появления соответствующего контекста. Таким 
образом, контекстное моделирование оценивает условную вероятность появления символов 
сообщения.

Один из естественных подходов к моделированию открытых текстов связан с учетом 

их частотных характеристик, приближения для которых можно вычислить с нужной 
точностью, исследуя тексты достаточной длины. Основанием для такого подхода является 
устойчивость частот m-грамм или целых словоформ реальных языков человеческого общения 
(то есть отдельных букв, слогов, слов и некоторых словосочетаний). Основанием для 
построения модели может служить также и теоретико-информационный подход, развитый в 
работах К. Шеннона [5].

Пусть задан некоторый конечный алфавит
, где ai – символ. Контекстом 

порядка m (или m-граммой) на алфавите A называют произвольную цепочку длиной m, 
например, последовательность из m букв русского языка одного слова, одной фразы, одного 
текста или, в более интересном случае, последовательность из грамматически допустимых 
описаний m подряд стоящих слов [6].

Для понимания естественного языка m-граммы стали применять сравнительно недавно.

В работе [7] предложена вероятностная модель речи на основе теории цепей Маркова, 
различающая разных авторов и даже фольклор. Значение m-грамм исчерпывается их 
прикладной направленностью: они являются эффективным инструментом решения важной 











k
k
i

i
k
i
k
k
k
k
s
p
s
p
P
H
P
H
))
(
(
log
)
(
2

kP

 
is
p
is

 
is
q

is

}
{ ia
A 

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

5

http://naukovedenie.ru 86TVN114

задачи – отбраковки вариантов, а их использование сводится к наложению допустимых mграмм на имеющиеся данные.

Пусть 
– число вхождений строки w в генеральную совокупность Ω 

текстов языка. Вероятность p(a) появления m-граммы w можно представить в виде:

.
(2.1)

Подобным образом определяют вероятность p(a) униграмм (контекстов первого 

порядка) как вырожденного случая m-граммы. Если вероятности появления символов в любой 
позиции цепочки независимы и одинаково распределены, то:

.
(2.2)

Таким образом, перестановки символов 
имеют одну и ту же вероятность. 

Например, в языке вероятность встретить выражения «красно-коричневый» та же, что и 
выражение
«к-рснкрчнваооиеый». Для разрешения указанного недоразумения вводят 

условные вероятности. Тогда вероятность очередного символа строки определяется в 
зависимости от предшествующих ему символов в виде:

.
(2.3)

Модель m-граммы описывается марковской цепью (m-1)-го порядка. Задача 

оценивания статистических параметров m-граммы решается с использованием теории 
марковских цепей, а оценкой вероятности m-граммы служит частота ее встречаемости:

.
(2.4)

Формула (2.4) для условных вероятностей триграмм (контекстов третьего порядка) 

использовалась в системе распознавания речи, разработанной фирмой IBM. [8].

C более общих позиций открытый текст может рассматриваться как реализация 

стационарного эргодического случайного процесса с дискретным временем и конечным 
числом состояний [5].

Контекстно-ограниченные модели данных можно использовать для определения 

местоположения искажения в сжатом сообщении и частичного восстановления информации 
из поврежденного архива.

3. Формат сжатия данных «Deflate»

В настоящее время в системах связи и в сети «Интернет» одним из наиболее 

распространенных на практике является формат сжатия данных «Deflate», который широко 
используется, например, в протоколе HTTP, форматах PNG, ZIP, GZIP и сервисах потоковой 
оптимизации данных в реальном масштабе времени, таких как «Slonax», «Globax», «Riverbed» 
и т.д. В формате «Deflate» используется алгоритм сжатия данных LZH, который является 
комбинацией метода словарного сжатия LZ77 и кодирования Хаффмана и обеспечивает 
хорошие результаты сжатия при относительно высокой скорости работы как при архивации, 
так и при декомпрессии.

)
,...,
,
|
(
2
1
n
a
a
a
a
a
C









x

x
C
a
C
a
p
)
(
)
(
)
(







n

i

ia
p
a
p

1

)
(
)
(

A
ai 

)
,...,
,
(
)
,...,
,
|
(
)
,...,
,
(
1
2
1
1
2
1
2
1

 

n
n
n
n
a
a
a
p
a
a
a
a
p
a
a
a
p

)
,...,
,
(

)
,...,
,
(
)
,...,
,
|
(
)
,...,
,
(ˆ

1
2
1

2
1

1
2
1
2
1







n

n

n
n
n
a
a
a
C

a
a
a
C
a
a
a
a
f
a
a
a
p

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

6

http://naukovedenie.ru 86TVN114

Формат «Deflate» состоит из заголовка и последовательности «контейнеров» со 

сжатыми данными (рис. 3.1). Каждый контейнер имеет свой внутренний заголовок, в котором 
содержится информация о типе кодирования Хаффмана (статический/динамический код) и 
информация для восстановления (т.е. построения) кодовых деревьев Хаффмана (для 
динамического кода). Размер контейнера зависит от типа кодируемой информации и для 
текстовых данных составляет примерно 30 Кбайт.

Рис. 3.1. Структурная схема формата «Deflate»

Сжатие, применяемое в формате «Deflate», можно условно разделить на две категории: 

по используемой стратегии и по методу кодирования информации (pис. 3.2). Стратегия 
сжатия задает кодеру LZ77 режим поиска совпадений текущего кодируемого фрагмента 
исходного сообщения с фрагментом данных в скользящем окне. На практике наиболее 
распространенная стратегия сжатия – «хорошее сжатие» (сжатие по умолчанию) и метод 
кодирования – алгоритм LZ77 и динамический код Хаффмана.

Рис. 3.2. Классификация процедур сжатия формата «Deflate»

Процедура декомпрессии цифрового потока в формате «Deflate» состоит в следующем. 

На вход декодера поступают сжатые данные в формате «Deflate», в заголовке которых 
содержится информация о параметрах декодера LZ77 и служебное поле для проверки 
корректности данного заголовка. Процесс декодирования начинается с обработки заголовка 
первого контейнера сжатых данных и построения кодовых таблиц Хаффмана (в случае 
динамического кодирования). После декодирования кода Хаффмана осуществляется 
процедура обратного преобразования в соответствии с алгоритмом LZ77 для фрагмента, 
представленного в виде множества элементов «символ, длина, смещение». Символ является 
элементом множества алфавита исходного (т.е. не сжатого) сообщения. Смещение указывает 
на позицию начала фрагмента данных относительно указателя текущего смещения размером, 
определяемым элементом «длина» в скользящем окне LZ77. Данные после процедуры 
декодирования кода LZ77, а также несжатые данные поступают на выход декодера [4].

Заголовок 
«Deflate»
Контейнер 1
Контейнер 2
Контейнер N
CRC32

2 байта
variable
4 байта

. . .

Тип 
блока

Режим 

кодирования

Данные для восстановления 
кодовых деревьев Хаффмана
Сжатая информация

1 бит
2 бита

variable
variable

variable
variable

Сжатие «Deflate»

По стратегии

Без сжатия

Быстрое 
сжатие
Хорошее 
сжатие

Наилучшее 

сжатие

По методу

LZ77 и код 
Хаффмана

Только код 
Хаффмана

Только 

RLE

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

7

http://naukovedenie.ru 86TVN114

4. Искажения в сообщениях, возникающие при наличии
ошибок в коде источника информации

При передаче сжатого сообщения по каналу связи зачастую возникают ошибки, 

которые не могут быть исправлены на канальном уровне и проявляются на уровне кода 
источника. В результате сообщение, декодированное из сжатого потока с ошибками, может 
значительно отличаться от сообщения, полученного при декодировании неискаженного 
сжатого потока (pис. 4.1) [9].

а)
б)

Рис. 4.1. Пример влияния одной битовой ошибки в сжатом сообщении

на результат декодирования

а) исходное сообщение; б) декодированное сообщение

Так как алгоритм сжатия «Deflate» – это комбинация двух алгоритмов сжатия данных, 

то целесообразно рассмотреть влияние искажений на информацию на каждом этапе процесса 
декодирования (pис. 4.2).

Рис. 4.2. Обобщенная классификация искажений, возникающих
в процессе декодирования сжатых данных формата «Deflate»

при воздействии ошибки на код источника

На этапе декодирования кода Хаффмана могут возникнуть символьные и трековые 

искажения. Символьные искажения приводят к искажению одного значения (либо символа, 
либо длины, либо смещения) множества элементов «символ, длина, смещение» кода LZ77 на 
этапе его декодирования. Трековые искажения приводят к групповому искажению сообщения, 
т.е. к искажению одного или нескольких элементов «символ, длина, смещение» кода LZ77. На 
представленном этапе преобразования символьные искажения приводят к изменению 
декодированного символа и, соответственно, фрагмента скользящего окна декодера LZ77. 
Влияние данного искажения на декодированное сообщение может быть как одиночным, так и 
периодическим в зависимости от периода обращения декодера LZ77 к текущему фрагменту 
данных в скользящем окне. Если период обращения меньше, либо равен периоду обновления 
скользящего окна, то искажение – одиночное, в противном случае – периодическое. 

Искажения

на уровне 

декодирования 
кода Хаффмана

на уровне 

декодирования 

кода LZ77

символьные

трековые

символьные

смещения 
фрагмента 
в словаре

длины 

фрагмента 
в словаре

групповые

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

8

http://naukovedenie.ru 86TVN114

Искажение значения длины или смещения текущего указателя в скользящем окне влечет за 
собой обращение декодера LZ77 к неверной области в скользящем окне, что приводит к 
искажению всей последовательности символов при декодировании (рис. 4.1). Искажения 
данного вида также могут быть как одиночными, так и периодическими.

5. Обнаружение местоположения ошибок в коде источника информации

Для 
обнаружения 
местоположения 
ошибок 
в 
коде 
источника 
предлагается 

использовать контекстное моделирование декодированных сообщений.

Пусть 
–
алфавит 
источника 
мощности 
, 

– исходное сообщение размером k, 
– символ сообщения S, 

причем, 
, 
, 
, 
, тогда контекстами порядка m для сообщения S

являются множества вида:

,
,
,
(5.1)

где 
, 
. Если 
, то 
, т.е. контекстами первого порядка 

являются символы алфавита сообщения. Если 
, то 
, где 
– пустое множество. 

Этот случай рассматривается как равновероятное распределение символов алфавита A в 
сообщении S. Например, для слова «декодер» контекстами второго порядка будут множества 
следующего вида:

,
,
, 
,
,
.

Если S – декодированное сообщение, то для его анализа необходима априорная 

информация о правилах формирования подобных сообщений, т.е. информация о разрешенных 
или запрещенных комбинациях.

При анализе сообщения S с множеством 
разрешенных комбинаций порядка m

необходимо использовать априорно известное сообщение-эталон (словарь)
с множеством 

разрешенных 
комбинаций, 
которое 
с 
определенной 
достоверностью 
описывает 

большинство сообщений подобных S:

, 
,
(5.2)

где 
,
, 
– мощность множества 
, 
– мощность 

множества 
.

Если множество 
и 
– мощность множества 
, то 

говорят, что сообщение S схоже с сообщением-эталоном 
со степенью схожести порядка m, 

количественной мерой которой является коэффициент совпадения контекстов 
сообщения 

S с контекстами сообщения-эталона 
:

.
(5.3)

Коэффициент 
– безразмерная величина, которая изменяется в пределах 
, 

причем, 
означает, что m-символьные элементы (фразы) сообщения S содержатся в 

}
,...,
,
{
1
0
n
a
a
a
A 
|
| A
n 

}
,...,
,
,
{
)1
(
2
1
0


k
j
j
j
j
a
a
a
a
S
ji
a

A
a ji 


j
i,
n
j 

0
k
i 

0

}
,...,
{
)
1
(
0
0


m
j
j

m
a
a
K
}
,...,
{
1
1
jm
j

m
a
a
K

}
,...,
{
)
1
(



m
z
j
jz

m
z
a
a
K

)
(
0
m
k
z



m
k 
1

m
}
{
1

jz
z
a
K 

0

m


0
z
K


}'
','
{'
2
0
å
ä
K

}'
','
{'
2
1
ê
å
K 
}'
','
{'
2
2
î
ê
K 
}'
','
{'
2
3
ä
î
K 
}'
','
{'
2
0

2
4
å
ä
K
K 
}'
','
{'
2
5
ð
å
K 

m
S
Q

O
S

m
SO
Q

}
,...,
,
{
)
1
(
)
1
(
)
0
(

m

N
S

m
S

m
S

m
S
S
K
K
K
Q


}
,...,
,
{
)
1
(
)
1
(
)
0
(

m

N
SO

m
SO

m
SO

m
SO
SO
K
K
K
Q





S
N
0

S
N
|
|
m
S
S
Q
N 
m
S
Q
|
|
m
SO
SÎ
Q
N


m
SO
Q





m
S

m
SO

m
Q
Q
P
|
|
m

P
P
N

m
P

O
S

m
μ

O
S

|
|

|
|
μ
m
S

m

S

P
m

Q
P

N
N



m
μ
1
μ
0


m

1
μ

m

Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

9

http://naukovedenie.ru 86TVN114

сообщении 
, а 
свидетельствует о том, что S и 
– два разных сообщения без 

взаимных корреляций их m-символьных элементов. Сообщение 
представляет собой 

определенного рода словарь, в котором содержатся отдельные фразы сообщения S. Например, 
значение коэффициента 
свидетельствует о том, что половина контекстов порядка 

сообщения S содержатся в сообщении 
, иными словами 50% двухсимвольных фраз

сообщения S содержится в сообщении
.

При формировании 
необходимо правильно выбрать порядок контекстов m. С одной 

стороны, чем выше m, тем более достоверно 
будет описывать S, так как минимальной 

единицей оценки сообщений 
и S являются m-символьные фразы. С другой стороны, при 

увеличении m коэффициент
уменьшается, если сообщение-эталон 
не содержит в себе 

сообщение S полностью. Например, если 
= «декодирование», а S = «кодер», то при 
, 

. Следовательно, можно сделать ложный вывод о том, что либо 
и S являются 

одинаковыми сообщениями, либо сообщение S содержится в 
. При 
, 
, 

следовательно, сообщение «декодирование» содержит в себе 33% информации о сообщении 
«кодер». При 
, 
, означает, что 
не содержит никакой информации о S. Такой 

результат анализа так же является не достоверным. На рис. 5.1 представлена зависимость 
коэффициентов совпадения контекстов 
от порядка контекстов для текстовых данных и 

случайного набора символов (декодированные текстовые данные при наличии ошибок в коде 
источника).

Рис. 5.1. Зависимость коэффициента совпадения контекстов 
от порядка контекстов для 

текстовых данных и случайного набора символов

Пусть 
и 
– коэффициенты совпадения контекстов для текстовых данных и 

случайного набора символов соответственно, и 
– показатель различия между 
и 

для контекстов порядка m, тогда:

.
(5.4)

O
S
0
μ

m

O
S

O
S

5,0
μ2 

2

m
O
S

O
S

O
S

O
S

O
S

m
μ
O
S

O
S
1

m

1
μ1 
O
S

O
S
3

m
33
,0
μ3 

5

m
0
μ5 
O
S

m
μ

m

m
μ

для текстов

для случайного набора символов

m
Dmax

m
μ

m
1
μ

m
2
μ

m
D

m
1
μ
m
2
μ

m
m
m
D
2
1
μ
μ 


Интернет-журнал «НАУКОВЕДЕНИЕ»
Выпуск 1, январь – февраль 2014
Опубликовать статью в журнале - http://publ.naukovedenie.ru

Институт Государственного управления, 

права и инновационных технологий (ИГУПИТ)
Связаться с редакцией: publishing@naukovedenie.ru

10

http://naukovedenie.ru 86TVN114

Величина 
показывает разницу между совпадением контекстов порядка m

текстовых данных и случайного набора символов с контекстами сообщения-эталона. 
Зависимость D(m) для текстовых данных и случайного набора символов представлена
на рис. 5.2.

Рис. 5.2. Зависимость показателя различия между коэффициентами совпадения контекстов 
для текстовых данных и случайного набора символов с контекстами сообщения-эталона от 

порядка контекстов

На основе анализа рис. 5.1 и 5.2 можно сделать вывод, что величина различия между 

коэффициентами совпадения контекстов для текстовых данных и случайного набора 
символов с контекстами сообщения-эталона принимает максимальное значение Dmax при m = 
mопт = 7 – 8. На практике для распознавания текстов используют контексты порядка m = 5 –
12, при которых различие между текстами и случайными данными более чем 40% (т.е. 
коэффициент совпадения контекстов для текстовых данных более чем в 1,5 раза больше 
коэффициента для случайных данных).

Экспериментальным путем установлено, что для определения местоположения 

искажения в декодируемом текстовом сообщении необходимо вычислять мгновенные 
значения коэффициента совпадения контекстов декодируемого сообщения S с контекстами 
сообщения-эталона 
для порядков контекстов m = 5 – 12 согласно формулам (5.5) и (5.6):

,
(5.5)

,
(5.6)

Уменьшение значений коэффициента совпадения контекстов 
свидетельствует о 

наличии искажения в декодируемом сообщении на текущей позиции i. Если, начиная с i-ой 
позиции, n значений величины 
меньше порогового значения, то можно сделать вывод, 

m
D

m

m
Dmax

m
D

O
S








12

5

)
(
8
1
)
(
μ

m

m
i
h
i








m
SO

m

i
S

m
SO

m

i
S

Q
K

Q
K
i
h

)
(

)
(

,0
,1
)
(

)
(
μ
i
m

)
(
μ
i
m