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

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} ) еще не закончил обновление, но операционная система отключилась от него.