Я не думаю, что для этого есть какая-либо свободно доступная реализация (во всяком случае, я не знаю, хотя я написал как минимум 3 похожие конструкции в коммерческом коде), поэтому вам придется свернуть свою собственную.
Замечание, сделанное Марсело о добавлении элементов по порядку, очень актуально, поскольку я полагаю, вы, вероятно, захотите сжимать данные во время добавления - быстрый доступ к записям, уже похожим на добавляемую, дает гораздо лучшую производительность, чем необходимость найдите «наиболее подходящую запись» (необходимую для сжатия-подобия) по всему набору.
Еще одна вещь, о которой вы, возможно, захотите прочитать, - это веревки - концептуально отличный от строк тип, который Я уже предлагал Марко Канту некоторое время назад. За счет следующего указателя на «шпагат» (из-за отсутствия лучшего слова) вы можете объединять части строки, не сохраняя никаких повторяющихся данных. Основная проблема заключается в том, как получить части, которые можно объединить в новую «веревку», представляющую вашу исходную строку. Как только эта проблема будет решена, вы сможете в любой момент реконструировать данные в виде строки, сохранив при этом компактное хранилище.
Если вы не хотите идти по «веревочному» маршруту, вы также можете попробовать так называемое «сокращение префикса», которое представляет собой простую форму сжатия - просто начинайте каждую строку с индекса предыдущей строки и количества символов. это следует рассматривать как префикс для новой строки. Имейте в виду, что вам не следует не возвращаться слишком далеко назад, иначе скорость доступа сильно пострадает. В одной простой реализации я сделал mod 16 в индексе, чтобы установить запись, с которой началось сокращение префикса, что дало мне в среднем около 40% экономии памяти (это число, конечно, полностью зависит от данных).
person
PatrickvL
schedule
13.09.2010
