2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5, 6  След.
 
 Сжатие данных без потерь при помощи ряда Фурье
Сообщение12.11.2010, 14:33 


09/11/10
29
Рассматривается задача сжатия данных без потерь при помощи разложения функции в ряд Фурье.
Дано: Функция, заданная в $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$, чтобы можно было остановить процесс разархивации.

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

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


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

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

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

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


09/11/10
29
venco в сообщении #374043 писал(а):
В формулах разбираться лень, поэтому возражение по идее.

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

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


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

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


26/07/09
1559
Алматы
Чем-то похоже на дельта-компрессию. :)

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


09/11/10
29
Circiter в сообщении #374094 писал(а):
Чем-то похоже на дельта-компрессию. :)

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

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


04/05/09
4582
Rino в сообщении #374120 писал(а):
Был создан архиватор, с небольшим, но сжатием примерно в 1.3 раза, но на основе формулы и без зависимости от исходных данных. mp3 сжимал но за счет потерь времени.
Зависит от mp3 файла. Mp3 с постоянным bit-rate могут содержать большое количество байтов 0xff. Не удивлюсь, если Вы нашли файл, в котором четверть таких байтов.
Принципиально невозможен архиватор без потерь, который мог бы сжимать любые данные. Если у Вас такое получилось - ищите ошибку.

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


09/11/10
29
venco в сообщении #374136 писал(а):
Rino в сообщении #374120 писал(а):
Был создан архиватор, с небольшим, но сжатием примерно в 1.3 раза, но на основе формулы и без зависимости от исходных данных. mp3 сжимал но за счет потерь времени.
Зависит от mp3 файла. Mp3 с постоянным bit-rate могут содержать большое количество байтов 0xff. Не удивлюсь, если Вы нашли файл, в котором четверть таких байтов.
Принципиально невозможен архиватор без потерь, который мог бы сжимать любые данные. Если у Вас такое получилось - ищите ошибку.

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

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


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

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


09/11/10
29
venco в сообщении #374165 писал(а):
Rino в сообщении #374155 писал(а):
Хотя...возьмусь утверждать, что смогу сжать любые данные больше одного килобайта...хотябы на один байт :)
Это принципиально невозможно.

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

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


04/05/09
4582
Rino в сообщении #374177 писал(а):
venco в сообщении #374165 писал(а):
Rino в сообщении #374155 писал(а):
Хотя...возьмусь утверждать, что смогу сжать любые данные больше одного килобайта...хотябы на один байт :)
Это принципиально невозможно.

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

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


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

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


04/05/09
4582
Rino в сообщении #374201 писал(а):
А архиваторы Вы совсем отменили?
Каким образом Вы сделали такой вывод из моих слов.

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

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


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

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


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

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


09/11/10
29
Xaositect в сообщении #374212 писал(а):
Суть в том, что любая конкретная программа-алгоритм некоторые файлы сжимает, а некоторые увеличивает. И от этого никуда не уйти.

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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