python - 将 a(字符串或整数)划分为 min(长度或值)为 2 的 n 个元素

Question

我有一个大约 120'000 个不同长度(从 4 到 27)的字符串的列表，我想检查这些字符串是否由字典中存在的子字符串组成，并且这个子字符串可以是各种长度，最小 2 个字符长。

例如，一个 9 个字符长的字符串将被分成至少 2 个子字符串。当然我需要所有可能的组合

astring = '123456789'
# possible divisions
2 sub-strings = [['12','3456789'],['1234567','89'],['123','456789'],...]
3 sub-strings = [['12345', '67','89'],['1234','567','89']...]
4 sub-strings = [['12','34','56','789'],['12','34','567','89']...]

我找到了code below at this address，根据要求拒绝结果后我得到了我需要的东西，但我不确定它是不是太慢了。对于 18 个字符长的字符串，处理一个字符串需要 2 秒(整个列表需要几个小时)。 如果是 18 个字符长的字符串，我会从 131072 个可能的切片中得到 1596 个好的切片，所以 98% 是无用的。 有没有更快的方法？

from itertools import chain, combinations

def partition(iterable, chain=chain, map=map):
    s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable)
    n = len(s)
    first, middle, last = [0], range(1, n), [n]
    getslice = s.__getslice__
    return [map(getslice, chain(first, div), chain(div, last))
            for i in range(n) for div in combinations(middle, i)]
some_string = '12345678'

for xyz in xrange(100):
    for x in partition(some_string):
        if (any(len(astring) == 1 for astring in x)):
            continue
        if len(x) == 1:
            continue
        # otherwise do something here

在回复eyquem评论时指定:

我有一本日语单词词典(日语不使用空格)，许多长度为 4 个字符或更长的单词是由较短单词组成的复合词。我想过滤掉那些可以分成更短单词的单词。稍后我可以浏览列表并确保单词切片具有语义意义。

这种方法是一种残酷的力量，我认为它会更简单，我可以使用它来代替更逻辑但更复杂的有限递归的循环。 从左边开始，找到最长的单词...

问候 巴特

Answer 1

我不确定这是否有帮助，但您可以尝试实现修改后的 radix tree .