Как разбить строку на пробел и сохранить смещения и длины слов

Question

Мне нужно разбить строку на слова, но также получить начальное и конечное смещение слов. Так, например, если входная строка:

input_string = "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)]

У меня есть некоторый рабочий код, который делает это с помощью input_string.split и вызывает .index, но он медленный. Я пытался закодировать его, вручную перебирая строку, но это было еще медленнее. У кого-нибудь есть быстрый алгоритм для этого?

Вот мои две версии:

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

Используя timeit, «using_split» является самым быстрым, затем следует «manual_iteration», затем самое медленное до сих пор использует re.finditer, как предложено ниже.

Answer 1

Будет делать следующее:

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)

Это производит:

[('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)]

Answer 2

Следующее выполняется немного быстрее - экономит около 30%.Все, что я сделал, это заранее определил функции:

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

Answer 3

def split_span(s):
    for match in re.finditer(r"\S+", s):
        span = match.span()
        yield match.group(0), span[0], span[1] - 1

Answer 4

Мне удалось получить примерно 35% ускорение за несколько минут с помощью прямого мошенничества: я преобразовал вашу функцию using_split () в модуль Python на основе C, используя cython.Это было первое оправдание, которое мне когда-либо приходилось пробовать на Cython, и я вижу, что это довольно легко и полезно - см. Ниже.

Вставка в C была последним средством: сначала я потратил несколько часов, бездельничаяпытаясь найти более быстрый алгоритм, чем ваша версия using_split ().Дело в том, что нативный python str.split () удивительно быстр, быстрее, чем все, что я пробовал, например, используя numpy или re.Таким образом, даже если вы сканируете строку дважды, str.split () достаточно быстр, что, по-видимому, не имеет значения, по крайней мере, для этих конкретных тестовых данных.

Чтобы использовать Cython, я поместил ваш парсер в файл с именем 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
===============================================================

Затем я запустил его для установки Cython (при условии, что Debian-ish box для Linux):

sudo apt-get install cython

Затем я вызвал синтаксический анализатор из этого сценария 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)

===============================================================

Чтобы проверить, я запустил это:

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

На моем компьютере, ваш чистый PythonФункция using_split () в среднем составляет около 8,5 usec, в то время как моя версия на Cython в среднем составляет около 5,5 usec.

Подробнее на http://docs.cython.org/src/userguide/source_files_and_compilation.html

Answer 5

Внимание, скорость этого решения ограничена скоростью света:

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), (' TWO29, 31), (ДВА, 33, 35), (ТРИ, 37, 41)]

Answer 6

Мне приходит в голову, что цикл python является медленной операцией, поэтому я начал на растровых изображениях, продвинулся так далеко, и все еще быстро, но я не могу придумать способ без циклов получить индексы запуска / остановкиit:

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)

Возвращенное целое число имеет биты, установленные для каждой начальной позиции и каждой позиции остановки + 1.

PS zip () относительно медленный: достаточно быстрый, чтобы его можно было использовать один раз.медленно использовать 3 раза.

Answer 7

Вот пара идей, которые вы могли бы профилировать, чтобы убедиться, что они достаточно быстры:

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

Answer 8

Кажется, это работает довольно быстро:

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

Answer 9

Здесь у вас есть c-ориентированный подход, который повторяется только один раз по всей строке Вы также можете определить свои собственные разделители. Проверено и работает, но, вероятно, может быть чище.

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

Answer 10

Следующие идеи могут привести к ускорению:

1. Используйте деку, а не список, чтобы сохранить смещения и конвертировать в список только по возвращении.Добавление Deque не приводит к перемещению памяти, как делает добавление в список.
2. Если известно, что слова короче некоторой длины, укажите это в функции индекса.
3. Определите свои функции вместный словарь.

Примечание: я не проверял их, но вот пример

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)