Cómo dividir una cadena en el espacio en blanco y retener las compensaciones y la longitud de las palabras

Necesito dividir una cadena en palabras, pero también obtener el desplazamiento inicial y final de las palabras. Entonces, por ejemplo, si la cadena de entrada es:

input_string = "ONE ONE ONE \t TWO TWO ONE TWO TWO THREE" 

Quiero tener:

 [('ONE', 0, 2), ('ONE', 5, 7), ('ONE', 9, 11), ('TWO', 17, 19), ('TWO', 21, 23), ('ONE', 25, 27), ('TWO', 29, 31), ('TWO', 33, 35), ('THREE', 37, 41)] 

Tengo un código de trabajo que hace esto usando input_string.split y llama a .index, pero es lento. Intenté codificarlo iterando manualmente a través de la cadena, pero eso fue aún más lento. ¿Alguien tiene un algoritmo rápido para esto?

Aquí están mis dos versiones:

 def using_split(line): words = line.split() offsets = [] running_offset = 0 for word in words: word_offset = line.index(word, running_offset) word_len = len(word) running_offset = word_offset + word_len offsets.append((word, word_offset, running_offset - 1)) return offsets def manual_iteration(line): start = 0 offsets = [] word = '' for off, char in enumerate(line + ' '): if char in ' \t\r\n': if off > start: offsets.append((word, start, off - 1)) start = off + 1 word = '' else: word += char return offsets 

Al usar timeit, “using_split” es el más rápido, seguido de “manual_iteration”, luego el más lento hasta ahora es usar re.finditer como se sugiere a continuación.

Lo siguiente corre un poco más rápido: ahorra aproximadamente un 30%. Todo lo que hice fue definir las funciones de antemano:

 def using_split2(line, _len=len): words = line.split() index = line.index offsets = [] append = offsets.append running_offset = 0 for word in words: word_offset = index(word, running_offset) word_len = _len(word) running_offset = word_offset + word_len append((word, word_offset, running_offset - 1)) return offsets 

Lo siguiente lo haremos:

 import re s = 'ONE ONE ONE \t TWO TWO ONE TWO TWO THREE' ret = [(m.group(0), m.start(), m.end() - 1) for m in re.finditer(r'\S+', s)] print(ret) 

Esto produce:

 [('ONE', 0, 2), ('ONE', 5, 7), ('ONE', 9, 11), ('TWO', 17, 19), ('TWO', 21, 23), ('ONE', 25, 27), ('TWO', 29, 31), ('TWO', 33, 35), ('THREE', 37, 41)] 
 def split_span(s): for match in re.finditer(r"\S+", s): span = match.span() yield match.group(0), span[0], span[1] - 1 

Pude obtener una aceleración de aproximadamente el 35% en unos pocos minutos haciendo trampa: convertí tu función using_split () en un módulo de python basado en C usando cython. Esta fue la primera excusa que tuve para probar el cython, y veo que es bastante fácil y gratificante, ver más abajo.

Punting into C era un último recurso: primero pasé algunas horas intentando encontrar un algoritmo más rápido que tu versión using_split (). La cuestión es que el nativo python str.split () es sorprendentemente rápido, más rápido que cualquier otro que haya intentado usar numpy o re, por ejemplo. Entonces, aunque esté escaneando la cadena dos veces, str.split () es lo suficientemente rápido como para que no parezca importante, al menos no para estos datos de prueba en particular.

Para usar cython, pongo tu analizador en un archivo llamado parser.pyx:

 ===================== parser.pyx ============================== def using_split(line): words = line.split() offsets = [] running_offset = 0 for word in words: word_offset = line.index(word, running_offset) word_len = len(word) running_offset = word_offset + word_len offsets.append((word, word_offset, running_offset - 1)) return offsets =============================================================== 

Luego ejecuté esto para instalar cython (asumiendo una caja debian-ish Linux):

 sudo apt-get install cython 

Luego llamé al analizador desde este script de python:

 ================== using_cython.py ============================ #!/usr/bin/python import pyximport; pyximport.install() import parser input_string = "ONE ONE ONE \t TWO TWO ONE TWO TWO THREE" def parse(): return parser.using_split(input_string) =============================================================== 

Para probar, corrí esto:

 python -m timeit "import using_cython; using_cython.parse();" 

En mi máquina, su función pure-python using_split () promedia alrededor de 8.5 usec runtime, mientras que mi versión de cython promedia alrededor de 5.5 usec.

Más detalles en http://docs.cython.org/src/userguide/source_files_and_comstacktion.html

Advertencia, la velocidad de esta solución está limitada por la velocidad de la luz:

 def get_word_context(input_string): start = 0 for word in input_string.split(): c = word[0] #first character start = input_string.find(c,start) end = start + len(word) - 1 yield (word,start,end) start = end + 2 print list(get_word_context("ONE ONE ONE \t TWO TWO ONE TWO TWO THREE")) 

[(‘ONE’, 0, 2), (‘ONE’, 5, 7), (‘ONE’, 9, 11), (‘TWO’, 17, 19), (‘TWO’, 21, 23) , (‘ONE’, 25, 27), (‘TWO’, 29, 31), (‘TWO’, 33, 35), (‘THREE’, 37, 41)]

Las siguientes ideas pueden resultar en aceleraciones:

  1. Use un deque en lugar de una lista para almacenar las compensaciones y convertirlas a una lista solo en la devolución. Los apéndices de Deque no producen movimientos de memoria como lo hace un apéndice de lista.
  2. Si se sabe que las palabras son más cortas que cierta longitud, proporcione esto en la función de índice.
  3. Define tus funciones en el diccionario local.

Nota: no he probado estos, pero aquí hay un ejemplo

 from collections import deque def using_split(line): MAX_WORD_LENGTH = 10 line_index = line.index words = line.split() offsets = deque() offsets_append = offsets.append running_offset = 0 for word in words: word_offset = line_index(word, running_offset, running_offset+MAX_WORD_LENGTH) running_offset = word_offset + len(word) offsets_append((word, word_offset, running_offset - 1)) return list(offsets) 

Aquí tiene un enfoque orientado a C, que solo itera una vez sobre la cadena completa. También puedes definir tus propios separadores. Probado y funciona, pero probablemente podría estar más limpio.

 def mySplit(myString, mySeperators): w = [] o = 0 iW = False word = [None, None,None] for i,c in enumerate(myString): if not c in mySeperators: if not iW: word[1]=i iW = True if iW == True and c in mySeperators: word[2]=i-1 word[0] = myString[word[1]:i] w.append(tuple(word)) word=[None,None,None] iW = False return w mySeperators = [" ", "\t"] myString = "ONE ONE ONE \t TWO TWO ONE TWO TWO THREE" splitted = mySplit(myString, mySeperators) print splitted 

Esto parece funcionar bastante rápido:

 tuple_list = [(match.group(), match.start(), match.end()) for match in re.compile("\S+").finditer(input_string)] 

Aquí hay un par de ideas que podrías perfilar para ver si son lo suficientemente rápidas:

 input_string = "".join([" ","ONE ONE ONE \t TWO TWO ONE TWO TWO THREE"," "]) #pre processing from itertools import chain stuff = list(chain(*zip(range(len(input_string)),range(len(input_string))))) print stuff stuff = iter(stuff) next(stuff) #calculate switches = (i for i in range(0,len(input_string)-1) if (input_string[next(stuff)] in " \t\r\n") ^ (input_string[next(stuff)] in " \t\r\n")) print [(word,next(switches),next(switches)-1) for word in input_string.split()] #pre processing from itertools import chain stuff = list(chain(*zip(range(len(input_string)),range(len(input_string))))) print stuff stuff = iter(stuff) next(stuff) #calculate switches = (i for i in range(0,len(input_string)-1) if (input_string[next(stuff)] in " \t\r\n") ^ (input_string[next(stuff)] in " \t\r\n")) print [(input_string[i:j+1],i,j-1) for i,j in zip(switches,switches)] 

Se me ocurre que el bucle de Python es el funcionamiento lento aquí, así que comencé con mapas de bits, llegué tan lejos y aún es rápido, pero no puedo encontrar una manera libre de bucles para obtener índices de inicio / parada:

 import string table = "".join([chr(i).isspace() and "0" or "1" for i in range(256)]) def indexed6(line): binline = string.translate(line, table) return int(binline, 2) ^ int(binline+"0", 2) 

El entero devuelto tiene bits establecidos para cada posición de inicio y cada parada + 1 posición.

PS zip () es relativamente lento: lo suficientemente rápido para ser usado una vez, demasiado lento para ser usado 3 veces.