Wie können wir Text ohne Leerzeichen effizient in eine Wortliste aufteilen und dabei Worthäufigkeit und dynamische Programmierung nutzen?

Text ohne Leerzeichen in eine Wortliste aufteilen

Übersicht

Angenommen eine Zeichenfolge, die aus Wörtern ohne Leerzeichen besteht, stellt dieser Artikel einen effizienten Algorithmus zur Segmentierung vor in einzelne Wörter unter Berücksichtigung ihrer relativen Häufigkeiten.

Problemstellung

Eingabe: "tableapplechairtablecupboard..."

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

Algorithmus-Übersicht

Anstatt einen naiven Ansatz zu verwenden, nutzt der Algorithmus die Worthäufigkeit, um die Genauigkeit zu verbessern. Unter der Annahme, dass Wörter unabhängig voneinander verteilt werden und dem Gesetz von Zipf folgen, verwendet der Algorithmus dynamische Programmierung, um die wahrscheinlichste Wortfolge zu identifizieren.

Der Code

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

Worthäufigkeitsschätzung

Der Algorithmus basiert auf einem Wörterbuch, das Wörter ihren relativen Häufigkeiten zuordnet und dabei das Zipf-Gesetz annimmt. Um unsichtbare Wörter zu berücksichtigen, werden ihnen hohe Kosten zugewiesen.

Dynamische Programmierung

Der Algorithmus berechnet die Kosten jedes möglichen Wortsegments unter Berücksichtigung der potenziellen nächsten Wörter. Mithilfe dynamischer Programmierung wird der Pfad mit den geringsten Kosten ausgewählt und so die wahrscheinlichste Wortfolge sichergestellt.

Leistungsoptimierung

Bei großen Eingaben kann der Algorithmus optimiert werden, indem der Text in Blöcke aufgeteilt und verarbeitet wird sie unabhängig voneinander. Dies reduziert den Speicherverbrauch, ohne die Genauigkeit wesentlich zu beeinträchtigen.

Das obige ist der detaillierte Inhalt vonWie können wir Text ohne Leerzeichen effizient in eine Wortliste aufteilen und dabei Worthäufigkeit und dynamische Programmierung nutzen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!