Алгоритм сжатия коротких сообщений

Здравствуйте
Необходимо сжимать короткие сообщения (несколько десятков байт). Сообщения это обычный тект, короткие фразы. Посоветуйте оптимальный алгоритм(желательно с исходниками, можно на любом языке). Решил использовать lzw, но пока не уверен

 

попробуй rle, он достаточно простой в реализации.

 

несколько десятков байт

на таких маленьких смысла нет ..

 

Ну могу предложить один вариант. (Изврат полный)

Если передается текст водишь свой словарь из часто используемых слов и нумеруешь их по порядку.
А передаешь порядковый номер в словаре.
Недостаток: нужно сделать такой словарь и хранить его на источнике и получателе, а если меняется то синхронизировать их.

Т.о. в 10 байт можно поместить 10 слов любой длины. Ну это при условии, что словарь не больше 256 слов.

 

Я,неточно задачу описал. Несколько десятков байт это минимальная длинна сообщения. Максимальная килобайт 70. RLE не думаю что подойдет, сжимается осмысленный текст, повторений мало.
Думаю использовать 2 алгоритма. Для более-менее длинных сообщений lzw, а для коротких арифметическое сжатие, оно, кажется в худшем случае не удлинняет сообщение(или есть другие алгоритмы?). С реальзицией арифметического на асм, думаю будут проблемы, я еще учусь, может у кого-нибудь есть исходники?

 

Хаффман
Тут тебе самое оно
готовые исходники на асме ищи на compression.ru

 

S_Alex
А это разве не извращенный LZ ?

 

zoool
Спасибо, сайт классный!

 

Sov

лучше арифметика не найти, но он черепаха. оптимумом являются координатки - у них и скорость выше, и на малоизбыточных данных при такой длинне строки они даже арифметик обогнать могут, но выигрыш весьма........ весьма мал. я этим делом одно время занимался, могешь вот тут почитать обсуждение на форуме http://wasm.ru/forum/viewtopic.php?id=19505 (там же и урлосы на описания найдёшь). и кстати, вопрос: по твоей задачи есть возможность склейки сообщений??

 

UbIvItS
Хм... Идея интересная,надо думать...
В моей задаче склейка сообщений не предусматривается, хотя, используя коорд это легко сделать, никакой перепаковки...
Я сжатием 2-й день занимаюсь, крыша едет от обилия алгоритмов)
Пожалуй попробую реализовать этот алгоритм, арифметика сложна
А скорость меня не очень волнует, сообщения-то коротенькие

 

aPlib - вылизанная библиотека - w*w.ibsensoftware.com

 

Sov

алгосов много, а подходов, на коих они базируются, не превышает пальцев руки:
словарные, координатные и статистические. а их обилие исходит из того, что много разных видов данных и требуется адаптация.

 

Sov

а кол-во мессаг какое??

 

Sov
Самый простой вариант, если сжимается, например английский текст и нет разницы строчные/прописные буквы -- латинский алфавит - 27 символов + точка + пробел + восклицательны/вопросительный знаки + перевод строки = 32 символа или 2^5
т.е. каждый символ требует 5 бит. На ASCII-символы отводится 8 бит. При кодировании отбрасываешь первые 3 бита, при декодировании 3 нулевых бита восстанавливаешь - коэффицент сжатия 8/5=1,6 для короткого сообщения вполне приемлемо...

 

Код (Text):

1. ;      (с) 2006 Алгоритм сжатия Лимпен - Зива
2.  
3. LZW_Decompress proc stdcall src:DWORD, dest:DWORD
4.     pushad
5.     xor ebx,ebx        ; ebx=ctrl_count
6.     mov esi,src
7.     movzx edx,byte ptr [esi]   ; edx=ctrl
8.     inc esi
9.     mov edi,dest
10. NextByte:
11.     bt edx,7
12.     jc IsCodeWord
13.     movsb
14.     jmp Next
15. IsCodeWord:
16.     xor eax,eax
17.     lodsb
18.     shl eax,8
19.     lodsb                              
20.     mov ecx,eax          ;eax=codeword
21.     shr ecx,4            ;ecx=phrase_index
22.     jecxz Finished
23.     push esi
24.     mov esi,edi
25.     sub esi,ecx
26.     and eax,0Fh
27.     inc eax
28.     inc eax
29.     mov ecx,eax
30.     rep movsb
31.     pop esi
32. Next:
33.     shl edx,1
34.     inc ebx
35.     cmp bl,8
36.     jb NextByte
37.     movzx edx,byte ptr [esi]    ;edx=ctrl
38.     inc esi
39.     xor ebx,ebx
40.     jmp NextByte   
41. Finished:  
42.     mov eax,edi
43.     sub eax,[dest]
44.     mov dword ptr [esp+28],eax
45.     popad
46.     ret
47. LZW_Decompress endp
48.  
49.  
50. SearchForPhrase proc stdcall string:DWORD, src:DWORD, max_len:DWORD, best_lenptr:DWORD
51.     pushad
52.     mov esi,[string]
53.     mov edi,esi
54.     mov bl,byte ptr [esi]
55.     xor edx,edx             ;edx=best string
56.     mov eax,[best_lenptr]
57.     mov dword ptr [eax],1
58.     dec esi
59. NextByte:
60.     cmp esi,[src]
61.     jb Finished
62.     cmp byte ptr [esi], bl
63.     jnz NotHere
64.     push esi
65.     push edi
66.     inc esi
67.     inc edi
68.     mov ecx,max_len
69.     mov eax,ecx
70.     repe cmpsb
71.     sub eax,ecx
72.     pop edi
73.     pop esi
74.     mov ecx,[best_lenptr]
75.     cmp eax,[ecx]
76.     jbe NotHere
77.     mov [ecx],eax
78.     mov edx,esi
79. NotHere:
80.     dec esi
81.     jmp NextByte   
82. Finished:
83.     mov [esp+28],edx   
84.     popad
85.     ret
86. SearchForPhrase endp
87.  
88.  
89. LZW_Compress proc stdcall src:DWORD, dest:DWORD, len:DWORD
90.     local src_end:DWORD
91.     local dest_end:DWORD
92.     local phrase_ptr:DWORD
93.     local lazy_ptr:DWORD
94.     local ctrl_ptr:DWORD
95.     local phrase_len:DWORD
96.     local lazy_len:DWORD
97.     local temp:DWORD
98.     pushad
99.     mov eax,[src]
100.     add eax,[len]
101.     mov [src_end],eax
102.     mov eax,[dest]
103.     add eax,[len]
104.     sub eax,3
105.     mov [dest_end],eax
106.     xor eax,eax
107.     mov [phrase_ptr],eax
108.     cdq                         ;edx=ctrl
109.     xor ebx,ebx                     ;ebx=ctrl_count
110.     mov esi,[src]
111.     mov edi,[dest]
112.     mov [ctrl_ptr],edi
113.     inc edi
114. NextByte:
115.     cmp esi,[src_end]
116.     jge Finished
117.     cmp edi,[dest_end]
118.     jge Finished
119.     inc ebx
120.     cmp ebx,9
121.     jnz StillBitsInCode
122.     mov eax,[ctrl_ptr]
123.     mov byte ptr [eax],dl
124.     mov [ctrl_ptr],edi
125.     inc edi
126.     xor edx,edx
127.     mov ebx,1
128. StillBitsInCode:
129.     mov ecx,[src_end]
130.     sub ecx,esi
131.     cmp ecx,15+2
132.     jbe LenGood
133.     mov ecx,15+2                        ;ecx=max_len
134. LenGood:
135.     mov eax,esi
136.     sub eax,4095
137.     cmp eax,[src]
138.     jae WindowGood
139.     mov eax,[src]
140. WindowGood:
141.     mov [temp],eax
142.     cmp [phrase_ptr],0
143.     jnz TestLazy
144.     invoke SearchForPhrase,esi,[temp],ecx,addr phrase_len
145.     mov [phrase_ptr],eax
146. TestLazy:  
147.     cmp ecx,2
148.     jb CantTestLazy
149.     inc esi
150.     inc [temp]
151.     invoke SearchForPhrase,esi,[temp],ecx,addr lazy_len
152.     dec ecx
153.     mov [lazy_ptr],eax
154.     dec esi
155. CantTestLazy:  
156.     shl edx,1
157.     cmp [phrase_ptr],0
158.     jz code_literal
159.     jecxz code_literal
160.     cmp [lazy_ptr],0
161.     jz code_word
162.     mov eax,[lazy_len]
163.     cmp eax,[phrase_len]
164.     jbe code_word
165. code_literal:  
166.     push [lazy_ptr]
167.     pop [phrase_ptr]
168.     push [lazy_len]
169.     pop [phrase_len]
170.     movsb
171.     jmp NextByte
172. code_word: 
173.     or edx,1
174.     mov eax,esi
175.     sub eax,[phrase_ptr]
176.     shl eax,4
177.     mov ecx,[phrase_len]
178.     dec ecx
179.     dec ecx
180.     and ecx,0Fh
181.     or eax,ecx
182.     push eax
183.     shr eax,8
184.     stosb
185.     pop eax
186.     stosb
187.     add esi,[phrase_len]
188.     mov [phrase_ptr],0
189.     jmp NextByte
190. Finished:
191.     inc ebx
192.     shl edx,1
193.     or edx,1
194. TryNextBits:
195.     cmp ebx,8
196.     jae NoMoreBits
197.     shl edx,1
198.     inc ebx
199.     jmp TryNextBits
200. NoMoreBits:
201.     mov eax,[ctrl_ptr]
202.     mov byte ptr [eax],dl
203.     xor eax,eax
204.     stosw
205.     sub edi,[dest]
206.     mov [esp+28],edi
207.     popad
208.     ret
209. LZW_Compress endp

 

не менее извратный вариант, чем вариант S_Alex. Составляется словарь слогов. Для русского языка из 32 букв - 10 гласных, 20 согласных, 2 знака (тверд/мягкий). 20*10=200 символов под слоги типа С-Г + 10 гласных + 20 согласных + знаки пунктуации (запятая, пробел, перевод строки и т.п.) укладываемся в 256 символов. Тексты сжимаются почти в 2 раза

 

// Copyright (c) 1993 by Chuck Guzis. All rights reserved
// Dr. Dobb's Journal. #207 November 1993. pp. 117, 118, 144, 145.

Повторюсь, для коротких текстовых сообщений (от десятков до сотен байт) aPLib оптимален, с увеличением размера текстов выгодны арифметика и PPM (если память некритична).

 

UbIvItS
Одно сообщение)

Mikl__
От словарей я решил отказаться, переход от расширенной ascii к "мини" очень интересен. Пожалуй самым эффективным решением окажется. Все гениальное просто)

asmlamo
Спасибо большое, я все сомневолся на си писать или на асме. Сейчас вопрос решен)

Всем большое спасибо

 

gazlan
Я и не подозревал, что нарушил чей-то копирайт,

вообще-то сам додумался, но на всякий случай выражаю глубокую благодарность Кирилу и Мефодию за предоставленный алфавит, а также Лоренцу, Максвелу, Гальвани, А.С.Попову, чей неоценимый труд увенчался созданием компьютера, на котором я сейчас работаю

 

Mikl__

угу. вот так живёшь, живёшь, а вдруг раз - и уже ПЛАГИАТОР. жесть
P.S. думаю не всех перечислили