문자열의 분할 영역에 대해 계산을 수행하는 현명한 효율적인 알고리즘이 있습니까?

Question

저는 문자열 모음을 분할하고 각각에 대해 간단한 계산을 실행하는 모든 가능한 방법을 반복하는 통계 프로젝트에 참여하고 있습니다. 특히, 가능한 각 하위 문자열에는 확률이 연관되어 있으므로 파티션의 하위 문자열 확률을 곱하여 합계를 구하려고합니다.

예를 들어 문자열이 'abc'이면 'a', 'b', 'c', 'ab', bc '및'abc '에 대한 확률이 있습니다. 문자열에는 'abc', 'ab | c', 'a | bc'및 'a | b | c'의 네 가지 가능한 분할이 있습니다. 알고리즘은 각 분할에 대한 구성 요소 확률의 곱을 찾은 다음 4 개의 결과 수를 합산해야합니다.

현재 파티션 (예 : 위의 예에서는 00, 01, 10, 11)에 대한 정수의 2 진 표현을 사용하는 파이썬 반복기를 작성하고 단순히 정수를 실행합니다. 불행하게도 이것은 20 자 정도의 문자열보다 훨씬 느립니다.

누구나 단순히 한 번에 하나씩 모든 파티션을 실행하지 않고이 작업을 수행하는 영리한 방법을 생각할 수 있습니까? 나는 지금이 일에 붙어있어. 일부 의견에 응답

여기에 좀 더 정보입니다 :
이 문자열 그냥 아무것도 할 수있다, 예를 들면 "는 foobar (에서는 foo2)"- 우리의 알파벳 소문자 문자 및 숫자를 더한 중괄호의 세 가지 유형 ("(",
목표는 개별 단어 '우도'가 주어진 문자열의 가능성을 얻는 것입니다. 따라서 L (S = 'abc') = P ('abc') + P ('ab') P ('c') + P ('a') P ('b' L (S = 'abc')는 문자열 'abc'을 관찰 할 통계적 우도입니다.)

Answer 1

Dynamic Programming 용액 (I 바로 질문을 이해한다면)

def dynProgSolution(text, probs): 
    probUpTo = [1] 
    for i in range(1, len(text)+1): 
    cur = sum(v*probs[text[k:i]] for k, v in enumerate(probUpTo)) 
    probUpTo.append(cur) 
    return probUpTo[-1] 

print dynProgSolution(
    'abc', 
    {'a': 0.1, 'b': 0.2, 'c': 0.3, 
    'ab': 0.4, 'bc': 0.5, 'abc': 0.6} 
) 

복잡성은 O (N ²) 때문에 쉽게 N = 20에 대한 문제를 해결하는 것이다.

왜 이런 일이 않는 방법 :

• 모든 당신이 probs['a']*probs['b'] 곱합니다 당신은 또한 곱셈 곱셈과 추가의 Distributive Property-probs['ab']
• 감사에 의해, 당신은 함께 그 두 가지를 요약하고이 하나를 곱 수있는 것 그것의 계속 전부에 의하여 합계하십시오.
• 모든 가능한 마지막 하위 문자열에 대해 이전 경로의 모든 확률의 합계를 곱한 확률을 추가하여 그로 끝나는 모든 분할 문자열의 합계를 더합니다. (대체 말씨를 감상 할 수있다. 내 파이썬 내 영어보다 더 ..)

Answer 2

먼저 병목 현상을 파악하는 프로파일 .

병목 현상이 단순히 많은 수의 가능한 파티션 일 경우, multiprocessing을 통해 병렬 처리를 권장합니다. 그래도 충분하지 않다면 Beowulf 클러스터를 조사 할 수 있습니다.

병목 현상이 단지 계산 속도가 느리다면 C로 퍼지는 것이 좋습니다. ctypes을 통해 꽤 쉽게 할 수 있습니다.

또한 파티션을 저장하는 방법에 대해서는 잘 모르겠지만 한 문자열과 suffix array을 사용하면 메모리 사용량을 상당히 줄일 수 있습니다. 병목 현상이 스왑 및/또는 캐시 미스 인 경우 큰 이점이 될 수 있습니다.

Answer 3

귀하의 문자열이 긴 문자열로 반복해서 재사용 할 예정되고, 그래서 memoizing 기술을 사용하여 값을 캐시 것 같아 시도 할 명백한 것. 이것은 단지 시간 - 공간 교환 일뿐입니다. 가장 간단한 구현은 값을 계산할 때 사전을 사용하여 값을 캐시하는 것입니다. 모든 문자열 계산에 대해 사전 조회를 수행합니다. 사전에 없으면 계산하고 추가하십시오. 후속 호출은 사전 계산 된 값을 사용합니다. 사전 조회가 계산보다 빠르다면 운이 좋을 것입니다.

나는 당신이 파이썬을 사용하고 있다는 것을 알고 있지만, 흥미가있을 수있는 부수적 인 말로 만일 당신이 펄에서 이것을한다면, 어떤 코드도 작성할 필요가 없다. Memoize module에 내장되어 있으면 캐싱이 수행됩니다.

Answer 4

산술 (및 문자열 연결)의 연관 속성을 기반으로하는 작은 리팩토링으로 계산량이 약간 줄었을 수도 있지만, 나는 그것이 생명 체인저가 될지 모르겠다. 핵심 아이디어는 다음과 같습니다.

예 : 'abcdefghik', 10-long, 일반성의 상실을 동반 한 명확성. 순진한 접근법에서는 p (a)에 9- 꼬리의 많은 파티션, p (ab)에 8- 꼬리 등의 많은 파티션을 곱하는 것입니다. 특히 p (a)와 p (b)는 p (ab)가 3 개의 곱셈과 2 개의 합계로 8 테일 (모두)의 정확히 같은 파티션을 곱하게됩니다. 그래서 밖으로 요인 :

(p(ab) + p(a) * p(b)) * (partitions of the 8-tail) 

우리는 1 개 제품 1 합을 저장하는 데,이 곱셈이 부분에 대한 1 합까지입니다. 'b'바로 오른쪽에 분할 점이있는 모든 파티션을 포함합니다. 물론 비록 하나는 이중 계산에주의해야합니다 - 그것은 'C'의 바로 분할,

(p(abc) + p(ab) * p(c) + p(a) * (p(b)*p(c)+p(bc)) * (partitions of the 7-tail) 

저축, 내부 리팩토링에 부분적으로 감사를 장착하여 파티션에 관해서. 나는이 접근법이 일반화 될 수 있다고 생각하고있다. 중간 점에서 시작하여 왼쪽과 오른쪽 부분을 분리하여 (그리고 재귀 적으로) 나누고 합산하는 모든 분할을 고려한다. 거기에 분할이없는 모든 파티션을 추가하십시오. 예에서 반쪽은 왼쪽에서 'abcde'이고 오른쪽에서 'fghik'이고, 두 번째 부분은 'ef'가 떨어져있는 모든 파티션에 대한 것입니다. 따라서 'ef'를 고려하여 모든 확률을 "축소"합니다. '를 새로운'수퍼 레터 'X로 사용하면 더 짧은 문자열'abcdXghik '(물론 그 부분 문자열에 대한 확률은 원본에 직접 매핑됩니다. 예를 들어 새 문자열의 p (cdXg)는 원래 정확히 p (cdefg).

Answer 5

itertools 모듈을 조사해야합니다. 그것은 당신을 위해 매우 빠른 발전기를 만들 수 있습니다. 입력 문자열을 받으면 가능한 모든 순열을 제공합니다. 필요한 항목에 따라 combinations() 생성기도 있습니다. 나는 당신이 "abc"를보고있을 때 "b | ca"를보고 있는지 잘 모르겠지만, 어느 쪽이든,이 모듈은 당신에게 유용 할 것입니다.