Tokenisierung von Text ohne Leerzeichen in Wörter mithilfe effizienter Algorithmen

Im Bereich der Verarbeitung natürlicher Sprache die Fähigkeit, einen kontinuierlichen Zeichenstrom aufzuteilen in bedeutungsvolle Worte zu übersetzen, ist entscheidend. Dieser Prozess, der als Tokenisierung bezeichnet wird, stellt eine besondere Herausforderung dar, wenn es um Text geht, dem Leerzeichen oder Trennzeichen fehlen „tableapplechairtablecupboard…“ in eine Wortliste unter Berücksichtigung der Möglichkeit mehrdeutiger Teilzeichenfolgen, bei denen eine Sequenz mehrere Wörter bilden kann (z. B. „cupboard“) „Tasse“ oder „Brett“).

Algorithmus: Worthäufigkeit ausnutzen

Ein naiver Ansatz, iterativ das längstmögliche Wort an jeder Position zu identifizieren, führt in der Realität zu unbefriedigenden Ergebnissen -Weltszenarien. Um diese Einschränkung zu überwinden, nutzen wir einen Algorithmus, der die Worthäufigkeitsverteilung berücksichtigt.

Modellierung der Worthäufigkeit

Wir gehen davon aus, dass Worthäufigkeiten dem Gesetz von Zipf folgen, das besagt, dass die Wahrscheinlichkeit der Anzahl der Begegnungen mit dem n-ten häufigen Wort beträgt ungefähr 1/(n * log(N)), wobei N die Gesamtzahl der Wörter in der Sprache ist. Mithilfe eines vorberechneten Kostenwörterbuchs, das diese Beziehung kodiert, können wir jedem potenziellen Wortkandidaten Kosten zuweisen.

Dynamischer Programmieransatz

Um die optimale Wortsegmentierung zu bestimmen, haben wir dynamische Programmierung einsetzen. Wir durchlaufen die Eingabezeichenfolge und behalten für jeden potenziellen Teilungspunkt einen laufenden Kostenwert bei. An jeder Position bewerten wir die Kandidatenwörter beginnend am Ende der Zeichenfolge und wählen die Aufteilung mit den niedrigsten Kosten aus.

Algorithmusimplementierung

Der bereitgestellte Python-Code bietet eine prägnante Implementierung dieses Algorithmus:

aus dem Mathe-Importprotokoll # Vorberechnetes Wortkostenwörterbuch unter Verwendung des Zipf-Gesetzes Wortkosten = ... # Hilfsfunktion zum Finden der besten Wortübereinstimmung basierend auf den Kosten def best_match(i): ... # Funktion zum Ableiten von Leerzeichen in der Eingabezeichenfolge mithilfe dynamischer Programmierung def infer_spaces(s): ...

Beispielverwendung

from math import log

# Precomputed word cost dictionary using Zipf's law
wordcost = ...

# Helper function to find the best word match based on cost
def best_match(i):
    ...

# Function to infer spaces in the input string using dynamic programming
def infer_spaces(s):
    ...

s = 'thumbgreenappleactiveassignmentweeklymetapher ' print(infer_spaces(s))

Ergebnisse und Bewertung

s = 'thumbgreenappleactiveassignmentweeklymetaphor'
print(infer_spaces(s))