私は、非自明の長さの文字列（約3-4kb）を含む多くのオブジェクトを持っているとしましょう。文字列はすべて互いに異なっていますが、同時に多くの共通部分/部分列が含まれています。平均して、個々の文字列の80〜90％が他の文字列に含まれている可能性があります。データを圧縮するためにこの巨大な冗長性を自動的に利用する簡単な方法はありますか？
理想的には、ソリューションはC++であり、ユーザーにとって透過的です（つまり、通常の読み取り専用const std :: stringにアクセスしているかのように使用できますが、圧縮された記憶域から読み取る）。圧縮された文字列の記憶
アルゴリズムでは、すべてのオブジェクト/文字列に対して1つの辞書を持つLempel–Ziv–Welchが適しています。
時間の経過とともに多くの文字列が動的に作成された場合、この辞書は大きくなります。結局、LZWだけで文字列を別々に圧縮するほうが簡単で良いアイデアかもしれません。 –
最初のバッチがロードされた後に作成される文字列は非常に少ないので、そこに問題はないと思います... – BuschnicK
文字列の共通部分が他の文字列から構成されているため共通部分である場合は、stlportropeクラスを使用していくつかの牽引力を得ることができます。これはstd :: stringのように全世界を検索し、それらは非常に効率的なスペース（共通部分文字列が共有されている）と、挿入や削除に非常に優れ両方になり書き込み上のコピーとのツリー表現（（n）をログ）
ロープを使用する：
ロープを使用しない：
私はそれが書き込み時のコピー以上であると思います。私はデータが連続したメモリゾーンではなく、文字列のツリーに格納されていると思います。 –
文字列に付加するのと同じアルゴリズムコストで文字列を付加する機能と組み合わせてコピーオンライトです。 –
私はあなたの2番目のケースに合っていると思う：私の弦は私によって制御されず、私はそれらをデータベースから得る。 – BuschnicK
あなたはhuffman codingの実装は難しくありません、また、言語（例えばC＃やjavaなど）でzipアルゴリズムがあり、それらを使用することができます。
また、80-90％がすべて繰り返されている場合は、すべての単語の辞書を作成してから、辞書の単語の位置を格納する文字列ごとに、ビッグサイズのビット配列（10000 ie）を付け、現在の文字列にwords[i]が存在する場合は、bits[i]〜1となります。各単語の長さが5文字であると考えて、略語は約1/5のサイズをとります。
@Saeedと同様、シンプルなハフマンコーディングがここでうまくいきます。
一般的な単語がapriori（あなたはHTMLだと言われています）と知られている場合、辞書には必要ありません。多くのHTMLファイルの統計データを使用して、ハフマンテーブルを事前に計算するだけです（単一のシンボルで全体のタグをエンコードでき、必要な数のシンボルを持つことができます）。
どのように文字列は共通のサブシーケンスを持つようになります。これはデータの編集や偶然の繰り返しによるものですか？ – SingleNegationElimination
CSSをサポートしない静的HTMLを想像してみてください。あなたは冗長なHTMLをたくさん持ち、実際の情報を含む変更部分はごくわずかです。 – BuschnicK
1GBのRAMは、3〜4KBのサイズの非圧縮ブロブ100,000個を保持します。あなたは本当にそれをより少ないものに収める必要がありますか？ – SingleNegationElimination