détection bloc dans le flux répété

Question

Je dois récupérer un bloc de données à partir d'un flux de données répétées. Je cherche à voir ce que les algorithmes peuvent déjà exister pour cela comme il ne se sent pas comme une nouvelle situation.

Voici les détails:

1. Il est un bloc N-longueur des données contenues dans un courant
2. Le bloc est répété plusieurs fois dans le courant
3. les données sont très corrompues, certains octets pourraient simplement se tromper, alors que d'autres peuvent être détectés comme manquants (ratures)
4. Il y a une F(data) fonction qui peut dire si un bloc représente des données valides (la probabilité d'un faux positif est pratiquement nul)
5. F peut également fournir une valeur de probabilité que même si le bloc ne sont pas des données valides si le bloc lui-même est valide (mais a juste trop de corruption à récupérer)
6. La chance de données corrompues est très faible par rapport aux données manquantes

Par exemple, dire que j'ai ce flux de données et souhaite récupérer la séquence 10 longueur 1234567890. Les données sont juste un exemple visuel rugueux (je ne peux pas garantir la récupération est effectivement possible de ce bit). Un . représente un octet manquant, et <break> indique un bloc inconnu des données (aucune donnée et non longueur connue). Notez également les Qs comme un exemple de données corrompues.

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

Comment puis-je prendre un tel flux de données et récupération probablement des blocs de données N? Comme les données réelles comprend la récupération d'erreur avant la nécessité de récupération de bloc ne soit pas parfait. Tout ce qu'il a besoin de faire est de donner des blocs reconstruits probables de données et la fonction F tentera de faire la récupération d'erreur. Ainsi, je pense F remplissage doivent être appelé à plusieurs reprises.

Je voudrais trouver quelque chose de mieux que F simplement appeler à chaque point dans le courant puisque le taux d'erreur pourrait être assez élevé qu'aucun bloc d'exécution unique de N peut être récupéré - les répétitions dans le flux doivent être utilisés en quelque sorte .

Answer 1

Je pense que ce que vous voulez est impossible de le faire sans d'autres hypothèses sur F.

Considérez ce qui suit, assez simple flux de données pour une longueur de données cible de 5:

123441233512245113451255513555 ...

Notez que d'un seul bloc contient 12345 (nos données d'origine). Afin de trouver une bonne combinaison de pièces de données, vous devez vérifier tous combinaisons, en général. Quelle est la probabilité qu'une combinaison autre que 12345 est acceptée par F? Et cela est un flux sans symboles perdus ou corrompus et en ignorant le problème des chevauchements entre les blocs qui pourrait par hasard être données valides!

Par conséquent, je pense que garder un tampon de taille $ N $ et en cours d'exécution F à chaque étape de temps est le meilleur que vous pouvez faire. Notez que vous pouvez sauter l'évaluation des F s'il est un symbole de corruption dans la mémoire tampon (à condition que vous pouvez identifier les). Vous avez encore le problème des erreurs de chevauchement et de mauvais blocs valides, bien que.

Vous avez plus de potentiel si F a des propriétés agréables, par exemple si elle est en mesure d'identifier valide pièces de données. Ensuite, vous pouvez stocker seulement maximale des pièces valides et assemblez les ensemble. En outre, le formatage du flux de données peut aider; un exemple simple serait marqueurs pour le début d'un bloc de données (qui permettrait de se débarrasser des problèmes avec des chevauchements et de réduire le nombre d'appels à F). En outre, les hypothèses habituelles telles que la « probabilité d'erreur est faible » peut faire l'attente d'une copie valide complète des données viables; de nombreux protocoles se décomposent si pratiquement tous les autres symboles est corrompu.

Tous ces problèmes ne sont pas nouveaux. Je suggère davantage de lecture sur

• codes de détection et de correction d'erreur ,
• en général et
• protocoles de communication .