Реально ли распаковать ZIP имея менее 30кБ ОЗУ?

From

Vovanius Uryvaeff (2:5020/175.2)

To

Roman =KRoN= Karshiev

Date

2002-11-19T18:28:29Z

Area

RU.ALGORITHMS

From: "Vovanius Uryvaeff" <micro-s@vniiofi.ru>

Tue Nov 19 2002 14:19, Roman =KRoN= Karshiev wrote to All:

 RKK> Сабж. Максимум heep'а - около 30кБ. По классическому алгоритму нужно не
 RKK> менее 40кБ. А ведь ещё и для самой программы что-то ещё надо. Неужто ZIP
 RKK> даже в теории с малой памятью не распаковать?

Разница смотрю невелика. Можно попробовать данные поплотнее утрамбовать.
А какой алгоритм у ZIPа? LZ-Huffman ? Попробуй таблицу поплотнее разместить,
например левую ветвь дерева хафмана храни в следующей ячейке (избывишся от
одного указателя). Используй битовые поля.
Например дерево хафмана следующего вида:
        ^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)