Сжатие данных без потерь при помощи ряда Фурье

[Bulinator]

Rino в сообщении #375617 писал(а):

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

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

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

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

[Rino]

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

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

Bulinator в сообщении #375636 писал(а):

Rino в сообщении #375617 писал(а):

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

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

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

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

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

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

[Rino]

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

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

[venco]

Rino в сообщении #375666 писал(а):

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

К каждому архиву своя программа?

[Rino]

venco в сообщении #375716 писал(а):

Rino в сообщении #375666 писал(а):

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

К каждому архиву своя программа?

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

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

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

[venco]

Rino в сообщении #375732 писал(а):

venco в сообщении #375716 писал(а):

Rino в сообщении #375666 писал(а):

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

К каждому архиву своя программа?

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

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

[Rino]

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

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

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

[venco]

Rino в сообщении #375751 писал(а):

Именно! Можно держать архиватор скажем на гигабайт. И пусть он делает свои дела...

Что "именно"? Размер такого персонального архиватора надо учитывать, как размер архива.

Rino в сообщении #375751 писал(а):

Ну не до нуля конечно

А что мешает?

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

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

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

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

[AlexNew]

Rino в сообщении #375595 писал(а):

AlexNew в сообщении #375545 писал(а):

Пример JPEG сжатие изображения, было у вас серенькое изображение, каждому пикселю соответствовал 1 байт (8 бит) . Потом вы применили дискретное преобразование Фурье, и вместо значений функции (последовательности байт) получили послд. коэффициентов ряда Фурье. Но тут есть проблема, для записи коэффициента Фурье не достаточно одного байта! ели использовать 1 байт то информация теряется, при обратном преобразовании не получить исходную функцию. Сжатие методом Фурье всегда происходит с потерями, даже если вы сохраняете все коэффициенты.
Как вы решили эту проблему?

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

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

[Rino]

2 venco
Согласен.

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

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

[venco]

Rino в сообщении #375800 писал(а):

2 venco
Согласен.

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

[AlexNew]

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

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

venco писал(а):

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

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

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

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

[Sonic86]

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 писал(а):

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

неверно.

(Оффтоп)

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

[Rino]

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

[Xaositect]

Rino в сообщении #377767 писал(а):

Вроде как ограничений не было на размеры архиватора. Пусть она(они в Вашей терминологии) будет хоть гигабайт весить и она сожмёт таки все файлы 1к хотя бы на один байт.

Ну не сможет она этого сделать, потому что она не сможет после этого разжать некоторые файлы однозначно. Давайте рассмотрим для примера не 1к-файлы, а двухбитовые. Хоть миллионогигабайтная программа не сможет однозначно сопоставить {00,01,10,11} и {0,1,""}.