2

我不会详细介绍我要解决的问题，但它处理的是一个大字符串，并涉及查找字符串中存在的重叠间隔。我只能使用其中一个重叠的区间，所以我想将这些区间分开并单独分析。我想知道使用什么算法来尽可能有效地做到这一点。

我必须强调，速度在这里是最重要的。我需要尽快分开间隔。我想到的算法是区间树，但我不确定这是否是我们能做的最好的。

可以在 O(log n) 时间内查询区间树，n 是区间数，构建需要 O(nlog n) 时间，但我想知道我们是否可以减少其中任何一个。

谢谢！

编辑：我知道这个问题很模糊。我为混乱道歉。我建议人们看看 Aaron Huran 的答案和相同的评论。这应该有助于澄清更多事情。

4

3 回答 3

2

好吧，我昨晚很无聊，所以我用 Python 做了这个。它是不必要的递归（我刚刚阅读了 The Little Schemer 并认为递归现在非常简洁）但它解决了您的问题并处理了我向它抛出的所有输入。

intervals = [(0,4), (5,13), (8,19), (10,12)]  

def overlaps(x,y): 
   x1, x2 = x 
   y1, y2 = y 
   return ( 
      (x1 <= y1 <= x2) or 
      (x1 <= y2 <= x2) or  
      (y1 <= x1 <= y2) or 
      (y1 <= x2 <= y2) 
   ) 

def find_overlaps(intervals, checklist=None, pending=None): 
   if not intervals:  
      return [] 

   interval = intervals.pop() 

   if not checklist: 
      return find_overlaps(intervals, [interval], [interval]) 

   check = checklist.pop() 

   if overlaps(interval, check): 
      pending = pending or [] 
      checklist.append(check) 
      checklist.append(interval) 
      return pending + [interval] + find_overlaps(intervals, checklist) 
   else: 
      intervals.append(interval) 
      return find_overlaps(intervals, checklist)

像这样使用：

>>> find_overlaps(intervals)
[(10, 12), (8, 19), (5, 13)]

请注意，它以起点的反向顺序返回所有重叠间隔。希望这是一个小问题。这只是因为我在列表中使用push()和pop()，它在列表的末尾运行，而不是在列表insert(0)的pop(0)开头运行。

这并不完美，但它在线性时间内运行。还要记住，实际字符串的大小根本不重要——运行时间与间隔数有关，而不是字符串的大小。

于 2010-07-09T15:42:48.660 回答
2

您可能想尝试使用 Ukkonen 的算法（请参阅https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm）。

在http://biit.cs.ut.ee/~vilo/edu/2002-03/Tekstialgoritmid_I/Software/Loeng5_Suffix_Trees/Suffix_Trees/cs.haifa.ac.il/shlomo/suffix_tree/suffix_tree有一个免费的代码版本。 C

于 2016-01-24T20:43:39.090 回答
1

您正在寻找计算两个字符串之间的差异吗？你想用什么语言来做这件事？

更新：没有任何关于如何选择要使用的时间间隔的标准，有很多可能的解决方案。

一种方法是取最低的起始数字，抓住它的结尾。获取高于前一个区间结束的下一个起始数字。获取此间隔的结束并重复。

所以对于 0-4、5-13、8-19、10-12 你得到：0-4、5-13 并忽略其他。

于 2010-07-09T03:55:09.183 回答