Wie können wir eine Textfolge aus aneinandergereihten Wörtern ohne Leerzeichen effizient in einzelne Wörter aufteilen?

Text in eine Wortliste ohne Leerzeichen aufteilen

Problem

Gegeben sei eine Textzeichenfolge, die aus aneinandergereihten Wörtern ohne Leerzeichen besteht:

Input: "tableapplechairtablecupboard..."

Wie können wir diesen Text effizient in eine Liste einzelner Wörter aufteilen?

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

Algorithmus

Ein einfacher Ansatz besteht darin, iterativ das längstmögliche Wort im Text zu finden. Dies kann jedoch zu suboptimalen Ergebnissen führen.

Frequenzbasierter Algorithmus

Stattdessen können wir die relative Häufigkeit von Wörtern in der Sprache ausnutzen, um die Genauigkeit zu verbessern:

1. Modellieren Sie die Wortverteilung: Gehen Sie davon aus, dass Wörter unabhängig voneinander verteilt sind und dem Gesetz von Zipf folgen, wobei die Wortwahrscheinlichkeit umgekehrt proportional zu ihrem Rang ist.
2. Wortkosten definieren: Die Kosten eines Wortes ist definiert als der Logarithmus des Kehrwerts seiner Wahrscheinlichkeit.

3. Dynamischer Programmieransatz:

   • Initialisieren Sie ein Kostenarray, bei dem das erste Element ist 0.
   • Suchen Sie für jedes Zeichen im Text das Wort, das die Gesamtkosten für Zeichen bis zu diesem Punkt minimiert.
   • Gehen Sie vom Ende zurück, um die Wortsequenz mit den minimalen Kosten zu rekonstruieren .

Code-Implementierung

<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>

Ergebnisse

Dieser Algorithmus ist in der Lage, Text präzise in eine Liste von Wörtern zu segmentieren, sogar in das Fehlen von Leerzeichen.

Beispiel:

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

Optimierungen:

• Suffixbaum : Durch den Aufbau eines Suffixbaums aus der Wortliste kann die Kandidatensuche beschleunigt werden.
• Aufteilung von Textblöcken: Bei großen Texteingaben kann der Text in Blöcke aufgeteilt werden Minimieren Sie die Speichernutzung und bewahren Sie gleichzeitig die Genauigkeit.

Das obige ist der detaillierte Inhalt vonWie können wir eine Textfolge aus aneinandergereihten Wörtern ohne Leerzeichen effizient in einzelne Wörter aufteilen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!