Pouvez-vous créer une liste Python à partir d'une chaîne, tout en conservant les caractères de mots-clés spécifiques ensemble?

Question

Je souhaite créer une liste à partir des caractères d'une chaîne, tout en conservant des mots clés spécifiques.

Par exemple:

mots-clés: voiture, bus

CONTRIBUTION:

 "xyzcarbusabccar"
 

SORTIE:

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

Answer 1

Avec re.findall. Alterner entre vos mots clés.

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

En cas de chevauchement des mots-clés, notez que cette solution permettra de trouver le premier que vous rencontrez:

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

Vous pouvez rendre la solution plus générale, par la substitution de l' [a-z] de la partie avec ce que vous voulez, \w par exemple, ou un simple . pour correspondre à n'importe quel caractère.

Courte explication de ce qui fonctionne et pourquoi les regex '[a-z]|car|bus' ne fonctionnerait pas: Le moteur d'expression régulière essaie de l'alternance des options de gauche à droite et est "impatient" de retour d'un match. Cela veut dire qu'il tient compte de l'ensemble alternance de match dès que l'une des options a été parfaitement appariées. À ce stade, il ne va pas essayer toutes les options restantes, mais arrêter le traitement et rapport un match immédiatement. Avec '[a-z]|car|bus', le moteur de rapport un match quand il voit n'importe quel caractère dans la classe de caractères [a-z] et jamais de vérifier si "auto" ou " bus " pourrait également être adapté.

Answer 2

 s = "xyzcarbusabccar"
import re

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

Ou peut-être \S pour tout caractère autre qu'un espace:

 s = "xyzcarbusabccar!"
import re

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

Assurez-vous simplement que l'ordre est correct, en mettant les mots les plus longs en premier si vous voulez les correspondances les plus longues.

 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

Les solutions ci-dessus sont vraiment super, mais si les mots-clés dictionnaire est long il peut facilement devenir malpropre(peut-être unimplementable).

Je propose de stocker les mots-clés dans un arbre (qui exploite la redondance) et est plus efficace de l'espace.

Si les mots clés sont ["art,"at","atm","bus","can","car"] le dictionnaire ressemble à ceci

                 .
                 ^
            /    ¦      \

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

Je l'ai fait binaire car il était plus facile à dessiner. Le nœud "/0" a la signification de la fin du mot (personnage virtuel) et "." est la racine.

J'ai mis en place cette simple classe de l'Arbre pour construire l'arbre et de fonctions nécessaires

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)

Étant donné les mots-clés que nous pouvons construire la structure à l'aide de code comme ceci

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

Enfin, nous sommes la recherche de l'entrée de mots-clés. La solution ci-dessous offre pour une position donnée dans la saisie de tous les mots-clés appariés à partir de cette position.

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

Ce code de sorties ce

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

Important pour le code ci-dessus est le fait que le personnage virtuel à la fin des mots de deux lettres ("/0") et ne sera jamais égalé (même si la combinaison apparaît dans la séquence d'entrée comme détaillé ci-dessus). En outre, il gère toute la chaîne de caractère (pour l'entrée et des mots - clés n'ont pas besoin d'introduire des caractères d'échappement comme en re.findall() )

À partir de cette liste de sortie, vous pouvez décider ce que vous voulez faire. Si vous voulez la solution d' re.findall trouver le plus long appariés mot pour un poste (ou basé sur des mots-clés ordre logique) et le saut à l'avance le nombre de caractères que le mot contient.

En prenant le problème encore plus loin, tous les personnages de l'entrée est un sommet et lorsque vous trouvez un mot ajouter un bord à partir de cette position correspondant prochain sommet après le dernier caractère de la correspondance mot. Un plus court chemin algorithme de vous donner à nouveau la solution ci-dessus. La structuration de la sortie comme celle-ci ramène l'efficacité de l'espace et ouvre la porte à des algorithmes plus complexes.

Exemple, avoir des mots-clés "car" et "art" , l'art et la séquence d'entrée "acart" de la résultante des graphiques ressemble à ceci

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

L'analyse de la complexité

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)