重复流中的块检测

Question

我需要从重复的数据流中恢复数据块。我希望看到这算法可能已经存在，因为它并不像新颖的情况。

这是具体细节：

1. 流中包含一个N长度块
2. 该块在流中重复多次
3. 数据是高度损坏的，有些字节可能是错误的，因为可以检测到其他字节是缺失的（擦除）
4. 有一个函数 F(data) 可以说一个块是否代表有效的数据（假阳性的概率实际上为零）
5. F 还可以提供一个概率值，即使块无效数据，该块本身是否有效（但只是有太多损坏以无法恢复）
6. 与缺少数据相比，损坏数据的机会非常低

例如，说我有此数据流，并希望恢复10个长度序列 1234567890. 。数据只是一个粗略的视觉示例（我不能保证从这个位实际上可以恢复）。一个 . 代表缺失的字节，并且 <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）。此外，诸如“错误概率很小”之类的通常假设可以使数据可行的完整有效副本。如果几乎所有其他符号都是损坏的，许多协议会分解。

所有这些都不是新问题。我建议进一步阅读

• 错误检测和校正代码,
• 一般代码 和
• 通信协议.