Suche nach allen gängigen, nicht überlappenden Teilstrings

Question

Bei zwei Strings möchte ich alle gängigen Teilstrings vom längsten bis zum kürzesten String identifizieren.

Ich möchte alle "Sub" Sub-Strings entfernen. Zum Beispiel würden alle Teilstrings von '1234' nicht in der Übereinstimmung zwischen '12345' und '51234' enthalten sein.

string1 = '51234' 

string2 = '12345' 

result = ['1234', '5'] 

Ich dachte an die longest common substring zu finden, dann rekursiv die längste Teilkette zu finden (s) nach links/rechts. Ich möchte jedoch keine gemeinsame Teilzeichenfolge nach dem Fund entfernen. Zum Beispiel kann das Ergebnis unter Aktien a 6 in der Mitte:

string1 = '12345623456' 

string2 = '623456' 

result = ['623456', '23456'] 

Schließlich brauche ich eine Saite gegen eine feste Liste von Tausenden von Strings zu überprüfen. Ich bin mir nicht sicher, ob es einen intelligenten Schritt gibt, den ich machen könnte, wenn ich alle Teilstrings in diesen Strings haue.

früheren Antworten:

In diesem thread eine dynamische Programmierlösung gefunden wird, die O nimmt (nm) der Zeit, wobei n und m die Längen der Zeichenfolgen sind. Ich bin an einem effizienteren Ansatz interessiert, der Suffixbäume verwendet.

Hintergrund:

ich aus Schnipsel von Melodien Liedmelodien am Komponieren. Manchmal schafft es eine Kombination, eine Melodie zu erzeugen, die zu viele Noten in einer Reihe eines bestehenden zusammenbringt.

kann ich ein String Ähnlichkeitsmaß, wie Bearbeiten Entfernung verwenden, aber glaube, dass Melodien mit sehr kleinen Unterschieden zu Melodien einzigartig und interessant sind. Leider hätten diese Melodien Ähnlichkeiten mit Liedern, die viele Noten einer Melodie in einer Reihe kopieren.

Answer 1

Beginnen wir mit dem Baum

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) 

den Baum zu bevölkern, dann würden Sie die .add_ngram Methode verwenden.

Der nächste Teil ist ein wenig komplizierter, da sie eine gleichzeitige Traversal von Strings, während der Verfolgung des Baum Koordinaten suchen. Ziehen alle diese weg, müssen wir einige Funktionen, die auf dem Baum arbeiten und eine Abfrage-String

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)) 

So, jetzt das, was zu tun Sie wollten, dies tun:

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

Wenn etwas unklar ist, Bitte lassen Sie es mich wissen, und ich werde versuchen zu klären.