2

私は長年疑問に思っていた質問があり、誰かが私の心を休ませるために答えてくれることを望んでいました.

入力ストリーム (ファイル/ソケット/パイプなど) があり、受信データを解析したいとします。最も一般的なインターネット プロトコルのように、受信データの各ブロックが改行で分割されていると仮定しましょう。このアプリケーションは、html、xml、またはその他のスマート データ構造を解析することもできます。ポイントは、データが固定長ではなく区切り文字によって論理ブロックに分割されることです。区切り文字が表示されるのを待つためにデータをバッファリングするにはどうすればよいですか?

答えは単純に思えます: 全体に収まる十分な大きさのバイト/文字配列を用意するだけです。

しかし、バッファーがいっぱいになった後に区切り文字が来るとどうなるでしょうか? これは実際には、データの動的ブロックを固定サイズのブロックに収める方法に関する質問です。私は本当にいくつかの選択肢しか考えられません：

  1. 必要に応じてバッファ サイズを増やします。これには、大量のメモリの再割り当てが必要になる可能性があり、特別に細工されたストリームによるリソースの枯渇につながる可能性があります (または、枯渇攻撃から身を守り、リソースを枯渇させようとする接続を切断する必要があるソケットの場合は、サービス拒否にさえつながる可能性があります...そして攻撃者は、保護をトリガーするために偽の特大のパケットを送信し始めます)。

  2. 循環バッファーを使用して、古いデータの上書きを開始します。論理ブロックが不完全になるため、おそらく理想的な方法ではありません。

  3. バッファがいっぱいになったら、新しいデータをダンプします。ただし、この方法では区切り文字が見つからないため、この選択は明らかに適切なオプションではありません。

  4. 固定サイズのバッファを非常に大きくし、すべての着信論理データ ブロックがその境界内にあると仮定します...そして、いっぱいになった場合は、完全なバッファを論理ブロックとして解釈するだけです...

どちらの場合でも、論理ブロックが特定のサイズを超えることはないと想定する必要があると思います...

このトピックについて何か考えはありますか？readLine()高水準言語はストリーム メソッドで何らかのバッファリング メカニズムを提供するため、明らかに方法が必要です。

これを解決する「最善の方法」はありますか、それとも常にトレードオフがありますか? ある種のパーサーを書く必要があるたびにこの質問に悩まされていたので、このトピックに関するすべての考えとアイデアに本当に感謝しています。

4

4 に答える 4

2

通常、これには 2 つの手法があります。

1) readline が使用していると思われるもの - バッファがいっぱいになると、最後に区切り記号のないデータが返されます

2) バッファーがいっぱいになったら、いっぱいになったことを思い出し、区切り文字を取得してエラーを報告する (またはバッファー サイズでレコードを切り捨てる) まで読み続けます。

于 2008-11-29T01:09:25.670 に答える
0

どちらの場合もデータが失われるため、オプション (2) と (3) は使用できません。オプション (4) の巨大な固定サイズ バッファは、どのサイズが十分に大きいかを知ることができないため、問題を解決しませんか? すべての物理メモリ + スワップ スペース + 既知のユニバース内のすべてのディスクで使用可能な空きスペースですか?

バッファーのサイズを変更することが最善の解決策のようです。サイズを 2 倍に realloc して、書き込みを続けます。システムをダウンさせようとする DoS のような特別に構築されたストリームの可能性は常にあります。私の最初の考えは、バッファの max_size として任意に大きなサイズを設定することでした。ただし、それができれば、それをラージ バッファのサイズとして設定できます。したがって、バッファのサイズを変更することが私にとって最良の選択肢のように見えます。

于 2008-11-12T17:28:03.133 に答える
0

  1. プロトコルまたはユーザーが各ブロックの長さの上限を定義していない場合、メモリ不足のエッジ ケースを防ぐ方法がわかりません。

  2. 固定サイズのブロックを使用して上限があると仮定することは、妥当なサイズの制限に対する適切なアプローチのように思えます。

  3. 単一の固定バッファが非効率になるほど制限が高い場合は、固定サイズのバッファのリンクされたリストとして内部的に実装されるデータ構造を使用することをお勧めします。

于 2008-11-12T17:29:14.487 に答える
0

なぜ処理開始まで待たなければならないのですか？

通常、選択肢 4 は健全です。ただし、「仮定」は必要なく、定義が必要です。ブロックが 8K より小さいことを宣言するだけで、それで完了です。難しいことではありません。

さらに、選択肢 5 があります。部分バッファの処理を開始します。これは、ブロックの最後で重要なデータを送信する真に病理学的なプロトコルを設計していない限り機能します。

HTML、XML、JSON/YAML などはすべて、段階的に解析できます。有用な処理を行うために区切り記号は必要ありません。

于 2008-11-12T18:12:25.897 に答える