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

[Rino]

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

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

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

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

Опять же к старому возвращаемся. Речь шла о том, что каждому конкретному файлу пишется своя программа сжатия. вот и всё.

[venco]

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

Речь шла о том, что каждому конкретному файлу пишется своя программа сжатия. вот и всё.

Как получатель архива узнает, какую программу использовать для распаковки?

[sf1]

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

[Xaositect]

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

Опять же к старому возвращаемся. Речь шла о том, что каждому конкретному файлу пишется своя программа сжатия. вот и всё.

В этом случае верно.

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

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

В этом - нет.

[Евгений Машеров]

Очень долгая дискуссия на ту же тему:
http://forum.ixbt.com/topic.cgi?id=40:515

[erwins]

jpeg

[Евгений Машеров]

JPEG это сжатие с потерями...

[profrotter]

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

Рассматривается задача сжатия данных без потерь при помощи разложения функции в ряд Фурье.

С потерями.

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

Разложим функцию в ряд Фурье. (доопределив её так, как нам нужно)
$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$

Теперь смотрите какой фокус получился. Когда вы раскладываете вашу сумму

$$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}$$

в ряд Маклорена, вы должны этим самым рядом удовлетворительно представить все косинусы. Самый мощный в этой ситуации $cos\frac{(2k-1)\pi n} {2k}$. Сколько периодов этого косинуса укладывается на интервале разложения? И сколько членов ряда Маклорена потребуется лишь для того, чтобы представить один период косинуса? Потому имею предположение, что количество сумм $s$ окажется больше исходного количества отсчётов.

[Kallikanzarid]

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

Разложим функцию в ряд Фурье. (доопределив её так, как нам нужно)

$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$

Осталась самая малось: научиться хранить в компьютере произвольные вещественные числа и бесконечные ряды. Какой вы умный

-- Вт авг 02, 2011 14:16:54 --

Предлагаю супер-пупер алгоритм сжатия: для каждого текста пишем программу, в которую он зашит - таким образом, сжимая его до нуля! Где мой Филдз?!!!!!111

[Chifu]

А БПФ, терему Котельникова курили? Другие более подходящие для цифровых данных ортогональные функции, например Уолша?

[Kallikanzarid]

Chifu в сообщении #472819 писал(а):

Другие более подходящие для цифровых данных ортогональные функции, например Уолша?

Я думаю, поциент курил немного другие субстанции

[Pj.midgard2000]

Как известно x!#x/2 получается одного стека не хватает все ровно бывают не сжимаемые файлы где определенные части не сжимаются и даже при перев кладке не втиснуться, то могут на наоборот увеличиться, то есть тогда у вас на те же данные будут получатся разные варианты, а то есть не соответствует правилам архиваторов.

[Lia]

Pj.midgard2000
Замечание за бессодержательный некропостинг.

[Pj.midgard2000]

Замечание данная статье люди писали полную чушь про сжатие

[Lia]

Pj.midgard2000
Замечание за использование голословных тезисов.

Обратите внимание, пожалуйста, на название темы.