-
16-10-2019 - |
题
我需要从重复的数据流中恢复数据块。我希望看到这算法可能已经存在,因为它并不像新颖的情况。
这是具体细节:
- 流中包含一个N长度块
- 该块在流中重复多次
- 数据是高度损坏的,有些字节可能是错误的,因为可以检测到其他字节是缺失的(擦除)
- 有一个函数
F(data)
可以说一个块是否代表有效的数据(假阳性的概率实际上为零) F
还可以提供一个概率值,即使块无效数据,该块本身是否有效(但只是有太多损坏以无法恢复)- 与缺少数据相比,损坏数据的机会非常低
例如,说我有此数据流,并希望恢复10个长度序列 1234567890
. 。数据只是一个粗略的视觉示例(我不能保证从这个位实际上可以恢复)。一个 .
代表缺失的字节,并且 <break>
指示未知的数据块(没有数据,尚未知道)。还要注意 Q
S作为损坏数据的示例。
23.5678901.3456789<break>2345678..1..4567QQ012345678..3456
我如何获取这样的数据流和恢复可能的n个数据块?由于实际数据包括正向错误恢复,因此块恢复不必是完美的。它要做的就是提供可能的重建数据块,并提供 F
功能将尝试进行错误恢复。所以我期望 F
填充必须被调用几次。
我想找到比简单打电更好的东西 F
在流中的每个点,由于错误率可能足够高,因此无法恢复N的单个运行块 - 必须以某种方式使用流中的重复。
解决方案
我认为如果没有进一步的假设,您不可能做什么 F
.
考虑以下,相当简单的数据流,以达到目标数据长度 5
:
123441233512245113451255513555 ...
请注意,没有一个块包含 12345
(我们的原始数据)。为了找到适当的数据部件组合,您将需要检查 全部 一般而言。除了某些组合以外的概率是多少 12345
被接受 F
?这是在流中,没有丢失或损坏的符号,而忽略了块之间的重叠问题,而块之间可能是有效的数据!
因此,我认为保留尺寸$ n $的缓冲区并运行 F
在每个时间步骤中,您都可以做到最好。请注意,您可以跳过评估 F
如果缓冲区中有一个损坏的符号(前提是您可以识别这些符号)。但是,您仍然存在重叠错误和错误的有效块的问题。
如果您有更大的潜力 F
具有不错的属性,例如,如果它能够识别有效 部分 数据的。然后,您只能存储最大的有效零件并将其拼凑在一起。此外,格式化数据流可以有所帮助;一个简单的示例将是数据块开始的标记(这将消除重叠问题并减少调用量 F
)。此外,诸如“错误概率很小”之类的通常假设可以使数据可行的完整有效副本。如果几乎所有其他符号都是损坏的,许多协议会分解。
所有这些都不是新问题。我建议进一步阅读