min (길이 또는 값)이 2 인 n 요소로 문자열 (문자열 또는 정수) 분할

Question

다양한 길이 (~ 27)의 ~ 120'000 문자열 목록이 있으며이 문자열 는 사전에있는 하위 문자열로 구성되며이 하위 문자열은 다양한 길이와 최소 2자를 가질 수 있습니다.

예를 들어 9 자 길이의 문자열은 최소 2 개의 하위 문자열로 나뉩니다. 물론 나는 모든 가능한 내가 code below at this address을 발견

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']...] 

조합 내가 필요한 것을 가지고 요구 사항에 따라 결과를 거부 한 후 필요하지만, 너무 느린하지 있는지 확실하지 않습니다. 18 자 긴 문자열에서 한 문자열 (전체 목록의 경우 시간)을 처리하는 데 2 ​​초가 걸립니다. 18 문자 길이의 문자열의 경우 131072에서 1596 개의 좋은 조각을 얻을 수 있으므로 98 %는 쓸모가 없습니다. 더 빠른 방법이 있습니까? 나는 화합물이다 일본어 단어 (일본어 공백을 사용하지 않는) 4 개 문자 이상 길이의 단어의 많은 사전을 가지고

:

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에 대답 설명을 지정합니다 짧은 단어로 만들어진 단어. 짧은 단어로 나눌 수있는 단어를 걸러 내고 싶습니다. 나중에 나는 목록을 살펴보고 단어의 조각이 의미 론적 의미를 갖도록 할 수있다.

이 접근법은 다소 잔인한 힘입니다.이 방법은 좀 더 간단 할 것으로 생각되며 제한된 재귀가있는 더 복잡한 논리적 루프 대신 사용할 수 있습니다. 왼쪽에서 시작 및 가능한 가장 긴 단어를 찾는 ...

감사 바트

Answer 1

잘 모르겠어요이 있습니다,하지만 당신은 수정 radix tree을 구현하는 시도 할 수 있습니다.