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

[Rino]

Рассматривается задача сжатия данных без потерь при помощи разложения функции в ряд Фурье.
Дано: Функция, заданная в $k$ точках $x_1, x_2, x_3...x_k$: $f(x)=f_1, f_2, f_3...f_k$
Пусть, для наглядности, значения $f(x)$ будут целыми от 0 до 255. То есть для хранения $k$ значений функции потребуется $k$ байт.

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

$f(x)=\frac {a_0} 2$ +\sum\limits_{n=1}^\infty a_ncos\frac {\pi nx}k ; $a_0=\frac 2 k \int_{0}^k f(x)dx$ ; $a_n=\frac 2 k \int_{0}^k f(x)cos\frac {\pi nx}kdx$
после некоторых выкладок получим:

$a_0=\frac 2 k(f_1+f_2+f_3+...+f_k)$ $a_n=\frac 4 {\pi n}sin\frac{\pi n} {2k}(f_1cos\frac{\pi n} {2k}+f_2cos\frac{3\pi n} {2k}+f_3cos\frac{5\pi n} {2k}+...+f_kcos\frac{(2k-1)\pi n} {2k})$

К сожалению сумму $A=f_1cos\frac{\pi n} {2k}+f_2cos\frac{3\pi n} {2k}+f_3cos\frac{5\pi n} {2k}+...+f_kcos\frac{(2k-1)\pi n} {2k}$ свернуть не удалось. Разложив её в ряд Маклорена и перегруппировав получаем:

$a_n=\frac 4 {\pi n}sin\frac{\pi n} {2k}\left(f_1+f_2+f_3+...+f_k-\frac{(\frac{\pi n} {2k})^2} {2!}(f_1+3^2f_2+5^2f_3+...+(2k-1)^2f_k)+\frac{(\frac{\pi n} {2k})^4} {4!}(f_1+3^4f_2+5^4f_3+...+(2k-1)^4f_k)+...\right)$ или

$a_n=\frac 4 {\pi n}sin\frac{\pi n} {2k}\left(s_1-\frac{(\frac{\pi n} {2k})^2} {2!}s_2+\frac{(\frac{\pi n} {2k})^4} {4!}s_3+...\right)$ ну и, наконец,

$f(x)=\frac {1} k s_1 +\frac 4 \pi\sum\limits_{n=1}^\infty \frac 1 n sin\frac{\pi n} {2k}\left(s_1-\frac{(\frac{\pi n} {2k})^2} {2!}s_2+\frac{(\frac{\pi n} {2k})^4} {4!}s_3+...\right)cos\frac {\pi nx}k$

Применение формулы.
Дано $k$ значений функции(файл), например, $k=10000$
вычисляем нужное число сумм $s_i$ ,например, $i=100$. Сохраняем $s_i$ в файл-это будет архив. Когда нужно разархивировать используем последнюю формулу.

Значения функции $f$ могут быть и большими, в архиве хранится будут только $i$ сумм $s$
Придется использовать вычисления с большими числами.

В данное время пытаюсь оценить:

0. Применимо ли всё это на практике.(программу написал без Маклорена всё отлично сходится, теперь нужно с большими числами и разрядностью проверить)
1. Сколько сумм $s$ хранить в архиве при различных ОДЗ $f$
2. Какой должен быть $n$, чтобы можно было остановить процесс разархивации.

Пишите кому интересно..

[venco]

В формулах разбираться лень, поэтому возражение по идее.

Я правильно понял, что Вы утверждаете, будто этот алгоритм позволяет без потерь сжать произвольные 10000 байт в ("например") 100?

Безотносительно к алгоритму это просто невозможно. Даже в 9999 байт.

[Rino]

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

В формулах разбираться лень, поэтому возражение по идее.

Я правильно понял, что Вы утверждаете, будто этот алгоритм позволяет без потерь сжать произвольные 10000 байт в ("например") 100?

Безотносительно к алгоритму это просто невозможно. Даже в 9999 байт.

Не правильно. Пока это теория.
Но я считаю, что возможно придумать формулу для эффективного, в разумных пределах сжатия, пускай и с потерей по времени. Сжать 10000 байт в 100 уж точно не получится ввиду необходимости хранения коэффициентов Фурье, которые будут довольно большими(я имею ввиду $s$).
Суть алгоритма в том, что мне удалось построить формулу "почти" не зависящую от количества входной информации.

[Circiter]

Чем-то похоже на дельта-компрессию. :)

[Rino]

Circiter в сообщении #374094 писал(а):

Чем-то похоже на дельта-компрессию. :)

Нет. Это совершенно не то. Дельта-компрессия это, имхо, оператор подготовки к последующему сжатию.
PS Я защищал дипломную по сжатию данных. Был создан архиватор, с небольшим, но сжатием примерно в 1.3 раза, но на основе формулы и без зависимости от исходных данных. mp3 сжимал но за счет потерь времени.

[venco]

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

Был создан архиватор, с небольшим, но сжатием примерно в 1.3 раза, но на основе формулы и без зависимости от исходных данных. mp3 сжимал но за счет потерь времени.

Зависит от mp3 файла. Mp3 с постоянным bit-rate могут содержать большое количество байтов 0xff. Не удивлюсь, если Вы нашли файл, в котором четверть таких байтов.
Принципиально невозможен архиватор без потерь, который мог бы сжимать любые данные. Если у Вас такое получилось - ищите ошибку.

[Rino]

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

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

Был создан архиватор, с небольшим, но сжатием примерно в 1.3 раза, но на основе формулы и без зависимости от исходных данных. mp3 сжимал но за счет потерь времени.

Зависит от mp3 файла. Mp3 с постоянным bit-rate могут содержать большое количество байтов 0xff. Не удивлюсь, если Вы нашли файл, в котором четверть таких байтов.
Принципиально невозможен архиватор без потерь, который мог бы сжимать любые данные. Если у Вас такое получилось - ищите ошибку.

я такого и не говорил). Хотя...возьмусь утверждать, что смогу сжать любые данные больше одного килобайта...хотябы на один байт :)

[venco]

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

Хотя...возьмусь утверждать, что смогу сжать любые данные больше одного килобайта...хотябы на один байт :)

Это принципиально невозможно.

[Rino]

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

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

Хотя...возьмусь утверждать, что смогу сжать любые данные больше одного килобайта...хотябы на один байт :)

Это принципиально невозможно.

А вот как раз это возможно. Когда известна структура сжимаемых данных, под неё уже можно создать сжимающий алгоритм.
Но всё таки о теории хотелось бы поговорить...

[venco]

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

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

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

Хотя...возьмусь утверждать, что смогу сжать любые данные больше одного килобайта...хотябы на один байт :)

Это принципиально невозможно.

А вот как раз это возможно. Когда известна структура сжимаемых данных, под неё уже можно создать сжимающий алгоритм.
Но всё таки о теории хотелось бы поговорить...

Это как раз теория.
Вариантов входных файлов длины 1024 байт - $2^{8192}$.
Вариантов выходных файлов длины меньше 1024 байт - $\frac {2^{8192}-1}{2^8-1} < 2^{8192}$.
Соответственно, обязательно найдутся два входных файла, которым соответствуют одинаковые сжатые данные. Значит, распаковать эти данные Вы не сможете.

[Rino]

Я Вас понял. А архиваторы Вы совсем отменили?

[venco]

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

А архиваторы Вы совсем отменили?

Каким образом Вы сделали такой вывод из моих слов.

И по существу есть возражения?

[Rino]

Здесь дело вот в чём. Байты байтами, а интерпретация того что в архиве может быть разной. Например, в архиве может быть один байт, несколько...О чем они Вам расскажут? Да ни о чём. Они расскажут только разработчику.
Для одного разработчика этот байт будет означать Войну и мир. Для другого всю эпопею Звёздных войн. Аналогию понимаете? Одинаковые архивы Могут привести к разным данным, при наличии соответствующих программ-алгоритмов.

[Xaositect]

Суть в том, что любая конкретная программа-алгоритм некоторые файлы сжимает, а некоторые увеличивает. И от этого никуда не уйти.

[Rino]

Xaositect в сообщении #374212 писал(а):

Суть в том, что любая конкретная программа-алгоритм некоторые файлы сжимает, а некоторые увеличивает. И от этого никуда не уйти.

А я что говорю противное? Я придумал новый алгоритм прошу его оценить, прочитайте хотя бы , написал доступно, вроде)...