Сжатие данных

[vlad_light]

Нашлел статью в которой описывается сжатие с помощью деревьев Хаффмана:
http://www.researchgate.net/publication ... fman_trees
Насколько я понял, основная задача сжатия состоит в правильном выборе алфавита, например:
Для сообщения $ABCCABCABABCCAB$ следует взять алфавит $\{ABC, CAB\}$, а не $\{A,B,C\}$. Если это верно, то алгоритм шифрования, предложенный в статье, можно будет применить к любому алгоритму сжатия на основе деревьев Хаффмана.
Поправьте, если что не так и скиньте, пожалуйста, ссылки на статьи и другую литературу по данному вопросу (алгоритм Хаффмана). Заранее благодарен!

[Toucan]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Computer Science»

[nikvic]

vlad_light в сообщении #688928 писал(а):

алфавит $\{ABC, CAB\}$.

Это не алфавит.

[longstreet]

А что это?

[nikvic]

Кодовые слова?

[longstreet]

Почему? В новой записи $ABC$ принимается за одну букву - почему бы и нет - а две буквы уже составляют алфавит...

[vlad_light]

(Оффтоп)

Давайте не будем придираться к словам -- и так понятно, что я имел ввиду под словом "алфавит"
Вы лучше литературу мне посоветовали б, а то так и останусь бездарем, который неправильно термины использует

[venco]

Предлагаю для кодирования сообщения $ABCCABCABABCCAB$ взять алфавит $\{ABCCABCABABCCAB\}$.

[Yuri Gendelman]

vlad_light в сообщении #688928 писал(а):

скиньте, пожалуйста, ссылки на статьи и другую литературу по данному вопросу (алгоритм Хаффмана)

Начните с литературы, которую советуют Википедия (Код Хаффмана) и Wikipedia (Huffman coding).

[vlad_light]

Цитата:

Предлагаю для кодирования сообщения $ABCCABCABABCCAB$ взять алфавит $\{ABCCABCABABCCAB\}$.

Так плохо, потому что длина кода будет равна $L+1+1$, соответственно степень сжатия составит $\frac{L+2}{L}=1+\frac 2L >1, \forall L\geq 1$, а в моём случае длина составит $\frac 25L+2+5$ и степень сжатия будет равна $\frac{\frac 25L+2+5}{L}=\frac 25+\frac 7L<1, L\geq 12$, где $L$ - длина сообщения. Тут я использовал представление: код = алфавит + соответствующие ему биты + сообщение в битах.

Цитата:

Начните с литературы, которую советуют Википедия (Код Хаффмана) и Wikipedia (Huffman coding).

Там много книг, я думал Вы посоветуете какую-то одну хорошую.

[Yuri Gendelman]

vlad_light в сообщении #689008 писал(а):

Цитата:

Начните с литературы, которую советуют Википедия (Код Хаффмана) и Wikipedia (Huffman coding).

Там много книг, я думал Вы посоветуете какую-то одну хорошую.

Много...
В Wikipedia - 1 книга. В Википеди- 2 книги, причем 1-я из них - перевод упомянутой английской.
ИТОГО: 2 (ДВЕ) книги, обе хорошие.

[Pavia]

vlad_light
Советую взять и прочитать "В. В. Лидовский Теория информации Москва 2003."
А после
"Д. Сэломон. Сжатие данных, изображения и звука"

[toptyg]

Для себя открыл сайт ПМПУ, недавно читал
http://pmpu.ru/vf4/codes#коды_хаффмана