Мотивация
Представьте себе сжатый файл Хаффмана, который загружается частично, как в программном обеспечении P2P, поэтому мы сначала выделяем место на диске для всего файла, а затем начинаем загрузку случайных кусков файла. Один из кодов Хаффмана (но мы не знаем, какой именно) является кодом конца, поэтому, если этот код декодируется, мы останавливаемся. Предполагая, что файл состоит из нескольких сжатых потоков Хаффмана, мы можем попытаться распаковать некоторые из них до завершения загрузки.
Способ предварительного выделения дискового пространства теперь важен: давайте предположим, что у нас есть начало потока Хаффмана, но он не завершен, поэтому мы сталкиваемся с предварительно выделенным дисковым пространством. Обычно это пробел равен 0, поэтому мы продолжаем декодировать символы с кодом Хаффмана 00... Если это не наш конечный код, мы не замечаем «неверные» данные и т. Д. если есть 2 ГБ заранее выделенного пространства, мы делаем много бесполезного декодирования.
Таким образом, мы хотели бы предварительно распределить пространство таким образом, чтобы декодирование было остановлено как можно скорее.
Вопрос
Я ищу самую короткую цепочку битов, которая действует как «терминатор Хаффмана». Это означает, что если мы декодируем эту строку, мы декодируем каждый код Хаффмана хотя бы один раз, поэтому мы обязательно получим код конца. Это должно работать для каждой комбинации кодов Хаффмана длиной 1..n бит.
Примечание: я знаю, что есть простые решения для гипотетического сценария выше (использование 00.. в качестве конечного кода, использование данных сегмента P2P для обнаружения фрагментов, еще не загруженных), но это только примерный сценарий, демонстрирующий теоретическое использование цепочки битов "терминатора Хаффмана", я не заинтересован в решении этого сценария, но ищу алгоритмы / способы / идеи для генерации / поиска цепочек битов, которые действуют как "терминатор Хаффмана".
Пример
Давайте рассмотрим возможные комбинации кодов Хаффмана для n = 2: [0, 1], [00, 01, 1], [0, 10, 11], [00, 01, 10, 11]. Теперь давайте начнем с цепочки битов, которая содержит все возможные битовые последовательности длиной 1..n (0, 1, 00, 01, 10, 11):
001011
Декодирование с использованием различных комбинаций кодов Хаффмана дает (коды Хаффмана присваиваются символам A..D):
Combination Decoded symbols
[0, 1] AABABB
[00,01,1] ACBC
[0,10,11] AABC
[00,01,10,11] ACD
Это хорошее начало, и оно уже декодирует каждый код Хаффмана для первых трех, но если мы декодируем его с помощью [00, 01, 10, 11], мы пропускаем символ B (код Хаффмана 01). Итак, давайте просто добавим это к нашей цепочке:
00101101
Это действительный «терминатор Хаффмана» для n=2, длиной 8 бит. Если бы мы распределили наше дисковое пространство этим байтом, мы бы обязательно завершили все коды Хаффмана, которые не превышают 2 бита. Мы даже знаем, что не будет более коротких терминаторных строк для n=2, потому что это минимальная длина комбинации [00, 01, 10, 11] для декодирования каждого символа один раз.
Я также нашел «терминатор Хаффмана» для n=3, 0001011001110100111010011100010101111101110 (43 бита), но я не уверен на 100%, верен ли он, и я не знаю, является ли он самым коротким.
Что я ищу
Алгоритмы / идеи для поиска или генерации терминаторов Хаффмана для заданного n. Моя попытка была бы похожа на пример: генерирование стартовой строки и добавление битов, необходимых для удовлетворения всех различных комбинаций кода Хаффмана. Но я уверен, что есть лучшие способы.
Определенные терминаторы Хаффмана, n=8 и n=16, хотя их генерация может быть вычислительно дорогой, и они, возможно, будут очень длинными.
Статьи / ссылки об этой проблеме (или аналогичные), если таковые имеются.
Бонус
Бонусные баллы за нахождение «терминаторов Хаффмана», которые также работают, если мы начинаем с позиции бита 1..n, поэтому он даже заканчивается, если данные были декодированы ранее, и мы не прибудем и не начнем новый код Хаффмана с первого бита.