查找流中缺失位的位置
Finding position of missing bits in stream
不确定这是否是正确的频道...请指教:-)
- 您生成了一个 n 位流 (1 & 0)。
- 我删除了 k 位并广播了 n-k 位的流。
- 您在某个时间点开始收听我的流（即您可能错过了流的开头）。
任务：
告诉我我从你的流 中删除的位的原始位置，用于你收到的部分。
附加信息：
- 您的流必须包含至少 1000 位，但您可以按照自己喜欢的方式设计它，并且可以将其存储在内存中。
- 我将删除不超过 3 个连续位。
- 我将从原始流中删除不超过 10 位。
- 我将只播放一次流 - 没有循环等等。
这个可以解决吗？也许有校验和，集成位置编码......？
您需要我的流的多少位才能绝对肯定地给出您的答案？
我发现了这个：https://cs.stackexchange.com/questions/2079/determine-missing-number-in-data-stream 但是可以删除的数字是唯一的。
我的直觉是这是完全可行的。
给定一个n位字符串（稍后详细介绍），有一个相对高效的解码算法。抛开对手不丢弃超过 3 个连续位的要求（可能不丢弃，但算法会更复杂，我认为这不是什么限制）。初始化从字符串中的 n+1 个位置到删除计数（最初为零）和头部位置（最初为键）的映射。对于每个接收到的位，循环遍历映射。如果头部的下一位与该位匹配，则将其向前移动。否则，增加移除计数。如果删除计数超过10，则从地图中删除此键。一旦只有一个唯一的头部位置，解码就完成了。
我推测，统一的随机字符串很有可能效果很好。这种效果的一个简单的论点是，对于每个处于不正确位置的头，它都会以 1/2 的概率累积移除。比方说，在 200 位之后，应该有足够小的生存概率超过大约 1000 次 1000^11/11！对手的选择，不正确的头幸存下来的可能性可以忽略不计。 （这个论点是手摇的，因为我做了一堆未经证实的和字面上错误的独立性假设。）
不确定这是否是正确的频道...请指教:-)
- 您生成了一个 n 位流 (1 & 0)。
- 我删除了 k 位并广播了 n-k 位的流。
- 您在某个时间点开始收听我的流（即您可能错过了流的开头）。
任务： 告诉我我从你的流 中删除的位的原始位置，用于你收到的部分。
附加信息：
- 您的流必须包含至少 1000 位，但您可以按照自己喜欢的方式设计它，并且可以将其存储在内存中。
- 我将删除不超过 3 个连续位。
- 我将从原始流中删除不超过 10 位。
- 我将只播放一次流 - 没有循环等等。
这个可以解决吗？也许有校验和，集成位置编码......？ 您需要我的流的多少位才能绝对肯定地给出您的答案？
我发现了这个：https://cs.stackexchange.com/questions/2079/determine-missing-number-in-data-stream 但是可以删除的数字是唯一的。
我的直觉是这是完全可行的。
给定一个n位字符串（稍后详细介绍），有一个相对高效的解码算法。抛开对手不丢弃超过 3 个连续位的要求（可能不丢弃，但算法会更复杂，我认为这不是什么限制）。初始化从字符串中的 n+1 个位置到删除计数（最初为零）和头部位置（最初为键）的映射。对于每个接收到的位，循环遍历映射。如果头部的下一位与该位匹配，则将其向前移动。否则，增加移除计数。如果删除计数超过10，则从地图中删除此键。一旦只有一个唯一的头部位置，解码就完成了。
我推测，统一的随机字符串很有可能效果很好。这种效果的一个简单的论点是，对于每个处于不正确位置的头，它都会以 1/2 的概率累积移除。比方说，在 200 位之后，应该有足够小的生存概率超过大约 1000 次 1000^11/11！对手的选择，不正确的头幸存下来的可能性可以忽略不计。 （这个论点是手摇的，因为我做了一堆未经证实的和字面上错误的独立性假设。）