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

← →
AntonSh (2004-10-22 12:16) [0]

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

← →
Reindeer Moss Eater © (2004-10-22 12:18) [1]

Совершенно правильный метод

← →
Ega23 © (2004-10-22 12:20) [2]

Вот теперь только дешифровки алгоритм опиши, и дадуть тебе какую-нить деньгу большую в виде премии.

← →
Reindeer Moss Eater © (2004-10-22 12:21) [3]

Дешифровка - дело десятое.
Мы тут про сжатие.

← →
Ega23 © (2004-10-22 12:26) [4]

Ни фига себе "дело десятое"! А кому это сжатие без восстановления нужно?

← →
AntonSh (2004-10-22 12:32) [5]

Спасибо за ответы. Я хочу объяснить почему у меня возник данный вопрос. Вот везде в Inete описан данный метод следующим образом :
Алгоритм LZW-сжатия в простейшей форме приведен на рис.1. Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и , если так, выводит существующий код без генерации нового.
Процедура LZW-сжатия:

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

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

← →
Гарри Поттер © (2004-10-22 12:53) [6]

>Вот прочитал про такую реализацию метода

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

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

← →
mrcat © (2004-10-22 13:44) [7]

>Ни фига себе "дело десятое"! А кому это сжатие без восстановления нужно?

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

← →
Symb (2004-10-22 13:46) [8]

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

← →
Anatoly Podgoretsky © (2004-10-22 13:50) [9]

Ega23 © (22.10.04 12:26) [4]
Трудно обеспечить безопасность если будет возможно восстановление.

Действительно, на Хаффмана похоже, только так описано, что ничего не понятно.

← →
AntonSh (2004-10-22 17:25) [11]

Главное что данное сжатие работает. А почему автор одной умной книги по алгоритмам относит данный метод к LWZ остаётся только догадываться.

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

?

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

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

Сжатие информации Найти похожие ветки