¿Puede crear una lista de Python a partir de una cadena, mientras mantiene juntos los caracteres en palabras clave específicas?

Quiero crear una lista a partir de los caracteres de una cadena, pero mantener unidas palabras clave específicas.

Por ejemplo:

palabras clave: coche, autobús

ENTRADA:

"xyzcarbusabccar" 

SALIDA:

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

Con re.findall . Alterna entre tus palabras clave primero.

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

En caso de que haya palabras clave superpuestas, tenga en cuenta que esta solución encontrará la primera que encuentre:

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

Puede hacer que la solución sea más general sustituyendo la parte [az] con lo que quiera, \w por ejemplo, o un simple . para que coincida con cualquier personaje.

Explicación breve de por qué esto funciona y por qué el regex '[az]|car|bus' no funcionaría: el motor de expresiones regulares intenta alternar las opciones de izquierda a derecha y está ” ansioso ” por devolver una coincidencia. Eso significa que considera que toda la alternancia coincide, tan pronto como una de las opciones haya sido completamente igualada. En este punto, no intentará ninguna de las opciones restantes, sino que detendrá el procesamiento e informará de una coincidencia de inmediato. Con '[az]|car|bus' , el motor informará una coincidencia cuando vea cualquier carácter en la clase de caracteres [az] y nunca pasará a verificar si ‘car’ o ‘bus’ también podrían coincidir.

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

O tal vez \S para cualquier caracter que no sea espacios en blanco:

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

Solo asegúrese de obtener el orden correcto de colocar las palabras largas primero si desea las coincidencias más largas.

 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', '!'] 

Las soluciones anteriores son realmente geniales, pero si el diccionario de palabras clave es largo, puede volverse desordenado (tal vez impensable).

Propongo almacenar las palabras clave en un árbol (que explota la redundancia) y es más eficiente en el espacio.

Si las palabras clave son ["art,"at","atm","bus","can","car"] el diccionario se ve así.

  . ^ / ¦ \ / ¦ \ abc ^ ^ ^ / \ \ \ rtua ^ ^ ^ ^ / / \ \ / \ tm /0 snr ^ ^ ^ ^ ^ / / \ \ \ /0 /0 /0 /0 /0 

Lo hice binario ya que era más fácil de dibujar. El nodo "/0" tiene el significado de la palabra final (carácter virtual) y "." es la raiz

Implementé esta simple clase de árbol para construir el árbol y las funciones necesarias.

 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) 

Dadas las palabras clave podemos construir la estructura usando un código como este.

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

Finalmente buscamos la entrada de palabras clave. La solución a continuación ofrece para una posición determinada en la entrada todas las palabras clave que coincidan a partir de esa posición.

 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 

Este código produce este

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

Importante para el código anterior es el hecho de que el carácter virtual al final de las palabras es de dos letras ( "/0" ) y nunca coincidirá (incluso si la combinación aparece en la secuencia de entrada como se detalla arriba). Además, maneja cualquier carácter de cadena (para la entrada y las palabras clave, también no es necesario introducir caracteres de escape como en re.findall() )

Desde esta lista de salida puede decidir qué quiere hacer. Si desea la solución de re.findall encuentre la palabra coincidente más larga para una posición (o en base al orden lógico de las palabras clave) y avance la cantidad de caracteres que contiene esa palabra.

Llevando el problema aún más lejos, cada carácter de la entrada es un vértice y cuando encuentre una palabra, agregue un borde desde esa posición hasta el siguiente vértice correspondiente después del último carácter de la palabra coincidente. Un algoritmo de ruta más corta le dará nuevamente la solución anterior. La estructuración de la salida como esta trae nuevamente eficiencia de espacio y abre la puerta a algoritmos más complejos.

Por ejemplo, con las palabras clave "car" y "art" y el arte y la secuencia de entrada "acart" los gráficos resultantes se ven así.

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

Análisis de complejidad

 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)