2

解決しようとしている問題の詳細については説明しませんが、大きな文字列を扱い、文字列内に存在する重複する間隔を見つける必要があります。重複する間隔の 1 つしか使用できないため、これらの間隔を分離して個別に分析したいと考えました。これをできるだけ効率的に行うには、どのアルゴリズムを使用すればよいか考えていました。

ここではスピードが最優先であることを強調しなければなりません。できるだけ早く間隔を区切る必要があります。頭に浮かんだアルゴリズムは Interval Tree でしたが、それが最善かどうかはわかりませんでした。

間隔ツリーは O(log n) 時間でクエリできます。n は間隔の数であり、構築には O(nlog n) 時間が必要ですが、いずれかを削減できるかどうか知りたいと思っていました。

ありがとう！

編集：質問があいまいであることは知っています。混乱をお詫び申し上げます。Aaron Huran の回答とそれに対するコメントを参照することをお勧めします。それは物事をより明確にするのに役立つはずです。

4

3 に答える 3

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 に答える
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)]

開始点の逆順ですべての重複する間隔を返すことに注意してください。うまくいけば、それは小さな問題です。これは、リストの先頭で動作するandではなく、リストの最後で動作するpush()andを使用しているためです。pop()insert(0)pop(0)

これは完璧ではありませんが、線形時間で実行されます。また、実際の文字列のサイズはまったく問題ではないことも覚えておいてください。実行時間は、文字列のサイズではなく、間隔の数に比例します。

于 2010-07-09T15:42:48.660 に答える
1

あなたは2つの文字列の違いを計算しようとしていますよね? どの言語でこれを行おうとしていますか?

更新: 使用する間隔をどのように選択するかについての基準がなくても、膨大な解決策が考えられます。

1 つの方法は、開始番号の最も小さい番号を取得し、その終了番号を取得することです。前の間隔の終わりよりも大きい次の開始番号を取得します。この間隔の終わりを取得して繰り返します。

したがって、0 ～ 4、5 ～ 13、8 ～ 19、10 ～ 12 の場合、0 ～ 4、5 ～ 13 が得られ、その他は無視されます。

于 2010-07-09T03:55:09.183 に答える