ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vovanius Uryvaeff 2:5020/175.2 19 Nov 2002 19:28:29
To : Roman =KRoN= Karshiev
Subject : Реально ли распаковать ZIP имея менее 30кБ ОЗУ?
--------------------------------------------------------------------------------
Tue Nov 19 2002 14:19, Roman =KRoN= Karshiev wrote to All:
RKK> Сабж. Максимум heep'а - около 30кБ. По классическому алгоритму нужно не
RKK> менее 40кБ. А ведь ещё и для самой программы что-то ещё надо. Hеужто ZIP
RKK> даже в теории с малой памятью не распаковать?
Разница смотрю невелика. Можно попробовать данные поплотнее утрамбовать.
А какой алгоритм у ZIPа? LZ-Huffman ? Попробуй таблицу поплотнее разместить,
например левую ветвь дерева хафмана храни в следующей ячейке (избывишся от
одного указателя). Используй битовые поля.
Hапример дерево хафмана следующего вида:
^0--> *
0/ \1
/ \
^1--> * *
0/ \1 0/ \1
^2--> * C D E
0/ \1
A B
Положи в память в виде:
0 1 2 3 4 6 7 8 9
+---+---+---+---+---+---+---+---+---+
|^7 |^6 |^4 |'A'|'B'|'C'|^9 |'D'|'E'|
+---+---+---+---+---+---+---+---+---+
\\_/\\_/\\_/ / / /\\_/ /
\ \ \___/ / / \___/
\ \_________/ /
\________________/
^n - развилка
'A' - лист.
LEFT(x)=x+1;
RIGHT(x)=*x;
А определять - лист это или развилка можно по старшему биту (если ячейки
16-битные)
все равно он использоваться не будет(<32k)
И посильнее программу на подпрограммы порежь.
А что за машинка, если не секрет?
Send Email to vovanius2000<yxo>mail. ru
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
