Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ LZW
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Проблемно-орієнтовані методи та засоби комп’ютерних інформаційних технологій
Група:
КН-316
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
ЗВІТ
Про виконання лабораторної роботи №3
на тему:
«СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ LZW»
з курсу:
“Проблемно-орієнтовані методи та засоби комп’ютерних
інформаційних технологій”
МЕТА РОБОТИ
Мета роботи - вивчення методу Лемпеля-Зіва-Велча (LZW) для стиснення даних та його програмної реалiзацiї для практичного використання.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Метод LZW.
Відомі методи оптимального кодування різнозначними кодами (кодами різної довжини), які базуються на врахуванні різної частоти символів в тексті. Найбільш відомі з них: метод Шеннона-Фано та метод Хаффмана. Ці методи забезпечують достатньо ефективне стиснення без втрат. Для підвищення рівня стиснення даних доцільно перейти від оптимального кодування окремих символів до кодування буквосполучень. Саме таке кодування забезпечує метод LZW.
Метод базується на побудові таблиці фраз (словника), яка відображає стрічки символів повідомлення, що стискається, в коди фіксованої довжини (12 біт). Таблиця має властивість попередництва, тобто для кожної фрази словника, яка складається з деякої фрази w і символа K, фраза w теж міститься в словнику і представляється відповідним номером n.
Програмна реалізація методу здійснюється за наступним алгоритмом (ілюструється на прикладі кодування фрази МАМАМАЛАЛАМУ з представленням словника у вигляді таблиці:
У словник заносяться односимвольні фрази w, що відповідають символам вхідного алфавіту (ініціація словника).
Біжучий вказівник встановлюється на перший символ тексту (фраза М).
Здійснюється пошук фрази М у словнику (фраза є за номером 1).
Фраза М доповнюється наступним символом А і здійснюється пошук розширеної фрази МА у словнику (фраза відсутня).
Знайдена раніше частина розширеної фрази МА (фраза М) кодується її номером 1, а нова фраза МА заноситься у словник під номером 5 і представляється (у формі nK) кодом 1А.
Після цього, вказівник встановлюється на останній символ А розширеної фрази МА, який розглядається і кодується як нова фраза, аналогічно як у п. 3.
Фраза А є у словнику під номером 2.
Фраза А доповнюється наступним символом М і здійснюється пошук розширеної фрази АМ у словнику (фраза відсутня).
Знайдена частина розширеної фрази АМ (фраза а) кодується її номером 2, а нова фраза АМ заноситься в словник під номером 6 і представляється кодом 2М.
Вказівник встановлюється на останній символ М розширеної фрази АМ, який у свою чергу розглядається і кодується як нова фраза.
Здійснюється пошук фрази М у словнику (фраза є за номером 1).
Фраза М доповнюється наступним символом А і здійснюється пошук розширеної фрази МА у словнику (фраза є за номером 5).
Фраза МА доповнюється наступним символом М і здійснюється пошук розширеної фрази МАМ (фраза відсутня).
Знайдена частина (фраза МА) розширеної фрази МАМ кодується відповідним номером 5, а відсутня фраза МАМ заноситься у словник під номером 7.
Кроки циклічно повторюються до закінчення послідовності кодованих символів.
Результати кодування представлені на рис. 1 і таблицею словника.
М А М А М А Л А Л А М У
1 2 5 5 3 2 9 1 4
Рис 1. Результати кодування послідовності символів.
Таблиця 1
Номер фрази у словнику
Фраза у словнику
Код фрази у словнику
1
М
1
2
А
2
3
Л
3
4
У
4
5
МА
1А
6
АМ
2М
7
МАМ
5М
8
МАЛ
5Л
9
ЛА
3А
10
АЛ
2Л
11
ЛАМ
9М
12
МУ
1У
Декодування тексту здійснюється по таких кроках:
Закодований текст передається чи зберігається разом з проініційованою частиною (алфавітом) словника (перші чотири рядки словника)
Вибирається перший номер коду 1 і заміщається відповідною фразою М із словника.
Вибирається наступний номер коду 2 і заміщається фразою А.
З фраз М і А формується нова фраза у словнику МА і її код 1А (як при кодуванні).
Наступний номер коду 5 має код фрази 1А, що відповідає відновленій фразі МА.
По відомій фразі А та фразі МА формується нова фраза АМ, яка з кодом фрази 2М заноситься у шостий рядок словника.
Фраза МА записується і для наступного коду 5.
Починаючи з останнього символа М нової фрази АМ здійснюється пошук у словнику фрази МА (фраза є під номером 5), а потім нової розширеної фрази МАМ, яка відсутня у словнику і заноситься туди під номером 7, як при кодуванні.
Починаючи з останнього символа М нової фрази МАМ здійснюється пошук фраз М та МА (обидві фрази є).
Дописується фраза Л для коду 3.
З фраз МА та Л формується нова фраза МАЛ, яка відсутня в словнику і записується туди під номером 8.
Починаючи з останнього символа Л (код якого у словнику 3) фрази МАЛ для коду 2 дописується фраза А і формується нова фраза ЛА, яка відсутня в словнику і записується туди під номером 9.
Береться останній символ фрази ЛА і до нього дописується фраза ЛА для коду 9.
Здійснюється формування фрази АЛ , пошук її у словнику і так як фраза відсутная, то відбувається занесення фрази АЛ у словник під номером 10.
З останнього символа фрази АЛ формуються фрази Л та ЛА, які є у словнику.
Для відомого коду 1 записується фраза М і формується фраза ЛАМ, яка відсутня в словнику і заноситься у рядок під номером 11.
Вибирається останній символ М фрази ЛАМ, який є у словнику і до нього по відомому коду 4 дописується фраза У .
Відсутня нова фраза МУ заноситься у словник і на цьому відновлення словника і закодованого і стисненого тексту закінчується.
Текст програми:
PROGRAM bdn_compression_LZW;
Uses Crt;
CONST
MaxStack = 4096;
MaxBuff = 8192;
MaxTab = 4095;
No_Prev = $7FFF;
EOF_Char = -2 ;
End_List = -1 ;
Empty = -3 ;
TYPE
AnyStr = STRING[255] ;
String_Table_Entry = RECORD
Used : BOOLEAN ;
PrevChar : INTEGER ;
FollChar : INTEGER ;
Next : INTEGER ;
END;
VAR
Key : Char;
Stack : array[1..MaxStack] of Integer;
Stack_Pointer : Integer;
Input_File : FILE ;
Output_File : FILE ;
InBufSize : INTEGER;
Input_Buffer : ARRAY[1..MaxBuff] OF BYTE;
Output_Buffer : ARRAY[1..MaxBuff] OF BYTE;
Input_Pos : INTEGER;
Output_Pos : INTEGER;
String_Table : ARRAY[0..MaxTab] OF String_Table_Entry;
Table_Used : INTEGER;
Output_Code : INTEGER;
Input_Code : INTEGER;
If_Compressing : BOOLEAN;
Ierr : INTEGER;
PROCEDURE Terminate;
BEGIN
IF ( Output_Pos > 0 ) THEN
BlockWrite( Output_File, Output_Buffer, Output_Pos );
Ierr := IOResult;
CLOSE( Input_File );
Ierr := IOResult;
CLOSE( Output_File );
Ierr := IOResult;
END;
FUNCTION Get_Hash_Code( PrevC, FollC : INTEGER ) : INTEGER;
VAR
Index : INTEGER;
Index2 : INTEGER;
BEGIN
Index := ( ( PrevC SHL 5 ) XOR FollC ) AND MaxTab;
IF ( NOT String_Table[Index].Used ) THEN
Get_Hash_Code := Index
ELSE
BEGIN
WHILE ( String_Table[Index].Next <> End_List ) DO
Index := String_Table[Index].Next;
Index2 := ( Index + 101 ) AND MaxTab;
WHILE ( String_Table[Index2].Used ) DO
Index2 := SUCC( Index2 ) AND MaxTab;
String_Table[Index].Next := Index2;
Get_Hash_Code := Index2;
END;
END ;
PROCEDURE Make_Table_Entry( PrevC, FollC: INTEGER );
BEGIN
IF ( Table_Used <= MaxTab ) THEN
BEGIN
WITH String_Table[ Get_Hash_Code( PrevC , FollC ) ] DO
BEGIN
Used := TRUE;
Next := End_List;
PrevChar := PrevC;
FollChar := FollC;
END;
INC( Table_Used );
END;
END;
PROCEDURE Initialize_String_Table;
VAR
I: INTEGER;
BEGIN
Table_Used := 0;
FOR I := 0 TO MaxTab DO
WITH String_Table[I] DO
BEGIN
PrevChar := No_Prev;
FollChar := No_Prev;
Next := -1;
Used := FALSE;
END;
FOR I := 0 TO 255 DO
Make_Table_Entry( No_Prev , I );
END;
PROCEDURE Initialize;
VAR
Input_Name : AnyStr;
Output_Name : AnyStr;
BEGIN
IF ( ParamCount > 0 ) THEN
Input_Name := ParamStr( 1 )
ELSE
BEGIN
CASE If_Compressing OF
TRUE: WRITE('Enter the name of file to COMPRESS : ');
FALSE: WRITE('Enter the name of file to DECOMPRESS : ');
END ;
READLN( Input_Name );
Ierr := IOResult;
END;
ASSIGN ( Input_File , Input_Name );
RESET ( Input_File , 1 );
Ierr := IOResult;
IF ( ParamCount > 1 ) THEN
Output_Name := ParamStr( 2 )
ELSE
BEGIN
CASE If_Compressing OF
TRUE: WRITE('Enter name of new PACKed file : ');
FALSE: WRITE('Enter name of new UnPACKed file : ');
END;
READLN( Output_Name );
Ierr := IOResult;
END;
ASSIGN ( Output_File , Output_Name );
REWRITE( Output_File , 1 );
Ierr := IOResult;
Input_Pos := MaxBuff + 1;
Output_Pos := 0;
InBufSize := 0;
Output_Code := Empty;
Input_Code := Empty;
Initialize_String_Table;
END;
FUNCTION Lookup_String( PrevC, FollC: INTEGER ) : INTEGER;
VAR
Index : INTEGER;
Index2 : INTEGER;
Found : BOOLEAN;
BEGIN
Index := ( ( PrevC SHL 5 ) XOR FollC ) AND MaxTab;
Lookup_String := End_List;
REPEAT
Found := ( String_Table[Index].PrevChar = PrevC ) AND
( String_Table[Index].FollChar = FollC );
IF ( NOT Found ) THEN
Index := String_Table[Index].Next;
UNTIL Found OR ( Index = End_List );
IF Found THEN
Lookup_String := Index;
END;
PROCEDURE Get_Char( VAR C: INTEGER );
BEGIN
INC( Input_Pos );
IF ( Input_Pos > InBufSize ) THEN
BEGIN
BlockRead( Input_File, Input_Buffer, MaxBuff, InBufSize );
Input_Pos := 1;
Ierr := IOResult;
END;
IF ( InBufSize = 0 ) THEN
C := EOF_Char
ELSE
C := Input_Buffer[Input_Pos];
END ;
PROCEDURE Put_Char( C : INTEGER );
BEGIN
IF ( Output_Pos >= MaxBuff ) THEN
BEGIN
BlockWrite( Output_File, Output_Buffer, MaxBuff );
Output_Pos := 0;
Ierr := IOResult;
END;
INC( Output_Pos );
Output_Buffer[Output_Pos] := C;
END;
PROCEDURE Put_Code( Hash_Code : INTEGER );
BEGIN
IF ( Output_Code = Empty ) THEN
BEGIN
Put_Char( ( Hash_Code SHR 4 ) AND $FF );
Output_Code := Hash_Code AND $0F;
END
ELSE
BEGIN
Put_Char( ( ( Output_Code SHL 4 ) AND $FF0 ) +
( ( Hash_Code SHR 8 ) AND $00F ) ) ;
Put_Char( Hash_Code AND $FF );
Output_Code := Empty;
END;
END ;
PROCEDURE Do_Compression;
VAR
C : INTEGER;
WC : INTEGER;
W : INTEGER;
BEGIN
Get_Char( C );
W := Lookup_String( No_Prev , C );
Get_Char( C );
WHILE( C <> EOF_Char ) DO
BEGIN
WC := Lookup_String( W , C );
IF ( WC = End_List ) THEN
BEGIN
Make_Table_Entry( W , C );
Put_Code( W );
W := Lookup_String( No_Prev , C );
END
ELSE
W := WC;
Get_Char( C );
END;
Put_Code( W );
END;
PROCEDURE Push( C : INTEGER );
BEGIN
INC( Stack_Pointer );
Stack[ Stack_Pointer ] := C;
IF ( Stack_Pointer >= MaxStack ) THEN
BEGIN
WRITELN('Stack overflow!');
Terminate;
Halt;
END;
END ;
PROCEDURE Pop( VAR C : INTEGER );
BEGIN
IF ( Stack_Pointer > 0 ) THEN
BEGIN
C := Stack[Stack_Pointer];
DEC( Stack_Pointer );
END
ELSE
C := Empty;
END;
PROCEDURE Get_Code( VAR Hash_Code : INTEGER );
VAR
Local_Buf : INTEGER;
BEGIN
IF ( Input_Code = Empty ) THEN
BEGIN
Get_Char( Local_Buf );
IF ( Local_Buf = EOF_Char ) THEN
BEGIN
Hash_Code := EOF_Char;
EXIT;
END;
Get_Char( Input_Code );
IF ( Input_Code = EOF_Char ) THEN
BEGIN
Hash_Code := EOF_Char;
EXIT;
END;
Hash_Code := ( ( Local_Buf SHL 4 ) AND $FF0 ) +
( ( Input_Code SHR 4 ) AND $00F );
Input_Code := Input_Code AND $0F;
END
ELSE
BEGIN
Get_Char( Local_Buf );
IF ( Local_Buf = EOF_Char ) THEN
BEGIN
Hash_Code := EOF_Char;
EXIT;
END;
Hash_Code := Local_Buf + ( ( Input_Code SHL 8 ) AND $F00 );
Input_Code := Empty;
END;
END;
PROCEDURE Do_Decompression;
VAR
C : INTEGER;
Code : INTEGER;
Old_Code : INTEGER;
Fin_Char : INTEGER;
In_Code: INTEGER;
Last_Char: INTEGER;
Unknown : BOOLEAN;
Temp_C: INTEGER;
BEGIN
Stack_Pointer := 0;
Unknown := FALSE;
Get_Code( Old_Code );
Code := Old_Code;
C := String_Table[Code].FollChar;
Put_Char( C );
Fin_Char := C;
Get_Code( In_Code );
WHILE( In_Code <> EOF_Char ) DO
BEGIN
Code := In_Code;
IF ( NOT String_Table[Code].Used ) THEN
BEGIN
Last_Char := Fin_Char;
Code := Old_Code;
Unknown := TRUE;
END;
WHILE( String_Table[Code].PrevChar <> No_Prev ) DO
WITH String_Table[Code] DO
BEGIN
Push( FollChar );
Code := PrevChar;
END;
Fin_Char := String_Table[Code].FollChar;
Put_Char( Fin_Char );
Pop( Temp_C );
WHILE( Temp_C <> Empty ) DO
BEGIN
Put_Char( Temp_C );
Pop( Temp_C );
END;
IF Unknown THEN
BEGIN
Fin_Char := Last_Char;
Put_Char( Fin_Char );
Unknown := FALSE;
END;
Make_Table_Entry( Old_Code , Fin_Char );
Old_Code := In_Code;
Get_Code( In_Code );
END;
END;
BEGIN
ClrScr;
Writeln('COMPRESS - 1');
Writeln('DECOMPRESS - 2');
Key:=ReadKey;
IF Key='1' THEN
begin
If_Compressing := TRUE;
Initialize;
Do_Compression;
Terminate;
END
ELSE
IF Key='2' THEN
Begin
If_Compressing := FALSE;
Initialize;
Do_Decompression;
Terminate;
End;
END.
Висновок: на даній лабораторній роботі я вивчив метод Лемпеля-Зіва-Велча (LZW) для стиснення даних та написав програму на мові програмування PASCAL, яка стискає та відновлює дані за цим методом.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора