Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Сжатие информации

AntonSh © (2004-10-22 12:16:00)
Подскажите, пожалуйста, может кто знает.
Вот прочитал про такую реализацию метода. Например есть строка – “Антон”. Подсчитываем какой символ встречается чаще всего: н – 2. Тогда записываем нашу строку в виде: 01001. Удаляем из нашей строки символ – н: Ато. Производим ту же операцию. Так как все одинаковое количество, то берем символ А : 100. Остаётся – то. Соответственно: 10. В итоге получаем: 01001100100. Вместо 5 байт получаем 1 и 1 бит. Можно ли данный метод считать правильным? Спасибо.

TUser (2004-10-22 17:42:00) [1]

> Действительно, на Хаффмана похоже

Да не Хафман это. Хотя бы потому, что здесь не гарантируется никак "суффиксность" шифра

TUser (2004-10-22 17:40:00) [2]

> автор одной умнойкниги

?

AntonSh (2004-10-22 17:25:00) [3]
Главное что данное сжатие работает. А почему автор одной умной книги по алгоритмам относит данный метод к LWZ остаётся только догадываться.

Анонимщик (2004-10-22 16:23:00) [4]
Действительно, на Хаффмана похоже, только так описано, что ничего не понятно.

Anatoly Podgoretsky (2004-10-22 13:50:00) [5]
Ega23 © (22.10.04 12:26) [4]
Трудно обеспечить безопасность если будет возможно восстановление.

Symb (2004-10-22 13:46:00) [6]
AntonSh, алгоритм LZW анализирует входной текст не посимвольно, а пытается найти повторяющиеся строки. То, что описано в вопросе -- посимвольный анализ, где новый код символа зависит от его частоты.
Алгоритмы, которые так работают (вполне успешно): Метод Хаффмана (Huffman) и метод Шеннона-Фано (Shannon-Fano). Посмотри в инете их описание.

mrcat (2004-10-22 13:44:00) [7]
>Ни фига себе "дело десятое"! А кому это сжатие без восстановления нужно?

Хэш-функции: сжатие без восстановления

Гарри Поттер (2004-10-22 12:53:00) [8]
>Вот прочитал про такую реализацию метода

Здесь прочитал?
http://www.lapsha.ru/articles/tech/2004/01/06/150700.html

Ну тогда объединяйтесь и пишите разархиватор, тоже на страницы лапшпа.ру попадешь.

AntonSh (2004-10-22 12:32:00) [9]
Спасибо за ответы. Я хочу объяснить почему у меня возник данный вопрос. Вот везде в Inete описан данный метод следующим образом :
Алгоритм LZW-сжатия в простейшей форме приведен на рис.1. Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и , если так, выводит существующий код без генерации нового.
Процедура LZW-сжатия:

СТРОКА = очередной символ из входного потока
WHILE входной поток не пуст DO
СИМВОЛ = очередной символ из входного потока
IF СТРОКА+СИМВОЛ в таблице строк THEN
СТРОКА = СТРОКА+СИМВОЛ
ELSE
вывести в выходной поток код для СТРОКА
добавить в таблицу строк СТРОКА+СИМВОЛ
СТРОКА = СИМВОЛ
END of IF
END of WHILE
вывести в выходной поток код для СТРОКА

Но как мне кажется мой способ(предложенный моим товарищем) несколько отличается от описаного в книге. Где же правда?

Ega23 (2004-10-22 12:26:00) [10]
Ни фига себе "дело десятое"! А кому это сжатие без восстановления нужно?

Reindeer Moss Eater (2004-10-22 12:21:00) [11]
Дешифровка - дело десятое.
Мы тут про сжатие.

Ega23 (2004-10-22 12:20:00) [12]
Вот теперь только дешифровки алгоритм опиши, и дадуть тебе какую-нить деньгу большую в виде премии.

Reindeer Moss Eater (2004-10-22 12:18:00) [13]
Совершенно правильный метод

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »