Сжатие строк с общими частями - PullRequest
Новая
       14

Сжатие строк с общими частями

4 голосов
/ 13 октября 2011

У меня есть приложение, которое управляет большим количеством строк.Строки в формате пути и имеют много общих частей, но без четкого правила.Они не являются путями в файловой системе, но могут рассматриваться как таковые.Мне явно нужно оптимизировать потребление памяти, но без большого снижения производительности.

Я рассматриваю 2 варианта:
- реализовать класс compressed_string, который хранит данные в сжатом виде, но мне нужен фиксированный словарь, и я не могунайти библиотеку для этого прямо сейчас.Я не хочу Хаффмана для байтов, я хочу его для слов.
- реализовать какой-то шаблон flyweight для строковых частей.

Проблема выглядит как обычная, и мне интересночто является лучшим решением или если кто-то знает библиотеку, которая нацелена на эту проблему.

спасибо

Ответы [ 2 ]

1 голос
/ 13 октября 2011

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

«Стандартный» способ решения этой проблемы состоит в том, чтобы разделить исходные данные на небольшие блоки (например, 256 КБ) и сжимать их по отдельности. При доступе к данным в блоке вам необходимо сначала их декодировать. Следовательно, оптимальный размер блока действительно зависит от вашего приложения, то есть чем больше потоков приложений, тем больше блоков; с другой стороны, чем больше шаблон произвольного доступа, тем меньше размер блока.

Если вас беспокоит скорость сжатия / распаковки, используйте высокоскоростной алгоритм. Если скорость распаковки является наиболее важной метрикой (для времени доступа), что-то вроде LZ4 обеспечит вам скорость декодирования 1 ГБ / с на ядро ​​, так что это дает вам представление о том, сколько блоков в секунду вы можете декодировать .

Если имеет значение только скорость декомпрессии, вы можете использовать вариант с высокой степенью сжатия LZ4-HC, который увеличит степень сжатия еще примерно на 30%, а также улучшит скорость декомпрессии.

0 голосов
/ 13 октября 2011

Строки в формате пути и имеют много общих частей, но без четкого правила.

В том смысле, что они являются локаторами в иерархии вида имя , ( разделитель , имя ) *? Если это так, вы можете использовать interning : сохранить name parts как char const * элементы, которые указывают на пул строк. Таким образом, вы эффективно сжимаете имя, которое используется n раз, до чуть более n * sizeof(char const *) + strlen(name) байтов. Полный путь станет последовательностью интернированных имен, например, std::vector.

Может показаться, что sizeof(char const *) велико на 64-битном оборудовании, но вы также экономите часть затрат на распределение. Или, если по какой-то причине вы знаете, что вам никогда не понадобится больше, чем, скажем, 65536 строк, вы можете сохранить их как 

class interned_name
{
    uint16_t tab_idx;

  public:
    char const *c_str() const
    {
        return NAME_TABLE[tab_idx];
    }
};

, где NAME_TABLE - это static std::unordered_map<uint16_t, char const *>.

...