Comment pouvons-nous diviser efficacement une chaîne de texte de mots concaténés sans espaces en mots individuels ?

Diviser le texte en une liste de mots sans espaces

Problème

Étant donné une chaîne de texte composée de mots concaténés sans espaces :

Input: "tableapplechairtablecupboard..."

Comment pouvons-nous diviser efficacement ce texte en une liste de mots individuels ?

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

Algorithme

Une approche simple consiste à trouver de manière itérative le mot le plus long possible dans le texte. Cependant, cela peut conduire à des résultats sous-optimaux.

Algorithme basé sur la fréquence

Au lieu de cela, nous pouvons exploiter la fréquence relative des mots dans la langue pour améliorer la précision :

1. Modéliser la distribution des mots : Supposons que les mots sont distribués indépendamment et suivent la loi de Zipf, où la probabilité du mot est inversement proportionnelle à son rang.
2. Définir le coût des mots : Le coût d'un mot est défini comme le logarithme de l'inverse de sa vraisemblance.

3. Approche de programmation dynamique :

   • Initialiser un tableau de coûts où le premier l'élément est 0.
   • Pour chaque caractère du texte, trouvez le mot qui minimise le coût total des caractères jusqu'à ce point.
   • Reculez depuis la fin pour reconstruire la séquence de mots au coût minimum .

Mise en œuvre du code

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

Résultats

Cet algorithme est capable de segmenter avec précision le texte en une liste de mots, même dans l'absence d'espaces.

Exemple :

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

Optimisations :

• Arbre de suffixes : En créant un arbre de suffixes à partir de la liste de mots, la recherche de candidats peut être accélérée.
• Fractionnement des blocs de texte : Pour les saisies de texte volumineuses, le texte peut être divisé en blocs pour minimiser l'utilisation de la mémoire tout en maintenant la précision.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!