Алгоритм кодирования. Примеры кодов
Один из самых простых методов кодирования — ROT 13. Он заключается в том, что каждой букве присваивается число, например А—1, В—2 и т.д. Если вы пишете HELLO, то присваиваете число каждой букве, затем к каждому из них прибавляете 13, после чего полученные числа снова заменяются буквами. Если это число больше 26, то из него следует вычесть 26, чтобы не превысить количество букв в алфавите (в латинском.— Прим. ред.). Слово HELLO состоит из чисел 8, 5, 12, 12, 15. Теперь прибавляем к каждому числу 13 и получаем 21, 18, 25, 25, 28. 28 больше 26, значит, необходимо вычесть 26 из 28; в конечном виде последовательность чисел будет выглядеть так: 21, 18, 25, 25, 2. Превращаем ее снова в буквы и получаем слово URYYB, которое ничем не напоминает исходное HELLO. Это пример очень простого алгоритма кодирования. Его вполне достаточно, если вы опасаетесь, что в процессе передачи ваше письмо будут просматривать для обнаружения ключевых слов. В письме, зашифрованном таким образом, никакие ключевые слова найти невозможно. Но это не гарантия полной безопасности: если конкуренты включат в программу сканирования простенький алгоритм декодирования, ваши усилия будут мгновенно сведены на нет.
В некоторых странах, например во Франции, шифрование разрешается использовать только в том случае, если копия ключей, применяемых для шифрования, своевременно передана в соответствующие государственные организации. Эта система, которая называется депонированием ключей, позволяет полиции и иным государственным учреждениям расшифровывать закодированные послания. Может быть, идея и неплоха, только на практике она не работает. Пользователи и бизнесмены не доверяют методам шифрования, если знают, что закодированные с их помощью сообщения могут прочитать государственные служащие. К тому же есть основания опасаться, что при такой системе ключами кодирования могут воспользоваться террористы и преступники.
В большинстве стран мира запрещено хранить оружие, однако преступники все равно им пользуются. Объявление шифрования незаконным еще хуже. Деловые операции, осуществляемые в Internet, могут стать всем известными, и этой информацией не преминут воспользоваться конкуренты, чтобы расправиться с вашей компанией. К тому же, даже если во всем мире кодирование будет запрещено законом, преступники все равно будут его применять, поскольку они уже нарушают закон и им плевать, что говорят политики или полицейские.
Идея арифметического кодирования
Стандартный метод сжатия файлов. Хорош для любой информации. Двухпроходной. Лучше Хаффмана, но в чистом виде не используется.
Метод LZW-сжатия данных
LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры ( текст, сжатие видеоформ и копий экранов). Сжатие однопроходное и может быть осуществлено 'на лету'.
Использование алгоритма расширяющегося префикса для кодирования и схожих пpоцессов
Статья дает описание арифметического кодирования с применением 'splay trees' - расширяющихся деревьев. C исходниками..
Сжатие по алгоритму Хаффмана
Старый, добрый двухпроходной Хаффман. Классика кодирования. Исходник прилагается.
RLE (Групповое кодирование)
Старейший двухпроходной алгоритм сжатия информации. Применяется только как дополнение к другим методам. Легок для освоения и реализации.
UUE-кодирование
Основные алгоритмы UUE-кодирования. Описание используемого при UUE CRC-алгоритма. Исходник прилагается.
Huffman - Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.
Сжимая файл по алгоритму Хаффмана первое что мы должны сделать - это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.
После подсчета частоты вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и сформировать мнимую компоновку между кодами по убыванию. То есть не меняя местонахождение каждого символа из таблицы в памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней таблицы назовем "узлом". В дальнейшем ( в дереве ) мы будем позже размещать указатели которые будут указывает на этот "узел". Для ясности давайте рассмотрим пример:
Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее :
|-----------------|-----|-----|-----|-----|-----|-----|
| cимвол | A | B | C | D | E | F |
|-----------------|-----|-----|-----|-----|-----|-----|
| число вхождений | 10 | 20 | 30 | 5 | 25 | 10 |
|-----------------|-----|-----|-----|-----|-----|-----|
Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа. Разместим таблицу как ниже.
|-----------------|-----|-----|-----|-----|-----|-----|
| cимвол | C | E | B | F | A | D |
|-----------------|-----|-----|-----|-----|-----|-----|
| число вхождений | 30 | 25 | 20 | 10 | 10 | 5 |
|-----------------|-----|-----|-----|-----|-----|-----|
Коды исправляющие ошибки
Существует множество кодов, исправляющих ошибки в двоичном коде. Это очень полезно, потому что множество информации портиться при хранении или передачи информации. Одним из примеров данных кодов можно привести «код Хемминга»(Подробно о нём уже написал другой автор http://habrahabr.ru/post/140611/). Они добавляют к бинарному тексту дополнительные, кодовые биты, при помощи которых мы сможем исправить полученные ошибки.
Каждый такой код имеет две характеристики – k и n. Такой код называется (n,k)-кодом. Здесь “n” обозначает общее количество символов в блоке закодированного текста, а “k” – число значимых символов.
Например, простейшим кодом является код с повторениями. В этом коде к каждому символу двоичного кода добавляется по n-1 кодовых битов, которые дублируют, значимый символ и в последствие мы сможем исправить ошибку. Например (3,1)-код дописывает к каждому символу в двоичной системе два таких же и при зашумлении, если меняется один символ из блока, то остаётся 2 одинаковых и по ним мы возвращаем исходный символ.
Для того чтобы иметь возможность передать максимальное количество сообщений по каналу связи, необходимо использовать коды с, максимальным числом элементов при заданной корректирующей способности. Построение таких кодов является одной из основных задач теории К. с и. о. Эта задача достаточно далеко продвинута только для нек-рых рассматриваемых ниже конечных множеств Ln. В то гке время как для приложений, так и для теории интересны коды на нек-рых бесконечных множествах, напр, на сфере в евклидовом пространстве Rn.
При практическом использовании К. с и. о. возникают задачи отображения информации, предназначенной для передачи в множество элементов К. с и. о. и нахождения по принятому элементу х' переданного элемента кода х. Первая задача наз. задачей кодирования, вторая - задачей декодирования. Сложность кодирования и декодирования в значительной мере определяется свойствами используемого К. с и. <о. Это обстоятельство приводит к изучению относительно узких классов кодов, как, например, рассматриваемых ниже двоичных линейных кодов.
Наиболее широко исследовались блоковые r-и чные коды в метрике Хемминга, ввиду того что они находят многочисленные применения, а методы их построения связаны с известными ранее математическими структурами. Элементами этих кодов являются нек-рые элементы множества В nr, состоящего из всех векторов длины п, координаты к-рых принадлежат множеству из rэлементов. Расстоянием Хемминга d(x, у )между векторами х, у из В nr наз. число их несовпадающих координат. Окрестность ошибок Ut(x)кратности t(t- целое) вектора хсостоит из всех векторов из В nr, отличающихся от хне более чем в r координатах, т. е. Uf(x)- шар в метрике d(,) радиуса tс центром в точке х. В частности, U1 (х). состоит из (r-1)n+1 векторов. Для произвольного множества функция наз. кодовым расстоянием r-ичного кода К. Код Кявляется К. си. о. кратности t, если При выполнении последнего неравенства каждая окрестность ошибок Ut(x), не пересекается ни с какой другой окрестностью ошибок кратности tвектора уиз К. Значительный прогресс в изучении r-ичных кодов получен для случая, когда г является степенью простого числа. В этом случае в качестве множества координат берут конечное поле GF(q)из qэлементов и используют алгебраические свойства этого понятия. Ниже предполагается, что координатами элементов множества являются элементы поля GF(q). Множество является линейным пространством над полем GF(q). Если векторы кода Кобразуют линейное подпространство пространства то код наз. линейным. Линейный код К может быть задан как своим базисом, так и базисом линейного пространства, двойственного к К. Последний способ более распространен. Матрица А, строками к-рой служат базисные векторы пространства, двойственного к К, наз. проверочной матрицей К. Для векторов справедливо соотношение: хА T=0, где А T- транспонированная матрица А. Далее п - длина кода, к- размерность линейного кода и d- кодовое расстояние. Код над наз. двоичным кодом.