공백 없이 연결된 단어의 텍스트 문자열을 개별 단어로 효율적으로 분할할 수 있는 방법은 무엇입니까?

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

문제

공백 없이 연결된 단어로 구성된 텍스트 문자열이 주어진 경우:

Input: "tableapplechairtablecupboard..."

이 텍스트를 개별 단어 목록으로 효율적으로 분할할 수 있는 방법은 무엇입니까?

Output: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

알고리즘

간단한 접근 방식은 텍스트 내에서 가능한 가장 긴 단어를 반복적으로 찾는 것입니다. 그러나 이는 최적이 아닌 결과로 이어질 수 있습니다.

빈도 기반 알고리즘

대신, 언어에서 단어의 상대적 빈도를 활용하여 정확성을 높일 수 있습니다.

1. 단어 분포 모델링: 단어가 독립적으로 분포되어 있고 단어 확률이 순위에 반비례하는 Zipf의 법칙을 따른다고 가정합니다.
2. 단어 비용 정의: 비용 단어의 확률은 우도의 역의 로그로 정의됩니다.

3. 동적 프로그래밍 접근 방식:

   • 첫 번째 단어가 있는 비용 배열을 초기화합니다. 요소는 0입니다.
   • 텍스트의 각 문자에 대해 해당 지점까지 문자의 총 비용을 최소화하는 단어를 찾습니다.
   • 끝에서 역추적하여 최소 비용 단어 시퀀스를 재구성합니다. .

코드 구현

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

wordcost = {}  # Dictionary of word costs using Zipf's law

maxword = max(len(word) for word in wordcost)

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

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

    return " ".join(reversed(out))</code>

결과

이 알고리즘은 텍스트를 단어 목록으로 정확하게 분할할 수 있습니다. 공백이 없습니다.

예:

Input: "tableapplechairtablecupboard..."
Output: ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]

최적화:

• 접미사 트리 : 단어 목록에서 접미사 트리를 구축하면 후보 검색 속도가 빨라질 수 있습니다.
• 텍스트 블록 분할: 큰 텍스트 입력의 경우 텍스트를 블록으로 분할하여 정확성을 유지하면서 메모리 사용량을 최소화하세요.

위 내용은 공백 없이 연결된 단어의 텍스트 문자열을 개별 단어로 효율적으로 분할할 수 있는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!