重複しない共通の部分文字列をすべて検索する

Question

2つの文字列を指定すると、すべての共通部分文字列を最長から最短まで識別したいと考えています。

"サブ"サブストリングをすべて削除します。例として、 '1234'の部分文字列は '12345'と '51234'の間の一致に含まれません。

string1 = '51234' 

string2 = '12345' 

result = ['1234', '5'] 

私は再帰的に右/左に最長部分文字列（複数可）を見つけ、その後、longest common substringを見つけることを考えていました。しかし、見つかった後に共通の部分文字列を削除したくありません。例えば、株式真ん中に6以下の結果：

string1 = '12345623456' 

string2 = '623456' 

result = ['623456', '23456'] 

最後には、私は、文字列の何千もの固定リストに対して1つの文字列をチェックする必要があります。私は、これらの文字列のすべての部分文字列をハッシングする際にスマートなステップがあるかどうかはわかりません。

前回答：このthreadで

、動的プログラミングソリューションは、nおよびmは、文字列の長さであるO（nm）の時間を要することが分かります。私はサフィックスツリーを使うより効率的なアプローチに興味があります。

背景：

は私がメロディーの断片から曲のメロディーを構成しています。時には、コンビネーションが、既存のものの行の中で非常に多くの音符に一致するメロディーを生成することを管理することもある。

距離の編集などの文字列類似度を使用できますが、メロディとの差が非常に小さい曲はユニークで興味深いものだと思います。残念なことに、これらの曲は、メロディの多くの音符を連続してコピーする曲と同様のレベルの類似性を持っています。

Answer 1

、あなたが.add_ngramメソッドを使用したいツリーを移入するにはツリー

from collections import defaultdict 
def identity(x): 
    return x 


class TreeReprMixin(object): 
    def __repr__(self): 
     base = dict(self) 
     return repr(base) 


class PrefixTree(TreeReprMixin, defaultdict): 
    ''' 
    A hash-based Prefix or Suffix Tree for testing for 
    sequence inclusion. This implementation works for any 
    slice-able sequence of hashable objects, not just strings. 
    ''' 
    def __init__(self): 
     defaultdict.__init__(self, PrefixTree) 
     self.labels = set() 

    def add(self, sequence, label=None): 
     layer = self 
     if label is None: 
      label = sequence 
     if label: 
      layer.labels.add(label) 
     for i in range(len(sequence)): 
      layer = layer[sequence[i]] 
      if label: 
       layer.labels.add(label) 

     return self 

    def add_ngram(self, sequence, label=None): 
     if label is None: 
      label = sequence 
     for i in range(1, len(sequence) + 1): 
      self.add(sequence[:i], label) 

    def __contains__(self, sequence): 
     layer = self 
     j = 0 
     for i in sequence: 
      j += 1 
      if not dict.__contains__(layer, i): 
       break 
      layer = layer[i] 
     return len(sequence) == j 

    def depth_in(self, sequence): 
     layer = self 
     count = 0 
     for i in sequence: 
      if not dict.__contains__(layer, i): 
       print "Breaking" 
       break 
      else: 
       layer = layer[i] 
      count += 1 
     return count 

    def subsequences_of(self, sequence): 
     layer = self 
     for i in sequence: 
      layer = layer[i] 
     return layer.labels 

    def __iter__(self): 
     return iter(self.labels) 


class SuffixTree(PrefixTree): 
    ''' 
    A hash-based Prefix or Suffix Tree for testing for 
    sequence inclusion. This implementation works for any 
    slice-able sequence of hashable objects, not just strings. 
    ''' 
    def __init__(self): 
     defaultdict.__init__(self, SuffixTree) 
     self.labels = set() 

    def add_ngram(self, sequence, label=None): 
     if label is None: 
      label = sequence 
     for i in range(len(sequence)): 
      self.add(sequence[i:], label=label) 

で始まるのをしてみましょう。

次の部分は、ツリーの座標を追跡しながら、同時に並んでいる文字列を探しているので少し難解です。このすべてをやってのけるために、我々はあなたが望んでいたことを行うようになりましたので、木の上で動作し、いくつかの機能とクエリ文字列

def overlapping_substrings(string, tree, solved=None): 
    if solved is None: 
     solved = PrefixTree() 
    i = 1 
    last = 0 
    matching = True 
    solutions = [] 
    while i < len(string) + 1: 
     if string[last:i] in tree: 
      if not matching: 
       matching = True 
      else: 
       i += 1 
       continue 
     else: 
      if matching: 
       matching = False 
       solutions.append(string[last:i - 1]) 
       last = i - 1 
       i -= 1 
     i += 1 
    if matching: 
     solutions.append(string[last:i]) 
    for solution in solutions: 
     if solution in solved: 
      continue 
     else: 
      solved.add_ngram(solution) 
      yield solution 

def slide_start(string): 
    for i in range(len(string)): 
     yield string[i:] 

def seek_subtree(tree, sequence): 
    # Find the node of the search tree which 
    # is found by this sequence of items 
    node = tree 
    for i in sequence: 
     if i in node: 
      node = node[i] 
     else: 
      raise KeyError(i) 
    return node 

def find_all_common_spans(string, tree): 
    # We can keep track of solutions to avoid duplicates 
    # and incomplete prefixes using a Prefix Tree 
    seen = PrefixTree() 
    for substring in slide_start(string): 
     # Drive generator forward 
     list(overlapping_substrings(substring, tree, seen)) 
    # Some substrings are suffixes of other substrings which you do not 
    # want 
    compress = SuffixTree() 
    for solution in sorted(seen.labels, key=len, reverse=True): 
     # A substrings may be a suffix of another substrings, but that substrings 
     # is actually a repeating pattern. If a solution is 
     # a repeating pattern, `not solution in seek_subtree(tree, solution)` will tell us. 
     # Otherwise, discard the solution 
     if solution in compress and not solution in seek_subtree(tree, solution): 
      continue 
     else: 
      compress.add_ngram(solution) 
    return compress.labels 

def search(query, corpus): 
    tree = SuffixTree() 
    if isinstance(corpus, SuffixTree): 
     tree = corpus 
    else: 
     for elem in corpus: 
      tree.add_ngram(elem) 
    return list(find_all_common_spans(query, tree)) 

を必要とし、これを実行します。何かが不明である場合

search("12345", ["51234"]) 
search("623456", ["12345623456"]) 

を、私に知らせてください、私は明確にしようとします。