Операционные системы -вопросы теории

       

Русская азбука Морзе



Таблица 1.4. Русская азбука Морзе



Буква

Символы Морзе

Слово

Буква

Символы Морзе

Слово

А

.-

а-том

Р

.-.

ра-ду-га

Б

-...

бес-са-раб-ка

С

са-ма-ра

В

.--

ва-ви-лон

Т

-

Ток

Г

--.

го-ло-ва

У

..-

 

Д

-..

до-бав-ка

ф

..-.

фа-на-тич-ка

Е

   

X

 

ха-на-ан-ка

Ж

...-

жат-ва-зла-ков

ц

-.-.

цы-га-ноч-ка

3

--..

звон-бу-ла-та

ч

 

че-ре-му-ха

И

   

ш

— -

ше-ре-ме-тев

К

-.-

конс-тан-тин

Щ

--.-

щу-ро-гла-зый

Л

.-..

ла-до-жан-ка

ю

..--

 

М

--

ми-иин

я

.-.-

 

Н

-.

но- га

ы

-.--

ы-ка-ни-е

0

о-ло-во

ь-ъ

-..-

 

П

.--.

па-ни-хи-да

     

Примечание
Примечание

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

В конце сороковых годов XX века основателем современной теории информации Шенноном, и независимо от него, Фано был разработан универсальный алгоритм построения оптимальных кодов. Более известый аналог этого алгоритма был предложен несколько позже Дэвидом Хаффманом [Huffman 1952]. Принцип построения этих кодов в целом соответствует логике, которой руководствовался Морзе, — кодировать значения, которые часто повторяются в потоке, более короткими последовательностями битов.
Коды Хаффмана и Шеннона-Фано устраняют автокорреляции, соответствующие неравномерности встречаемости символов, но сохраняют без изменений часто встречающиеся последовательности символов, а они ответственны за значительную часть избыточности текстов на естественных и синтетических языках. Для упаковки данных такого рода в конце 70-х Лемпелем и Зиффом было предложено семейство алгоритмов, наиболее известные из которых - LZ77 и LZW [Lempel-Ziv 1978].
Все эти алгоритмы сводятся к поиску в потоке повторяющихся последовательностей и замене этих последовательностей на их номер в динамически формируемом словаре. Различие состоит в способах кодирования номера и формирования словаря. Номер последовательности в словаре должен содержать больше битов, чем символы исходного потока, хотя бы уже для того, чтобы его можно было отличить от символа, поэтому алгоритмы Лемпеля-Зиффа предполагают дальнейшее перекодирование преобразованного потока кодом Хаффмана. Большинство современных архиваторов, такие, как PkZip, GNU Zip, RAR, основаны на вариациях и аналогах алгоритмов Лем-пеля-Зиффа.
При упаковке нетекстовых данных могут применяться и другие способы удаления повторений. Например, при упаковке растровых изображений широко используется метод RLE (Run-Length Encoding), когда повторяющиеся пикселы заменяются счетчиком повторений и значением пиксела.
Наиболее универсальны так называемые арифметические алгоритмы, которые находят и устраняют все автокорреляции, присутствующие во входных данных. Математическое обоснование и принципы работы этих алгоритмов заслуживают отдельной книги и увели бы нас далеко в сторону от темы. К сожалению, из-за больших вычислительных затрат эти алгоритмы и реализующие их программы не получают широкого распространения.
Все перечисленные алгоритмы способны только устранять автокорреляции, уже существующие во входном потоке. Понятно, что если автокорреляций не было, то упаковки не произойдет, поэтому гарантировать уровень упаковки эти алгоритмы не могут.
Для упаковки данных, полученных оцифровкой реальных сигналов, прежде всего изображений и звука, точные алгоритмы не подходят совершенно. Дело в том, что реальный сигнал всегда сопровождается тепловым, так называемым белым (равномерно содержащим все частоты) шумом. Этот шум искажает наличествующие в сигнале автокорреляции, сам же автокорреляций не имеет, поэтому обратимые алгоритмы с зашумленным сигналом справиться не могут.
Чтобы убедиться в этом, можно попробовать упаковать любым, или даже несколькими из распространенных архиваторов трек аудио-CD или цифровую фотографию впрочем, чтобы с цифровой фотографией фокус получился, необходимо, чтобы кадр был снят без обработки встроенным упаковщиком камеры.
Идея обширного семейства алгоритмов, пригодных для сжатия зашумлен-ных сигналов, была позаимствована из принципа работы цифровых фильт-ров-"щумодавов". Шумодав работает следующим образом: он осуществляет над сигналом преобразование Фурье и удаляет из полученного спектрального образа самые слабые частоты, которые ниже порога подавления.
Сигнал при этом, конечно, искажается, но сильнее всего при этом страдает равномерно распределенный по спектру шум, что и требуется (Рисунок 1.8).



Содержание раздела