Архиваторы

← →
Cerberus © (2006-12-03 20:59) [0]

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

И всё. может я что-то не так понял. Просто как всё это реализовать не доходит. Если есть какой нибудь маленький листинг на pascal то выложите плз.

← →
tesseract © (2006-12-03 21:01) [1]

http://www.compression.ru/

← →
ANTPro © (2006-12-03 21:08) [2]

Кто-нибудь встречал порт алгоритма PPM на pascal?

← →
Zeqfreed © (2006-12-03 21:16) [3]

Думаю, самый простой для понимания это один из семейства LZW. Можно взять deflate. Да и в реализации он попроще будет, чем хафман :)

← →
Cerberus © (2006-12-03 21:22) [4]

> Zeqfreed © (03.12.06 21:16) [3]
> Думаю, самый простой для понимания это один из семейства
> LZW. Можно взять deflate. Да и в реализации он попроще будет,
> чем хафман :)

Про хавмана нам и в институте читали сам алогритм понятен. А вот как сделат чтобы он что-то действительно сжимал а не просто одна теория. К примеру есть текст закодируем его получим ещё более длинный текст(причём ещё говорим о каком-то сжатие). А вот тонкостей "не стекстом" нам не читали.

← →
MeF Dei Corvi © (2006-12-03 21:37) [5]

> А вот как сделат чтобы он что-то действительно сжимал а
> не просто одна теория. К примеру есть текст закодируем его
> получим ещё более длинный текст(причём ещё говорим о каком-
> то сжатие).

Можно пример такого текста? :)

← →
Zeqfreed © (2006-12-03 21:47) [6]

> А вот тонкостей "не стекстом" нам не читали.

Хорошо вам, нам вот вообще не будут ничего читать...

← →
palva © (2006-12-03 21:51) [7]

http://sources.codenet.ru/download/401/Haffman.html

← →
Gero © (2006-12-03 22:38) [8]

http://algolist.manual.ru

← →
ferr © (2006-12-03 22:41) [9]

> Можно пример такого текста? :)

for i := 1 to 255 do write(Chr(i));
P.S. если хранить дерево.

← →
palva © (2006-12-03 22:54) [10]

> А вот как сделат чтобы он что-то действительно сжимал а
> не просто одна теория.

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

← →
Джо © (2006-12-03 23:07) [11]

> [10] palva © (03.12.06 22:54)

> А текст длиной один байт не может быть сжат в принципе.

"Сжать" можно совершенно что угодно. Необходимо еще соблюдение условия, чтобы "сжатое" можно было без потерь и однозначно восстановить :)

← →
click (2006-12-03 23:14) [12]

> Cerberus © (03.12.06 21:22) [4]
> Про хавмана нам и в институте читали сам алогритм понятен.
> А вот как сделат чтобы он что-то действительно сжимал а
> не просто одна теория.

Почитай:
Джулиан Бакнелл "Фундаментальные алгоритмы и структуры данных в Delphi"
поможет!

Конкурент: http://www.lapsha.ru/articles/tech/2004/01/06/150700.html :)

← →
ИА (2006-12-03 23:32) [14]

>И всё. может я что-то не так понял. Просто как всё это реализовать не доходит. Если есть какой нибудь маленький листинг на pascal то выложите плз.

Ваш вопрос противоречит себе самому. В наши дни писать простой архиватор имеет смысл если только вы хотите разобраться (с достаточно интересными, кстати) алгоритмами сжатия. Но к чему при этом просить пример кода? Я бы кстати выбрал для первичного упражнения словарный алгоритм, как тут уже говорили, LZW

> [0] Cerberus © (03.12.06 20:59)

Это скорее компрессор. Для написания архиватора писать алгоритм сжатия не обязательно :) Можно использовать готовый или вообще обойтись без сжатия (например tar).

Учат обычно Хафману со статической таблицей или с таблицей, вычисляемой для блока и записываемой вместе с этим блоком. А применяют на практике как минимум алгоритмы с динамической модификацией таблицы без сохранения ее, а то и с другими наворотами. Часто алгоритм Хафмена применяется уже к результатам работы других алгоритмов сжатия(тот же LZW), так что текста там уже нет.

Архиваторы Найти похожие ветки