Сжатие строки из 1 и 0, содержащих то же количество 1, что и 0

Question

У меня есть строка из 1 и 0, в которой число 1 и 0 одинаковы. Я хотел бы сжать это в число, которое меньше с точки зрения количества битов, необходимых для его хранения. Кроме того, преобразование между сжатой формой и несжатой формой не требует большой работы.

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

Простым решением было бы позволить сжатым данным быть только первыми n-1 символами строки, где строка имеет длину n. Преобразование сжатых и распакованных данных было бы простым, но это обеспечивает небольшое сжатие, только один бит на строку.

Я хотел бы алгоритм, который сжимал бы строку с этим свойством (то же самое число единиц и нулей), который может быть обобщен до строки с любой четной длиной. Я также хотел бы сжать больше, чем метод, описанный выше.

Спасибо за помощь.

Answer 1

Это проблема комбинирования, N предметов, взятых по k за раз.

В вашем комментарии в качестве примера длины 10, взятой по 5 за раз, подразумевается, что существует только 252 уникальных паттерна. Который может вписываться в 8-битное значение вместо 10-битного. СМОТРИТЕ: ВИКИ: Комбинации

Расширяя индексированное значение от 0 до 251, здесь есть примеры:

СМ. Алгоритм возврата всех комбинаций k элементов из n.

При извлечении вы можете использовать извлеченное значение, чтобы установить битовую позицию в восстановленном значении, которое составляет O(1) время на расширение. Если список не равен миллионам +, вы можете предварительно вычислить таблицу поиска, которая намного быстрее преобразует значение индекса в декодированное значение. IE: составить список всего возможного и поискать перевод.