2.13. Инъективное преобразование множества в элементы меньшего множества

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

Однако исследования в области языковых множеств показали, что относительные частоты появления различных букв в различных языках при не подчиняются равномерному закону распределения. Более того, частоты появления таких букв как «о» и «щ» существенно разнятся и составляют величины 0,09 и 0,003 соответственно (то есть в 30 раз). Данный факт указывает на возможность применения системы кодирования чисел, основывающейся на неравномерной длине кодов для символов, имеющих разную частоту появления.

Сущность неравномерного кодирования заключается в следующем. На первом этапе выбирается группа символов-разделителей букв, указывающих на начало каждой буквы. Например, пара цифр 01 может служить элементами разделения символов сообщения. На втором этапе формируются кодовые наборы различной длины, не содержащие кодов выбранных разделяющих пар. С этой целью удобно использовать счетчик Джексона, формирующий первую часть всех состояний схемы.

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

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

Пример. «Основа государства это самоорганизация и развитие» - текст, состоящий из 44 букв, который при кодировании байтами имеет длину 352 бита. Использование кодов из табл.2.8 неравномерной длины приводит к образованию последовательности, состоящей, с учетом разделителей, из 216 бит.

011 01110 0100 011 01000 0110 01000000 011 01110 0111111 011110 0110 (57)

01111 01110 01100 01000 0110 011000000 01100 011 01110 0110 011100 (56)

011 011 01111 01000000 0110 0100 0111 0111000 0110 011111100 0111 01 (57)

11110 0111 01111 0110 0111000 01000 0111 01100 0111 010 (46)

Это на 38,63% меньше, чем начально-исходный массив. В целом процесс кодирования на этом шаге может быть закончен. Однако, зная, что число букв русского языка составляет 32 символа, полученный текст может быть разбит на «пятерки» бит (см.табл.2.9) и алгоритм кодирования в соответствии с таблицей неравномерных кодов выполнен еще раз (неполная «пятерка» доопределяется нулевыми символами).

01101 11001 00011 01000 01100 10000 00011 01110 01111 11011 11001 10011

13 25 3 8 12 16 3 14 15 27 25 19

11011 10011 00010 00011 00110 00000 01100 01101 11001 10011 10001 10110

27 19 2 3 6 0 12 13 25 19 17 22

11110 10000 00011 00100 01110 11100 00110 01111 11000 11101 11110 01110

30 16 3 4 14 28 6 15 24 29 30 14

11110 11001 11000 01000 01110 11000 11101 0(0000)

30 25 24 8 14 24 29 0

Символ 00000 отождествляется, например как *, и перекодированию не подлежит.

Полученный шифротекст имеет вид и размер:

«нщвзмрвопьщу ьубве*мнщусц юрвгоъепшэюо ющшзошэ*» 44×5=220.

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

Аналитический подход к предложенному методу кодирования, а именно определение средней длины кода по формуле:

бита, (2.134)

где - частоты символов языка, - длины кодов из табл.2.8, указывает на среднестатистическую эффективность (53%) предложенного алгоритма.

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