¿Cuál es la forma más eficiente de encontrar una de varias subcadenas en Python?

Question

Tengo una lista de posibles subcadenas, p. Ej. ['gato', 'pez', 'perro']. En la práctica, la lista contiene cientos de entradas.

Estoy procesando una cadena, y lo que estoy buscando es encontrar el índice de la primera aparición de cualquiera de estas subcadenas.

para aclarar, para '012cat' el resultado es 3, y por '0123dog789cat' el resultado es 4.

También necesito saber qué subcadena se encuentra (por ejemplo, su índice en la lista subcadena o el texto sí mismo), o al menos la longitud de la subcadena correspondiente.

Existen formas obvias de fuerza bruta para lograr esto, me preguntaba si hay alguna solución elegante de Python/Regex para esto.

Gracias, Rax

Answer 1

que asumiría una expresión regular es mejor que la comprobación de cada subcadena individualmente, porque conceptualmente la expresión regular se modela como un DFA, y así como la entrada se consume todos los partidos se están probando al mismo tiempo (lo que resulta en un escaneo de la cadena de entrada).

lo tanto, aquí está un ejemplo:

import re 

def work(): 
    to_find = re.compile("cat|fish|dog") 
    search_str = "blah fish cat dog haha" 
    match_obj = to_find.search(search_str) 
    the_index = match_obj.start() # produces 5, the index of fish 
    which_word_matched = match_obj.group() # "fish" 
    # Note, if no match, match_obj is None 

ACTUALIZACIÓN: Algunos se debe tener cuidado al combinar palabras a un solo patrón de palabras alternativas. El siguiente código construye una expresión regular, pero escapes any regex special characters y ordena las palabras para que las palabras más largas tienen la oportunidad de igualar antes de que los prefijos más cortos de la misma palabra:

def wordlist_to_regex(words): 
    escaped = map(re.escape, words) 
    combined = '|'.join(sorted(escaped, key=len, reverse=True)) 
    return re.compile(combined) 

>>> r.search('smash atomic particles').span() 
(6, 10) 
>>> r.search('visit usenet:comp.lang.python today').span() 
(13, 29) 
>>> r.search('a north\south division').span() 
(2, 13) 
>>> r.search('012cat').span() 
(3, 6) 
>>> r.search('0123dog789cat').span() 
(4, 7) 

FIN DE ACTUALIZACIÓN

Debería tenga en cuenta que querrá formar la expresión regular (es decir, llamar a re.compile()) lo menos posible. El mejor caso sería que usted sepa de antemano cuáles son sus búsquedas (o las compute una vez/con poca frecuencia) y luego guarde el resultado de re.compilar en alguna parte. Mi ejemplo es simplemente una función sin sentido para que pueda ver el uso de la expresión regular. Hay algunos documentos más expresiones regulares aquí:

http://docs.python.org/library/re.html

Espero que esto ayude.

ACTUALIZACIÓN: estoy seguro acerca de cómo pitón implementa expresiones regulares, pero a contestar la pregunta de Rax acerca de si hay o no limitaciones de re.compile() (por ejemplo, ¿cuántas palabras se puede tratar de " | "juntos para coincidir de una vez), y la cantidad de tiempo para ejecutar la compilación: ninguno de estos parece ser un problema. Probé este código, que es lo suficientemente bueno para convencerme. (Pude haber mejorado esto agregando tiempo y reportando resultados, así como arrojar la lista de palabras en un conjunto para asegurarme de que no haya duplicados ... pero ambas mejoras parecen excesivas). Este código funcionó básicamente de forma instantánea y me convenció de que puedo buscar 2000 palabras (de tamaño 10), y que, de ellas, coincidirán adecuadamente.Aquí está el código:

import random 
import re 
import string 
import sys 

def main(args): 
    words = [] 
    letters_and_digits = "%s%s" % (string.letters, string.digits) 
    for i in range(2000): 
     chars = [] 
     for j in range(10): 
      chars.append(random.choice(letters_and_digits)) 
     words.append(("%s"*10) % tuple(chars)) 
    search_for = re.compile("|".join(words)) 
    first, middle, last = words[0], words[len(words)/2], words[-1] 
    search_string = "%s, %s, %s" % (last, middle, first) 
    match_obj = search_for.search(search_string) 
    if match_obj is None: 
     print "Ahhhg" 
     return 
    index = match_obj.start() 
    which = match_obj.group() 
    if index != 0: 
     print "ahhhg" 
     return 
    if words[-1] != which: 
     print "ahhg" 
     return 

    print "success!!! Generated 2000 random words, compiled re, and was able to perform matches." 

if __name__ == "__main__": 
    main(sys.argv) 

ACTUALIZACIÓN: Debe tenerse en cuenta que el orden de las cosas ORED juntos en la expresión regular importa. Echar un vistazo a la siguiente prueba inspirada en TZOTZIOY:

>>> search_str = "01catdog" 
>>> test1 = re.compile("cat|catdog") 
>>> match1 = test1.search(search_str) 
>>> match1.group() 
'cat' 
>>> match1.start() 
2 
>>> test2 = re.compile("catdog|cat") # reverse order 
>>> match2 = test2.search(search_str) 
>>> match2.group() 
'catdog' 
>>> match2.start() 
2 

Esto sugiere las cuestiones de orden: - /. No estoy seguro de lo que esto significa para la aplicación de Rax, pero al menos se conoce el comportamiento.

ACTUALIZACIÓN: he publicado this questions about the implementation of regular expressions in Python que esperamos que nos dará una idea de los problemas encontrados con esta pregunta.

Answer 2

subs = ['cat', 'fish', 'dog'] 
sentences = ['0123dog789cat'] 

import re 

subs = re.compile("|".join(subs)) 
def search(): 
    for sentence in sentences: 
     result = subs.search(sentence) 
     if result != None: 
      return (result.group(), result.span()[0]) 

# ('dog', 4) 

Answer 3

Esta es una respuesta vaga y teórica sin ningún código proporcionado, pero espero que pueda orientarlo en la dirección correcta.

En primer lugar, necesitará una búsqueda más eficiente para su lista de subcadenas. Yo recomendaría algún tipo de estructura de árbol. Comience con una raíz, luego agregue un nodo 'a' si alguna subcadena comienza con 'a', agregue un nodo 'b' si alguna subcadena comienza con 'b', y así sucesivamente. Para cada uno de estos nodos, sigue agregando subnodos.

Por ejemplo, si usted tiene una subcadena con la palabra "hormiga", usted debe tener un nodo raíz, un nodo secundario 'a', un nodo nieto 'n', y un gran nodo nieto 't'.

Los nodos deberían ser lo suficientemente fáciles de hacer.

class Node(object): 
    children = [] 

    def __init__(self, name): 
     self.name = name 

donde name es un personaje.

Itere a través de sus cadenas letra por letra. Mantenga un registro de la carta en la que está. En cada letra, intente usar las siguientes letras para atravesar el árbol. Si tiene éxito, su número de letra será la posición de la subcadena, y su orden transversal indicará la subcadena que se encontró.

Edición de clarificación: los DFA deben ser mucho más rápidos que este método, por lo que debería aprobar Tom's answer. Solo estoy manteniendo esta respuesta en caso de que su lista de subcadenas cambie a menudo, en cuyo caso usando un árbol podría ser más rápido.

Answer 4

Antes que nada, le sugiero que ordene la lista inicial en orden ascendente. Debido a que escanear una subcadena más corta es más rápido que escanear una subcadena más larga.

Answer 5

¿Qué le parece esto?

>>> substrings = ['cat', 'fish', 'dog'] 
>>> _string = '0123dog789cat' 
>>> found = map(lambda x: (_string.index(x), x), filter(lambda x: x in _string, substrings)) 
[(10, 'cat'), (4, 'dog')] 
>>> if found: 
>>>  min(found, key=lambda x: x[0]) 
(4, 'dog') 

Obviamente, puede devolver algo que no sea una tupla.

Esto funciona por:

• Filtrado de la lista de subcadenas a los que están en la cadena
• construcción de una lista de tuplas que contienen el índice de la subcadena, y la subcadena
• Si una subcadena se ha encontrado, encuentre el valor mínimo basado en el índice

Answer 6

Solo quiero señalar la diferencia de tiempo entre la respuesta de DisplacedAussie y la respuesta de Tom. Ambos eran rápido cuando se usa una vez, por lo que no debería tener ninguna esperar perceptible para cualquiera, pero cuando el tiempo les:

import random 
import re 
import string 

words = [] 
letters_and_digits = "%s%s" % (string.letters, string.digits) 
for i in range(2000): 
    chars = [] 
    for j in range(10): 
     chars.append(random.choice(letters_and_digits)) 
    words.append(("%s"*10) % tuple(chars)) 
search_for = re.compile("|".join(words)) 
first, middle, last = words[0], words[len(words)/2], words[-1] 
search_string = "%s, %s, %s" % (last, middle, first) 

def _search(): 
    match_obj = search_for.search(search_string) 
    # Note, if no match, match_obj is None 
    if match_obj is not None: 
     return (match_obj.start(), match_obj.group()) 

def _map(): 
    search_for = search_for.pattern.split("|") 
    found = map(lambda x: (search_string.index(x), x), filter(lambda x: x in search_string, search_for)) 
    if found: 
     return min(found, key=lambda x: x[0]) 


if __name__ == '__main__': 
    from timeit import Timer 


    t = Timer("_search(search_for, search_string)", "from __main__ import _search, search_for, search_string") 
    print _search(search_for, search_string) 
    print t.timeit() 

    t = Timer("_map(search_for, search_string)", "from __main__ import _map, search_for, search_string") 
    print _map(search_for, search_string) 
    print t.timeit() 

Salidas:

(0, '841EzpjttV') 
14.3660159111 
(0, '841EzpjttV') 
# I couldn't wait this long 

Me gustaría ir con la respuesta de Tom, por tanto legibilidad y velocidad.