1

関数がさまざまな長さのデータを継続的に受け取るという状況があります。データは何でもかまいません。このデータで特定の文字列を探すための最良の方法を見つけたいと思っています。解決策には、以前のデータを何らかの形でバッファリングする必要がありますが、問題に頭を悩ませることはできません。

問題の例を次に示します。

データ入力 -> [\x00\x00\x01\x23B][][LABLABLABLABLA\x01TO][KEN][BLA\x01]...

すべての [...] がデータ チャンクを表し、[] がアイテムのないデータ チャンクを表す場合、文字列 TOKEN をスキャンする最良の方法は何ですか?

更新: 質問がもう少し複雑であることに気付きました。[] はセパレータではありません。上記の例に従って、チャンクの構造を説明するためにそれらを使用しています。また、TOKEN 自体は静的文字列ではありません。可変長です。行ごとに読み取る最良の方法だと思いますが、問題は、可変長のストリーミング バッファを行に読み取る方法です。

4

3 に答える 3

2

TOKEN を検索する最も簡単な方法は次のとおりです。

  • ストリームの位置 0 から始まる "TOKEN" との一致を試みます
  • ストリーム内の位置 1 から始まる「TOKEN」との一致を試みます
  • 等

したがって、バッファリングする必要があるのは、「TOKEN」の長さに等しいストリームからのバイト数だけです (5 バイト、または実際には 4 バイトで十分です)。各位置で「TOKEN」との一致を試みます。これには、バッファに少なくとも 5 バイトが読み込まれるまで待機する必要がある場合があります。マッチングに失敗した場合は、マッチングを開始した位置に 1 を加えた位置まで巻き戻します。検索している文字列の長さ (マイナス 1) を超えて巻き戻すことはないので、本当に必要なバッファはそれだけです。

技術的な問題は、ストリームから継続的に読み取るときに、5 バイトのバッファー データを維持する方法です。1 つの方法は、いわゆる「循環バッファー」です。もう 1 つの方法は、特にトークンが小さい場合は、より大きなバッファーを使用し、最後に近づきすぎるたびに、必要なバイトを最初にコピーしてからやり直すことです。

関数がコールバックで、データの新しいチャンクごとに 1 回呼び出される場合、2 つのチャンクにまたがる一致を可能にするために、ある呼び出しから次の呼び出しまで何らかの状態を維持する必要があります。運が良ければ、コールバック API に「ユーザー データ ポインター」が含まれており、バッファーを含む任意の構造体を指すように設定できます。そうでない場合は、グローバル変数またはスレッドローカル変数が必要になります。

ストリームのデータ レートが高い場合は、KMP アルゴリズムなどを使用して速度を上げることを検討してください。

于 2013-01-28T15:54:58.180 に答える
0

申し訳ありませんが、質問に対する私の理解が正しくなかったため、以前の回答を削除することに投票しました。私は十分に注意深く読んでおらず、[] がトークン区切り文字であると考えていました。

あなたの問題については、単純なカウンターに基づいて小さなステートマシンを構築することをお勧めします: すべての文字に対して、次の擬似コードのようなことを行います:

if (received_character == token[pos]) {
    ++pos;
    if (pos >= token_length) {
        token_received = 1;
    }
}
else {
    pos = 0; // Startover
}

これには最小限のプロセッサ サイクルと最小限のメモリしか必要としないため、受信したばかりのチャンク以外は何もバッファリングする必要はありません。

于 2013-01-28T16:10:43.207 に答える