Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Однако посмотрим на это под другим углом: во всех приведенных примерах записи данных мы сохраняем одни и те же результаты - одну и ту же информацию - используя все меньший и меньший объем памяти. Другими словами, мы выполняем сжатие данных.
Сжатие данных
Сжатие данных (data compression) - это алгоритм эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее. Мы избавляемся от избыточности (redundancy), т.е. удаляем из физического представления данных те биты, которые в действительности не требуются, оставляя только то количество битов, которое необходимо для представления информации в соответствии со значением энтропии. Существует показатель эффективности сжатия данных: коэффициент сжатия (compression ratio).
Конечно, сжатые данные могут быть записаны в форме недоступной для непосредственного считывания и понимания человеком. Люди нуждаются в определенной избыточности представления данных, способствующей их эффективному распознаванию и пониманию. Применительно к эксперименту с подбрасыванием монеты последовательности символов "О" и "Р" обладают большей наглядностью, чем 8-битовые значения байтов. (Возможно, что для большей наглядности пришлось бы разбить последовательности символов "О" и "Р" на группы, скажем, по 10 символов в каждой.) Иначе говоря, возможность выполнения сжатия данных бесполезна, если отсутствует возможность их последующего восстановления. Эту обратную операцию называют декодированием (decoding).
Типы сжатия
Существует два основных типа сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие без потерь проще для понимания. Это метод сжатия данных, когда при восстановлении данных возвращается точная копия исходных данных. Такой тип сжатия используется программой PKZIB"1: распаковка упакованного файла приводит к созданию файла, который имеет в точности то же содержимое, что и оригинал перед его сжатием. И напротив, сжатие с потерями не позволяет при восстановлении получить те же исходные данные. Это кажется недостатком, но для определенных типов данных, таких как данные изображений и звука, различие между восстановленными и исходными данными не имеет особого значения: наши зрение и слух не в состоянии уловить образовавшиеся различия. В общем случае алгоритмы сжатия с потерями обеспечивают более эффективное сжатие, чем алгоритмы сжатия без потерь (в противном случае их не стоило бы использовать вообще). Для примера можно сравнить предназначенный для хранения изображений формат с потерями JPEG с форматом без потерь GIF. Множество форматов потокового аудио и видео, используемых в Internet для загрузки мультимедиа-материалов, являются алгоритмами сжатия с потерями.
В случае экспериментов с подбрасыванием монеты было очень легко определить наилучший способ хранения набора данных. Но для других данных эта задача становится более сложной. При этом можно применить несколько алгоритмических подходов. Два класса сжатия, которые будут рассмотрены в этой главе, представляют собой алгоритмы сжатия без потерь и называются кодированием с минимальной избыточностью (minimum redundancy coding) и сжатием с применением словаря (dictionary compression).
Кодирование с минимальной избыточностью - это метод кодирования байтов (или, более строго, символов), при котором чаще встречающиеся байты кодируются меньшим количеством битов, чем те, которые встречаются реже. Например, в тексте на английском языке буквы Е, m и А встречаются чаще, нежели буквы Q, X и Z. Поэтому, если бы удалось закодировать буквы Е, m и А меньшим количеством битов, чем 8 (как должно быть в соответствии со стандартом ASCII), а буквы Q, X и Z - большим, текст на английском языке удалось бы сохранить с использованием меньшего количества битов, чем при соблюдении стандарта ASCII.
При использовании сжатия с применением словаря данные разбиваются на большие фрагменты (называемые лексемами), чем символы. Затем применяется алгоритм кодирования лексем определенным минимальным количеством битов. Например, слова "the", "and" и "to" будут встречаться чаще, чем такие слова, как "electric", "ambiguous"
Потоки битов
Прежде чем приступить к исследованию реальных алгоритмов сжатия, необходимо кратко рассмотреть задачу манипулирования битами. При использовании большинства алгоритмов сжатия, которые будут рассмотрены, сжатие данных выполняется с использованием переменного количества битов, независимо от того, рассматриваются ли данные в качестве последовательности символов или лексем. Нельзя считать, что байты всегда будут состоять из групп по 8 битов.
Нам потребуется выполнять две базовых операции: считывание отельного бита и запись отдельного бита. На основе этих операций можно было бы построить операции, выполняющие считывание и запись сразу нескольких битов. Поэтому мы разработаем и создадим поток битов (bit stream) - структуру данных, содержащую в себе набор битов. Понятно, что поток битов будет использовать еще одну структуру данных, в которой данные битов хранятся в виде последовательности байтов. Эта структура будет извлекать биты в соответствии с байтами в данных, на основе которых она построена. Поскольку мы используем Delphi, в качестве базовой структуры данных потока битов мы выберем объект TStream (или производный от него). В результате, например, мы смогли бы рассматривать поток памяти или поток файла как поток битов. Фактически, поскольку потоки битов будут использоваться только в качестве последовательных групп битов, мы создадим два различных типа: входной поток битов и выходной поток битов. Кроме того, можно избавиться от обычно используемого метода Seek, поскольку поиск в потоке битов мы выполнять не будем.
Код интерфейса классов TtdInputBitStream и TtdOutputBitStream приведен в листинге 11.1.
Листинг 11.1. Интерфейс классов потоков битов
type
TtdInputBitStream = class private
FAccum : byte;
FBufEnd : integer;
FBuffer : PAnsiChar;
FBufPos : integer;
FMask : byte;
FName : TtdNameString;
FStream : TStream;
protected
procedure ibsError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure ibsReadBuffer;
public
constructor Create(aStream : TStream);
destructor Destroy; override;
function ReadBit : boolean;
procedure ReadBits(var aBitString : TtdBitString; aBitCount : integer);
function ReadByte : byte;
property Name : TtdNameString read FName write FName;
end;
TtdOutputBitStream = class private
FAccum : byte;
FBuffer : PAnsiChar;
FBufPos : integer;
FMask : byte;
FName : TtdNameString;
FStream : TStream;
FStrmBroken : boolean;
protected
procedure obsError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure obsWriteBuffer;
public
constructor Create(aStream : TStream);
destructor Destroy; override;
procedure WriteBit(aBit : boolean);
procedure WriteBits(const aBitString : TtdBitString);
procedure WriteByte(aByte : byte);
property Name : TtdNameString read FName write FName;
end;
Оба конструктора Create требуют передачи им в качестве параметра уже созданного производного объекта TStream. Из этого потока байтов класс потока битов будет извлекать или сохранять отдельные байты. Код конструкторов Create и деструкторов Destroy этих классов приведен в листинге 11.2.
Листинг 11.2. Создание и уничтожение объектов потока битов
constructor TtdInputBitStream.Create(aStream : TStream);
begin
inherited Create;