У меня есть строка из 1 и 0, в которой количество 1 и 0 одинаково. Я хотел бы сжать это число, которое меньше по количеству бит, необходимых для его хранения. Кроме того, преобразование между сжатой формой и не сжатой формой не требует большой работы.Сжатие строки из 1 и 0, содержащих то же число 1, что и 0
Например, при заказе всех возможных строк и их нумерации и при условии, что это число будет сжатым, будет слишком много работать.
Простым решением было бы позволить сжатым данным быть только первыми n-1 символами строки, где строка имеет длину n. Преобразование между сжатыми и распакованными данными было бы простым, но это обеспечивает небольшое сжатие, только один бит на строку.
Мне нужен алгоритм, который бы сжимал строку с этим свойством (такое же количество единиц и нулей), которое может быть обобщено на строку с любой четной длиной. Мне также хотелось бы сжать больше, чем описанный выше метод.
Спасибо за помощь.
«Например, упорядочить все возможные строки и пронумеруть их и дать этому числу сжатые данные будет слишком много работать». Слишком много работы по преобразованию двоичной строки в целое число? – Blorgbeard
[Java one-liner] (http://stackoverflow.com/questions/17833463/how-do-you-convert-a-binary-number-to-a-biginteger-in-java) – Blorgbeard
нет, но заказать все возможные строки - это слишком много работы. например, строки длиной 10, вы можете сделать 0000011111 первой строкой, чтобы она была сжата до 0, вторая может быть 0000101111 и так далее. для преобразования между ними было бы много работы. Превращение двоичной строки в целое число, как вы предлагали, не сжимало бы данные, оно все равно занимало бы такое же количество бит. – mathew