Обнаружение блоков в повторном потоке

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 n - повторение в потоке должно быть каким -то образом использовать.

Answer 1

Я думаю, что вы хотите сделать без дальнейших предположений F.

Рассмотрим следующее, довольно простой поток данных для целевой длины данных 5:

123441233512245113451255513555 ...

Обратите внимание, что ни один блок не содержит 12345 (наши первоначальные данные). Чтобы найти правильную комбинацию деталей данных, у вас будет проверить все Комбинации, в целом. Какова вероятность, что какая -то комбинация, кроме 12345 принимается F? И это находится на потоке без утраченных или поврежденных символов и игнорировать проблему перекрытий между блоками, которые случайно могут быть допустимыми данными!

Поэтому я думаю, что хранение буфера размером $ n $ и бег F В каждом временем шаг - лучшее, что вы можете сделать. Обратите внимание, что вы можете пропустить оценку F Если в буфере есть коррумпированный символ (при условии, что вы можете идентифицировать их). У вас все еще есть проблема ошибок перекрытия и неправильных действительных блоков.

У вас больше потенциала, если F имеет хорошие свойства, например, если он способен идентифицировать действительный части данных. Затем вы можете хранить только максимальные достоверные детали и собрать их вместе. Кроме того, форматирование потока данных может помочь; Простым примером могут быть маркеры для начала блока данных (который избавится от проблем с перекрытиями и уменьшит количество вызовов на F) Кроме того, обычные предположения, такие как «вероятность ошибки мала», могут сделать ожидание полной допустимой копии данных жизнеспособной; Многие протоколы ломаются, если практически любой другой символ поврежден.

Все это не новые проблемы. Я предлагаю дальнейшее чтение на

• Коды обнаружения ошибок и коррекции,
• Коды в целом а также
• Протоколы связи.