О сжатии случайных данных. Не гербалайф!
Вдогонку моей прошлой задаче - ее "случайный" вариант, в котором об оптимальности можно говорить строго.
У нас есть словарь из N строк, каждая строка - длиной M байт. Все символы - случайны, с равномерным распределением от 0 до 255.
Нужен алгоритм который позволит сжать-расжать словарь. Порядок строк в востановленном словаре неважен (т.е. главное, чтобы в декомпрессированном словаре было N строк, и между элементами исходного и декомпрессированного словаря можно было установить взаимно-ознозначное соответствие).
Требуется
1) определить теоретический предел компресии для произвольных N и M
2) спроектировать практический алгоритм, который даст наилуший ожидаемый коэффициент компрессии для заданных N и M
Задача (1) - несложная, а вот (2) - мне кажется более интересной.
У нас есть словарь из N строк, каждая строка - длиной M байт. Все символы - случайны, с равномерным распределением от 0 до 255.
Нужен алгоритм который позволит сжать-расжать словарь. Порядок строк в востановленном словаре неважен (т.е. главное, чтобы в декомпрессированном словаре было N строк, и между элементами исходного и декомпрессированного словаря можно было установить взаимно-ознозначное соответствие).
Требуется
1) определить теоретический предел компресии для произвольных N и M
2) спроектировать практический алгоритм, который даст наилуший ожидаемый коэффициент компрессии для заданных N и M
Задача (1) - несложная, а вот (2) - мне кажется более интересной.