2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение15.11.2010, 22:12 
Заслуженный участник
Аватара пользователя


30/10/10
1481
Ереван(3-й участок)
Rino в сообщении #375617 писал(а):
2 Bulinator
Вы путаете понятия "вот этот алгоритм...может" и "Rino сможет сжать любой файл более килобайта".


Тогда вот такие размышления.
Будем рассматривать файл как натуральное число(пусть очень большое) представленное единичками и нулями(Тот факт, что эти единички и нули разбиты на байты нас не интересует).
Т.е. файл- это натуральное число.

Теперь, вы утверждаете, что любому натуральному числу вы можете поставить в соответствие другое натуральное число от 1 до $2^{1024}-1$ плюс еще одно число, которое определяет номер алгоритма сжатия.

По-моему очевидно, чтобы сделать так, кол-во алгоритмов сжатия должно быть бесконечно большим.

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение15.11.2010, 22:45 


09/11/10
29
Не приписывайте мне свои утверждения. Я Вас понимаю. А Вы меня почему то не хотите понимать.

-- Вт ноя 16, 2010 01:28:32 --

Bulinator в сообщении #375636 писал(а):
Rino в сообщении #375617 писал(а):
2 Bulinator
Вы путаете понятия "вот этот алгоритм...может" и "Rino сможет сжать любой файл более килобайта".


Тогда вот такие размышления.
Будем рассматривать файл как натуральное число(пусть очень большое) представленное единичками и нулями(Тот факт, что эти единички и нули разбиты на байты нас не интересует).
Т.е. файл- это натуральное число.

Теперь, вы утверждаете, что любому натуральному числу вы можете поставить в соответствие другое натуральное число от 1 до $2^{1024}-1$ плюс еще одно число, которое определяет номер алгоритма сжатия.

По-моему очевидно, чтобы сделать так, кол-во алгоритмов сжатия должно быть бесконечно большим.

Отвечу Вам так. Надеюсь Вы поймёте.
На любую Вашу хитрость, можно ответить другой хитростью, которая будет вшита в программу, называемую архиватором. Я говорю про заранее заданные Ваши натуральные числа...И не забывайте, что архиваторы имеют право быть не только одного размера, одной интерпретации, но и как угодно большими.

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

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение15.11.2010, 23:55 


09/11/10
29
Забыл сказать, я более программист чем математик, поэтому строго не судите. Ну и прошу, кто может помочь с оценкой влияний погрешностей на сходимость ряда Фурье, помогите.

ps Я так понял, что возникли непонятки в выводе конечной формулы. В ближайшее время распишу подробнее, ну и программа будет, напишите только где лучше разместить.

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 00:04 
Заслуженный участник


04/05/09
4582
Rino в сообщении #375666 писал(а):
Прошу не забывать, что к архиву еще и программа прилагается, а какой она длины, что в ней, и что она может только разработчик и знает.
К каждому архиву своя программа?

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 00:36 


09/11/10
29
venco в сообщении #375716 писал(а):
Rino в сообщении #375666 писал(а):
Прошу не забывать, что к архиву еще и программа прилагается, а какой она длины, что в ней, и что она может только разработчик и знает.
К каждому архиву своя программа?

Зачем к каждому?
Ну, если задача так поставлена(найти алгоритм сжатия для КОНКРЕТНОГО файла), тогда да.

-- Вт ноя 16, 2010 03:13:54 --

Вроде, доступно объяснил, свою позицию.
Пока на ошибки не указали , буду считать теорию, как минимум "интересной идеей"...
Жду критику по существу.

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 01:22 
Заслуженный участник


04/05/09
4582
Rino в сообщении #375732 писал(а):
venco в сообщении #375716 писал(а):
Rino в сообщении #375666 писал(а):
Прошу не забывать, что к архиву еще и программа прилагается, а какой она длины, что в ней, и что она может только разработчик и знает.
К каждому архиву своя программа?

Зачем к каждому?
Ну, если задача так поставлена(найти алгоритм сжатия для КОНКРЕТНОГО файла), тогда да.
Тогда размер программы тоже надо учитывать, иначе архив вообще не нужен, и любой файл сжимается до нуля.

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 01:36 


09/11/10
29
Именно! Можно держать архиватор скажем на гигабайт. И пусть он делает свои дела...От задачи опять же зависит.
Ну не до нуля конечно

-- Вт ноя 16, 2010 03:45:30 --

Так вот программа то будет занимать мало байт, аделов делать ойойой

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 02:34 
Заслуженный участник


04/05/09
4582
Rino в сообщении #375751 писал(а):
Именно! Можно держать архиватор скажем на гигабайт. И пусть он делает свои дела...
Что "именно"? Размер такого персонального архиватора надо учитывать, как размер архива.

Rino в сообщении #375751 писал(а):
Ну не до нуля конечно
А что мешает?

-- Пн ноя 15, 2010 18:43:43 --

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

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

Согласны с такими определениями?

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 06:09 
Аватара пользователя


28/06/08
1706
Rino в сообщении #375595 писал(а):
AlexNew в сообщении #375545 писал(а):
Пример JPEG сжатие изображения, было у вас серенькое изображение, каждому пикселю соответствовал 1 байт (8 бит) . Потом вы применили дискретное преобразование Фурье, и вместо значений функции (последовательности байт) получили послд. коэффициентов ряда Фурье. Но тут есть проблема, для записи коэффициента Фурье не достаточно одного байта! ели использовать 1 байт то информация теряется, при обратном преобразовании не получить исходную функцию. Сжатие методом Фурье всегда происходит с потерями, даже если вы сохраняете все коэффициенты.
Как вы решили эту проблему?

ОДЗ функции берется такой, чтобы было сжатие.

Вы не поняли то что я написал.
Сжатие то у вас будет, всегда будет, и всегда с потеряй качества,
(скажем если исходным файлом был текст то на выходе у вас начнут путаться буквы :lol: )
единственный способ этого избежать сохранять более осторожно коэффициенты Фурье, на что потребуется больше чем один байт( в изначальном файле был один байт на значение функции)
Ваш способ в лучшем случае увеличит исходный фаил без потери качества :)))

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 09:30 


09/11/10
29
2 venco
Согласен.

-- Вт ноя 16, 2010 11:33:19 --

2 AlexNew
А если значения функции будут, скажем , 16 байт?

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 19:07 
Заслуженный участник


04/05/09
4582
Rino в сообщении #375800 писал(а):
2 venco
Согласен.
Тогда Вам придётся согласиться с тем, что не может быть архиватора, сжимающего любые данные. Что-то будет сжиматься, а что-то - наоборот, увеличится в размерах. Если же у Вас по формулам получается гарантированное сжатие, значит формулы неправильные.

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение16.11.2010, 19:09 
Аватара пользователя


28/06/08
1706
не знаю, с 16 битами я не писал код :)) попробуйте...
говорят что Фурье метод всегда дает ошибки, но для звука и изображение это не критично (частотное представление является более естественным.)
А вот в общем случае я думаю ничего путного не выйдет

-- Вт ноя 16, 2010 20:16:44 --

venco писал(а):
Тогда Вам придётся согласиться с тем, что не может быть архиватора, сжимающего любые данные. Что-то будет сжиматься, а что-то - наоборот, увеличится в размерах. Если же у Вас по формулам получается гарантированное сжатие, значит формулы неправильные.

странно что приходится доказывать такой очевидный тезис...
я думаю следует расматривать не просто архиватор а "Self Extracting" архиватор, тоесть входные данные отображаятся в программу которая сама распоковывается (даные -> .ехе).

-- Вт ноя 16, 2010 20:46:22 --

P.S.
Да, вопрос интересный: сколько нужно знаков после запятой/бит в коэффициентах Фурье чтобы без ошибки восстановить начальную функцию ???

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение20.11.2010, 13:59 
Заслуженный участник


08/04/08
8556
Rino писал(а):
На любую Вашу хитрость, можно ответить другой хитростью, которая будет вшита в программу, называемую архиватором.

Возьмем все возможные файлы длиной в 1 kb. Их может быть всего конечное число, обозначим его $m$. Пусть venco дает Вам последовательно по одному все файлы $f_j, j=1,...,m$длиной в 1 kb и предположим, что на каждый файл Вы выдумываете хитрый архиватор $M_j$, который сжимает файл хотя бы на 1 b. Каждый Ваш архиватор $M_j$ - это программа, закодированный алгоритм $A_j$. Обозначим содержимое входного файла $f$. Тогда существует следующая программа-архиватор $M$:
Код:
for(j=0;j<m;j++){
  if(f==f_j){
     A_j;
  }
}

Очевидно, что программа $M$ сжимает любой файл размером в 1 kb в файл меньшего размера. Однако файлов меньшего размера меньше, чем файлов в 1kb. Значит существуют различные файлы $f_{a}, f_{b}$, которые $M$ будет сжимать в одинаковые файлы. Значит $M$ не существует. Противоречие. Значит, Ваше предположение
Rino писал(а):
На любую Вашу хитрость, можно ответить другой хитростью, которая будет вшита в программу, называемую архиватором.

неверно.

(Оффтоп)

новый вид ферманьяков

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение20.11.2010, 14:35 


09/11/10
29
2 Sonic86
Ваши аргументы мне понятны. Но!
Где Вы учитываете размер самой программы архиватора? Она может быть намного больше килобайта по размеру.
Вроде как ограничений не было на размеры архиватора. Пусть она(они в Вашей терминологии) будет хоть гигабайт весить и она сожмёт таки все файлы 1к хотя бы на один байт.

 Профиль  
                  
 
 Re: Сжатие данных без потерь при помощи ряда Фурье
Сообщение20.11.2010, 15:52 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Rino в сообщении #377767 писал(а):
Вроде как ограничений не было на размеры архиватора. Пусть она(они в Вашей терминологии) будет хоть гигабайт весить и она сожмёт таки все файлы 1к хотя бы на один байт.
Ну не сможет она этого сделать, потому что она не сможет после этого разжать некоторые файлы однозначно. Давайте рассмотрим для примера не 1к-файлы, а двухбитовые. Хоть миллионогигабайтная программа не сможет однозначно сопоставить {00,01,10,11} и {0,1,""}.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 76 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Yules


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group