2つのmin（長さまたは値）のn要素に（文字列または整数）を分割する

Question

私はさまざまな長さの文字列が〜120,000文字のリストを持っています。辞書に存在するサブストリングで構成され、このサブストリングはさまざまな長さと最小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文字の長い文字列では、1文字列を処理するのに2秒かかる（リスト全体の時間）。 18文字の長い文字列の場合、私は131072のうち1596個の良いスライスが得られるので、98％は役に立たない。 より速い方法がありますか？ eyquemコメントへの回答で指定する

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 

：

私は日本語で単語の辞書を持っている（日本はスペースを使用していない）と4文字以上の長さの言葉の多くは化合物です短い言葉でできた言葉。短い単語に分割できる単語を除外したい後で私はリストを通って、言葉のスライスが意味的な意味を持つことを確かめることができた。

このアプローチは残酷な力です。私はこれがより簡単になると思っていましたが、より論理的ではなく複雑なforループと限られた再帰を使用することができました。 左から開始とで​​きるだけ長い単語を見つける...

よろしく バートは

Answer 1

私はわからないんだけど、これは役立ちますが、あなたは修正radix treeを実装してみてください。