2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 
Сообщение09.10.2006, 21:31 
Аватара пользователя
BE@R писал(а):
To photon:можно использовать например кодировку ASCII,тогда для хранения 1 символа нужно будет 3 байта.В итоге размер файла увеличивается.

Так много? :shock:

 
 
 
 
Сообщение09.10.2006, 21:35 
Цитата:
mp3 файлы не сжимаются не потому, что архиваторы глупые, а потому, что они уже сжаты, причем близким к порогу способом

Это я прекрасно понимаю!

 
 
 
 
Сообщение09.10.2006, 21:42 
Аватара пользователя
Ну так чего хотите? По сути, Вы хотите сделать способ сжатия общего назначения, т.е. такой, который ничего не знает о структуре сжимаемой информации. Именно такого рода работу делают всякие zip-rar, причем весьма эффективно. Если они Вашу информацию "не берут", то сделать это более эффективно Вам вряд ли удастся.

Единственный Ваш козырь - Вы знаете формат Ваших данных. На этом потенциально можно сыграть. Как минимум, проверить, не тратится ли что-то впустую. Например, сохраняете целое в 4 байта, а на самом деле оно всегда помещается в два. Или в один, если это bool. Но, правда, если на этом играть, то придется более сложным образом организовывать файловый вывод, возможно на уровне отдельный бит...

Более сложный метод - проанализировать статистические свойства данных и применить какие-либо известные методы сжатия, если получится.

А исходная задача - взять, и просто уменьшить число цифр - не решается в принципе. Любое преобразование такого рода будет что-то уменьшать, а что-то увеличивать. Плюс, придется еще ставить какие-то разделители между числами, так как они будут разной длины.

 
 
 
 
Сообщение09.10.2006, 23:45 
BE@R писал(а):
можно использовать например кодировку ASCII,тогда для хранения 1 символа нужно будет 3 байта. В итоге размер файла увеличивается.

С помощью ASCII-кодов любое число, вплоть до $4.294.967.295_1_0$ можно задать не более, чем 4-мя символами.
Т.о. для хранения 9-тизначного числа (9 байт) с помощью преобразования понадобится не более 4-х байт.

 
 
 
 
Сообщение10.10.2006, 15:58 
Попробуйте арифметическое кодирование с предварительным расчетом статистики символов.

 
 
 
 
Сообщение10.10.2006, 18:27 
vbn писал(а):
С помощью ASCII-кодов любое число, вплоть до $4.294.967.295_1_0$ можно задать не более, чем 4-мя символами.
Т.о. для хранения 9-тизначного числа (9 байт) с помощью преобразования понадобится не более 4-х байт.

Как ни странно, но ASCII-коды кодируют (извините за тавтологию) символы, а не числа. Задать то число для отображения можно меньшим количеством символов, но для вычислений оно будет занимать не меньше (если не реализовать свои функции) места по причине определенного задания в памяти компьютера.
И с чего Вы взяли, что 9-тизначное число - это 9 байт?

 
 
 
 
Сообщение11.10.2006, 01:46 
Werwolf писал(а):
Как ни странно, но ASCII-коды кодируют (извините за тавтологию) символы, а не числа.

Число состоит из цифр. А каждая цифра-символ из [0..9] является частью ASCII-таблицы.

Werwolf писал(а):
И с чего Вы взяли, что 9-тизначное число - это 9 байт?

Это действительно так, если хранить число "как оно есть" в файле на жестком диске.

 
 
 
 
Сообщение11.10.2006, 14:22 
vbn писал(а):
Werwolf писал(а):
И с чего Вы взяли, что 9-тизначное число - это 9 байт?

Это действительно так, если хранить число "как оно есть" в файле на жестком диске.

Не понятно, почему так много внимания уделяется ASCII-представлению числа. Что это такое - число "как оно есть"? 9-значное число без знака во внутреннем представлении занимает не более 30 бит. Для хранения его достаточно 4 байт, как Вы уже писали. Используя алгоритм, аналогичный UU-кодированию, можно поместить 4 9-значных беззнаковых числа в 15 байт (3.75 байта на число). При этом упаковка-распаковка будет достаточно быстрой. Арифметическое кодирование, которое упомянул HOKUM, или префиксное кодирование (алгоритм Хаффмана) - более медленные, но скорее всего уменьшат размер сжатого массива.

 
 
 
 
Сообщение11.10.2006, 14:52 
Yuri Gendelman писал(а):
vbn писал(а):
Werwolf писал(а):
И с чего Вы взяли, что 9-тизначное число - это 9 байт?

Это действительно так, если хранить число "как оно есть" в файле на жестком диске.

Что это такое - число "как оно есть"?

Наберите в текстовом редакторе 9-тизначное число, сохраните файл, а затем посмотрите, каков его размер.

 
 
 
 
Сообщение11.10.2006, 17:23 
vbn писал(а):
Наберите в текстовом редакторе 9-тизначное число, сохраните файл, а затем посмотрите, каков его размер.

В текстовом файле сохраняется не число, а строка, в которой записаны цифры.

 
 
 
 
Сообщение11.10.2006, 22:10 
Признаться, мне несколько удивительно, что самое дельное замечание из всей этой длинной дискуссии - использовать арифметическое кодирование (HOKUM) - осталось без внимания. А ведь это, во первых, ближе всего к изначальной идее автора темы (хотя он и сформулировал свой вопрос в весьма наивных терминах) а, во вторых, арифметическое кодирование ближе всего подходит к теоретической границе энтропийного сжатия.

 
 
 
 
Сообщение12.10.2006, 14:15 
vbn писал(а):
Наберите в текстовом редакторе 9-тизначное число, сохраните файл, а затем посмотрите, каков его размер.

Это конечно железный довод :)
Теперь наберите его же в текстовом редакторе в Unicode - получите 18 байт. А теперь наберите его же на русском языке - получите переменное число байт, что-то порядка 80.

Igor Borovikov писал(а):
Признаться, мне несколько удивительно, что самое дельное замечание из всей этой длинной дискуссии - использовать арифметическое кодирование (HOKUM) - осталось без внимания.

Вот именно. А сжатие текстового представления - еще удивительнее.
Но не будем забывать, что арифметическое кодирование очень медленное. Если архив создается для оперативного хранения, то вряд ли АК - подходящий выбор.

 
 
 
 
Сообщение12.10.2006, 20:43 
Igor Borovikov писал(а):
арифметическое кодирование ближе всего подходит к теоретической границе энтропийного сжатия.


Не не правда ваша. Еще Хафман доказал оптимальность кода хафмана. Тут как раз в пределе и достигается граница энтропийная.

 
 
 
 
Сообщение13.10.2006, 19:41 
Не вижу где тут "неправда". Асимптотическая оптимальность кодов Хаффмана не противоречит тому, что арифметическое кодирование дает более высокую компрессию. Естественно, эта компрессия тоже ограничена энтропийным пределом.

См. например “Lossless compression handbook” Khalid Sayood, 2003, Academic Press

 
 
 
 
Сообщение14.10.2006, 08:46 
Igor Borovikov писал(а):
Не вижу где тут "неправда". Асимптотическая оптимальность кодов Хаффмана не противоречит тому, что арифметическое кодирование дает более высокую компрессию. Естественно, эта компрессия тоже ограничена энтропийным пределом.

См. например “Lossless compression handbook” Khalid Sayood, 2003, Academic Press


Код хафмана стремиться к энтропии в пределе. Арифметическое кодирование лучше. ЗНачит они ниже энтропии в пределе?

 
 
 [ Сообщений: 36 ]  На страницу Пред.  1, 2, 3  След.


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