Есть алгоритм распаковки. Надо сделать упаковку. Вроде бы и не хаффман, и не LZ... Код (Text): in_index = 0; while (in_index < comp_size) { for (i = 0; i < 0x100; i++) left[i] = i; //set all nodes to leaves tree_index = 0; while (tree_index != 0x100) { cmp_byte = in_buffer[in_index++]; if (cmp_byte > 0x7F) { tree_index += (cmp_byte - 0x7F); cmp_byte = 0; } if (tree_index != 0x100) { do { left[tree_index] = in_buffer[in_index++]; if (tree_index != left[tree_index]) //not a leaf right[tree_index] = in_buffer[in_index++]; //add right child tree_index++; } while (cmp_byte--); } } chunk_size = (in_buffer[in_index] << 8) | in_buffer[in_index+1]; in_index+=2; stack_size = 0; while (chunk_size>0 || stack_size>0) { if (stack_size > 0) node = stack[--stack_size]; else { chunk_size--; node = in_buffer[in_index++]; } child = left[node]; if (node == child) //reached a leaf, output it out_buffer[out_index++] = child; else { //add both children to stack stack[stack_size++] = right[node]; stack[stack_size++] = child; } } }
Помница копирование фраз в обратную сторону через stack обычно применяется в методе Shrinking (LZW). Но там вроде поболее кода должно быть.
Вот пара реальных деревьев, получаемых при распаковке (запись немного упростил для экономии места). Может натолкнёт на какую мысль... Код (Text): ff -> (00, 00) = [00 00 ] fe -> (ff, ff) = [00 00 00 00 ] fd -> (fe, fe) = [00 00 00 00 00 00 00 00 ] fc -> (fd, fd) = [00 ] x 16 fb -> (fc, fc) = [00 ] x 32 fa -> (fb, fb) = [00 ] x 64 f9 -> (fa, fa) = [00 ] x 128 Код (Text): fe -> (00, 00) = 00 00 fd -> (fe, fe) = 00 00 00 00 fc -> (fd, fd) = 00 00 00 00 00 00 00 00 fb -> (3b, 05) = 3b 05 fa -> (fb, 00) = 3b 05 00 f9 -> (fa, fa) = 3b 05 00 3b 05 00 f8 -> (fc, fc) = [00 ] x 16 f7 -> (f9, f9) = [3b 05 00 ] x 4 f6 -> (f8, f8) = [00 ] x 32 f5 -> (ff, ff) = ff ff f4 -> (f6, f6) = [00 ] x 64 f2 -> (f7, f7) = [3b 05 00 ] x 8 f1 -> (f5, ff) = ff ff ff f0 -> (f4, f4) = [00 ] x 128 ee -> (cf, c2) = cf c2 ed -> (ee, c0) = cf c2 c0 ec -> (f2, f2) = [3b 05 00 ] x 16 eb -> (4e, 4a) = 4e 4a ea -> (75, eb) = 75 4e 4a e9 -> (f9, fa) = [3b 05 00 ] x 3 e8 -> (78, 75) = 78 75
Лучше дай небольшой кусок запакованных данных, ну или начало хотя бы, или проверь сам - сможет ли он с помощью LZW распаковаться
Если это и LZW, то явно нестандартный, т.к. коды восьмибитные, а не переменной длины. Вот пример данных Дерево (первый цикл алгоритма): Код (Text): FE 7F F7 F9 F9 06 FA FA FB FB FC FC FD FD FE FE FF FF 00 00 При расшифровке получается первое из тех, что я привёл. Собственно данные (второй цикл): Код (Text): 00 25 42 4D 38 00 03 FE 00 36 FF 00 28 FE 01 FF 00 01 FF 01 00 18 FD 00 C3 0E FF C3 0E F8 F8 F8 F8 F8 F8 F8 F9 FB FE (00 25) - длина следующего фрагмента кодов (chunk_size). После распаковки получается: Код (Text): 42 4D 38 00 03 00 00 00 00 00 36 00 00 00 28 00 00 00 00 01 00 00 00 01 00 00 01 00 18 00 00 00 00 00 00 00 00 00 C3 0E 00 00 C3 0E 00 00 00 00 ...и ещё много нулей...
Итак, имеем : 1) строится дерево с 255 узлами (для всех букв появившихся в сжимаемом блоке, зарезервированы узлы + оставшиеся номера узлов используются для более длинных комбинаций) 2) в выходной поток идут только номера узлов - явный признак того, что за основу взят LZW 3) но в качестве узлов для склейки используются как сочетания (нода+символ) - LZW, так и (нода+нода) - LZMV 4) практически все в алгоритме ориентировано на размерность байта (в т.ч. индексы нод в дереве) - очень напоминает какую-то специализированную разновидность LZW наподобие того как в DOS-овских EXE-паковщиках на основе LZ77 был построен очень красивый байт-ориентированный алгоритм сжатия с объектным кодом функции распаковки в 77 байт. Offtopic : с трудом верю в практическую значимость подобного алгоритма из-за слишком маленького для LZW-семейства размера дерева. Насколько хорошо он сжимает данные ?
OLS Во, это уже ближе к делу. Не подскажешь, как примерно это дерево строить? Я что-то пытался прикинуть на бумажке, но выходит не очень. Насчёт эффективности есть такие данные: 90 файлов общим размером 28673111 байт (28666991 если отбросить заголовки) распаковываются в 66128936. Получается где-то 43%. Причём, по-моему, алгоритм используется не на полную мощность, т.к. в этих файлах максимальная длина кодируемых строк ограничена 256 байтами.
Так, кажись нашёл публикацию в которой описан этот самый алгоритм. Правда только японский вариант, но это не страшно Код (Text): constant K=256; procedure code; begin initialize(T); readfile(M); while maxn(M,ci,cj) >= 2 do begin enter(T,ci,cj,(ci·cj),nil); change(M,ci,cj,(ci·cj)); end; Cmax:=K - 1; for i:=l to length(M) do writetree(element(M,i)); end; procedure wrltetree(c); begin if c<K then writetreecode(0); writecode(e); else if assignedcode(T,c) <> nil then writetreecode(0); writecode(assignedcode(T,c)); else writetreecode(1); writetree(left(c)); writetree(right(c)); Cmax:=Cmax + 1; reenter (left(c),right(c), c, Cmax); fi; end; constant K=256; procedure decode; begin initialize(T); Cmax:=K - 1; while not end of file do dummy:=readtree; end; function readtree; begin t:=readtreecode; if t=0 then n:=readcode; writestr(c); return(c); else cl:=readtree; cr:=readtree; Cmax=Cmax+1; enter(T, cl, cr, (cl·er),Cmax); return(Cmax); fi; end; procedure writestr(c); begin if c<K then write(c); else writestr(left(T,c)); writestr(right(T,c)); fi; end; Всем спасибо, будем копать...
