Коды, учитывающие частоту символов

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

Учет частоты символов позволяет строить “экономные” для техники коды постоянной длины. Например, условимся, что двоичная единица технически реализуется включенной лампочкой накаливания (как это и было в первых ламповых компьютерах), а двоичный ноль – выключенной лампочкой. Пусть также известны частоты букв русского алфавита, и в соответствии с этой частотой буквам назначены коды (мы умышленно задались неполным алфавитом русского языка), показанные в таблице.

               

Буква	Частота	Коды
о	0,090	0001
е	0,072	0010
а	0,062	0100
и	0,062	1000
я	0,018	0011
ы	0,016	0101

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

Очевидно, чем больше частота исходного символа, тем меньше в соответствующем коде единиц, т.е. тем меньше включенных лампочек применяется для представления символа в компьютере, а значит меньше тратится электроэнергии.

Код Штибица

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

Код Штибица (или код плюс-3) используется для кодирования десятичных чисел для простого перехода от двоичного значения числа к его дополнению.

Для построения кода Штибица используется понятие прямого целочисленного эквивалента двоичного кода – это десятичное число, соответствующее двоичному коду. Тогда код Штибица – это сдвинутый на 3 прямой код: чтобы получить представляемое данным двоичным кодом число, надо из прямого целочисленного эквивалента вычесть 3.

В таблице приведены значения кода Штибица для десятичных цифр (для сравнения также указан их прямой код).

Исходная цифра	Прямой код	Код Штибица
0	0000	0011
1	0001	0100
2	0010	0101
3	0011	0110
4	0100	0111
5	0101	1000
6	0110	1001
7	0111	1010
8	1000	1011
9	1001	1100

В этом коде используется понятие взаимно дополнительных пар чисел: это такие числа, при сложении двоичных значений которых получается двоичное число, состоящее только из единиц. Примером таких пар чисел могут служить 0 и 9, 1 и 8 и т.д.

Криптографические коды

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

В качестве символов кодирования могут использоваться как символы произвольного алфавита, так и двоичные коды.

Существуют различные методы, рассмотрим два из них: метод простой подстановки и метод Вижинера.

Метод простой подстановки

Простейшим случаем криптографического кодирования является простая подстановка: каждому исходному символу ставится в соответствие произвольный символ кодирования из какого-либо другого алфавита или из того же исходного – получается таблица соответствия. Тогда в кодируемом сообщении выполняется замена символов в соответствии с полученной таблицей.

Пример 1. Пусть исходным является русский алфавит. Составим таблицу соответствия, используя служебные символы, знаки препинания и знаки арифметических действий из таблицы ASCII- кодов в качестве кодового алфавита:

А  Б  В  Г  Д  Е  Ё  Ж  З  И  Й  К  Л  М  Н  О  П  Р С  Т  У Ф  Х  Ц  Ч  Ш  Щ  Э  Ю  Я  Ь  Ъ  Ы

!   № $  %  &  *  (    )   {   }   [   ]    -    |    =   ”   ’  ~   `   :   ;   _   <   >  ^   •    ↑  →  ↓  ←  ±  ?   ¤

Тогда сообщение ИНФОРМАТИКА будет закодировано как }=_”~|!:}]!        .

Данный метод кодирования является ненадежным, так как при достаточно большой выборке закодированных сообщений при известных частотах символов исходного алфавита можно с определенной долей погрешности выполнить декодирование. В самом деле, пусть есть представительная выборка закодированных русскоязычных сообщений, общее число букв в которых равно M, и известны частоты букв русского алфавита:

Буква	Частота	Буква	Частота	Буква	Частота
О	0,090	М	0,026	Й	0,010
Е(Ё)	0,072	Д	0,025	Х	0,009
А	0,062	П	0,023	Ж	0,007
И	0,062	У	0,021	Ю	0,006
Т	0,053	Я	0,018	Ш	0,006
Н	0,053	Ы	0,016	Ц	0,004
С	0,045	З	0,016	Щ	0,003
Р	0,040	Ъ,Ь	0,014	Э	0,003
В	0,038	Б	0,014	Ф	0,001
Л	0,035	Г	0,013	пробелы и знаки препинания	0,175
К	0,028	Ч	0,012

Можно рассчитать частоту каждого символа s – f_S :

f_{S =} m_S /M,

где m_S – количество символов S в сообщениях.

Тогда получив частоты и сопоставив их с приведенной таблицей, можно определить исходный текст.

Пример 2.  Пусть есть закодированное сообщение из примера 1: }=_”~|!:}]!. Известно, что до кодирования оно было составлено из букв русского алфавита. Требуется декодировать его, используя в качестве представительной выборки закодированных русскоязычных текстов настоящее учебное пособие, предварительно выполнив все замены русских букв символами из таблицы соответствия примера 1.

Воспользуемся встроенными средствами текстового процессора WINWORD для определения требуемых статистических данных. 

Так определим, что общее число символов М в учебном пособии на момент подготовки данного примера составляет 275979.

Определяем, сколько раз встречаются интересующие нас символы из закодированного сообщения - m_s:

символ s	}	=	_	"	~	|	!	:	]
ms	18716	14396	1436	22027	12058	8503	16835	13426	6592

Это позволяет рассчитать частоты символов f_s по приведенной выше формуле:

символ s	}	=	_	"	~	|	!	:	]
fs	0,068	0,052	0,005	0,078	0,044	0,031	0,061	0,049	0,024

Сопоставим полученные данные с приведенной выше таблицей частот символов. Наиболее близкие по значению символы для полученных частот показаны ниже:

символ s	}	=	_	"	~	|	!	:	]
подходящий символ	Е,А.И	Т,Н	Ю,Ш,Ц	Е,О	С,Р	Л,К	А,И	Т,Н,С	Д,П

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

Если построить все возможные сочетания символов из указанных множеств, там будет, в частности и сочетание вида И Н * О Р * А Т И * А, где знак * означает любой символ из соответствующего, определенного выше, множества исходных символов (в случае * декодирование, очевидно, выполнено неверно). Если предъявить полученную строку человеку или автомату, способному распознать русское слово, зашифрованное сообщение можно считать декодированным.

Очевидно, декодирование также возможно при известной таблице соответствия.