python - 我如何进一步分析和优化这个字符串标记化函数？

Question

如果查看源代码更容易，请随意跳过我冗长的解释!

所以我编写了一个函数来标记文本字符串。在最简单的情况下，它采用类似 It's a beautiful morning 的字符串并返回标记列表。对于前面的示例，输出将是 ['It', "'", 's', ' ', 'a', ' ', 'beautiful', ' ', 'morning'] .

这是通过函数的前两行实现的:

separators = dict.fromkeys(whitespace + punctuation, True)
tokens = [''.join(g) for _, g in groupby(phrase, separators.get)]

这里要注意的是 It's 被拆分成 ["It", "'", "s"]。在大多数情况下，这不是问题，但有时是。出于这个原因，我添加了 stop_words kwarg，它采用一组要“未标记化”的字符串。例如:

>>> tokenize("It's a beautiful morning", stop_words=set("It's"))
>>> ["It's", , ' ', 'a', ' ', 'beautiful', ' ', 'morning']

这种“取消标记化”是通过在标记列表中移动的滑动窗口来实现的。考虑下面的架构。该窗口被描述为 []

Iteration 1:  ['It', "'",] 's', ' ', 'a', ' ', 'beautiful', ' ', 'morning'
Iteration 2:  'It', ["'", 's',] ' ', 'a', ' ', 'beautiful', ' ', 'morning'
Iteration 3:  'It', "'", ['s', ' ',] 'a', ' ', 'beautiful', ' ', 'morning'

在每次迭代中，窗口中包含的字符串将根据 stop_words 的内容进行连接和检查。如果窗口到达标记列表的末尾并且没有找到匹配项，则窗口的大小增加 1。因此:

Iteration 9:  ['It', "'", 's',] ' ', 'a', ' ', 'beautiful', ' ', 'morning'

这里我们有一个匹配项，所以整个窗口被替换为一个元素:它的内容，连接在一起。因此，在第9次迭代结束时，我们得到:

"It's", ' ', 'a', ' ', 'beautiful', ' ', 'morning'

现在，我们必须重新开始，以防这个新标记在与它的邻居组合时形成停用词。该算法将窗口大小设置回 2 并继续。 整个过程在迭代结束时停止，其中窗口大小等于 token 列表的长度。

这种递归是我的算法效率低下的根源。对于很少取消标记的小字符串，它工作得非常快。然而，计算时间似乎随着取消标记化的数量和原始字符串的总长度呈指数增长。

这是该函数的完整源代码:

from itertools import groupby, tee, izip
from string import punctuation, whitespace

def tokenize(phrase, stop_words=None):
    separators = dict.fromkeys(whitespace + punctuation, True)
    tokens = [''.join(g) for _, g in groupby(phrase, separators.get)]

    if stop_words:
        assert isinstance(stop_words, set), 'stop_words must be a set'
        window = 2  # Iterating over single tokens is useless
        while window <= len(tokens):
            # "sliding window" over token list
            iters = tee(tokens, window)
            for i, offset in izip(iters, xrange(window)):
                for _ in xrange(offset):
                    next(i, None)

            # Join each window and check if it's in `stop_words`
            for offset, tkgrp in enumerate(izip(*iters)):
                tk = ''.join(tkgrp)
                if tk in stop_words:
                    pre = tokens[0: offset]
                    post = tokens[offset + window + 1::]
                    tokens = pre + [tk] + post
                    window = 1  # will be incremented after breaking from loop
                    break

            window += 1

    return tokens

这里有一些难以处理的数字(无论如何，这是我能做的最好的)。

>>> import cProfile
>>> strn = "it's a beautiful morning."
>>> ignore = set(["they're", "we'll", "she'll", "it's", "we're", "i'm"])
>>> cProfile.run('tokenize(strn * 100, ignore=ignore)')
cProfile.run('tokenize(strn * 100, ignore=ignore)')
         57534203 function calls in 15.737 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1   10.405   10.405   15.737   15.737 <ipython-input-140-6ef74347708e>:1(tokenize)
        1    0.000    0.000   15.737   15.737 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method fromkeys}
      899    0.037    0.000    0.037    0.000 {itertools.tee}
      900    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   365450    1.459    0.000    1.459    0.000 {method 'join' of 'str' objects}
 57166950    3.836    0.000    3.836    0.000 {next}

据此，我了解到大部分执行时间都发生在我的函数范围内。如上所述，我怀疑 window 的不断重置是导致效率低下的原因，但我不确定如何进一步诊断。

我的问题如下:

1. 我如何进一步分析此函数以确定是否确实是 window 的重置导致执行时间过长？
2. 我可以做些什么来提高性能？

非常感谢!

Answer 1

我可能误解了这个问题，但似乎只要在拆分前搜索被忽略的词就可以解决问题:

def tokenize(phrase, stop_words=()):
    stop_words = '|'.join(re.escape(x) + r'\b' for x in stop_words)
    other = '\s+|\w+|[^\s\w]+'
    regex = stop_words + '|' + other if stop_words else other
    return re.findall(regex, phrase)

正如 Michael Anderson 所指出的，您应该添加 \b 以避免匹配部分单词

编辑:新的正则表达式会将空格与标点分开。