2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Posted automatically
Сообщение27.02.2013, 19:50 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Computer Science»

 
 
 
 Re: Сжатие данных
Сообщение27.02.2013, 20:33 
Аватара пользователя
vlad_light в сообщении #688928 писал(а):
алфавит $\{ABC, CAB\}$.

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

 
 
 
 Re: Сжатие данных
Сообщение27.02.2013, 21:23 
А что это?

 
 
 
 Re: Сжатие данных
Сообщение27.02.2013, 21:53 
Аватара пользователя
Кодовые слова?

 
 
 
 Re: Сжатие данных
Сообщение27.02.2013, 22:02 
Почему? В новой записи $ABC$ принимается за одну букву - почему бы и нет - а две буквы уже составляют алфавит...

 
 
 
 Re: Сжатие данных
Сообщение27.02.2013, 22:24 

(Оффтоп)

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

 
 
 
 Re: Сжатие данных
Сообщение27.02.2013, 23:03 
Предлагаю для кодирования сообщения $ABCCABCABABCCAB$ взять алфавит $\{ABCCABCABABCCAB\}$.

 
 
 
 Re: Сжатие данных
Сообщение27.02.2013, 23:05 
vlad_light в сообщении #688928 писал(а):
скиньте, пожалуйста, ссылки на статьи и другую литературу по данному вопросу (алгоритм Хаффмана)
Начните с литературы, которую советуют Википедия (Код Хаффмана) и Wikipedia (Huffman coding).

 
 
 
 Re: Сжатие данных
Сообщение28.02.2013, 00:19 
Цитата:
Предлагаю для кодирования сообщения $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).
Там много книг, я думал Вы посоветуете какую-то одну хорошую.

 
 
 
 Re: Сжатие данных
Сообщение28.02.2013, 19:14 
vlad_light в сообщении #689008 писал(а):
Цитата:
Начните с литературы, которую советуют Википедия (Код Хаффмана) и Wikipedia (Huffman coding).
Там много книг, я думал Вы посоветуете какую-то одну хорошую.
Много...
В Wikipedia - 1 книга. В Википеди- 2 книги, причем 1-я из них - перевод упомянутой английской.
ИТОГО: 2 (ДВЕ) книги, обе хорошие.

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

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

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group