Учебное пособие: Дискретная мат-ка_УП
101
При
заданном
п
количество
дополнительных
разрядов
k
подбирается
таким
образом
,
чтобы
2
k
≥
п + 1.
Имеем
:
m
n
k
n
n
k
n
n
n
2
1
2
2
1
2
1
2
≥
+
⇒
≥
+
⇒
+
≥
−
.
Пример
Для
сообщения
длиной
m = 32
потребуется
k = 6
дополни
-
тельных
разрядов
,
поскольку
64 – 2
6
> 32 + 6 + 1 = 39.
Определим
последовательности
натуральных
чисел
в
соот
-
ветствии
с
их
представлениями
в
двоичной
системе
счисления
следующим
образом
:
●
V
1
: = 1, 3, 5, 7, 9, 11, … –
все
числа
,
у
которых
разряд
№
1
равен
1;
●
V
2
: = 2, 3, 6, 7, 10, … –
все
числа
,
у
которых
разряд
№
2
равен
1;
●
V
3
: = 4, 5, 6, 7, 12, … –
все
числа
,
у
которых
разряд
№
3
равен
1,
●
и
т
.
д
.
По
определению
последовательность
V
k
начинается
с
числа
2
k–1
.
Рассмотрим
в
слове
b
1
... b
n
k
разрядов
с
номерами
2
0
= 1, 2
1
=
=2, 2
2
= 4,... 2
k–1
.
Эти
разряды
назовем
контрольными.
Остальные
разряды
,
а
их
ровно
m,
назовем
информационными.
Поместим
в
информационные
разряды
все
разряды
слова
a
1
...а
n
как
они
есть
.
Контрольные
разряды
определим
следующим
образом
:
b
1
: = b
3
⊕ b
5
⊕ b
7
⊕ …, –
то
есть
все
разряды
с
номерами
из
V
1
,
кроме
первого
;
b
2
: = b
3
⊕ b
6
⊕ b
7
⊕ …, –
то
есть
все
разряды
с
номерами
из
V
2
,
кроме
первого
;
b
4
: = b
5
⊕ b
6
⊕ b
7
⊕ …, –
то
есть
все
разряды
с
номерами
из
V
3
,
кроме
первого
;
и
вообще
,
{ }
i
V
i
b
b
j
j
j
⊕
−
−
∈
=
1
1
2
\
2
:
.
Пусть
после
прохождения
через
канал
получен
код
c
1
…
с
n
,
то
есть
c
1
…
с
n
:
= C(b
1
… b
п
)
,
причем
102
⎩
⎨
⎧
=
∃
I
I
I
b
b
c
I
,
∀ i ≠ I c
i
= b
i
.
Здесь
I –
номер
разряда
,
в
котором
,
возможно
,
произошла
ошибка
замещения
.
Пусть
это
число
имеет
следующее
двоичное
представление
:
I = i
l
… i
1
.
Определим
число
J = j
l
… j
1
следующим
образом
:
j
1
:
= c
1
⊕ c
3
⊕ c
5
⊕ c
7
⊕ …, –
то
есть
все
разряды
с
номерами
из
V
1
;
j
2
: = c
2
⊕ c
3
⊕ c
6
⊕ c
7
⊕ …, –
то
есть
все
разряды
с
номерами
из
V
2
;
j
3
: = c
4
⊕ c
5
⊕ c
6
⊕ c
7
⊕ …, –
то
есть
все
разряды
с
номерами
из
V
3
;
и
вообще
,
q
V
q
p
c
j
p
⊕
∈
=
:
.
ТЕОРЕМА. I = J.
8.4
Сжатие
данных
Материал
раздела
кодирования
с
минимальной
избыточно
-
стью
показывает
,
что
при
кодировании
наблюдается
некоторый
баланс
между
временем
и
памятью
.
Затрачивая
дополнительные
усилия
при
кодировании
и
декодировании
,
можно
сэкономить
память
,
и
,
наоборот
,
пренебрегая
оптимальным
использованием
памяти
,
можно
существенно
выиграть
во
времени
кодирования
и
декодирования
.
Конечно
,
этот
баланс
имеет
место
только
в
опре
-
деленных
пределах
,
и
нельзя
сократить
расход
памяти
до
нуля
или
построить
мгновенно
работающие
алгоритмы
кодирования
.
Для
достижения
прогресса
нужно
рассмотреть
неалфавитное
ко
-
дирование
.
Сжатие текстов
Допустим
,
что
имеется
некоторое
сообщение
,
которое
зако
-
дировано
каким
-
то
общепринятым
способом
(
для
текстов
это
,
на
-
пример
,
код
ASCII)
и
хранится
в
памяти
компьютера
.
Заметим
,
что
равномерное
кодирование
(
в
частности
, ASCII)
не
является
103
оптимальным
для
текстов
.
Действительно
,
в
текстах
обычно
ис
-
пользуется
существенно
меньше
,
чем
256
символов
(
в
зависимо
-
сти
от
языка
–
примерно
60
−80
с
учетом
знаков
препинания
,
цифр
,
строчных
и
прописных
букв
).
Кроме
того
,
вероятности
по
-
явления
букв
различны
и
для
каждого
естественного
языка
из
-
вестны
(
с
некоторой
точностью
)
частоты
появления
букв
в
тек
-
сте
.
Таким
образом
,
можно
задаться
некоторым
набором
букв
и
частотами
их
появления
в
тексте
и
с
помощью
алгоритма
Хаф
-
фмена
построить
оптимальное
алфавитное
кодирование
текстов
(
для
заданного
алфавита
и
языка
).
Простые
расчеты
показывают
,
что
такое
кодирование
для
распространенных
естественных
язы
-
ков
будет
иметь
цену
кодирования
несколько
меньше
6,
то
есть
даст
выигрыш
по
сравнению
с
кодом
ASCII
на
25%
или
несколь
-
ко
больше
.
Методы
кодирования
,
которые
позволяют
построить
(
без
потери
информации
!)
коды
сообщений
,
имеющие
меньшую
дли
-
ну
по
сравнению
с
исходным
сообщением
,
называются
методами
сжатия (
или
упаковки
)
данных
.
Качество
сжатия
определяется
коэффицентом сжатия,
который
обычно
измеряется
в
процен
-
тах
и
показывает
,
на
сколько
процентов
кодированное
сообщение
короче
исходного
.
Известно
,
что
практические
программы
сжатия
(arj, zip
и
другие
)
имеют
гораздо
лучшие
показатели
:
при
сжатии
текстовых
файлов
коэффициент
сжатия
достигает
70%
и
более
.
Это
означа
-
ет
,
что
в
таких
программах
используется
не
алфавитное
кодиро
-
вание
.
Предварительное построение словаря
Рассмотрим
следующий
способ
кодирования
.
1.
Исходное
сообщение
по
некоторому
алгоритму
разбива
-
ется
на
последовательности
символов
,
называемые
словами
(
сло
-
во
может
иметь
одно
или
несколько
вхождений
в
исходный
текст
сообщения
).
2.
Полученное
множество
слов
считается
буквами
нового
алфавита
.
Для
этого
алфавита
строится
разделимая
схема
алфа
-
витного
кодирования
(
равномерного
кодирования
или
оптималь
-
104
ного
кодирования
,
если
для
каждого
слова
подсчитать
число
вхождений
в
текст
).
Полученная
схема
обычно
называется
слова
-
рем,
так
как
она
сопоставляет
слову
код
.
3.
Далее
код
сообщения
строится
как
пара
–
код
словаря
и
последовательность
кодов
слов
из
данного
словаря
.
4.
При
декодировании
исходное
сообщение
восстанавлива
-
ется
путем
замены
кодов
слов
на
слова
из
словаря
.
Пример
Допустим
,
что
требуется
кодировать
тексты
на
русском
языке
.
В
качестве
алгоритма
деления
на
слова
примем
естествен
-
ные
правила
языка
:
слова
отделяются
друг
от
друга
пробелами
или
знаками
препинания
.
Можно
принять
допущение
,
что
в
каж
-
дом
конкретном
тексте
имеется
не
более
2
16
различных
слов
(
обычно
гораздо
меньше
).
Таким
образом
,
каждому
слову
можно
сопоставить
номер
–
целое
число
из
двух
байтов
(
равномерное
кодирование
).
Поскольку
в
среднем
слова
русского
языка
состоят
более
чем
из
двух
букв
,
такое
кодирование
дает
существенное
сжатие
текста
(
около
75%
для
обычных
текстов
на
русском
язы
-
ке
).
Если
текст
достаточно
велик
(
сотни
тысяч
или
миллионы
букв
),
то
дополнительные
затраты
на
хранение
словаря
оказыва
-
ются
сравнительно
небольшими
.
Данный
метод
попутно
позволяет
решить
задачу
полнотек
-
стового поиска,
то
есть
определить
,
содержится
ли
заданное
сло
-
во
(
или
слова
)
в
данном
тексте
,
причем
для
этого
не
нужно
про
-
сматривать
весь
текст
(
достаточно
просмотреть
только
словарь
).
Указанный
метод
можно
усовершенствовать
следующим
образом
.
На
шаге
2
следует
применить
алгоритм
Хаффмена
для
построения
оптимального
кода
,
а
на
шаге
1 –
решить
экстремаль
-
ную
задачу
разбиения
текста
на
слова
таким
образом
,
чтобы
сре
-
ди
всех
возможных
разбиений
выбрать
то
,
которое
дает
наи
-
меньшую
цену
кодирования
на
шаге
2.
Такое
кодирование
будет
«
абсолютно
»
оптимальным
.
К
сожалению
,
указанная
экстремаль
-
ная
задача
очень
трудоемка
,
поэтому
на
практике
не
используется
–
время
на
предварительную
обработку
большого
текста
оказы
-
вается
чрезмерно
велико
.
105
Алгоритм Лемпела-Зива
На
практике
используется
следующая
идея
,
которая
извест
-
на
также
как
адаптивное
сжатие.
За
один
проход
по
тексту
од
-
новременно
динамически
строится
словарь
и
кодируется
текст
.
При
этом
словарь
не
хранится
–
за
счет
того
,
что
при
декодиро
-
вании
используется
тот
же
самый
алгоритм
построения
словаря
,
словарь
динамически
восстанавливается
.
Здесь
приведена
простейшая
реализация
этой
идеи
,
извест
-
ная
как
алгоритм
Лемпела-Зива.
Вначале
словарь
D : array [int]
of string
содержит
пустое
слово
,
имеющее
код
0.
Далее
в
тексте
последовательно
выделяются
слова
.
Выделяемое
слово
–
это
мак
-
симально
длинное
слово
из
уже
имеющихся
в
словаре
плюс
еще
один
символ
.
В
сжатое
представление
записывается
найденный
код
слова
и
расширяющая
буква
,
а
словарь
пополняется
расши
-
ренной
комбинацией
.
Алгоритм 3.
Упаковка
по
методу
Лемпела
-
Зива
.
Вход
:
исходный
текст
,
заданный
массивом
кодов
символов
f: array [l..n] of char.
Выход
:
сжатый
текст
,
представленный
последовательно
-
стью
пар
<
р
, q>,
где
р
–
номер
слова
в
словаре
,
q –
код
допол
-
няющей
буквы
.
D[0]: = ««;
d: = 0 {
начальное
состояние
словаря
}
k: = 1 {
номер
текущей
буквы
в
исходном
тексте
}
while
k
≤ n do
p: = FD(k) { р –
индекс
найденного
слова
в
словаре
}
l: = Length(D[p[) {lI –
длина
найденного
слова
в
словаре
}
yield
<р
, f[k + l]) {
код
найденного
слова
и
еще
одна
буква
}
d: = d+ 1; D[d]: = D[p] U f[k +lI
{
пополнение
словаря
,
здесь
U –
это
конкатенация
}
k: = k + l + 1 {
продвижение
вперед
по
исходному
тексту
}
end while
Слово
в
словаре
ищется
с
помощью
несложной
функции
FD.
Вход
:
k –
номер
символа
в
исходном
тексте
,
начиная
с
кото
-
рого
нужно
искать
в
тексте
слова
из
словаря
.