Эффективный алгоритм (ы) для сжатия строк, содержащих пути файлов Windows

Question

Мне нужно разработать эффективный способ кодирования/декодирования нескольких строк, содержащих пути файлов Windows, например. C: \ Users \ Public \ Documents \ CompanyName \ ApplicationName \ VersionNumber \ Filename.ext во встроенной системе с ограниченным долгосрочным хранением.

В настоящее время мы берем 3 символа и преобразуем их в единственное уникальное целое число, которое мы затем храним в одном из регистровых мест. Поскольку для всего блока имеется всего ~ 500 мест для хранения, совершенно очевидно, что использование 1 регистра для 3 символов не является хорошим решением.

документооборота Применение:

1. Пользователь выбирает файл на компьютере с ОС Windows.
2. Имя файла закодировано, как описано выше, и отправляется во встроенную систему вместе с другой информацией (не связанной с именем файла) в сохраненное хранилище.
3. Оператор выбирает, когда следует выполнить информацию, отправленную на шаге 2. Это может быть далеко в будущем.
4. Встроенная система выполняет операции.
5. Информация (включая декодированное имя файла) отправляется обратно на ПК с ОС Windows.
6. Windows PC обновляет файл с результатами операции.

Примечания:

1. Обработка питания (ЦП) не является препятствием для этой смешанной системы (Windows PC и встраиваемых систем). В настоящее время мы выполняем кодирование на ПК с ОС Windows и декодирование встроенной системы, но этого не должно быть.
2. Пути файлов Windows обычно находятся в 1 из нескольких мест, но клиент может изменить местоположение файла по умолчанию на все, что захочет, и они часто это делают.
3. Пересмотренный алгоритм, скорее всего, будет реализован на C++.

Что было бы хорошим алгоритмом для этого кодирования/декодирования?

Пожалуйста, дайте мне знать, если я забыл какие-либо важные детали. Я старался быть настолько тщательным, насколько это возможно, но сжатие - это не мой опыт.

Answer 1

Поскольку в именах путей есть много подобных префиксов, вы можете использовать trie. Это экономит много места, и это также быстро для поиска. В Интернете существует множество бесплатных реализаций, и их реализация также проста.

Вот немного больше объяснений, почему это полезно. Пусть рассмотрим каждый путь к файлу как одну строку. Многие из этих строк имеют общий префикс, например. строка C:\Users\Public\Documents\ появится очень часто. Это может быть, даже в том случае у вас есть что-то вроде

C:\Users\Public\Documents\file1 
C:\Users\Public\Documents\file2 
..... 
C:\Users\Public\Documents\file10000 

Тогда весь приставкой C:\Users\Public\Documents\file появляется во многих файлах и нам не нужно, чтобы спасти их всех. Но мы также не знаем, как выглядит структура (так как она динамическая, а не статическая), поэтому мы не можем записать жесткий код префикса x. Но trie помогает поддерживать целые строки в небольшом пространстве. например в каждой очень большой текстовой поисковой системе есть подобная структура.Поскольку они не могут сохранять все тексты строк, поскольку они дорогостоящие и требуют большого количества аппаратного обеспечения, и что более важно, трудно найти конкретный текст среди миллиардов строк текстов. Вместо этого они делают его компактным со структурой вроде trie.

Существуют и другие структуры, такие как Huffman coding, которые относительно эффективны для уплотнения огромной базы данных строк, но в вашем конкретном случае, я думаю, вы не ищете только для уплотнения строк, но вы хотите иметь возможность запрашивать и быстро находить релевантная информация. Так что trie поможет.

Answer 2

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