ВУЗ:
Составители:
ные методы кодирования для надежного закрытия содержимого файлов.
Примером такого кодирования является метод рассечения-разнесения, в
соответствии с которым содержимое одного файла разбивается на блоки,
которые разносятся по нескольким файлам. Каждый такой файл не несет
никакой информации, а сбор данных в единое целое осуществляется про-
стой программой.
Пример. Блок (файл открытого текста) начинается словами: "МЕ-
ТОД_РАССЕЧЕНИЯ-РАЗНЕСЕНИЯ".
Для рассечения блока открытого текста на 8 частей запишем откры-
тый текст в следующем виде (табл. 2.11).
2.11. Рассечения открытого текста
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 М Е Т О С С Е Ч – Р А З Н И Я _
2 Д _ Р А Е Н И Я Н Е С Е
Для рассечения текста на 8 частей выбраны 2 строки и 4 столбца.
Пусть столбцы s
j
выбираются в последовательности {4, 1, 3, 2}, а строки r
i
– в последовательности {2, 1}. Тогда номер k блока Ф
k
, куда записывается
очередной символ открытого текста, определяется по формуле
k = (r
i
– 1)n + s
j
,
где n – число столбцов.
Первый символ М запишется в блок с номером (r
i
= 2, s
j
= 4) : k = (2 –
1)*4 + 4 = 8; второй символ E – в блок с номером (r
i
= 2, s
j
= 1) : k = (2 – 1)*4
+ 1 = 5, и т.д.
Тогда блоки Ф
k
, записанные в порядке номеров, будут содержать
следующие символы: Ф
1
= (_НЕ...), Ф
2
= (АЯЕ...), Ф
3
= (РИС..,),
Ф
4
= {ДЕН...), Ф
5
= {ЕСРИ...}, Ф
6
= {ОЧЗ...), Ф
7
= {ТЕАЯ...), Ф
8
= {МС-
Н...}. Таким образом, один блок открытого текста заменяется восемью бло-
ками, которые в сумме дают длину исходного блока.
Одной из важных проблем при использовании ПЭВМ является про-
блема хранения больших массивов данных. Для этой цели применяют раз-
личные методы сжатия данных (сжатие рассматривается как метод кодиро-
вания).
Методы сжатия данных осуществляют такое преобразование повто-
ряющихся символов и строк символов, которое позволяет использовать для
хранения данных меньший объем памяти. Методы сжатия можно разделить на
два класса: статические и динамические (адаптивные).
Методы статического сжатия данных эффективны, когда частоты по-
явления символов изменяются незначительно. Методы динамического сжа-
тия адаптивно отслеживают неравномерности частот появления символов с
сохранением последовательности изменений вероятностей появления сим-
волов.
Адаптивные методы сжатия могут динамично реагировать на измене-
ния в открытом тексте, происходящие по мере кодирования. Первые такие
методы являлись модификацией кодов Хаффмена и использовали счетчики
для хранения текущих частот появления каждого символа. При таких мето-
дах наиболее часто встречающиеся символы сдвигаются ближе к корню
дерева и, следовательно, получают более короткие кодовые слова.
Кодирование Лемпеля-Зива использует синтаксический метод для ди-
намического источника. Этот метод осуществляет синтаксический анализ
символьных потоков, которые не превышают заданной длины, и строит
таблицу отображения этих потоков в кодированные слова фиксированной
длины. Длина кодового слова зависит от размера таблицы, используемой
для хранения кодового отображения поток-слово. Например, размер табли-
цы в 4096 слов требует 12-битового кодового слова. Кодовое слово являет-
ся просто табличным адресом соответствующих слов в таблице.
При кодировании по методу Лемпеля-Зива-Уэлча таблица инициали-
зируется символьным множеством и содержит вместо потоков заданной
длины пары (кодовое слово, символ) фиксированной длины. Таблица стро-
ится на основе синтаксического анализа самого длинного опознанного в
таблице потока и использовании последующего символа для формирования
нового входа в таблицу. Это позволяет уменьшить размеры таблицы.
Страницы
- « первая
- ‹ предыдущая
- …
- 47
- 48
- 49
- 50
- 51
- …
- следующая ›
- последняя »
