Идея этого алгоритма основана на том предположении, что входящие в сжимаемый
текст слова неоднократно повторяются. Сжатие достигается заменой обнаруженных
повторов ссылками на предшествующие вхождения этих же слов. Т.е. повторное
вхождение слова заменяется парой чисел <Расстояние до предыдущего вхождения
слова, Длина слова>. Под словом понимается не слово естественного языка, а
произвольная последовательность символов.
Последнее предложение (Под словом понимается не слово естественного
языка, а произвольная последовательность символов) может
быть записано так: Под словом понимается не<21,6> ест<3,3>венного языка, а
произвольная<56,3>следовате<17,3>ость сим<3,3>ов.
Всего восемнадцать символов удалось заменить кодами - не очень много,
но при сжатии большого текста результат может быть гораздо лучше. Предполагается
также, что поиск совпадений производится не во всем тексте, а лишь в его части,
непосредственно предшествующей обрабатываемому слову. В приведенных примерах
длина этой части шестнадцать килобайт.
При записи в архив несжатый символ предваряется нулем - 0<символ>,
ссылка на ранее встречавшееся слово - единицей, т.е. 1SSSSSSSSSSSSSSNNNNN
(SSSSSSSSSSSSSS - расстояние до предыдущего входения, NNNNN - длина слова).
Это не самый экономный способ, но для начала ов вполне подойдет. Нужно только решить,
как кодировать конец файла. Можно пожертвовать самым большим смещением и использовать
его в качестве кода конца файла, а можно использовать код 1111111111111110, в этом
случае для максимального смещения придется использовать код 1111111111111111
(все коды двоичные) - так и будет сделано.
Программная состоит из четырех функций - Encode (выполняет кодирование), Decode
(выполняет декодирование), Save и Load (побитовые запись и чтение архива). Вот
как может выглядеть функция Encode:
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)
nTxt=0;
pTxt=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;
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 I+J>=pTxt then
exit
end
if J>=STR_LEN 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 L>=PAK_MIN then // запись ссылки
S=pTxt-S;
Save(1,1);
Save(S-OFS_MIN,OFS_LEN);
if S=FRM_LEN+OFS_MIN-1 then
Save(1,1);
end
Save(L-PAK_MIN,PAK_LEN);
pTxt=pTxt+L;
else
Save(0,1);
Save(Txt[pTxt],8);
inc pTxt;
end
end
Save(1,1);
Save(FRM_LEN,OFS_LEN);
Save(0,1);
if pTmp<15 then // нужно для корректного завершения
Save(0,16);
end
if pArc>0 then
write(hArc,@Arc,pArc);
end
end
Эта функция работоспособна, но содержит погрешности и лишние действия. В ней
реализован наивный подход к решению задачи, в худшем случае внутренний цикл
выполняется около FRM_LEN*STR_LEN раз. И так получилось, что похожая функция
была использована для тестирования компиляторов Context'а на различных машинах,
но здесь она принесла некоторую пользу.
Вот что можно улучшить. Во-первых, кодируемое и кодирующее слова могут пересекаться,
недопустимо лишь их полное наложение. Поэтому выход из цикла по условию I+J>=pTxt
не требуется и условие внешнего цикла нужно заменить на I<pTxt. Условия J>=STR_LEN
и pTxt+J>=nTxt можно заменить одним J>=N, где N - меньшее из STR_LEN и nTxt-pTxt.
Эти и некоторые другие улучшения приведены ниже:
void Encode(word hArc, hTxt)
nTxt=0;
pTxt=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;
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;
if I<0 then
I=0;
end
int N=STR_LEN;
if N>nTxt-pTxt then
N=nTxt-pTxt;
end
byte T=Txt[pTxt];
int S=0;
int L=0;
int J=0;
while TRUE do
while TRUE do
if Txt[I+J]!=Txt[pTxt+J] then
exit
end
if J>=N then
exit
end
inc J;
end
if L<=J then
if I=pTxt then
exit
end
S=I;
L=J;
end
inc I;
while Txt[I]!=T do
inc I;
end
J=1;
end
if L>=PAK_MIN then
S=pTxt-S;
Save(1,1);
Save(S-1,OFS_LEN);
if S=FRM_LEN then
Save(1,1);
end
Save(L-PAK_MIN,PAK_LEN);
pTxt=pTxt+L;
else
Save(0,1);
Save(Txt[pTxt],8);
inc pTxt;
end
end
Save(1,1);
Save(FRM_LEN-1,OFS_LEN);
Save(0,1);
if pTmp<15 then
Save(0,16);
end
if pArc>0 then
write(hArc,@Arc,pArc);
end
end
Этот алгоритм обеспечивает приемлемое сжатие (примерно в 1.1-1.5 раза хуже,
чем распространенные DOS-архиваторы), а вот его быстродействие очень низко.
Для демонстрации идеи это не важно, для практического использования алгоритм
должен быть усовершенствован. Для поиска совпадений можно использовать алгоритм
Кнута-Морриса-Пратта, но он даст выигрыш лишь в худшем случае (например, когда
сжимаемый текст состоит из одних пробелов). Индексный поиск дает выигрыш лишь
при большой ширине окна. Можно использовать хэш-таблицу, но в этом случае высокая
скорость достигается за счет явного ограничения длин цепочек коллизий и найденные
совпадения могут не быть наилучшими. Можно использовать комбиникованные алгоритмы.
Наконец степень сжатия можно повысить за счет более оптимального кодирования, например
за счет преобразования смещений, длин и несжатых символов в коды Хаффмана. Это также
позволит увеличить ширину окна и максимальную длину совпадения.
В заключение - полный текст программы. Содержательная часть начинается с первого
define:
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
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
byte Txt [TXT_LEN];
word nTxt;
word pTxt;
byte Arc [ARC_LEN];
word nArc;
word pArc;
word P2 [16];
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)
nTxt=0;
pTxt=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;
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;
if I<0 then
I=0;
end
int N=STR_LEN;
if N>nTxt-pTxt then
N=nTxt-pTxt;
end
byte T=Txt[pTxt];
int S=0;
int L=0;
int J=0;
while TRUE do
while TRUE do
if Txt[I+J]!=Txt[pTxt+J] then
exit
end
if J>=N then
exit
end
inc J;
end
if L<=J then
if I=pTxt then
exit
end
S=I;
L=J;
end
inc I;
while Txt[I]!=T do
inc I;
end
J=1;
end
if L>=PAK_MIN then
S=pTxt-S;
Save(1,1);
Save(S-1,OFS_LEN);
if S=FRM_LEN then
Save(1,1);
end
Save(L-PAK_MIN,PAK_LEN);
pTxt=pTxt+L;
else
Save(0,1);
Save(Txt[pTxt],8);
inc pTxt;
end
end
Save(1,1);
Save(FRM_LEN-1,OFS_LEN);
Save(0,1);
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:
Txt[pTxt]=Load(8);
inc pTxt;
case C=1:
int S=Load(OFS_LEN)+1;
if S=FRM_LEN then
if Load(1)=0 then
if pTxt>0 then
write(hTxt,@Txt,pTxt);
end
exit
end
end
int N=Load(PAK_LEN)+PAK_MIN;
int P=pTxt-S;
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