Алгоритм объединения последовательности из нескольких фрагментов

Question

Я работаю над встроенной системой реального времени.Я пытаюсь создать подробный анализ времени.Я собрал данные времени выполнения, записав время начала и окончания каждого прерывания.Каждый пакет данных выглядит примерно так:

 ISR#  time
 -----  ----
  1     34
  end   44
  4     74
  3     80
  end   93
  end   97
  ...

Мой выходной канал имеет ограниченную пропускную способность, и мой высокоточный таймер очень быстро переполняет слово, поэтому я собираю данные за ~ 150 микросекундных пакетов, а затем выводим ихчерез некоторое время.На основе этих данных я смог собрать время, затраченное на каждое прерывание, а также количество вызовов и упреждений.

Я хотел бы собрать полную последовательность выполнения для типичного кадра, длина которого ~ 2 мс.

Мне приходит в голову, что это почти похоже на проблему секвенирования генов.У меня есть несколько тысяч фрагментов, каждый из которых покрывает 7% от общего кадра.Я должен быть в состоянии выстроить их в ряд - сопоставить части, которые покрывают одну и ту же часть кадра - таким образом, чтобы я мог построить единую последовательность событий за весь период.Будут некоторые вариации от кадра к кадру, но я надеюсь, что они могут быть учтены в алгоритме с наилучшим соответствием.

Итак, мой вопрос: какие существуют алгоритмы для такого рода последовательности?Существуют ли какие-либо инструменты, не предназначенные для ДНК или Protiens?

Answer 1

Ваши данные кажутся довольно специфичными для приложения, поэтому вам, возможно, придется просто поэкспериментировать.Сначала посмотрите, достаточно ли различен порядок вызовов ISR с номерами прерываний (без информации о синхронизации);просто возьмите последние N вызовов каждого пакета и выполните поиск, чтобы найти любые другие пакеты с похожими фрагментами в начале.Для этой задачи вы можете использовать любой алгоритм поиска строк.Если возвращается слишком мало совпадений, попробуйте алгоритм нечеткого поиска.Если возвращено слишком много совпадений, попробуйте более умный алгоритм сопоставления, который также взвешивает каждое совпадение по схожести времени.В целом, это не должно быть слишком сложным, поскольку полная цепочка занимает всего около 15 пакетов, в то время как, например, при секвенировании ДНК вам нужно сопоставлять миллионы очень коротких фрагментов.