1

文字列の圧縮に関するインタビューでよく聞かれる質問があります。コードを探しているわけではありません。問題を解決する効率的なアルゴリズムだけが必要です。

文字列 ( aaabbccaaadd など) を指定すると、それを圧縮します ( 3a2b2c3a2d )。

私の解決策：

ひもで移動します。同じ文字を見るたびに数えます。別の手紙が来るのを見たときに、手紙とカウンターを出力します（そして最初からやり直します）。

これを行うより効率的な方法はありますか？

ありがとう

4

3 に答える 3

6

これはランニングレングスエンコーディングと呼ばれ、あなたが名前を付けたアルゴリズムは基本的にあなたが得る最高のものです。O(1) の補助ストレージ (最後に見たシンボルを保存するか、次の要素を同等に検査します。また、見た同一のシンボルの数のカウンターも保存します) を必要とし、O(n) 時間で実行されます。結果を知るために各シンボルを少なくとも 1 回検査する必要があるため、とにかく O(n) 時間よりも良い結果を得ることはできません。さらに、ストリームを一度に 1 つのシンボルで処理し、一度に 1 つのシンボルを出力することもできるため、実際には O(1) RAM しか必要ありません。

一定の因数をより良くするためにいくつかのトリックを引き出すことができますが、アルゴリズムは基本的に同じままです。そのようなトリックは次のとおりです。

  • 低速の宛先 (ディスクやネットワークなど) にストリーミングする場合は、バッファリングします。広範囲に。
  • 同一のシンボルが長時間実行されることが予想される場合は、それらをカウントするループをベクトル化するか、少なくとも他のケースを移動してそのループをよりタイトにすることができます。
  • 該当する場合は、入力ポインターと出力ポインターの間のエイリアシングを気にしないようにコンパイラーに指示してください。

データソースが遅い場合、このようなマイクロ最適化は意味がないかもしれません。アドレスの上のいくつかのポイントの最適化のレベルについては、RAM でさえ遅いと見なすことができます。

于 2012-10-26T19:57:17.597 に答える
1

文字列が十分に長い場合は、Lempel Ziv 圧縮を使用します。利点は、個別の繰り返しを短縮するだけでなく、繰り返しの「グループ」も効率的に短縮できることです。ウィキペディアを参照してください: Lempel-Ziv-Welch

漠然とした例 - アイデアを得るために:
aaabqxyzaaatuoiaaabhaaabi は次のように圧縮されます:
Abqxyz Atui Bh Bi
where [ A= aaa] & [ B= Ab = aaab]

于 2012-10-26T20:00:16.723 に答える
0

多くの圧縮アルゴリズムは、ハフマン符号化に基づいています。それが私がインタビューで与える答えです

于 2012-10-26T19:51:27.253 に答える