| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Избыточность при кодировании состояния. |
| Автор: semibug 30.4.2011, 16:13 |
| Имеем 256 коробок, в которых находятся карточки с числами из набора 0..255 (расбросаные по одной в каждую коробку, случайно). Необходимо сохранить состояние (в какой коробке какая карточка) в меньшем нежели 256 байт объеме информации. |
| Автор: Lipetsk 30.4.2011, 16:51 |
| легко в 255 байт!!! 256-ой получается из 255-ти |
| Автор: semibug 30.4.2011, 17:13 |
| Хочется ещё меньше, по тому же принципу. т.е. к примеру в первой коробке может быть один из 256 вариантов , во второй коробке уже 255, в следующей 254 и т.д. Соответственно под каждую коробку выделять по байту - излишне. |
| Автор: Pavia 30.4.2011, 17:17 |
| semibug, Сжимать можно только те последовательности у которых есть за закономерности. А тут последовательность случайна. Добавлено через 3 минуты и 50 секунд А сори не подумал. Есть тут закономерность. Можно построить дерево и закодировать дерево путем обхода дерева. Выбо левой или правой вершины определяет единичка или нолик соответственно получится 256 бит. |
| Автор: _Y_ 30.4.2011, 17:28 |
| Lipetsk, ответ рулит! Думаю можно сжать еще больше. Самый простой вариант - любой алгоритм сжатия информации. Наверняка хоть чуть, а сожмет. Или вот такой странный вариант (на лету придумываю - могу и наврать): 1. Представляем коробки как 256-элементный массив типа байт. 2. Далее начинаем паковать информацию в память. В первые 128 байт памяти загоняем номера коробок, содержащих карточки с номерами от 0 до 127. В каждый байт памяти по номеру коробки. Т.е. потратили Байт*128=1024бита памяти. 3. Убираем из массива коробки, номера которых уже сохранены в памяти. Остается массив из 128 коробок. 4. Т.к. максимальный номер элемента в оставшемся массиве коробок =127, для хранения номеров (после перенумерации) достаточно 7-бит на номер. 5. Записываем еще 64 номера в 7-битном формате, убираем учтенные коробки из массива. Потратили еще 7бит*64=448 бит. 6. Теперь в массиве осталось 64 коробки. 6-бит достаточно. 7. Регистрируем еще 32 коробки в 6-битном формате. Тратим еше 192 бита. 8. Убираем зарегистрированные. Регистриуем 16 коробок в 5-битном формате. Еще 80 бит. 9. Убираем зарегистрированные. Регистриуем 8 коробок в 4-битном формате. Еще 32 бита. 10. Убираем зарегистрированные. Регистриуем 4 коробоки в 3-битном формате. Еще 12 бит. 11. Регистриуем 2 коробоки в 2-битном формате. Еще 4 бита. 12. Регистриуем 1 коробоку в 1-битном формате. Еще 1 бит. 13. Оставшаяся коробка находится там, гду ей указано Lipetsk-ом. 14. Итого потратили 1024+448+192+80+32+12+4+1=1793, коее число бит лекго помещается в 225 байт, да еще и огромный хвост от последнего байта останется. |
| Автор: semibug 30.4.2011, 18:07 |
| _Y_, cool, выглядит жизнеспособно. Развивая мысль, пытаюсь определить теоретический предел - для 256 коробок в результате перестановок получаем 256! вариантов (8,578177753×10⁵⁰⁶), если я правильно помню математику. Такое число укладывается в 211 байт. Но с какого боку подойти, чтобы преобразовать исходные данные в эти 211 байт идей нет ( |
| Автор: maxim1000 30.4.2011, 18:54 |
| да просто посчитать номер перестановки и его закодировать в битах номер можно посчитать, как число в специфической системе счисления - у которой основание меняется от разряда к разряду i[0]+255*i[1]+255*254*i[2]+... i[k] - номер карточки в коробке k, но с учётом пропусков уже использованых карточек например, если i[0]=5, то i[1] будет соответствовать номеру карточки, если он меньше 5, и отличаться на 1, если он больше 5 |
| Автор: esperanto 30.4.2011, 22:29 |
| Достаточно пронумеровать в лексикографисеском порядке все разложения и вернуть номер разложения. |