Können Sie eine Python-Liste aus einer Zeichenfolge erstellen und gleichzeitig Zeichen in bestimmten Schlüsselwörtern beibehalten?

Question

Ich möchte eine Liste aus den Zeichen in einer Zeichenfolge erstellen, aber bestimmte Schlüsselwörter zusammenhalten.

Zum Beispiel:

Schlüsselwörter: Auto, Bus

INPUT:

"xyzcarbusabccar" 

OUTPUT:

["x", "y", "z", "car", "bus", "a", "b", "c", "car"] 

Answer 1

Mit re.findall. Wechseln Sie zuerst zwischen Ihren Keywords.

>>> import re 
>>> s = "xyzcarbusabccar" 
>>> re.findall('car|bus|[a-z]', s) 
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car'] 

Falls Sie überlappende Schlüsselwörter haben, beachten Sie, dass diese Lösung die erste Sie begegnen finden:

>>> s = 'abcaratab' 
>>> re.findall('car|rat|[a-z]', s) 
['a', 'b', 'car', 'a', 't', 'a', 'b'] 

Sie können die Lösung allgemeiner, indem es den [a-z] Teil ersetzen mit dem, was Sie mögen, \w zum Beispiel, oder eine einfache ., um jedes Zeichen zu entsprechen.

Kurze Erklärung, warum dies funktioniert und warum die Regex '[a-z]|car|bus' nicht funktionieren würde: Die reguläre Ausdruck Engine die Wechseloptionen von links nach rechts versucht und ist „eifrig“ ein Spiel zurückzukehren. Das bedeutet, dass der gesamte Wechsel berücksichtigt wird, sobald eine der Optionen vollständig übereinstimmt. Zu diesem Zeitpunkt wird keine der verbleibenden Optionen getestet, sondern die Verarbeitung gestoppt und sofort eine Übereinstimmung gemeldet. Mit '[a-z]|car|bus' meldet die Engine eine Übereinstimmung, wenn sie ein Zeichen in der Zeichenklasse [a-z] sieht und überprüft nicht, ob auch 'Auto' oder 'Bus' gefunden werden kann.

Answer 2

s = "xyzcarbusabccar" 
import re 

print re.findall("bus|car|\w", s) 
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car'] 

Oder vielleicht \S für alle nicht Leerzeichen Zeichen:

s = "xyzcarbusabccar!" 
import re 

print re.findall("bus|car|\S", s) 
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car', '!'] 

So stellen Sie sicher, dass Sie die Reihenfolge richtig setzen mehr Worte erhalten zuerst, wenn Sie die längsten Matches wollen.

In [7]: s = "xyzcarsbusabccar!" 

In [8]: re.findall("bus|car|cars|\S", s) 
Out[8]: ['x', 'y', 'z', 'car', 's', 'bus', 'a', 'b', 'c', 'car', '!'] 

In [9]: re.findall("bus|cars|car|\S", s) 
Out[9]: ['x', 'y', 'z', 'cars', 'bus', 'a', 'b', 'c', 'car', '!'] 

Answer 3

Die oben genannten Lösungen sind wirklich toll, aber wenn die Schlüsselwörter Wörterbuch kann es chaotisch werden (vielleicht unimplementable) leicht lang ist.

Ich schlage vor, die Schlüsselwörter in einem Baum zu speichern (der Redundanz ausnutzt) und ist mehr Platz effizient.

Wenn die Schlüsselwörter ["art,"at","atm","bus","can","car"] das Wörterbuch sind wie folgt aussieht

    . 
       ^
      / ¦  \ 

     / ¦  \ 
     a  b   c 
     ^ ^  ^
    / \  \   \ 
    r  t  u   a 
    ^ ^ ^  ^
/ /\  \  / \ 
    t  m /0  s  n  r 
^ ^  ^ ^ ^
/ /   \  \  \ 
/0  /0    /0  /0 /0 

ich es binär gemacht, da es leichter war, zu ziehen. Der Knoten "/0" hat die Bedeutung von Wortende (virtuelles Zeichen) und "." ist die Wurzel.

Ich implementierte diese einfache Tree-Klasse den Baum und die notwendigen Funktionen

class Tree(object): 

    def __init__(self, name='root', children=None): 
     self.name = name 
     self.children = {} 
     if children is not None: 
      for child in children: 
       self.add_child(child.name,child) 

    def __repr__(self): 
     return self.name 

    def add_child(self, node): 
     assert isinstance(node, Tree) 
     self.children[node.name] = node 


    def has_child(self,name): 
     return name in self.children 

    def get_child(self,name): 
     return self.children[name] 

    def print_tree(self,level=0): 
     sys.stdout.write('-' * level) 
     print self.name 
     for childTag in self.children: 
      self.children[childTag].print_tree(level+1) 

die Schlüsselwörter Da wir die Struktur unter Verwendung von Code wie dieser

keywords = ["car","at","atm","bus"] 
keywordsTree = Tree('') 

for keyword in keywords: 
    keywordsTreeNode = keywordsTree 
    for character in keyword: 
     if not keywordsTreeNode.has_child(character): 
      keywordsTreeNode.add_child(Tree(character)) 
     keywordsTreeNode = keywordsTreeNode.get_child(character) 

    keywordsTreeNode.add_child(Tree('/0')) 

Schließlich suchen wir den Eingang für Keywords erstellen können bauen . Die untenstehende Lösung bietet für eine gegebene Position in der Eingabe alle Schlüsselwörter, die von dieser Position ausgehend übereinstimmen.

inputWords = "xyzcarbusabccar8hj/0atm" 
output = [] 
lengthInput = len(inputWords) 
for position in range(0,lengthInput): 
    ##add by default the character 
    # allMathcedKeyWords = [inputWords[position]] 

    allMathcedKeyWords = [] 
    keywordsTreeNode = keywordsTree 
    searchPosition = position 
    curMathcedWord = '' 

    while searchPosition < lengthInput and keywordsTreeNode.has_child(inputWords[searchPosition]) : 

     keywordsTreeNode = keywordsTreeNode.get_child(inputWords[searchPosition]) 
     curMathcedWord = curMathcedWord + inputWords[searchPosition] 

     if (keywordsTreeNode.has_child("/0")): 
      allMathcedKeyWords.append(curMathcedWord) 

     searchPosition += 1 

    if len(allMathcedKeyWords)==0: 
     allMathcedKeyWords = inputWords[position] 

    output.append(allMathcedKeyWords) 

print output 

Dieser Code gibt dieses

['x', 'y', 'z', 
['car'], 
'a', 'r', 
['bus'], 
    'u', 's', 'a', 'b', 'c', 
['car'], 
    'a', 'r', '8', 'h', 'j', '/', '0', 
['at', 'atm'], 
    't', 'm'] 

Wichtig für den Code oben ist die Tatsache, dass der virtuelle Charakter am Ende der Wörter zwei Buchstaben ("/0") und wird nie (auch wenn die abgestimmt werden Kombination erscheint in der Eingabesequenz wie oben beschrieben). Darüber hinaus behandelt es jedes String-Zeichen (für die Eingabe und Schlüsselwörter - müssen auch keine Escape-Zeichen wie in re.findall())

Aus dieser Liste können Sie entscheiden, was Sie tun möchten. Wenn Sie die Lösung re.findall möchten, finden Sie das am längsten übereinstimmende Wort für eine Position (oder basierend auf der logischen Reihenfolge der Schlüsselwörter) und springen Sie die Anzahl der Zeichen, die das Wort enthält, vor. Wenn das Problem noch weiter geht, ist jedes Zeichen in der Eingabe ein Eckpunkt, und wenn Sie ein Wort finden, fügen Sie eine Kante von dieser Position zum entsprechenden nächsten Eckpunkt nach dem letzten Zeichen des übereinstimmenden Wortes hinzu. Ein Algorithmus für den kürzesten Pfad gibt Ihnen die obige Lösung erneut. Durch die Strukturierung der Ausgabe wird die Raumeffizienz wieder erhöht und die Tür zu komplexeren Algorithmen geöffnet.

Beispiel, mit Schlüsselwörter "car" und "art" und Kunst und Eingangssequenz "acart" die resultierenden Graphen

   ______________ 
      ¦    ¦ 
- a -> c -> a -> r -> t -> 
     ¦______________¦ 

Komplexität Analyse

Space : longest_word_length * number_of_letters_in_keywords 
     input_length + input_length * input_length (worst case-fully connected graph) 
Time : input_length * longest_word_length 
     input_length + input_length * input_length (worst case-fully connected graph)