Алгоритмы и структуры данных

j := j-1;

until (j < 1) or (Wrd[j] <> Txt[i+j-1]); if j >= 1 then

i := i + (j + Shift[Txt[i+j-1]] - M);    {Сдвиг слова вправо} until (j < 1) or (i > N-M+1);    {Оценка результатов поиска} if j < 1 then begin

BMTxtSearch := true;

Position := i; end else begin

 

BMTxtSearch := false; end; end;

Почти всегда, кроме специально построенных примеров, данный алгоритм требует значительно меньше O(N) сравнений. В самых же благоприятных обстоятельствах, когда последний символ слова всегда попадает на несовпадающий символ текста, число сравнений пропорционально O(N/M).

Авторы алгоритма приводят и несколько соображений по поводу дальнейших усовершенствований алгоритма. Одно из них - объединить приведенную только что стратегию, обеспечивающую большие сдвиги в случае несовпадения, со стратегией Кнута, Морриса и Прат-та, допускающей «ощутимые» сдвиги при обнаружении совпадения (частичного). Такой метод требует двух таблиц, получаемых при пред-трансляции: Shift' - только что упомянутая таблица, а Shift'' - таблица, соответствующая КМП-алгоритму. Из двух сдвигов выбирается больший. Дальнейшее обсуждение этого предмета приводить не будем, поскольку дополнительное усложнение формирования таблиц и самого поиска, возможно, не оправдает видимого выигрыша в производительности. Фактические дополнительные расходы будут высокими и неизвестно, приведут ли все эти ухищрения к выигрышу или проигрышу.

2.4. Алгоритмы кодирования (сжатия) данных

 

2.4.1. Основные виды сжатия

Сжатие сокращает объем пространства, требуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установленной ширины пропускания. Это есть форма кодирования. Другими целями кодирования являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию - он увеличивает избыточность данных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифрованию, что затрудняет поиск шифра доступным для взломщика статистическим методом.

В этом подразделе рассматривается обратимое сжатие или сжатие без наличия помех, где первоначальный текст может быть в точнос-

125 ти восстановлен из сжатого состояния. Необратимое или ущербное сжатие используется для цифровой записи аналоговых сигналов, таких как человеческая речь или рисунки. Обратимое сжатие особенно важно для текстов, записанных на естественных и на искусственных языках, поскольку в этом случае ошибки обычно недопустимы. Хотя первоочередной областью применения рассматриваемых методов есть сжатие текстов, однако, эта техника может найти применение и в других случаях, включая обратимое кодирование последовательностей дискретных данных.

Существует много веских причин осуществлять сжатие данных, так как более быстрая передача данных и сокращение пространства для их хранения позволяют сберечь значительные средства и зачастую улучшить показатели ЭВМ. Сжатие, вероятно, будет оставаться в сфере внимания из-за все возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того, его можно использовать для преодоления некоторых физических ограничений, таких как, например, сравнительно низкая ширина пропускания телефонных каналов.

Существуют два основных способа проведения сжатия: статистический и словарный. Лучшие статистические методы применяют кодирование Хаффмана, лучшие словарные - метод Зива-Лемпела. В статистическом сжатии каждому символу присваивается код, основанный на вероятности его появления в тексте. Высоковероятные символы получают короткие коды, и наоборот. В словарном методе группы последовательных символов или «фраз» заменяются кодом. Замененная фраза может быть найдена в некотором «словаре». Только в последнее время было показано, что любая практическая схема словарного сжатия может быть сведена к соответствующей статистической схеме сжатия, и найден общий алгоритм преобразования словарного метода в статистический. Поэтому при поиске лучшего сжатия статистическое кодирование обещает быть наиболее плодотворным, хотя словарные методы и привлекательны своей быстротой.

Далее более подробно рассмотрим кодирование Хаффмана.

2.4.2. Метод Хаффмана. Оптимальные префиксные коды

В этом методе при сжатии данных, как уже говорилось выше, каждому символу присваивается оптимальный префиксный код, основанный на вероятности его появления в тексте.

Префиксные коды - это коды, в которых никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Префикс, применительно к цепочке а - это какая-либо строка b, где а - конкатенация bc для некоторой цепочки c.

Оптимальный префиксный код - это префиксный код, имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа:

1. определение вероятности появления символов в файле;
2. нахождение оптимального префиксного кода.

На первом этапе необходимо прочитать файл полностью и подсчитать вероятности появления символов в файле (иногда подсчитывают, сколько раз встречается каждый символ). Если при этом учитываются все 256 символов, то не будет разницы в сжатии текстового или файла иного формата.

Далее находятся два символа а и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x, который имеет вероятность появления, равную сумме вероятностей появления символов а и b. Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы а и b заменены одним символом x). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 или 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа а будет соответствовать коду x с добавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

Можно рассматривать префиксные коды как пути в двоичном дереве: прохождение от узла к его левому потомку соответствует 0 в коде, а к правому потомку - 1. Если пометить листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.

2.4.3. Кодовые деревья

Рассмотрим реализацию алгоритма Хаффмана с использованием кодовых деревьев.

Кодовое дерево - это бинарное дерево, у которого: - листья помечены символами, для которых разрабатывается кодировка;

- узлы (в том числе корень) помечены суммой вероятностей появления всех символов, соответствующих листьям поддерева, корнем которого является соответствующий узел.

Существует два подхода к построению кодового дерева: от корня к листьям и от листьев к корню. Рассмотрим первый подход в виде процедуры Паскаля. Входными параметрами этой процедуры являются массив используемых символов, отсортированный в порядке убывания вероятности появления символов (вначале идут символы с максимальными вероятностями, а в конце - с минимальными), а также указатель на создаваемое кодовое дерево, описание которого идентично описанию бинарного дерева в виде списков (см. 1.3.4.4), за исключением того, что поле Data здесь принимает символьный тип.

procedure CreateCodeTable(UseSimbol:  TUseSimbol;

var CodeTree: PTree); {Процедура создания кодового дерева по методу Хаффмана} var

Current: PTree; SimbolCount: integer; begin

{Создаем корень кодового дерева}

new(CodeTree);

Current := CodeTree;

CurrentA.Left := nil; CurrentA.Right := nil;

SimbolCount := 1;

{Создаем остальные вершины}

while SimbolCount <= n-1 do begin

{Создаем лист с символом в виде левого потомка}

new(CurrentA.Left);

CurrentA.LeftA.Data := UseSimbol[SimbolCount]; CurrentA.LeftA.Left := nil; CurrentA.LeftA.Right := nil; {Создаем следующий узел в виде правого потомка} new(CurrentA.Right); Current := CurrentA.Right;

CurrentA.Left := nil; CurrentA.Right := nil; SimbolCount := SimbolCount + 1; end;

{Последний узел превращаем в лист с символом} CurrentA.Data := UseSimbol[SimbolCount]; end;

Созданное кодовое дерево может быть использовано для кодирования и декодирования текста. Как осуществляется кодирование уже говорилось выше. Теперь рассмотрим процесс декодирования. Алгоритм распаковки кода можно сформулировать следующим образом:

procedure DecodeHuffman(CodeTree:  PTree; var ResultStr: string);

{Процедура декодирования по методу Хаффмана из некоторой битовой}

{последовательности в результирующую строку ResultStr}

var

Current: PTree; {Указатель в дереве}

CurrentBit, {Значение текущего бита кода}

CurrentSimbol: integer;{Индекс распаковываемого символа} 
FlagOfEnd: boolean; {Флаг конца битовой последовательности}

begin

{Начальная инициализация}

FlagOfEnd := false; CurrentSimbol := 1; Current := CodeTree; {Пока не закончилась битовая последовательность} while not FlagOfEnd do begin

{Пока не пришли в лист дерева}

while (CurrentA.Left <> nil) and (CurrentA.Right <> nil) and

 

not FlagOfEnd do begin {Читаем значение очередного бита} CurrentBit := ReadBynary(FlagOfEnd); {Бит - 0, то идем налево, бит - 1, то направо} if CurrentBit = 0 then Current := CurrentA.Left

else Current := CurrentA.Right;

end;

{Пришли в лист и формируем очередной символ} ResultStr[CurrentSimbol]   := CurrentA.Data; CurrentSimbol := CurrentSimbol + 1; Current := CodeTree; end; end;

В приведенном алгоритме используется функция ReadBinary, которая читает битовую последовательность и возвращает целое значение 0, если текущий бит равен 0 и возвращает 1, если бит равен 1. Кроме того, она формирует флаг конца битовой последовательности: он принимает значение true, если последовательность исчерпана.

Для осуществления распаковки необходимо иметь кодовое дерево, которое приходится хранить вместе со сжатыми данными. Это приводит к некоторому незначительному увеличению объема сжатых данных. Используются самые различные форматы, в которых хранят это дерево. Здесь следует отметить, что узлы кодового дерева являются пустыми. Иногда хранят не само дерево, а исходные данные для его формирования, т. е. сведения о вероятностях появления символов (или их количествах). При этом процесс декодирования предваряется построением нового кодового дерева, которое будет таким же, как и при кодировании.

 

2.5. Алгоритмы сортировки

2.5.1. Основные виды сортировки

Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, >, <, =. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию. В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются рядом друг с другом в любом порядке. Хотя иногда, бывает полезно сохранить первоначальный порядок элементов с одинаковыми значениями.

130

Алгоритмы сортировки имеют большое практическое применение. Их можно встретить почти везде, где речь идет об обработке и хранении больших объемов информации. Некоторые задачи обработки данных решаются проще, если данные упорядочены.

Традиционно различают внутреннюю сортировку, в которой предполагается, что данные находятся в оперативной памяти, и важно оптимизировать число действий программы (для методов, основанных на сравнении, число сравнений, обменов элементов и пр.), и внешнюю, в которой данные хранятся на внешнем устройстве с медленным доступом (диск, лента и т. д.) и, прежде всего, надо снизить число обращений к этому устройству.

2.5.2. Алгоритмы внутренней сортировки

При дальнейшем рассмотрении внутренней сортировки определим, что множество данных, которые упорядочиваются, описывается как массив фиксированной длины:

A: array[1..n]  of ItemType;

Обычно тип ItemType описывает запись с некоторым полем, играющим роль ключа, а сам массив представляет собой таблицу. Так как здесь рассматривается, прежде всего, сам процесс сортировки, то будем считать, что тип ItemType включает только ключ целого типа.

2.5.2.1. Сортировка подсчетом

Суть метода заключается в том, что на каждом шаге подсчитывается, в какую позицию результирующего массива B надо записать очередной элемент исходного массива A (рис. 40). Если некоторый элемент A[i] помещается в результирующий массив в позицию k + 1, то слева от B[k + 1] должны стоять элементы меньшие или равные B[k + 1]. Значит, число k складывается из количества элементов меньших A[i] и, возможно, некоторого числа элементов, равных A[i]. Условимся, что из равных будут учитываться только те элементы, которые в исходном массиве стоят левее A[i]:

procedure NumerSort(n:  integer;

var A: array [1..n] of integer); {Процедура сортировки подсчетом} var

i, j, k: integer;

B: array[1..n] of integer;

begin

for i := 1 to n do begin

{Вычисляем положение элемента в результирующем массиве}

k := 1;

for j  := 1 to n do if (A[j] < A[i]) or

((A[j] = A[i]) and (j < i)) then k := k+1;

{Включаем очередной элемент в результирующий массив}

B[k] := A[i];

end;

for i := 1 to n do A[i] := B[i];

end;

Рис. 40. Сортировка подсчетом

Легко видеть, что этот алгоритм всегда имеет временную сложность, пропорциональную O(n²) (два вложенных цикла, зависящих от n линейно и не зависящих от порядка элементов) и пространственную сложность, пропорциональную O(n) (результирующий массив). Также следует отметить, что данный алгоритм сохраняет порядок элементов с одинаковыми значениями.

2.5.2.2. Сортировка простым включением

В этой сортировке массив делится на две части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива (рис. 41).

Пусть отсортировано начало массива A[1], A[2], A[i-1], а остаток массива A[i], ... , A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый - с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной.

Так как массив из одного элемента можно считать отсортированным, начнем с i = 2.

Выглядит это в виде следующей процедуры:

procedure InsertSort(n:  integer;

var A: array[1..n]  of integer); {Процедура сортировки простым включением} var

i, j, Tmp: integer; begin

for i := 2 to n do begin

{Сохраняем текущий элемент} Tmp := A[i];

{Сдвигаем элементы, большие, чем текущий}

j := i-1;

while  (A[j]  > Tmp)  and (j > 1) do begin A[j+1]   := A[j];

Этот алгоритм также имеет максимальную и среднюю временную сложности, пропорциональные O(n²), но в случае исходно отсортированного