4

多数の文字列を管理するアプリケーションがあります。文字列はパスのような形式で、多くの共通部分がありますが、明確なルールはありません。それらはファイルシステム上のパスではありませんが、そのように考えることができます。メモリ消費を最適化する必要があることは明らかですが、パフォーマンスを大幅に犠牲にすることはありません。

私は 2 つのオプションを検討しています: -データを zip 形式で保存
するクラスを実装しますが、固定の辞書が必要で、現在このためのライブラリを見つけることができません。compressed_stringバイトではなく、言葉でハフマンが欲しい。
- 文字列部分にある種のflyweightパターンを実装します。

この問題は一般的な問題のように見えますが、それに対する最善の解決策は何か、またはこの問題を対象とするライブラリを誰かが知っているかどうか疑問に思っています。

ありがとう

4

2 に答える 2

1

問題に合わせて特定のアルゴリズムを調整したくなるかもしれませんが、それにはとてつもない時間と労力が必要になる可能性がありますが、標準の圧縮技術を使用すると、メモリ消費の問題を解決するのにすぐに役立ちます。

この問題を処理する「標準的な」方法は、ソース データを小さなブロック (256KB など) にチャンクし、個別に圧縮することです。ブロック内のデータにアクセスするときは、まずそれをデコードする必要があります。したがって、最適なブロック サイズは実際にはアプリケーションによって異なります。つまり、アプリケーション ストリームが多いほど、ブロックは大きくなります。一方、ランダムアクセスパターンが多いほど、ブロックサイズは小さくなります。

圧縮・伸張速度が気になる場合は、高速なアルゴリズムを使用してください。解凍速度が (アクセス時間の) 最も重要なメトリックである場合、LZ4 のようなものはコアあたり約 1GB/秒のデコード パフォーマンスを提供するため、これにより、1 秒あたりにデコードできるブロック数がわかります。

解凍速度だけが重要な場合は、高圧縮バリアント LZ4-HC を使用できます。これにより、圧縮率がさらに約 30% 向上し、解凍速度も向上します。

于 2011-10-13T09:23:16.427 に答える
0

文字列はパスのような形式で、多くの共通部分がありますが、明確なルールはありません。

name , ( separator , name )*?という形式の階層内のロケーターであるという意味で。その場合は、interningを使用できます。名前の部分を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 *>。

于 2011-10-13T08:17:11.420 に答える