Алгоритм LZSS
Идея этого алгоритма основана на том предположении, что входящие в сжимаемый
текст слова неоднократно повторяются. Сжатие достигается заменой обнаруженных
повторов ссылками на предшествующие вхождения этих же слов. Т.е. повторное
вхождение слова заменяется парой чисел <Длина слова, Расстояние до предыдущего
вхождения слова>. Под словом понимается не слово естественного языка,
а произвольная последовательность символов.
Пример. Последнее предложение
Под словом понимается не_слово естественного языка,
а произвольная_последовательность символов.
может кодироваться так:
Под словом понимается не<6,21> ест<3,3>венного языка, а
произвольная<3,56>следовате<3,17>ость сим<3,30>ов.
Всего восемнадцать символов удалось заменить кодами. Не очень много,
но при сжатии большого текста результат может быть гораздо лучше.
Способ записи архива следующий:
- Если записывается несжатая строка - 0..01 <символы строки>
(длина строки равна числу нулей)
- Если записывается ссылка - 1NNNNNSSSSSSSSSSSSSS
(NNNNN - длина строки, SSSSSSSSSSSSSS - расстояние до предыдущего
входения)
Это не лучший способ, но он лучше чем запись ссылки в три байта и префикса
длиной в один байт перед несжатой строкой.
Программная состоит из четырех функций - Encode (выполняет кодирование), Decode
(выполняет декодирование), Save и Load (побитовые запись и чтение архива). Вот
как выглядит функция Encode:
<![CDATA[
byte Txt [TXT_LEN]; // Текст
word nTxt;
word pTxt;
byte Arc [ARC_LEN]; // Архив
word nArc;
word pArc;
void Save(word C; word N); // запись N бит
void Encode(word hArc, hTxt)
word pChr;
nTxt=0;
pTxt=0;
pChr=0;
pArc=0;
while TRUE do // цикл просмотра текста
if pArc>=BLK_LEN then // запись в архив
write(hArc,@Arc,BLK_LEN);
puts (".");
word I=BLK_LEN;
word J=0;
while I<pArc do
Arc[J]=Arc[I];
inc J;
inc I;
end
pArc=J;
end
if pTxt>=FRM_LEN+BLK_LEN then // сдвиг окна
word I=BLK_LEN;
word J=0;
while I<nTxt do
Txt[J]=Txt[I];
inc J;
inc I;
end
nTxt=nTxt-BLK_LEN;
pTxt=pTxt-BLK_LEN;
pChr=pChr-BLK_LEN;
end
if pTxt+STR_LEN>=nTxt then
nTxt=nTxt+read(hTxt,@Txt[nTxt],BLK_LEN);
end
if pTxt>=nTxt then
exit
end
int I=pTxt-(FRM_LEN+(OFS_MIN-1));
if I<0 then
I=0;
end
int S=0;
int L=0;
while I+OFS_MIN<=pTxt do // поиск повторяющихся строк
int J=0;
while TRUE do // J<STR_LEN & I+J<pTxt & pTxt+J<nTxt do
if Txt[I+J]!=Txt[pTxt+J] then
exit
end
if J>=STR_LEN then
exit
end
if I+J>=pTxt then
exit
end
if pTxt+J>=nTxt then
exit
end
inc J;
end
if L<=J then
S=I;
L=J;
end
inc I;
end
if pChr<pTxt then
if L>2 | pTxt-pChr>=END_LEN then
int N=0;
while N<pTxt-pChr do
Save(0,1);
inc N;
end
Save(1,1);
while pChr<pTxt do
Save(Txt[pChr],8);
inc pChr;
end
end
end
if L>2 then // запись ссылки
S=pTxt-S;
Save(1,1);
Save(L-PAK_MIN,PAK_LEN);
Save(S-OFS_MIN,OFS_LEN);
pTxt=pTxt+L;
pChr=pTxt;
loop
end
inc pTxt;
end
if pChr<pTxt then
int N=0;
while N<pTxt-pChr do
Save(0,1);
inc N;
end
Save(1,1);
while pChr<pTxt do
Save(Txt[pChr],8);
inc pChr;
end
end
if pTmp<15 then // нужно для корректного завершения
Save(0,16);
end
if pArc>0 then
write(hArc,@Arc,pArc);
end
end
]]>
Извлечение данных из архива выполняется функцией Decode.
Этот алгоритм обеспечивает приемлемое сжатие (примерно в 1.1-1.5 раза хуже,
чем lha), а вот его быстродействие неприемлемо абсолютно. Для демонстрации
идеи это не важно, для практического использования алгоритм должен быть
усовершенствован. Значительно повысить быстродействие можно заменив поиск
перебором индексным поиском. Степень сжатия можно несколько повысить, например,
применив к полученным кодам алгоритм Хаффмана.
В заключение - полный текст программы. Содержательная часть начинается с первого
define:
<![CDATA[
struct Addr
word Ofs;
word Seg;
section
void @Ptr;
end
void @Ptr(word Seg,Ofs)
Addr P;
P.Seg=Seg;
P.Ofs=Ofs;
return @P.Ptr;
end
word GetPSP()
asm mov AH,62H
asm int 21H
asm mov AX,BX
end
word create(char @Name)
asm push DS
asm mov AH,3CH
asm mov CX,00H
asm mov DX,SS:[BP+6]
asm mov DS,DX
asm mov DX,SS:[BP+4]
asm int 21H
asm pop DS
end
word open(char @Name)
asm push DS
asm mov AH,3DH
asm mov AL,00H
asm mov DX,SS:[BP+6]
asm mov DS,DX
asm mov DX,SS:[BP+4]
asm int 21H
asm pop DS
end
word read(word F; void @Buff; word N)
asm push DS
asm mov AH,3FH
asm mov BX,SS:[BP+10]
asm mov CX,SS:[BP+4]
asm mov DX,SS:[BP+8]
asm mov DS,DX
asm mov DX,SS:[BP+6]
asm int 21H
asm pop DS
end
word write(word F; void @Buff; word N)
asm push DS
asm mov AH,40H
asm mov BX,SS:[BP+10]
asm mov CX,SS:[BP+4]
asm mov DX,SS:[BP+8]
asm mov DS,DX
asm mov DX,SS:[BP+6]
asm int 21H
asm pop DS
end
void close(word F)
asm mov AH,3EH
asm mov BX,SS:[BP+4]
asm int 21H
end
void putc(char Ch)
asm mov AH,2
asm mov DL,SS:[BP+4]
asm int 21H
end
void puts(char @St)
word P=0;
while St[P]!=#0 do
putc(St[P]);
inc P;
end
end
int strcmp(char @S1, @S2)
int P=0;
while TRUE do
if S1[P]<S2[P] then
return -1;
end
if S1[P]>S2[P] then
return 1;
end
if S1[P]=#0 then
return 0;
end
inc P;
end
end
define TXT_LEN 32768
define FRM_LEN 16384
define ARC_LEN 4096
define BLK_LEN 2048
define ARC_FWD 32
define END_LEN 16
define STR_LEN 34
define PAK_LEN 5
define PAK_MIN 3
define OFS_LEN 14
define OFS_MIN 3
byte Txt [TXT_LEN]; // Текст
word nTxt;
word pTxt;
byte Arc [ARC_LEN]; // Архив
word nArc;
word pArc;
word P2 [16]; // 2**0..2*15
word Tmp; // буфер для манипуляций с битами
word pTmp;
void Save(word C; word N)
if N>8 then
Save(C/256,N-8);
C=C%256;
N=8;
end
if pTmp<8 then
Arc[pArc]=Tmp/256;
inc pArc;
Tmp =256*(Tmp%256);
pTmp=pTmp+8;
end
Tmp =Tmp+P2[pTmp-(N-1)]*C;
pTmp=pTmp-N;
end
word Load(word N)
word C=0;
if N>8 then
C=256*Load(N-8);
N=8;
end
if pTmp>7 then
if pArc<nArc then
Tmp=Tmp+P2[pTmp-7]*Arc[pArc];
inc pArc;
end
pTmp=pTmp-8;
end
C=C+Tmp/P2[16-N];
Tmp =P2[N]*(Tmp%P2[16-N]);
pTmp=pTmp+N;
return C;
end
void Encode(word hArc, hTxt)
word pChr;
nTxt=0;
pTxt=0;
pChr=0;
pArc=0;
while TRUE do
if pArc>=BLK_LEN then
write(hArc,@Arc,BLK_LEN);
puts(".");
word I=BLK_LEN;
word J=0;
while I<pArc do
Arc[J]=Arc[I];
inc J;
inc I;
end
pArc=J;
end
if pTxt>=FRM_LEN+BLK_LEN then
word I=BLK_LEN;
word J=0;
while I<nTxt do
Txt[J]=Txt[I];
inc J;
inc I;
end
nTxt=nTxt-BLK_LEN;
pTxt=pTxt-BLK_LEN;
pChr=pChr-BLK_LEN;
end
if pTxt+STR_LEN>=nTxt then
nTxt=nTxt+read(hTxt,@Txt[nTxt],BLK_LEN);
end
if pTxt>=nTxt then
exit
end
int I=pTxt-(FRM_LEN+(OFS_MIN-1));
if I<0 then
I=0;
end
int S=0;
int L=0;
while I+OFS_MIN<=pTxt do
int J=0;
while TRUE do // J<STR_LEN & I+J<pTxt & pTxt+J<nTxt do
if Txt[I+J]!=Txt[pTxt+J] then
exit
end
if J>=STR_LEN then
exit
end
if I+J>=pTxt then
exit
end
if pTxt+J>=nTxt then
exit
end
inc J;
end
if L<=J then
S=I;
L=J;
end
inc I;
end
if pChr<pTxt then
if L>2 | pTxt-pChr>=END_LEN then
int N=0;
while N<pTxt-pChr do
Save(0,1);
inc N;
end
Save(1,1);
while pChr<pTxt do
Save(Txt[pChr],8);
inc pChr;
end
end
end
if L>2 then
S=pTxt-S;
Save(1,1);
Save(L-PAK_MIN,PAK_LEN);
Save(S-OFS_MIN,OFS_LEN);
pTxt=pTxt+L;
pChr=pTxt;
loop
end
inc pTxt;
end
if pChr<pTxt then
int N=0;
while N<pTxt-pChr do
Save(0,1);
inc N;
end
Save(1,1);
while pChr<pTxt do
Save(Txt[pChr],8);
inc pChr;
end
end
if pTmp<15 then
Save(0,16);
end
if pArc>0 then
write(hArc,@Arc,pArc);
end
end
void Decode(word hArc, hTxt)
nArc=0;
pArc=0;
pTxt=0;
while TRUE do
if pTxt>=FRM_LEN+BLK_LEN then
write(hTxt,@Txt,BLK_LEN);
word I=BLK_LEN;
word J=0;
while I<pTxt do
Txt[J]=Txt[I];
inc J;
inc I;
end
pTxt=J;
end
if pArc+ARC_FWD>=nArc then
word I=pArc;
word J=0;
while I<nArc do
Arc[J]=Arc[I];
inc J;
inc I;
end
nArc=J+read(hArc,@Arc[J],BLK_LEN);
pArc=0;
end
word C=Load(1);
select
case C=0: // Несжатые данные
int N=1;
while TRUE do
if N>END_LEN then
if pTxt>0 then
write(hTxt,@Txt,pTxt);
end
return
end
if Load(1)!=0 then
exit
end
inc N;
end
while N>0 do
Txt[pTxt]=Load(8);
inc pTxt;
dec N;
end
case C=1:
int N=Load(PAK_LEN)+PAK_MIN;
int S=Load(OFS_LEN)+OFS_MIN;
int P=pTxt-S;
if P<0 then
return
end
while N>0 do
Txt[pTxt]=Txt[P];
inc pTxt;
inc P;
dec N;
end
end
end
end
begin
char @Line=@Ptr(GetPSP(),129); // Командная строка
byte @Size=@Ptr(GetPSP(),128); // Длина командной строки
char Parm [3][128]; // Параметры
int F=1;
int I=0;
int J=0;
while I<3 do
while J<Size & Line[J] =' ' do
inc J;
end
int K=0;
while J<Size & Line[J]!=' ' do
Parm[I][K]=Line[J];
inc K;
inc J;
end
Parm[I][K]=#0;
if K<1 then
F=0;
end
inc I;
end
word hArc;
word hTxt;
int C=0;
if F!=0 then
select
case strcmp(@Parm[0][0],"e")=0 | strcmp(@Parm[0][0],"E")=0:
hArc=create(@Parm[1][0]);
hTxt=open (@Parm[2][0]);
C=1;
case strcmp(@Parm[0][0],"d")=0 | strcmp(@Parm[0][0],"D")=0:
hArc=open (@Parm[1][0]);
hTxt=create(@Parm[2][0]);
C=2;
end
end
if C=0 then
puts("arcdemo.com e(ncode)|d(ecode) arc-file txt-file");
return
end
I=1;
J=0;
while J<16 do
P2 [J]=I; I=2*I;
inc J;
end
Tmp = 0;
pTmp=15;
select
case C=1:
Encode(hArc,hTxt);
case C=2:
Decode(hArc,hTxt);
end
close(hTxt);
close(hArc);
end
]]>
Сайт создан в системе
uCoz