Сначала осуществляется поиск в окне символа х₁. Если символ не найден, то в качестве кода передается 0 как признак того, что этого символа нет в окне и двоичное представление х₁.

Если символ х₁ найден, то осуществляется поиск в окне слова х₁х₂, начинающегося с этого символа. Если слово х₁х₂ есть в окне, то производится поиск слова х₁х₂х₃ , затем х₁х₂х₃х₄ и так далее, пока не будет найдено слово, состоящее из наибольшего количества входных символов в порядке их поступления. В этом случае в качестве кода передается 1 и пара чисел (i, j), указывающая положение найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина этого слова, позиции в окне нумеруются справа налево). Затем окно сдвигается на j символов вправо по тексту и кодирование продолжается.

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

Пусть алфавит источника А={а, b, с}, длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac. (см. рис. 9)

После кодирования первых шести букв окно будет иметь вид bababa.

• Далее проверяем наличие в окне буквы а. Она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Этого слова нет в окне, тогда кодируем aba кодовой комбинацией (1,3,3), где 1– признак того, что слово есть в «окне», 3– номер позиции в окне, с которой начинается это слово, 3– длина этого слова.
• Далее окно сдвигаем на 3 символа вправо и ищем в окне букву с. Ее нет в окне, поэтому кодируем комбинацией (0, «с»), где 0– признак того, что буквы нет в окне, «с»– двоичное представление буквы. Окно сдвигаем на 1 символ вправо.
• Ищем в окне букву а, она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Это слово есть в окне, тогда кодируем abaс кодовой комбинацией (1,4,4), где 1 – признак того, что слово есть в окне, 4 –номер позиции в окне, с которой начинается это слово, 4 – длина этого слова.

Рисунок 9 Кодирование последовательности bababaabacabac

• 1. Кодирование с использованием адаптивного словаря

---

В этих словарных методах для хранения слов используется адаптивный словарь, заполняющийся в процессе кодирования. Перед началом кодирования в словарь включаются все символы алфавита источника. При кодировании сообщения Х=х₁х₂х₃х₄… сначала читаются два символа х₁х₂, поскольку это слово отсутствует в словаре, то передается код символа х₁ (обычно это номер строки, содержащей найденный символ или слово). В свободную строку таблицы записывается слово х₁х₂, далее читается символ х₃ и осуществляется поиск в словаре слова х₂х₃. Если это слово есть в словаре, то проверяется наличие слова х₂х₃х₄ и так далее. Таким образом, слово из наибольшего количества входных символов, найденное в словаре, кодируется как номер строки, его содержащей.

Пусть алфавит источника А={а, b, с}, размер словаря V=8. Необходимо закодировать исходное сообщение abababaabacabac.

1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины L = log₂V = log₂8 =3.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	–
4	–
5	–
6	–
7	–

1. Читаем первые две буквы ab, ищем слово ab в словаре. Этого слова нет, поэтому поместим слово ab в свободную 3-ю строку словаря, а букву а закодируем кодом 000.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	–
5	–
6	–
7	–

1. Далее читаем букву a и ищем в словаре слово ba. Этого слова нет, поэтому запишем в 4-ю строку словаря слово ba, букву b закодируем кодом 001.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	–
6	–
7	–

---

1. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba, его нет в словаре. Запишем слово aba в 5-ю строку словаря, и закодируем ab кодом 011.
2. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву а, получим слово abaа, его нет в словаре. Запишем слово abaа в 6-ю строку словаря, и закодируем abа кодом 101.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	011
6	abaа	101
7	–

1. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 7-ю строку словаря, и закодируем abа кодом 101. Если словарь заполняется до окончания кодирования, то можно записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	101
6	abaа	110
7	abaс	111

1. Читаем букву а, ищем в словаре слово са. Этого слова нет в словаре, поэтому запишем слово са в 7-ю строку словаря, удалив слово abас, и закодируем букву с кодом 010.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	101
6	abaа	110
7	abaс са	111

---

1. Читаем букву b, ищем в словаре слово ab. Это слово есть в словаре в строке 3. Читаем следующую букву а, получим слово aba. Это слово есть в словаре в строке 5. Читаем букву с, получим слово abaс, его нет в словаре. Запишем слово abaс в 6-ю строку словаря, и закодируем abа кодом 101.

Номер строки	Слово	Код
0	a	000
1	b	001
2	c	010
3	ab	011
4	ba	100
5	aba	101
6	abaа abaс	110
7	са	111

1. Закодируем букву с кодом 010. Конец входной последовательности.

Таким образом, входное сообщение будет закодировано так

Вход кодера: a b ab aba aba c aba c

Выход кодера: 000 001 011 101 101 010 101 010

Рассмотрим теперь на примере ранее закодированного сообщения abababaabacabac (алфавит источника А={а, b, с}, размер словаря V=8) процесс декодирования. Закодированная последовательность имела такой вид

000001011101101010101010

1. Запишем символы алфавита А в словарь, каждому символу припишем кодовое слово длины L = log₂V = log₂8 = 3. (Процесс заполнения словаря будет таким же, как и при кодировании.)
2. Читаем первые три бита кодовой последовательности (код 000), по коду найдем в словаре букву а.
3. Читаем следующий код 001, по коду найдем в словаре букву b. Получим новое слово ab, которого нет в словаре, поместим слово ab в свободную 3-ю строку словаря. На выход декодера передаем букву а, букву b запоминаем.
4. Читаем код 011, по коду находим в словаре слово ab. Добавляем первую букву а к предыдущему декодированному слову b, получим слово ba, его нет в словаре. Поместим слово ba в свободную 4-ю строку словаря. На выход декодера передаем букву b, слово ab запоминаем.
5. Читаем код 101, такого кода нет в словаре. Тогда добавляем к слову ab

первую букву этой же последовательности – а, получим слово aba, его нет в словаре. Поместим слово aba в свободную 5-ю строку словаря. На выход декодера передаем слово ab, слово aba запоминаем.

1. Читаем код 101, по коду находим в словаре слово aba, добавляем первую букву a к предыдущему декодированному слову aba, получим abaa. Добавим слово abaa в словарь в свободную 6-ю строку. На выход декодера передаем слово aba , и слово aba запоминаем.
2. Читаем код 010, по коду находим в словаре букву с, добавляем букву с к предыдущему декодированному слову aba, получим abac. Добавим слово abaс в словарь в свободную 7-ю строку. На выход декодера передаем слово aba , букву с запоминаем.
3. Читаем код 101, по коду находим в словаре слово aba, добавляем первую букву а к предыдущей декодированной букве с, получим слово са.

---

Так как словарь заполнился до окончания декодирования, то будем записывать новые слова в словарь, начиная со строки с наибольшим номером, удаляя ранее записанные там слова. Добавим слово са в 7-ю строку словаря вместо слова abac. На выход декодера передаем букву с, слово aba запоминаем.

1. Читаем код 010, по коду находим в словаре букву с, добавляем букву с к предыдущему декодированному слову aba, получим abac. Добавим слово abac в 6-ю строку словаря вместо слова abaа. На выход декодера передаем слово aba, букву с запоминаем.
2. На выход декодера передаем букву с.

В результате декодирования получим исходное сообщение

Вход декодера: 000 001 011 101 101 010 101 010

Выход декодера: a b ab aba aba c aba c

ЗАКЛЮЧЕНИЕ

Любая информация, с которой работает современная вычислительная техника, преобразуется в числа в двоичной системе счисления. Дело в том, что физические устройства (регистры, ячейки памяти) могут находиться в двух состояниях, которым соотносят 0 или 1. Используя ряд подобных физических устройств, можно хранить в памяти компьютера почти любое число в двоичной системе счисления. Сколько физических ячеек, используемых для записи числа, столько и разрядное число можно записать. Если ячеек 8, то и число может состоять из 8 цифр. Кодирование в компьютере целых чисел, дробных и отрицательных, а также символов (букв и др.) имеет свои особенности для каждого вида. Например, для хранения целых чисел выделяется меньше памяти (меньше ячеек), чем для хранения дробных независимо от их значения. Однако, всегда следует помнить, что любая информация (числовая, текстовая, графическая, звуковая и др.) в памяти компьютера представляется в виде чисел в двоичной системе счисления (почти всегда). В общем смысле кодирование информации можно определить как перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов. Надо понимать, что любые данные — это так или иначе закодированная информация. Информация может быть представлена в разных формах: в виде чисел, текста, рисунка и др. Перевод из одной формы в другую — это кодирование.

1. используемая ЛИТЕРАТУРА

2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. - М.: Издательский дом "Вильямс", 2000. - 384 с.
3. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. – М.: «Диалог-МИФИ», 2002.
4. Кричевский Р.Е. Сжатие и поиск информации. - М.: Радио и связь, 1989. - 168 с.
5. Марченко А.И., Марченко Л.А. Программирование в среде Turbo PASCAL 7.0. Базовый курс. Киев: «ВЕК+», 2003.
6. Панин В.В., Основы теории информации. Учебное пособие для ВУЗов. Бином, 2009.
7. Нечта И. В. Построение меню при помощи алфавитного кода // Вестник

---

Смотрите также файлы

• Особенности семейного воспитания(Семья – основа семейного воспитания).pdf

• Тенденции развития международной валютной системы ( Понятие и сущность международной валютной системы).pdf

• Социальное страхование и его функции (Проблемы и перспективы развития).pdf

• Государственная служба в Российской Федерации: опыт, современное состояние и направления совершенствования (История и опыт государственной службы в Российской Федерации ).pdf

• Основные направления реформы государственной службы в России (Система государственной службы ).pdf