Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 29 (всего у книги 36 страниц)
else begin
{обработать символ вертикальной черты}
inc(FPosn);
{конечное состояние исходного члена еще не существует (хотя член и содержит состояние, которое указывает на него), поэтому его нужно создать}
EndState1 := rcAddState(mtNone, #0, nil, UnusedState, UnusedState);
{для конструкции ИЛИ требуется новое начальное состояние: оно будет указывать на исходный член и на второе выражение, синтаксический анализ которого будет выполняться следующим}
OverallStartState := rcAddState(mtNone, #0, nil,
UnusedState, UnusedState);
{выполнить синтаксический анализ следующего выражения}
StartState2 := rcParseExpr;
if (StartState2 = ErrorState) then
Exit;
{изменить состояние, определенное для всего выражения, чтобы вторая связь указывала на начало второго выражения}
Result := rcSetState(OverallStartState, StartStatel, StartState2);
{определить конечное состояние исходного члена, чтобы оно указывало на результирующее конечное состояние, определенное для второго выражения и всего выражения в целом}
rcSetState(EndState1, FTable.Count, UnusedState);
end;
end;
После ознакомления с этой конкретной конструкцией создание конечных автоматов для операций замыкания ("*", и+" и сложности не представляет. Важно только создавать состояния в правильном порядке. Рассмотрим код, приведенный в листинге 10.11.
Листинг 10.11. Синтаксический анализ операций замыкания
function TtdRegexEngine.rcParseFactor : integer;
var
StartStateAtom : integer;
EndStateAtom : integer;
begin
{предположим худшее}
Result := ErrorState;
{вначале выполнить синтаксический анализ элемента}
StartStateAtom := rcParseAtom;
if (StartStateAtom = ErrorState) then
Exit;
{проверить на наличие операции замыкания}
case FPosn^ of
' ?' : begin
{обработать символ операции ?}
inc(FPosn);
{конечное состояние элемента еще не существует, поэтому его нужно создать}
EndStateAtom := rcAddState(mtNone, #0, nil,
UnusedState, UnusedState);
{создать новое начальное состояние для всего регулярного выражения}
Result := rcAddState(mtNone, #0, nil,
StartStateAtom, EndStateAtom);
{обеспечить, чтобы новое конечное состояние указывало на следующее еще не использованное состояние}
rcSetState(EndStateAtom, FTable.Count, UnusedState);
end;
' *' : begin
{обработать символ операции *}
inc(FPosn);
{конечное состояние элемента еще не существует, поэтому его нужно создать; оно будет начальным состоянием всего подвыражения регулярного выражения}
Result := rcAddState(mtNone, #0, nil,
NewFinalState, StartStateAtom);
end;
' + ' : begin
{обработать символ операции +}
inc(FPosn);
{конечное состояние элемента еще не существует, поэтому его нужно создать}
rcAddState(mtNone, #0, nil, NewFinalState, StartStateAtom);
{начальное состояние всего подвыражения регулярного выражения будет начальным состоянием элемента}
Result := StartStateAtom;
end;
else
Result := StartStateAtom;
end; {case}
end;
При выполнении ноля или одного замыкания (операции "?") нужно создать конечное состояние элементарного выражения, к которому применяется операция, и начальное состояние всего конечного автомата. Эти новые состояния связаны между собой, как показано на рис. 10.5.
При выполнении ноля или более замыканий (операции "*") задача еще проще: нужно создать только конечное состояние для элемента. Оно становится начальным состоянием всего выражения. При этом виртуальное конечное состояние является конечным состоянием выражения.
При выполнении одного или более замыканий (операции "+") задача почти столь же проста. Потребуется создать конечное состояние для элемента и связать его с начальным состоянием элемента (которое является также начальным состоянием выражения). При этом виртуальное конечное состояние снова является конечным состоянием выражения.
Теперь осталось написать код только для выполнения операции конкатенации. На рисунке 10.6 эта операция выглядит просто: конечное состояние первого подвыражения становится начальным состоянием второго, и эти подвыражения связаны одно с другим. На практике не все так просто. Конечное состояние первого выражения является виртуальным конечным состоянием, причем не существует никакой гарантии, что оно будет совпадать с начальным состоянием следующего выражения (в этом случае они были бы автоматически связаны). Нет, вместо этого необходимо создать конечное состояние первого выражения и связать его с начальным состоянием второго выражения. Код решения этой последней задачи, включая создание заключительного конечного состояния, приведен в листинге 10.12.
На данный момент мы успешно связали аспекты синтаксического анализа и компиляции, что позволяет принять регулярное выражение и выполнить его синтаксический анализ с целью генерации скомпилированной таблицы переходов. На этапе компиляции программа определит и сохранит начальное состояние полного конечного NFA-автомата для регулярного выражения.
Однако прежде чем приступать к компиляции, необходимо выполнить несколько дополнительных действий для некоторого повышения эффективности. В ряде случаев нам приходилось добавлять некоторые состояния, выход из которых был связан всего с одним бесплатным переходом, причем самым неприятным был случай, когда дополнительное состояние требовалось для выполнения конкатенации.
Листинг 10.12. Синтаксический анализ конкатенации
function TtdRegexEngine.rcParseTerm : integer;
var
StartState2 : integer;
EndState1 : integer;
begin
{выполнить синтаксический анализ исходного коэффициента; возращенный при этом номер состояния буде также номером возвращаемого состояния}
Result := rcParseFactor;
if (Result = ErrorState) then
Exit;
if (FPosn^ = '(') or (FPosn^ = '[') or (FPosn^ = '.') or
((FPosn^ <> #0) and not (FPosn^ in Metacharacters)) then begin
{конечное состояние исходного коэффициента еще не существует (хотя член и содержит состояние, которое указывает на него), поэтому его нужно создать}
EndState1 := rcAddState(mtNone, #0, nil, UnusedState, UnusedState);
{выполнить синтаксический анализ следующего члена}
StartState2 := rcParseTerm;
if (StartState2 = ErrorState) then begin
Result := ErrorState;
Exit;
end;
{объединить первый коэффициент со вторым членом}
rcSetState(EndState1, StartState2, UnusedState);
end;
end;
Естественно, состояния с единственным переходом для выхода приводят к нерациональной трате времени. Поэтому необходимо выполнить оптимизацию, исключив их из таблицы переходов. Такие состояния называются фиктивными.
Однако вместо того, чтобы их удалять, мы просто их пропустим. Соответствующий алгоритм достаточно прост: необходимо выполнить считывание всех состояний. Для каждого состояния необходимо следовать по ссылке, указанной в его поле NextStatel. Если она устанавливает связь с одним из фиктивных состояний, связь нужно заменить связью NextStatel фиктивного состояния. Это же потребуется выполнить для связи NextState2 каждого состояния, если она существует. Код выполнения этой итерационной процедуры приведен в листинге 10.13.
Листинг 10.13. Оптимизация фиктивных состояний
procedure TtdRegexEngine.rcLevel1Optimize;
var
i : integer;
Walker : PNFAState;
begin
{оптимизация первого уровня удаляет все состояния, которые содержат только один бесплатный переход к другому состоянию}
{циклически обработать все записи состояний, кроме последней}
for i := 0 to (FTable.Count – 2) do
begin {получить данное состояние}
with PNFAState (FTable [ i ])^ do
begin
{выполнить проход по цепочке, указанной первым следующим состоянием, и разорвать связи с состояниями, которые являются простыми одиночными бесплатными переходами}
Walker := PNFAState(FTable[sdNextState1]);
while (Walker^.sdMatchType = mtNone) and
(Walker^.sdNextState2 = UnusedState) do
begin
sdNextState1 := Walker^.sdNextState1;
Walker := PNFAState(FTable[sdNextState1]);
end;
{выполнить проход по цепочке, указанной вторым следующим состоянием, и разорвать связи с состояниями, которые являются простыми одиночными бесплатными переходами}
if (sdNextState2 <> UnusedState) then begin
Walker := PNFAState(FTable[sdNextState2]);
while (Walker^.sdMatchType = mtNone) and
(Walker^.sdNextState2 = UnusedState) do
begin
sdNextState2 := Walker^.sdNextState1;
Walker := PNFAState(FTable[sdNextState2]);
end;
end;
end;
end;
end;
Сопоставление строк с регулярными выражениями
Пора решить заключительную часть задачи использования регулярных выражений – выполнить сопоставление с ними строк. Вместо того чтобы использовать уже рассмотренный алгоритм обратной трассировки, мы применим другой алгоритм. Используя входную строку, мы выполним обход конечного NFA-автомата (т.е. таблицы переходов), при этом одновременно отслеживая все возможные пути через конечный автомат. Со временем символы в строке будут исчерпаны, причем к этой точке будет вести один или более путей, либо возможных путей обработки строки больше не останется.
Однако для реализации этого алгоритма потребуется реализация очереди с двусторонним доступом (deque). Очередь с двусторонним доступом – это двусторонняя очередь, в которой постановку в очередь и исключение из очереди можно выполнять с любого конца. Нам потребуется возможность постановки элементов в конец очереди и их заталкивания в начало и из начала очереди (иначе говоря, исключение элементов из очереди должно выполняться только из ее начала и никогда из ее конца). Элементы, которые нужно будет ставить в очередь, представляют собой целочисленные значения (фактически, номера состояний). Код реализации этой простой очереди с двусторонним доступом показан в листинге 10.14 (его также можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDIntDeq.pas).
Листинг 10.14. Класс очереди целочисленных значений с двусторонним доступом type
TtdIntDeque = class private
FList : TList;
FHead : integer;
FTail : integer;
protected procedure idGrow;
procedure idError(aErrorCode : integer;
const aMethodName : TtdNameString);
public
constructor Create(aCapacity : integer);
destructor Destroy; override;
function IsEmpty : boolean;
procedure Enqueue(aValue : integer);
procedure Push(aValue : integer);
function Pop : integer;
end;
constructor TtdIntDeque.Create(aCapacity : integer);
begin
inherited Create;
FList := TList.Create;
FList.Count := aCapacity;
{для облегчения задачи пользователя очереди с двусторонним доступом поместить указатели начала и конца очереди в ее середину – вероятно, это более эффективно}
FHead := aCapacity div 2;
FTail := FHead;
end;
destructor TtdIntDeque.Destroy;
begin
FList.Free;
inherited Destroy;
end
procedure TtdIntDeque.Enqueue(aValue : integer);
begin
FList.List^[FTail] := pointer(aValue);
inc(FTail);
if (FTail = FList.Count) then
FTail := 0;
if (FTail = FHead) then
idGrow;
end;
procedure TtdIntDeque.idGrow;
var
OldCount : integer;
i, j : integer;
begin
{увеличить размер списка на 50%}
OldCount := FList.Count;
FList.Count := (OldCount * 3) div 2;
{распределить данные по увеличенной области, поддерживая при этом очередь с двусторонним доступом}
if (FHead= 0) then
FTail := OldCount else begin
j := FList.Count;
for i := pred(OldCount) downto FHead do
begin
dec(j);
FList.List^[j] := FList.List^[i] end;
FHead := j;
end;
end;
function TtdIntDeque.IsEmpty : boolean;
begin
Result := FHead = FTail;
end;
procedure TtdIntDeque.Push(aValue : integer);
begin
if (FHead = 0) then
FHead := FList.Count;
dec(FHead);
FList.List^[FHead] := pointer(aValue);
if (FTail = FHead) then
idGrow;
end;
function TtdIntDeque.Pop : integer;
begin
if FHead = FTail then
idError(tdeDequeIsEmpty, 'Pop');
Result := integer(FList.List^[FHead]);
inc(FHead);
if (FHead = FList.Count) then
FHead := 0;
end;
Алгоритм работает следующим образом. Поставим значение -1 в очередь с двусторонним доступом. Это специальное значение, которое указывает о необходимости выполнить считывание входной строки по одному элементу. Теперь поставим в очередь с двусторонним доступом номер исходного состояния. Установим целочисленное значение равным 0. Это значение будет индексом текущего символа в строке, сопоставление с которой выполняется.
После того, как подготовка закончена, мы входим в цикл. На каждом этапе выполнения цикла выполняется одно и то же действие: выталкивание верхнего значения из очереди. Если этим значением является -1 (как, естественно, это будет вначале), мы увеличиваем индекс текущего символа и извлекаем этот символ из сопоставляемой строки. Снова поставим значение -1 в очередь, чтобы знать, когда нужно выполнить считывание следующего символа. Если это значение не -1, оно должно быть реальным номером состояния. Взглянем на запись состояния в таблице переходов. Если текущий входной символ соответствует шаблону символов этого состояния, значение NextStatel состояния нужно поставить в очередь. Понятно, что если шаблоном символов состояния был е, символ не соответствовал шаблону. В этом случае в очередь с двусторонним доступом мы заталкиваем значение NextStatel, а затем значение NextState2.
Выполнение цикла прекращается, как только очередь с двусторонним доступом оказывается пустой (ни один путь не соответствует входной строке) или при считывании всех символов из сопоставляемой строки (в этом случае очередь содержит набор состояний, достигнутых на момент достижения конца строки, которые можно выталкивать из очереди до тех пор, пока в зависимости от конкретной ситуации не будет найдено или не найдено одно единственное конечное состояние).
Общий результат применения этого алгоритма состоит в том, что в очередь с двусторонним доступом помещается значение "извлечь следующий символ" (-1). "Слева" от него располагается набор состояний, с которым нам по-прежнему необходимо сравнить текущий символ (мы постоянно выталкиваем из очереди эти состояния и помещаем в нее те, которых можно достичь за счет выполнения бесплатного перехода). "Справа" от него находятся состояния, полученные из тех, которые уже соответствуют текущему символу. Переход к ним будет осуществляться сразу после выталкивания значения -1 из очереди и извлечения следующего символа. Как видите, алгоритм одновременно проверяет все пути обхода конечного NFA-автомата.
Подпрограмма сопоставления приведена в листинге 10.15. Она была создана в качестве метода машины обработки регулярных выражений. Ей передается строка, с которой должно быть выполнено сопоставление, и значение индекса. Значение индекса указывает позицию в строке, начиная с которой предположительно должно начинаться совпадение. Это позволяет использовать регулярное выражение для сопоставления с любой частью строки, а не со всей строкой, как делалось в приведенных простых примерах конечных автоматов. Метод будет возвращать значение true, если таблица переходов регулярного выражения соответствует строке, начиная с данной позиции.
Листинг 10.15. Сопоставление подстрок с таблицей переходов
function TtdRegexEngine.rcMatchSubString(const S : string;
StartPosn : integer): boolean;
var
Ch : AnsiChar;
State : integer;
Deque : TtdIntDeque;
StrInx : integer;
begin
{предположить, что сопоставление будет неудачным}
Result := false;
{создать очередь с двусторонним доступом}
Deque := TtdIntDeque.Create(64);
try
{поставить в очередь специальное значение, означающее начало сканирования}
Deque.Enqueue(MustScan);
{поставить в очередь первое состояние}
Deque.Enqueue(FStartState);
{подготовить индекс строки}
StrInx := StartPosn – 1;
{выполнять цикл до тех пор, пока очередь не будет пуста, или пока строка не закончится}
while (StrInx <= length (S)) and not Deque.IsEmpty do
begin {вытолкнуть верхнее состояние из очереди}
State := Deque.Pop;
{вначале выполнить обработку состояния "необходимо выполнить сканирование "}
if (State = MustScan) then begin
{если очередь пуста, вполне вероятно, что задача выполнена, поскольку не осталось никаких состояний для обработки новых символов}
if not Deque.IsEmpty then begin
{если строка не закончилась, нужно извлечь символ и снова поставить в очередь состояние "необходимо выполнить сканирование"}
inc(StrInx);
if (StrInx <= length(S)) then begin
Ch := S[StrInx];
Deque.Enqueue(MustScan);
end;
end;
end
{в противном случае необходимо обработать состояние}
else with PNFAState (FTable [ State ])^ do
begin
case sdMatchType of
mtNone : begin
{для бесплатных переходов необходимо заталкивать в очередь следующие состояния}
Deque.Push(sdNextState2);
Deque.Push(sdNextState1);
end;
mtAnyChar : begin
{для сопоставления с любым символом необходимо поставить в очередь следующее состояние}
Deque.Enqueue(sdNextState1);
end;
mtChar : begin
{для сопоставления с символом необходимо поставить в очередь следующее состояние}
if (Ch = sdChar) then
Deque.Enqueue(sdNextState1);
end;
mtClass : begin
{для сопоставления с символом, входящим в состав класса, необходимо поставить в очередь следующее состояние}
if (Ch in sdClass^ ) then
Deque.Enqueue(sdNextState1);
end;
mtNegClass : begin
{для сопоставления с символом, не входящим в состав класса, необходимо поставить в очередь следующее состояние}
if not (Ch in sdClass^ ) then
Deque.Enqueue(sdNextState1);
end;
mtTerminal : begin
{в случае достижения конечного состояния строка соответствует регулярному выражению, если регулярное выражение не содержало никакого символа привязки или достигнут конец строки}
if (not FAnchorEnd) or (StrInx > length(S)) then begin
Result := true;
Exit;
end;
end;
end;
end;
end;
{достижение этой точки свидетельствует либо о том, что очередь исчерпана, либо о достижении конца строки. В первом случае подстрока не соответствует регулярному выражению, поскольку отсутствуют состояния для сопоставления. Во втором случае необходимо проверить состояния, расположенные слева от очереди, чтобы проверить, не является ли одно из них конечным. Если это так, строка соответствует регулярному выражению, определенному таблицей переходов}
while not Deque.IsEmpty do
begin
State := Deque.Pop;
with PNFAState (FTable [ State ])^ do
begin
case sdMatchType of
mtNone : begin
{для бесплатных переходов необходимо заталкивать в очередь следующие состояния}
Deque.Push(sdNextState2);
Deque.Push(sdNextState1);
end;
mtTerminal : begin
{в случае достижения конечного состояния строка соответствует регулярному выражению, если регулярное выражение не содержало никакого символа привязки или достигнут конец строки}
if (not FAnchorEnd) or (StrInx > length(S)) then begin
Result := true;
Exit;
end;
end;
end; {case}
end;
end;
finally
Deque.Free;
end;
end;
Было бы желательно, чтобы подпрограмму сопоставления можно было бы применять не только к любой начальной позиции строки, но, при необходимости, и только ко всей строке.
Поэтому представим два новых символа операций регулярных выражений: символы операций привязки "^" и "$". Знак вставки "^" означает, что любое соответствие должно иметь место только с начала строки. Знак доллара "$" означает, что совпадение должно происходить на всем пути до самого конца строки. Так, например, регулярное выражение "^function" означает "совпадение со словом function с начала строки", a "^end.$" означает, что вся строка должна состоять из символов е, n, d и точки. Она не должна содержать никаких других символов. Символы ^ и $ могут присутствовать, соответственно, только в начале и конце регулярного выражения. Они не могут находиться ни в какой другой позиции.
Это обусловливает небольшое изменение определенных нами грамматических правил. Изменение не очень велико, но, как мы видели, корректная формулировка грамматических правил существенно упрощает создание кода. Код реализации нового правила и соответствующего метода синтаксического анализа приведен в листинге 10.16. Естественно, интерфейсный метод Parse также изменен, чтобы вызывать именно его, а не первоначальный метод.
Листинг 10.16. Использование операций привязки
{
function TtdRegexEngine.rcParseAnchorExpr : integer;
begin
{проверить на наличие начального символа '^'}
if (FPosn^ = '^') then begin
FAnchorStart :=true;
inc(FPosn);
end;
{выполнить синтаксический анализ выражения}
Result := rcParseExpr;
{в случае успеха необходимо выполнить проверку на наличие конечного символа '$'}
if (Result <> ErrorState) then begin
if (FPosn^ = '$') then begin
FAnchorEnd := true;
inc(FPosn);
end;
end;
end;
Теперь код выполнения сопоставления строк можно изменить для сопоставления как целых строк, так и подстрок. Если регулярное выражение начинается с символа "А", нужно просто попытаться становить соответствие строки, начиная с первого символа. Если нет, необходимо попытаться установить соответствие с каждой из подстрок, образованных из исходной строки. Код метода MatchString, в котором принимается это решение, приведен в листинге 10.17.
Листинг 10.17. Метод MatchString
function TtdRegexEngine.MatchString(const S : string): integer;
var
i : integer;
ErrorPos : integer;
ErrorCode : TtdRegexError;
begin
{если синтаксический анализ строки регулярного выражения еще не был выполнен, необходимо его выполнить}
if (FTable.Count = 0) then begin
if not Parse (ErrorPos, ErrorCode) then
rcError(tdeRegexParseError, 'MatchString', ErrorPos);
end;
{теперь необходимо выяснить, соответствует ли строка регулярному выражению (сопоставление пустых строк не выполняется)}
Result := 0;
if (S <> '') then
{если указанное регулярное выражение содержит начальный символ привязки, нужно проверить соответствие строки только начиная с первой позиции}
if FAnchorStart then begin
if rcMatchSubString(S, 1) then
Result := 1;
end
{в противном случае необходимо проверить соответствие строки в каждой из позиций и при первом же успешном сопоставлении выполнить возврат}
else begin
for i := 1 to length(S) do
if rcMatchSubString (S, i) then begin
Result := i;
Break;
end;
end;
end;
Если вы еще раз внимательно просмотрите листинг 10.15, то увидите, что код сопоставления уже обеспечивает применение конечного символа привязки. Код воспринимает конечное состояние в качестве признака соответствия регулярному выражению, если регулярное выражение не содержало конечного символа привязки, или же в случае достижения конца строки. При невыполнении любого из этих условий, конечное состояние будет игнорироваться..
Полный исходный код класса TtdRegexEngine можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDRegex.pas.
Резюме
В этой главе мы рассмотрели как детерминированные (DFA), так и недетерминированные (NFA) конечные автоматы. При этом мы исследовали несколько простых примеров DFA-автоматов.
Мы установили также, что при кодировании вручную конечные DFA-автоматы проще определить, понять и создать соответствующий код, в то время как конечные NFA-автоматы больше подходят для автоматических процессов. В заключение мы реализовали полную машину обработки регулярных выражений, которая выполняет синтаксический анализ и компиляцию регулярного выражения в конечный NFA-автомат (представленный таблицей переходов). Этот конечный NFA-автомат может использоваться для сопоставления строк.
Глава 11. Сжатие данных.
Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных. Заботу об этом – отображении списка клиентов, воспроизведении компакт-диска, печати письма – берет на себя программа, манипулирующая данными.
Представление данных
Рассмотрим двойственность природы данных: с одной стороны, содержимое информации, а с другой – ее физическое представление. В 1950 году Клод Шеннон (Claude Shannon) заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных (термин был заимствован из термодинамики). Шеннон установил также, что обычно количество бит в физическом представлении данных превышает значение, определяемое их энтропией.
В качестве простого примера рассмотрим исследование понятия вероятности с помощью монеты. Можно было бы подбросить монету множество раз, построить большую таблицу результатов, а затем выполнить определенный статистический анализ этого большого набора данных с целью формулирования или доказательства какой-то теоремы. Для построения набора данных, результаты подбрасывания монеты можно было бы записывать несколькими различными способами: можно было бы записывать слова "орел" или "решка"; можно было бы записывать буквы "О" или "Р"; или же можно было бы записывать единственный бит (например "да" или "нет", в зависимости от того, на какую сторону падает монета). Согласно теории информации, результат каждого подбрасывания монеты можно закодировать единственным битом, поэтому последний приведенный вариант был бы наиболее эффективным с точки зрения объема памяти, необходимого для кодирования результатов. С этой точки зрения первый вариант является наиболее расточительным, поскольку для записи результата единственного подбрасывания монеты требовалось бы четыре или пять символов.
Однако посмотрим на это под другим углом: во всех приведенных примерах записи данных мы сохраняем одни и те же результаты – одну и ту же информацию – используя все меньший и меньший объем памяти. Другими словами, мы выполняем сжатие данных.
Сжатие данных
Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных. Заботу об этом – отображении списка клиентов, воспроизведении компакт-диска, печати письма – берет на себя программа, манипулирующая данными.
Представление данных
Рассмотрим двойственность природы данных: с одной стороны, содержимое информации, а с другой – ее физическое представление. В 1950 году Клод Шеннон (Claude Shannon) заложил основы теории информации, в том числе идею о том, что данные могут быть представлены определенным минимальным количеством битов. Эта величина получила название энтропии данных (термин был заимствован из термодинамики). Шеннон установил также, что обычно количество бит в физическом представлении данных превышает значение, определяемое их энтропией.
В качестве простого примера рассмотрим исследование понятия вероятности с помощью монеты. Можно было бы подбросить монету множество раз, построить большую таблицу результатов, а затем выполнить определенный статистический анализ этого большого набора данных с целью формулирования или доказательства какой-то теоремы. Для построения набора данных, результаты подбрасывания монеты можно было бы записывать несколькими различными способами: можно было бы записывать слова "орел" или "решка"; можно было бы записывать буквы "О" или "Р"; или же можно было бы записывать единственный бит (например "да" или "нет", в зависимости от того, на какую сторону падает монета). Согласно теории информации, результат каждого подбрасывания монеты можно закодировать единственным битом, поэтому последний приведенный вариант был бы наиболее эффективным с точки зрения объема памяти, необходимого для кодирования результатов. С этой точки зрения первый вариант является наиболее расточительным, поскольку для записи результата единственного подбрасывания монеты требовалось бы четыре или пять символов.
Однако посмотрим на это под другим углом: во всех приведенных примерах записи данных мы сохраняем одни и те же результаты – одну и ту же информацию – используя все меньший и меньший объем памяти. Другими словами, мы выполняем сжатие данных.
Сжатие данных
Сжатие данных (data compression) – это алгоритм эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее. Мы избавляемся от избыточности (redundancy), т.е. удаляем из физического представления данных те биты, которые в действительности не требуются, оставляя только то количество битов, которое необходимо для представления информации в соответствии со значением энтропии. Существует показатель эффективности сжатия данных: коэффициент сжатия (compression ratio). Он вычисляется путем вычитания из единицы частного от деления размера сжатых данных на размер исходных данных и обычно выражается в процентах. Например, если размер сжатых данных равен 1000 бит, а несжатых – 4000 бит, коэффициент сжатия составит 75%, т.е. мы избавились от трех четвертей исходного количества битов.
Конечно, сжатые данные могут быть записаны в форме недоступной для непосредственного считывания и понимания человеком. Люди нуждаются в определенной избыточности представления данных, способствующей их эффективному распознаванию и пониманию. Применительно к эксперименту с подбрасыванием монеты последовательности символов "О" и "Р" обладают большей наглядностью, чем 8-битовые значения байтов. (Возможно, что для большей наглядности пришлось бы разбить последовательности символов "О" и "Р" на группы, скажем, по 10 символов в каждой.) Иначе говоря, возможность выполнения сжатия данных бесполезна, если отсутствует возможность их последующего восстановления. Эту обратную операцию называют декодированием (decoding).
Типы сжатия
Существует два основных типа сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие без потерь проще для понимания. Это метод сжатия данных, когда при восстановлении данных возвращается точная копия исходных данных. Такой тип сжатия используется программой PKZIB"1: распаковка упакованного файла приводит к созданию файла, который имеет в точности то же содержимое, что и оригинал перед его сжатием. И напротив, сжатие с потерями не позволяет при восстановлении получить те же исходные данные. Это кажется недостатком, но для определенных типов данных, таких как данные изображений и звука, различие между восстановленными и исходными данными не имеет особого значения: наши зрение и слух не в состоянии уловить образовавшиеся различия. В общем случае алгоритмы сжатия с потерями обеспечивают более эффективное сжатие, чем алгоритмы сжатия без потерь (в противном случае их не стоило бы использовать вообще). Для примера можно сравнить предназначенный для хранения изображений формат с потерями JPEG с форматом без потерь GIF. Множество форматов потокового аудио и видео, используемых в Internet для загрузки мультимедиа-материалов, являются алгоритмами сжатия с потерями.
