Comment pouvons-nous séparer efficacement le texte sans espaces dans une liste de mots, en tirant parti de la fréquence des mots et de la programmation dynamique ?

Séparer du texte sans espaces dans une liste de mots

Vue d'ensemble

Étant donné une chaîne composée de mots sans espaces, cet article présente un algorithme efficace de segmentation en mots individuels tout en considérant leurs fréquences relatives.

Énoncé du problème

Entrée : "tableapplechairtablecupboard..."

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

Présentation de l'algorithme

Plutôt que d'utiliser une approche naïve, l'algorithme exploite la fréquence des mots pour améliorer la précision. En supposant que les mots sont distribués indépendamment et suivent la loi de Zipf, l'algorithme utilise une programmation dynamique pour identifier la séquence de mots la plus probable.

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

Estimation de la fréquence des mots

L'algorithme s'appuie sur un dictionnaire qui mappe les mots à leurs fréquences relatives, en supposant la loi de Zipf. Pour tenir compte des mots invisibles, un coût élevé leur est attribué.

Programmation dynamique

L'algorithme calcule le coût de chaque segment de mot possible, en tenant compte des mots suivants potentiels. Il sélectionne le chemin le moins coûteux à l'aide d'une programmation dynamique, garantissant la séquence de mots la plus probable.

Optimisation des performances

Pour les entrées volumineuses, l'algorithme peut être optimisé en divisant le texte en blocs et en le traitant. eux indépendamment. Cela réduit l'utilisation de la mémoire sans affecter de manière significative 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!