FSST
FSST: Fast Random Access String Compression (pdf)
Строки преобладают в наборах данных реального мира. Они часто занимают большую часть данных и медленно обрабатываются. В этой работе мы представляем Fast Static Symbol Table (FSST), упрощенную схему сжатия строк. Для текстовых данных FSST предлагает скорость распаковки и сжатия, аналогичную или превосходящую лучшие методы сжатия с оптимизацией скорости, такие как LZ4, но предлагает значительно лучшие коэффициенты сжатия. Более того, использование статической таблицы символов обеспечивает произвольный доступ к отдельным сжатым строкам, обеспечивая ленивую распаковку и обработку запросов к сжатым данным. Мы считаем, что эти функции сделают FSST ценным элементом в стандартном наборе инструментов сжатия.
Filtering on compressed data — это похоже пробовали прикрутить эту штуку к Clickhousу.
Где бы это еще использовать? Можно ли скажем писать блобы в бд сжимая таким образом строки на лету и потом делая по ним поиск?
Что-то типа записи текста бд в сжатом виде, но с поиском?
Здравствуйте, BlackEric, Вы писали:
BE>FSST
Я тут подумал. Этот алгоритм требует предварительного сбора статистики по ключам. Но если мы знаем статистику заранее, почему бы тогда не использовать что-нибудь посерьезнее, начиная с Хаффмана и заканчивая PPM? Они тоже выдают битовые строки, идентичные для идентичных ключей.