把一个（字符串或整数）分成最小值（长度或值）为2的元素

Question

我有一个12万个不同长度的字符串（从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个字符长的字符串的情况下，我得到了1596个很好的片从131072可能，所以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个字符或更长的单词是由较短的单词组成的复合词。我想过滤掉那些可以拆分成较短单词的单词。稍后我可以浏览列表，确保单词的切分具有语义意义。你知道吗

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

敬礼 巴特

Answer 1

我不确定这是否有帮助，但您可以尝试实现修改的radix tree。你知道吗