将多个片段拼凑成序列的算法
我正在研究实时嵌入式系统。我正在尝试创建详细的时序分析。我收集了运行时数据，记录了每个中断的开始和停止时间。每个突发数据看起来像这样
ISR# time
----- ----
1 34
end 44
4 74
3 80
end 93
end 97
...
我的输出通道的带宽有限，并且我的高精度计时器很快就会溢出一个字，因此我以约 150 微秒的突发速度收集数据，然后随着时间的推移将其流出。 从这些数据中，我能够收集每次中断所花费的时间以及数量 呼叫和先发制人。
我想做的是将典型帧的完整执行序列放在一起，该帧长约 2 毫秒。
我觉得这几乎就像一个基因测序问题。我有几千个片段，每个片段占总帧的 7%。我应该能够将它们排列起来——匹配覆盖画面同一部分的部分——这样我就可以为整个时期构建一个单一的事件序列。会有一些帧与帧之间的变化，但我希望这些可以在最佳匹配类型的算法中得到解释。
所以我的问题是：有哪些算法可以进行这种排序？是否存在不针对 DNA 或蛋白质的现有工具？
I am working on a real-time embedded system. I am trying to create a detailed timing analysis. I have collected runtime data, recording the start and stop time of each interrupt. Each burst of data looks something like this
ISR# time
----- ----
1 34
end 44
4 74
3 80
end 93
end 97
...
My output channel has limited bandwidth, and my high precision timer overflows a word very quickly, so I am collecting data in ~150 microsecond bursts, then trickling it out over time.
From this data I have been able to collect the time spent in each interupt, and the number
of calls and pre-emptions.
What I would like to do is put together the complete execution sequence for a typical frame, which is ~2 ms long.
It occurs to me that this is almost like a gene-sequencing problem. I have a few thousand fragments, each covering 7% of the total frame. I should be able to line them up - match the portions which cover the same part of the frame - in such a way that I can construct a single sequence of events for the whole period. There will be some frame-to-frame variations, but I am hoping that these can be accounted for in a best-match type of algorithm.
So my question is: What algorithms exist to do this kind of sequencing? Are there any existing tools not targeted to DNA or Protiens?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您的数据似乎相当特定于应用程序，因此您可能只需要进行试验。首先查看带有中断号（没有定时信息）的 ISR 调用顺序是否具有足够的区分性；只需获取每个突发的最后 N 个调用，并进行搜索以查找开头附近具有类似片段的任何其他突发。您可以使用任何字符串搜索算法来完成此任务。如果返回的匹配项太少，请尝试模糊搜索算法。如果返回太多匹配项，请尝试更智能的匹配算法，该算法还会根据时间相似性对每个匹配项进行加权。总的来说，这应该不会太复杂，因为一条完整的链大约只有 15 个突发，而例如在 DNA 测序中，您需要匹配数百万个非常短的片段。
Your data seems fairly application-specific, so you may just have to experiment. First see if the order of ISR invocations with interrupt numbers (without timing information) discriminates sufficiently; just take the final N calls of each burst and do a search to find any other bursts with similar fragments near the beginning. You can use any string search algorithm for this task. If too few matches are returned, try a fuzzy search algorithm. If too many matches are returned, try a smarter matching algorithm that also weighs each match by the similarity of timings. Overall this shouldn't be too complicated, since a complete chain is just about 15 bursts, whereas for example in DNA sequencing you need to match up millions of very short fragments.