Вы можете говорить о сжатии чего-либо, только если у вас есть дистрибутив и представление.Это вопрос словаря, который вы должны отправить: вам всегда нужен какой-то словарь протокола для распаковки чего-либо.Просто так получилось, что такие вещи, как .zip и .mpeg, уже имеют эти словари / кодеки.Даже такая простая вещь, как кодирование по Хаффману, является алгоритмом;на другой стороне канала связи (вы можете думать о сжатии как о связи), у другого человека уже есть немного кода (словарь) для выполнения схемы декомпрессии Хаффмана.
Таким образом, вы даже не можете начатьпоговорим о сжатии чего-либо, не думая сначала «какие матрицы я ожидаю увидеть?», «действительно ли данные случайны или есть порядок?», и если да, то «как я могу представить матрицы, чтобы воспользоваться преимуществами порядка вданные? ".
Вы не можете сжать некоторые матрицы, не увеличив размер других объектов (по крайней мере, на 1 бит).Это плохая новость, если все матрицы одинаково вероятны, и вы одинаково заботитесь обо всех них.
Дополнения:
Ответ на использование механизма разреженных матриц не обязательноправильный ответ.Например, матрица может быть представлена в python как [[(r+c)%2 for c in range (cols)] for r in range(rows)] (шаблон шахматной доски), и разреженная матрица вообще не будет сжимать ее, но сложность матрицы по Колмогорову - это длина программы, описанная выше.
Ну, я знаю, что каждая матрица будет иметь одинаковое количество единиц, так что это своего рода детерминизм.Единственное, что я не знаю, это где 1.Кроме того, если я передаю матрицу со словарем и возникают пакетные ошибки, возможно, словарь будет затронут, так что ... не будет ли полученная информация повреждена?Вот почему я пытался использовать сжатие данных без потерь, такое как длина цикла, декодеру просто не нужен словарь.- оригинальный плакат
Сколько единиц составляет матрица в виде доли от ее размера и каков ее размер (NxN - что такое N)?
Кроме того, это неверное утверждение, и его не следует использовать в качестве причины для желательного кодирования по длине прогона (для которого все еще требуется программа);когда вы передаете данные по каналу, вы всегда можете добавить исправление ошибок в эти данные.«Данные» - это просто кусочек.Вы можете передавать как данные, так и любые необходимые словари по каналу.Механизм исправления ошибок совершенно не заботится о том, для чего предназначены передаваемые вами биты.
Приложение 2:
Существуют (14*14) choose 20 возможные схемы, которые, как я полагаю,выбираются случайным образом.Если бы это число было больше 128^2, то то, что вы пытаетесь сделать, было бы невозможно.К счастью log_2((14*14) choose 20) ~= 90bits < 128bits, так что это возможно.
Простое решение записать 20 чисел, таких как 32,2,67,175,52,...,168, не будет работать, потому что log_2(14*14)*20 ~= 153bits > 128bits.Это было бы эквивалентно кодированию по длине прогона.Мы хотим сделать что-то подобное, но у нас очень строгий бюджет и мы не можем позволить себе быть «расточительными» с битами.
Поскольку вы одинаково заботитесь о каждой возможности, ваша «словарь» / «программа» будет имитироватьгигантский справочный стол. Реализация Matlab с разреженной матрицей может работать, но она не гарантированно работает и поэтому не является правильным решением.
Если вы можете создать биекцию между диапазоном чисел [0,2^128) и подмножествами размера 20ты в порядке.Это соответствует перечислению способов спуска пирамиды в http://en.wikipedia.org/wiki/Binomial_coefficient до 20-го элемента строки 196. Это то же самое, что и перечисление всех «k-комбинаций».См. http://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations
К счастью, я знаю, что Mathematica, Sage и другое программное обеспечение CAS, по-видимому, могут генерировать "5-е" или "12-е" или произвольно пронумерованное k-подмножество.Просматривая их документацию, мы сталкиваемся с функцией под названием «rank», например, http://www.sagemath.org/doc/reference/sage/combinat/subset.html
. Затем мы проводим дополнительный поиск и сталкиваемся с каким-то загадочным кодом Фортрана, таким как http://people.sc.fsu.edu/~jburkardt/m_src/subset/ksub_rank.m и http://people.sc.fsu.edu/~jburkardt/m_src/subset/ksub_unrank.m
Мы могли бы перепроектировать его, но он довольно плотный. Но теперь у нас достаточно информации для поиска k-subset rank unrank, что приводит нас к http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf - см. Раздел
«Генерация k-подмножеств (из n-множества): лексикографическая
Упорядочивание "и алгоритмы rank и unrank на следующих нескольких страницах.
Чтобы достичь точного теоретически оптимального сжатия, в случае равномерно случайного распределения 1 с, мы должны, таким образом, использовать эту технику, чтобы подвести наши матрицы к нашему выходному числу в диапазоне <<code>2^128. Так уж сложилось, что комбинации имеют естественный порядок, известный как ранжирование и расстановка комбинаций. Вы назначаете номер для каждой комбинации (рейтинг), и если вы знаете номер, вы автоматически знаете комбинацию (unranking). Поиск в Google k-subset rank unrank, вероятно, приведет к другим алгоритмам.
Таким образом, ваше решение будет выглядеть так:
serialize the matrix into a list
e.g. [[0,0,1][0,1,1][1,0,0]] -> [0,0,1,0,1,1,1,0,0]
take the indices of the 1s:
e.g. [0,0,1,0,1,1,1,0,0] -> [3,5,6,7]
1 2 3 4 5 6 7 8 9 a k=4-subset of an n=9 set
take the rank
e.g. compressed = rank([3,5,6,7], n=9)
compressed==412 (or something, I made that up)
you're done!
e.g. 412 -binary-> 110011100 (at most n=9bits, less than 2^n=2^9=512)
to uncompress, unrank it