Курсовая работа: Delphi. Немного относительно методов упаковки данных

💣 👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Running - Это самый простой из методов упаковки информации . Предположите что Вы имеете строку текста, и в конце строки стоит 40 пробелов. Налицо явная избыточность имеющейся информации. Проблема сжатия этой строки решается очень просто - эти 40 пробелов ( 40 байт ) сжимаются в 3 байта с помощью упаковки их по методу повторяющихся символов (running). Первый байт, стоящий вместо 40 пробелов в сжатой строке, фактически будет явлться пробелом ( последовательность была из пробелов ) . Второй байт - специальный байт "флажка" который указывает что мы должны развернуть предыдущий в строке байт в последовательность при восстановлении строки . Третий байт - байт счета ( в нашем случае это будет 40 ). Как Вы сами можете видеть, достаточно чтобы любой раз, когда мы имеем последовательность из более 3-х одинаковых символов, заменять их выше описанной последовательностью , чтобы на выходе получить блок информации меньший по размеру, но допускающий восстановление информации в исходном виде.
Оставляя все сказанное выше истинным , добавлю лишь то, что в данном методе основной проблемой является выбор того самого байта "флажка", так как в реальных блоках информации как правило используются все 256 вариантов байта и нет возможности иметь 257 вариант - "флажок". На первый взгляд эта проблема кажется неразрешимой , но к ней есть ключик , который Вы найдете прочитав о кодировании с помощью алгоритма Хаффмана ( Huffman ).
LZW - История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом ( J. Ziv ) и А. Лемпелем ( A. Lempel ) статьи в журнале "Информационные теории " под названием " IEEE Trans ". В последствии этот алгоритм был доработан Терри А. Велчем ( Terry A. Welch ) и в окончательном варианте отражен в статье " IEEE Compute " в июне 1984 . В этой статье описывались подробности алгоритма и некоторые общие проблемы с которыми можно
столкнуться при его реализации. Позже этот алгоритм получил название - LZW (Lempel - Ziv - Welch) .
Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку " Объект TSortedCollection порожден от TCollection.". Анализируя эту строку мы можем видеть, что слово "Collection" повторяется дважды. В этом слове 10 символов - 80 бит. И если мы сможем заменить это слово в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничится длинной кодируемой строки в 256 символов, то учитывая байт "флаг" получим, что строка из 80 бит заменяется 8+16+8 = 32 бита. Алгоритм LZW как-бы "обучается" в процессе сжатия файла. Если существуют повторяющиеся строки в файле , то они будут закодированны в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана ( Huffman ) , которому требуется два прохода.
Huffman - Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.
Сжимая файл по алгоритму Хаффмана первое что мы должны сделать - это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.
После подсчета частоты вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и сформировать мнимую компоновку между кодами по убыванию. То есть не меняя местонахождение каждого символа из таблицы в памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней таблицы назовем "узлом". В дальнейшем ( в дереве ) мы будем позже размещать указатели которые будут указывает на этот "узел". Для ясности давайте рассмотрим пример:
Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в
себе . Мы подсчитали вхождение каждого из символов в файл и получили
+-----------------+-----+-----+-----+-----+-----+-----+
+-----------------+-----+-----+-----+-----+-----+-----|
| число вхождений | 10 | 20 | 30 | 5 | 25 | 10 |
+-----------------+-----+-----+-----+-----+-----+-----+
Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа. Разместим таблицу как ниже.
+-----------------+-----+-----+-----+-----+-----+-----+
+-----------------+-----+-----+-----+-----+-----+-----|
| число вхождений | 30 | 25 | 20 | 10 | 10 | 5 |
+-----------------+-----+-----+-----+-----+-----+-----+
Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A. Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A :
Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов :
Рассматриваем таблицу снова для следующих двух символов ( B и E ). Мы продолжаем в этот режим пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу.
Теперь когда наше дерево создано, мы можем кодировать файл . Мы должны всегда начинать из корня ( Root ) . Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу . Код Хаффмана для нашего символа C - 00. Для следующего символа ( А ) у нас получается - лево,право,лево,лево , что выливается в последовательность 0100. Выполнив выше сказанное для всех символов получим
Каждый символ изначально представлялся 8-ю битами ( один байт ), и так как мы уменьшили число битов необходимых для представления каждого символа, мы следовательно уменьшили размер выходного файла . Сжатие складывется следующим образом :
+----------+----------------+-------------------+--------------+
| Частота | первоначально | уплотненные биты | уменьшено на |
+----------+----------------+-------------------+--------------|
| C 30 | 30 x 8 = 240 | 30 x 2 = 60 | 180 |
| A 10 | 10 x 8 = 80 | 10 x 3 = 30 | 50 |
| D 5 | 5 x 8 = 40 | 5 x 4 = 20 | 20 |
| F 10 | 10 x 8 = 80 | 10 x 4 = 40 | 40 |
| B 20 | 20 x 8 = 160 | 20 x 2 = 40 | 120 |
| E 25 | 25 x 8 = 200 | 25 x 2 = 50 | 150 |
+----------+----------------+-------------------+--------------+
Первоначальный размер файла : 100 байт - 800 бит;
Размер сжатого файла : 30 байт - 240 бит;
240 - 30% из 800 , так что мы сжали этот файл на 70%.
Все это довольно хорошо, но неприятность находится в том факте, что для восстановления первоначального файла, мы должны иметь декодирующее дерево, так как деревья будут различны для разных файлов . Следовательно мы должны сохранять дерево вместе с файлом . Это превращается в итоге в увеличение размеров выходного файла .
В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной. Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11 . 4 байта 11 раз - 44 . Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику - наша таблица будет приблизительно 50 байтов длинны. Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт . Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт - мы получили 20% сжатие информации. Не плохо . То что мы действительно выполнили - трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным.
Что мы можем получить на этом пути ?
Рассмотрим максимум которй мы можем получить для различных разрядных комбинацй в оптимальном дереве, которое является несимметричным.
Мы получим что можно иметь только :
Необходимо еще два 8 разрядных кода.
Итак мы имеем итог из 256 различных комбинаций которыми можно кодировать байт. Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта Все эти подсчеты производились для не префиксных кодов Хаффмана т.е. кодов, которые нельзя идентифицировать однозначно. Например код A - 01011 и код B - 0101 . Если мы будем получать эти коды побитно, то получив биты 0101 мы не сможем сказать какой код мы получили A или B , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего.
Необходимо добавить, что ключем к построению префиксных кодов служит обычное бинарное дерево и если внимательно рассмотреть предыдущий пример с построением дерева , можно убедится , что все получаемые коды там префиксные.
Одно последнее примечание - алгоритм Хаффмана требует читать входной файл дважды, один раз считая частоты вхождения символов , другой разпроизводя непосредственно кодирование.
P.S. О "ключике" дающем дорогу алгоритму Running.
---- Прочитав обзорную информацию о Huffman кодировании подумайтенад тем, что на нашем бинарном дереве может быть и 257 листиков.
1) Описание архиватора Narc фирмы Infinity Design Concepts, Inc.;
2) Чарльз Сейтер, 'Сжатие данных', "Мир ПК", N2 1991;
{$A+,B-,D+,E+,F-,G-,I-,L+,N-,O-,R+,S+,V+,X-}
{******************************************************}
{* Алгоритм уплотнения данных по методу *}
{******************************************************}
P0, P1 : PCodElement; {элемент входящий одновременно}
LengthBiteChain : byte; { в массив , очередь и дерево }
TCodeTable = array [0..255] of PCodElement;
LeftRange,RightRange : PCodElement;
LengthOutFile, LengthArcFile : longint;
{-------------------------------------------------}
8 : Writeln('Not enough memory ...');
10 : Writeln('Invalid environment ...');
11 : Writeln('Invalid format ...');
else Writeln('Error #',ErrorByte,' ...');
{ --- открытиефайладляархивации --- }
If NormalWork then Writeln('Pak file : ',ParamStr(3),'...');
{ --- открытие файла архива, или его создание --- }
If Pos('.',St)<>0 then Delete(St,Pos('.',St),4);
If Create then Writeln('Create archiv : ',St,'...')
else Writeln('Open archiv : ',St,'...')
{ --- вдальнейшем - поискименифайлавархиве --- }
{ --- уничтожение кодовой таблицы и очереди --- }
For I:=0 to 255 do Dispose(CodeTable[I]);
{ --- закрытиеархивируемогофайла --- }
If FileSize(OutputF)=0 then Erase(OutputF);
{ --- инициализация таблицы кодировки --- }
If I>0 then CodeTable[I-1]^.NewRight:=CodeTable[I];
If I<255 then CodeTable[I+1]^.NewLeft:=CodeTable[I];
{ --- пузырьковая сортировка по возрастанию --- }
If CurPoint^.CounterEnter > CurPoint^.NewRight^.CounterEnter then
HelpPoint^.NewLeft:=CurPoint^.NewLeft;
If HelpPoint^.NewRight<>Nil then HelpPoint^.NewRight^.NewLeft:=CurPoint;
CurPoint^.NewRight:=HelpPoint^.NewRight;
If HelpPoint^.NewLeft<>Nil then HelpPoint^.NewLeft^.NewRight:=HelpPoint;
If CurPoint=LeftRange then LeftRange:=HelpPoint;
If HelpPoint=RightRange then RightRange:=CurPoint;
If CurPoint = LeftRange then CurPoint:=CurPoint^.NewRight
{ --- подсчетчастотвхожденийбайтоввблоке --- }
Inc(CodeTable[(InBuf[C])]^.CounterEnter);
{ --- поиск в очереди пары открытых по Key минимальных значений --- }
While (not (HelpPoint=RightRange)) and (not HelpPoint^.Key) do
If (HelpPoint=CurPoint) and (HelpPoint<>RightRange) then
If HelpPoint=CurPoint then SearchOpenCode:=False else SearchOpenCode:=True;
{ --- создание дерева частот вхождения --- }
CounterEnter:=P0^.CounterEnter + P1^.CounterEnter;
While (HelpPoint^.CounterEnter < Root^.CounterEnter) and
(HelpPoint<>Nil) do HelpPoint:=HelpPoint^.NewRight;
If HelpPoint=Nil then { добавлениевконец }
If Root^.NewLeft<>Nil then Root^.NewLeft^.NewRight:=Root;
procedure ViewTree( P : PCodElement );
{ --- просмотр дерева частот и присваивание кодировочных цепей листьям --- }
If P^.P0<>Nil then ViewTree( P^.P0 );
If (P^.P0=Nil) and (P^.P1=Nil) then
{ --- обнуление переменных и запуск просмотра дерева с вершины --- }
If (CurPoint^.P0<>Nil) and (CurPoint^.P1<>Nil) then
CurPoint^.NewLeft^.NewRight:=CurPoint^.NewRight;
CurPoint^.NewRight^.NewLeft:=CurPoint^.NewLeft;
If CurPoint=LeftRange then LeftRange:=CurPoint^.NewRight;
If CurPoint=RightRange then RightRange:=CurPoint^.NewLeft;
{ --- записьвбуферзаголовкаархива --- }
Header : ByteField = ( $56, $53, $31, $00, $00, $00, $00 );
{ --- запись в буфер всей информации по файлу --- }
OutBuf[OutCounter]:=byte(Ord(St[I]));
Move(R.Size,OutBuf[OutCounter+1],4);
{ --- сохранить массив частот вхождений в архивном файле --- }
OutBuf[OutCounter]:=Hi(CodeTable[I]^.CounterEnter);
OutBuf[OutCounter]:=Lo(CodeTable[I]^.CounterEnter);
InitCodeTable; { инициализация кодовой таблицы }
CounterNumberEnter; { подсчет числа вхождений байт в блок }
SortQueueByte; { cортировка по возрастанию числа вхождений }
SaveBufHeader; { сохранить заголовок архива в буфере }
SaveBufFATInfo; { сохраняется FAT информация по файлу }
SaveBufCodeArray; { сохранить массив частот вхождений в архивном файле }
CreateTree; { создание дерева частот }
CreateCompressCode; { cоздание кода сжатия }
DeleteTree; { удаление дерева частот }
{ --- сжатие и пересылка в выходной буфер одного байта --- }
Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHR CounterBite;
CounterBite:=CounterBite+CodeTable[InBuf[InCounter]]^.LengthBiteChain;
If CounterBite>15 then Tail:=True else Tail:=False;
If OutCounter=(SizeOf(OutBuf)-4) then
BlockWrite(OutputF,OutBuf,OutCounter,NumWritten);
If CounterBite<>0 then OutWord:=OutWord SHL 8 else OutWord:=0;
Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHL
(CodeTable[InBuf[InCounter]]^.LengthBiteChain-CounterBite);
If (InCounter=(SizeOf(InBuf))) or (InCounter=NumRead) then
BlockRead(InputF,InBuf,SizeOf(InBuf),NumRead);
{ --- процедуранепосредственногосжатияфайла --- }
BlockRead(InputF,InBuf,SizeOf(InBuf),NumRead);
BlockWrite(OutputF,OutBuf,OutCounter,NumWritten);
{ --- открытие файла для распаковки --- }
St[InCounter-7]:=Chr(InBuf[InCounter]);
Move(InBuf[InCounter],TimeUnPakFile,4);
Move(InBuf[InCounter],LengthArcFile,4);
{ --- закрытиефайладляраспаковки --- }
If not NormalWork then Erase(InterF)
{ --- воссозданиекодовойтаблицыпоархивномуфайлу --- }
CodeTable[I]^.CounterEnter:=InBuf[InCounter];
CodeTable[I]^.CounterEnter:=CodeTable[I]^.CounterEnter SHL 8;
CodeTable[I]^.CounterEnter:=CodeTable[I]^.CounterEnter+InBuf[InCounter];
procedure UnPakByte( P : PCodElement );
{ --- распаковка одного байта --- }
If (P^.P0=Nil) and (P^.P1=Nil) then
If OutCounter = (SizeOf(OutBuf)-1) then
BlockWrite(InterF,OutBuf,OutCounter,NumWritten);
If InCounter = (SizeOf(InBuf)) then
BlockRead(OutputF,InBuf,SizeOf(InBuf),NumRead);
Mask:=Mask OR $FF7F; { установкавсехбитовкроместаршего }
If Mask=$FFFF then UnPakByte(P^.P1)
BlockRead(OutputF,InBuf,SizeOf(InBuf),NumRead);
If NormalWork then ResetUnPakFiles;
CreateTree; { создание дерева частот }
While LengthOutFile LengthArcFile do
BlockWrite(InterF,OutBuf,OutCounter,NumWritten);
{ ------------------------- main text ------------------------- }
WriteLn('ArcHaf version 1.0 (c) Copyright VVS Soft Group, 1992.');

Название: Delphi. Немного относительно методов упаковки данных
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа
Добавлен 11:42:58 05 марта 2005 Похожие работы
Просмотров: 112
Комментариев: 15
Оценило: 4 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Курсовая работа: Delphi. Немного относительно методов упаковки данных
Курсовая работа: Современные подходы к пониманию права
Реферат: Традиционная и современная семья
Федерация Реферат
Реферат по теме Латинские заимствования в английском языке
Сочинение Описание Помещения В Деловом Стиле
Реферат: Преферанс во всех видах. Скачать бесплатно и без регистрации
Реферат: Macbeth Fate Or Freewill Essay Research Paper
Курсовая работа: Особенности Американской модели менеджмента
Реферат На Тему Чудеса Света
Курсовая работа по теме Оборудование аудио и видео
Заключение К Курсовой Работе По Патологии Дыхания
Курсовая работа: Организация розничной торговли на примере компании "Oriflame" ("Орифлэйм")
Курсовая работа по теме Решение системы линейных уравнений методом Гаусса и Жордана-Гаусса
Дипломная работа по теме Совершенствование дифференциации оплаты труда в отраслях промышленности (на примере национальной экономики Республики Корея)
Магистрлік Диссертация Құрылымы
Какие Должны Быть Поля В Курсовой
Написать Сочинение По Литературе На Тему
Контрольная работа по теме Факторы, влияющие на экономическую безопасность Республики Татарстан
Готовая Дипломная Работа Скачать
7 Кл Итоговая Контрольная Работа
Курсовая работа: Москва многонациональная: конфликт или согласие?
Реферат: Экономический рост: источники, типы, движущие силы
Реферат: Государственная поддержка инновационной деятельности