단어 빈도와 동적 프로그래밍을 활용하여 공백 없이 텍스트를 단어 목록으로 효율적으로 분리할 수 있는 방법은 무엇입니까?

공백 없이 텍스트를 단어 목록으로 분리

개요

공백 없이 단어로 구성된 문자열이 주어지면 이 기사에서는 효율적인 분할 알고리즘을 제시합니다. 상대 빈도를 고려하여 개별 단어로 변환합니다.

문제 설명

입력: "tableapplechairtablecupboard..."

출력: ["table", "apple", " Chair", "table", ["cupboard", ["cup", "board"]], ...]

알고리즘 개요

순진한 접근 방식이 아닌 알고리즘은 정확성을 높이기 위해 단어 빈도를 활용합니다. 단어가 독립적으로 분포되고 Zipf의 법칙을 따른다고 가정하면 알고리즘은 동적 프로그래밍을 사용하여 가장 가능성이 높은 단어 시퀀스를 식별합니다.

코드

<code class="python">from math import log

words = open("words-by-frequency.txt").read().split()
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))
maxword = max(len(x) for x in words)

def infer_spaces(s):
    cost = [0]
    for i in range(1,len(s)+1):
        c,k = best_match(i)        
        cost.append(c)

    out = []
    i = len(s)
    while i>0:
        c,k = best_match(i)
        out.append(s[i-k:i])
        i -= k

    return " ".join(reversed(out))

def best_match(i):
    candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
    return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))</code>

단어 빈도 추정

알고리즘은 Zipf의 법칙을 가정하여 단어를 상대 빈도에 매핑하는 사전에 의존합니다. 보이지 않는 단어를 설명하기 위해 높은 비용이 할당됩니다.

동적 프로그래밍

알고리즘은 잠재적인 다음 단어를 고려하여 가능한 각 단어 세그먼트의 비용을 계산합니다. 동적 프로그래밍을 사용하여 비용이 가장 낮은 경로를 선택하고 가능성이 가장 높은 단어 순서를 보장합니다.

성능 최적화

대량 입력의 경우 텍스트를 블록으로 분할하고 처리하여 알고리즘을 최적화할 수 있습니다. 독립적으로. 이렇게 하면 정확성에 큰 영향을 주지 않고 메모리 사용량이 줄어듭니다.

위 내용은 단어 빈도와 동적 프로그래밍을 활용하여 공백 없이 텍스트를 단어 목록으로 효율적으로 분리할 수 있는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!