LZW сжатие и словарь
Я смотрю на реализацию сжатия LZW в C++ и не уверен в лучшей реализации словаря.
Хеш-таблица имела смысл, но я не понимаю, как я смогу "переназначить" значения. Если таблица заполняется, мне нужно начать перезаписывать предыдущие (самые старые) записи из нескольких символов. Хэш-таблица потребовала бы от меня, чтобы я отслеживал их, находил, удалял и вставлял новый.
Какие-либо предложения?
4 ответа
То, что вы ищете, на самом деле две структуры данных вместе взятые:
- Хеш-таблица.
- Очередь FIFO (для удаления старых записей таблицы)).
Вы можете реализовать их самостоятельно, если вам нужна практика, как предлагают ваши комментарии, или использовать реализации stl/sgi/ C++11 (unordered_map - это фактическая карта хеша, либо через sgi или C++11, и очередь FIFO является двусвязным списком, таким как std::deque).
Идея состоит в том, что всякий раз, когда вы хотите отбросить самую старую словарную запись, вы извлекаете последний элемент в очереди, а затем также удаляете его из хеш-таблицы.
Утилита сжатия Unix (ссылка на исходный код) использует двойное хеширование и очистку периодической таблицы.
Если вы хотите быстрое сжатие и декомпрессию, то есть гораздо лучший выбор, чем LZW, который ужасно устарел. Вам следует взглянуть на быстрое сжатие 1-го уровня в zlib (возможно, уже на вашем компьютере), LZO и lz4.
Нет никаких причин писать новый код LZW, кроме как для учебной или развлекательной ценности. Это только исторический интерес. Вы также можете изучить утилиту сжатия для таких инструкций и развлечений.
Вы должны использовать две разные структуры для сжатия и распаковки.
При сжатии вы должны использовать Trie, поскольку вы должны искать в словаре по содержимому, а не по ключу.
При распаковке вы получаете доступ к словарю более обычным способом, то есть по ключу. Затем вы можете использовать любые структуры ассоциативных массивов. как хеш-таблицы или даже вектор / дек строк (так как ваши индексы являются последовательными натуральными числами).
Вы можете найти максимально эффективную реализацию памяти lzw с однонаправленной очередью здесь LZW-AB. Но, пожалуйста, обратите внимание, что это не будет хорошо работать с большими файлами.
Сегодня LZW может использоваться для поддержки древних веб-серверов, которые его поддерживают. Это решение должно идеально работать таким образом.