Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

{соответствие отсутствует: необходимо сохранить текущий символ и сдвинуть скользящее окно на один символ}

AddCharToEncodings(aOutStream,

Signature.AsString[1], Encodings);

SlideWin.Advance(1);

end;

{добавить эту сигнатуру в хеш-таблицу}

HashTable.Insert(Signature, Offset);

{извлечь следующую сигнатуру}

SlideWin.GetNextSignature(Signature, Offset);

end;

{если последняя сигнатура содержала не более двух символов, их нужно сохранить как коды литеральных символов}

if (length(Signature.AsString) > 0) then begin

for i := 1 to length (Signature.AsString) do AddCharToEncodings(aOutStream,

Signature.AsString[i], Encodings);

end;

{обеспечить запись заключительных кодов}

if (Encodings.eaCount > 0) then

WriteEncodings(aOutStream, Encodings);

finally SlideWin.Free;

HashTable.Free;

end; {try.. finally}

end;

Подпрограмма

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

Код программы сжатия LZ77 разбит на несколько файлов: TDLZBase.pas содержит несколько общих констант, TDLZHash.pas создает специализированную хеш-таблицу, TDLZSWin - класс скользящего окна, а TDLZCmpr.pas - код выполнения сжатия и восстановления. Все перечисленные файлы можно найти на web-сайте издательства, в разделе материалов.

После того, как мы ознакомились с алгоритмом и кодом реализации сжатия и восстановления LZ77, можно теоретически оценить возможные значения коэффициентов сжатия. Если бы можно было сжать все 10 байтовые строки в файле до 2 байт - иначе говоря, каждый раз получать максимальное соответствие - для каждых 80 байтов файла можно было бы записывать по 17 байт (один байт флага и восемь 2-байтовых кодов). В этом случае коэффициент сжатия равнялся бы 79 процентам. С другой стороны, если бы соответствия в файле вообще не удалось бы найти, для каждых восьми байтов исходного файла в действительности пришлось бы записывать по девять байтов. В этом случае коэффициент сжатия составил бы -13 процентов. В общем случае, как правило, сжатие файлов с применением этого метода позволяет получать коэффициенты сжатия, лежащие между упомянутыми крайними значениями.

Резюме

В этой главе мы провели исследования методов сжатия данных. Мы начали рассмотрение с двух статических алгоритмов кодирования с минимальной избыточностью: кодирования Шеннона-Фано и кодирования Хаффмана. Мы рассмотрели недостатки этих методов - необходимость двукратного считывания входных данных и какого-либо кодирования дерева, чтобы его можно было поставлять со сжатыми данными. Затем мы ознакомились с адаптивным алгоритмом - сжатия с использованием скошенного дерева - позволяющим устранить обе упомянутых проблемы. И в заключение мы рассмотрели сжатие с применением алгоритма \JL11, в котором используется словарь, позволяющий сжимать строки символов, а не отдельные символы. Хотя все четыре рассмотренных алгоритма представляют интерес и сами по себе, для их реализации мы воспользовались рядом более простых алгоритмов и структур данных, которые были описаны в предшествующих главах.

Глава 12. Дополнительные темы.

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

Алгоритм считывания-записи

В многопоточных приложениях 32-разрядной операционной системы Windows приходится решать целый ряд проблем, которые в однопоточных программах просто не возникают. Действительно,

первая проблема, с которой приходится сталкиваться - определение способа запуска и останова потоков. Но в основном она решается на уровне операционной системы: достаточно внимательно прочесть программную документацию операционной системы и правильно применить почерпнутые сведения.

Этот раздел адресован только тем программистам, которые работают в среде 32-разрядной Windows. Delphi I вообще не поддерживает многопоточную обработку, в то время как Kylix и Linux не предоставляют необходимых примитивных объектов синхронизации, с помощью которых можно было бы решить проблему считывания-записи.

Более серьезная проблема - совместное использование данных несколькими потоками, независимо от того, являются ли данные отдельным целочисленным значением или более сложной структурой данных. По существу, приходится решать вопросы параллельного доступа. Если конкретный поток обновляет часть данных, считывание этих данных в это же время другим потоком лишено смысла. В этом случае считывающий поток (обычно называемый программой считывания {reader} ) может получить частично обновленное значение, поскольку обновляющий поток (программа записи {writer} ) еще не закончил обновление, но операционная система отключилась от него.

При наличии двух или более программ записи достаточно скоро могут возникнуть значительные проблемы, если эти программы обновляют одни и те же данные. Однако никакие проблемы параллельного доступа не должны возникать в случае считывания одних и тех же данных несколькими программами считывания.

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

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

Похоже, что в среде 32-разрядной Windows существует множество объектов, обеспечивающих синхронизацию: критический раздел, флаг синхронизации, семафор, событие, но ни один из них не подходит для решения поставленной задачи полностью. Критический раздел и флаг синхронизации подходят больше других, но они не позволят нескольким программам считывания одновременно получать доступ к одним и тем же данным.

Если для работы с многопоточными данными совместного использования применяется класс TList, Delphi 3 и последующие версии языка предоставляет класс TThreadedList. В основном, применяемая в этом классе стратегия синхронизации реализуется следующим образом: каждое обращение к TList защищается критическим разделом или флагом синхронизации. Delphi-версия класса TThreadedList предоставляет метод LockList, который выполняет вход в критический раздел и возвращает внутренний класс TList. Затем поток может свободно использовать этот объект TList до момента своего завершения, после чего подпрограмма потока должна вызвать метод UnLockList для выхода из критического раздела.