Решил не мелочиться, и продолжить парад хороших идей. В этот раз мы разбираем модель передачи данных позволяющую их сжимать. Суть метода в заглавии: нам интересны не только сами данные но и время их прибытия, и в зависимости от времени их кодирование будет меняться. Для лучшего понимания смотрим на пример с картиночки:

https://imgur.com/a/aDnPMUF

Рассмотрена простейшая модель сети. Есть сервер, к серверу подключены два клиента, клиенты не сообщаются друг с другом. В некий момент времени сервер начинает передавать одинаковые данные своим клиентам. Ширина канала по сути 2бита в сек. Как бы сервер передавал без схемы сжатия? Просто бы поделил канал на количество клиентов и подал все как есть. Конкретно для этой последовательности 16 бит: каждый клиент получает 16 бит за 16 секунд, общее количество переданных данных 32 бита. А теперь представим что у клиентов есть таблица перевода, допустим её когда-то передали им отдельно. Тогда, смотрим на картиночку, получается что используя подобную схему кодирования каждый клиент получает 8 бит за 9 секунд, а общее количество переданных данных будет 16 бита. Данная схема не самая оптимальная, самая передала бы за 8 сек. Оптимальность таблицы зависит от самих данных, строятся оптимальные таблицы обратным образом, просто прикидываешь что в какую секунду и кому должно было передаться. Ну это по времени оптимальное, если оптимизировать по общему количеству переданных бит для данной последовательности то получиться: передано 2 бита, по биту на каждого, за где-то в районе 2^16 секунд. Почему это работает: мы передаем одни и те же данные в одно и то же время, а это избыточно, и её можно сократить

Ну что, как идея? Не у кого нет желания разработать теорию полностью, для любой ширины канала и любого количества клиентов? Я этого делать не буду, ибо мне не платят и Phd защищать мне тоже не нужно.

Кстати, факт из разряда очевидного-невероятного: для передачи\обработки высокого сигнала «1» нужно больше энергии чем для низкого «0». Буквально можно проверить, взять и забить всю оперативку в одном случае нулями а в другом единицами и сравнить энергопотребление.

В своей основе вопрос сжатия это принцип Дирихле: вот у нас строки большого размера, их больше, вот у нас строки меньшего размера, их соответственно меньше. количество клеток не совпадает с количеством голубей, ничего не получается, все расходимся? А вот и нет, можно добиться равенства, причем двумя путями: или меньше голубей, или больше клеток.

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).

Остается только реализовать это все в софте. А вот это я не умею. Может кто-нибудь напишет?