Теория почему сжатие данных дальше сокращения избыточности возможно
В своей основе вопрос сжатия это принцип Дирихле: вот у нас строки большого размера, их больше, вот у нас строки меньшего размера, их соответственно меньше. количество клеток не совпадает с количеством голубей, ничего не получается, все расходимся? А вот и нет, можно добиться равенства, причем двумя путями: или меньше голубей, или больше клеток.
1)меньше голубей: Вот у нас множество всех строк, или файлов - вопрос интерпретации, длинны N. Мощность такого множество соответственно 2^N. Теперь посмотрим на множество всех строк длин (N-1) и (N-2) и...(1). Мощность этого множество будет ∑2^N, где N от (N-1) до (1), и равно это 2^N-2. Сравниваем мощности множеств, первое больше на два элемента. Ну а теперь финт ушами - мы просто берем и выкидываем два элемента из первого множества, для удобства это строки состоящие только из 0 или 1. И опаньки, биекция, если не верите можете прям на бумажке нарисовать и сравнить. И что получили в итоге? Получили что любую, кроме двух, строк можно переписать в виде минимум на один бит короче. Убрали бы больше элементов, сократили бы еще сильнее, это просто самый простой вариант.
2)больше клеток: Возьмем множество всех строк длинны от N до 1. Зададим функцию F(n), и обратную ей G(n), которая берет на вход один элемент и выдает другой. Во общем то все. F(n) функция абсолютно арбитрарная, просто применяешь F(n) несколько раз, пока нужный результат не получишь и все. Другое дело что хотелось бы побыстрее, поэтому -
2.1)столько же клеток, но в другом порядке: Вот возьмем множество всех строк размера N и упорядочим его следующим образом. Для этого мы берем функцию X(n), делает она следующие - берет бинарную строку и возвращает натуральное число от 1 до 2^N. Как она должна его считать честно не знаю, но она должна делать что-то приблизительно следующие: строим бинарное дерево(?) сравнений, сначала сравниваем половинки строки друг с другом. потом четвертинки, и вот тут уже не знаю, нужно ли сравнивать каждую с каждой или хватит сравнений 1 к 2, и 3 к 4. потом осьмушки итд. в конце сравниваем соседние биты, вот тут каждый с каждым точно лишнее. Потом переводим эти сравнения в значения с весами, например строки в которых есть повторения половинок должны быть ниже чем те у которых повторяются четвертинки, а те у которых нет повторений ни четвертинок ни половинок должны стоять выше, ближе к началу, к числу 1. Потом делаем над этими значениями некие операции и ВЖУХ! получаем натуральное число, он же порядковый номер. К примеру если N=8, то строка 11111111 должна иметь номер 256, строка 00000000 номер 255, строка 11111110 номер 254 итд. Вот что это за ВЖУХ! и нужно выяснить. Сначала я думал что можно просто обойтись тем что можно представить строку как число сочетаний из количества единиц по N, и все сочетания, где количество единиц приближается к половине длинны, просто поставить спереди, но потом прикинул что например строка 00001111 при таком подходе будет стоять выше чем строка 00101001, а это фатальный недостаток. Ну вот, допустим выясняли как ВЖУХ! выглядит, нашли порядковый номер в упорядоченном по повторениям списке. А теперь просто подставляем вместо этой строки другую строку с тем же номером, но в списке упорядоченном просто лексикографически. Ну а дальше например отправляешь данную строку в метод 1). Остается только реализовать это все в софте.
Обсуждения, предложения, критика, или вы просто жидомасон любящий позанюхивать газообразные продукты работы кишечника приветствуются.