繰り返されるストリームでのブロック検出

Question

データブロックを繰り返しデータのストリームから回復する必要があります。斬新な状況のように感じられないので、これにはどのようなアルゴリズムが存在するかを見たいと思っています。

ここに詳細があります：

1. ストリームに含まれるデータのn長ブロックがあります
2. ブロックはストリームで何度も繰り返されます
3. データは非常に破損しており、一部のバイトは間違っている可能性があります。
4. 関数があります F(data) ブロックが有効なデータを表すかどうか（偽陽性の確率が実質的にゼロであると言うことができます）
5. F また、ブロック自体が有効かどうか（ただし、腐敗が多すぎて回復するにはあまりにも多くのデータがあるかどうかが有効なデータでなくても、確率値を提供することもできます。
6. 破損したデータの可能性は、欠落データと比較して非常に低いです

たとえば、私はこのデータストリームを持っていて、10の長さのシーケンスを回復したいとします 1234567890. 。データは大まかな視覚的な例です（このビットから実際に回復が可能であることを保証することはできません）。 a . 欠落しているバイトを表します <break> データの未知のブロックを示します（データはありませんが、長さは知られていません）。また、 Qs破損したデータの例として。

23.5678901.3456789<break>2345678..1..4567QQ012345678..3456

このようなデータのストリームを採取して、おそらくnデータのブロックを回復するにはどうすればよいですか？実際のデータにはフォワードエラー回復が含まれているため、ブロックリカバリは完全ではありません。それが行う必要があることは、データの再構築されたブロックと F 関数はエラー回復を試みます。したがって、私は期待します F 塗りつぶしは何度か呼ばれなければなりません。

単に電話するよりも良いものを見つけたいです F エラー率が十分に高くなる可能性があるため、ストリームの各ポイントで、nの単一の実行ブロックを回復できない可能性があります。

Answer 1

私はあなたが望むことは、さらなる仮定なしに行うことは不可能だと思います F.

ターゲットデータの長さの次の、かなり単純なデータストリームを検討してください 5:

123441233512245113451255513555 ...

単一のブロックが含まれていないことに注意してください 12345 （元のデータ）。データパーツの適切な組み合わせを見つけるために、チェックが必要です すべて 一般的に組み合わせ。以外の組み合わせがある確率は何ですか 12345 に受け入れられます F？そして、これは紛失したり腐敗したシンボルのないストリーム上にあり、偶然に有効なデータである可能性のあるブロック間の重複の問題を無視しています！

したがって、サイズ$ n $のバッファーを保持して実行していると思います F 毎回ステップができる最善のステップです。の評価をスキップできることに注意してください F バッファに腐敗した記号がある場合（それらを識別できる場合）。ただし、エラーと間違った有効なブロックのオーバーラップの問題があります。

より多くの可能性があります F たとえば、有効な識別が可能な場合、優れたプロパティがあります 部品 データの。その後、最大の有効な部品のみを保存し、それらを一緒に断ち切ることができます。また、データストリームのフォーマットが役立ちます。簡単な例は、データブロックの開始のマーカーです（オーバーラップの問題を取り除き、通話の量を減らすことができます F）。さらに、「エラー確率が小さい」などの通常の仮定により、データの完全な有効なコピーを待つことができます。事実上他のすべてのシンボルが破損している場合、多くのプロトコルが崩壊します。

これらはすべて新しい問題ではありません。さらに読むことをお勧めします

• エラー検出および修正コード,
• 一般的にコード と
• 通信プロトコル.