Vous cherchez une solution de programmation dynamique

Question

J'ai le problème suivant:

Une chaîne (sans espace vide) est donnée. Et j'ai aussi une fonction de coût qui retourne le coût de la chaîne (construite en ajoutant le coût évalué de chaque mot dans la chaîne). En fait, il utilise un dictionnaire et évalue la distance d'édition.

Mon programme doit insérer des espaces (le moins possible) pour obtenir le coût global optimal.

Je veux l'algorithme brut, les optimisations viendront plus loin.

Exemple:

errorfreesampletext -> erreur texte libre échantillon
scchawesomeness -> tels génialité

Answer 1

Je pense que cela devrait fonctionner.

dp[i] = minimum cost if we consider only the first i characters 

for i = 1 to n do 
    dp[i] = cost(a[1, i]) // take sequence [1, i] without splitting it 
    for k = 1 to i - 1 do 
    dp[i] = min(dp[i], dp[k] + cost(a[k + 1, i])) // see if it's worth splitting 
                // sequence [1, i] into 
                // [1, k] and [k + 1, i] 

Answer 2

Voici un algorithme. Ce n'est probablement pas le plus efficace, mais c'est le meilleur que je puisse penser.

Input: 
    A string of length n 
    A list of words 
Create a lookup table: 
    Create a grid M of n x n slots. (1..n, 1..n) 
    Create a grid W of n x n slots. (1..n, 1..n) 
    For each starting position i in 1..n: 
     For each ending position j in i..n: 
     For each word w: 
      Find the edit distance d between w and substring (i..j) 
      If d is less than M[i,j]: 
       Set M[i,j] to d 
       Set W[i,j] to w 
Find the best words for each position: 
    Create a list L of (n+1) slots. (0..n) 
    Create a list C of (n+1) slots. (0..n) 
    Set L[0] to 0 
    For each ending position i in 1..n: 
     Set L[i] to infinity 
     For each starting position j in 0..i-1: 
     If L[j] + M[i,j] is less than L[i]: 
      Set L[i] to L[j] + M[i,j] 
      Set C[i] to j 
Create the final result string: 
    Create a list R 
    Let i be the length of the input (n) 
    Repeat while i > 0: 
     Let j be C[i] 
     Prepend W[j,i] to R 
     Set i to j-1 
    Return R 

Cet algorithme est divisé en trois étapes:

1. La première étape calcule une table de consultation. M est le meilleur coût de l'insertion de n'importe quel mot dans la sous-chaîne i .. j. W est le mot associé à ce coût. O ( n mw) (n = longueur d'entrée, w = longueur de mot maximale et m = nombre de mots)

2. La deuxième étape trouve les meilleurs mots pour chaque position. L est le meilleur coût total jusqu'à la position i. C est la position de départ du dernier mot associé à ce coût. O ( n)

3. La dernière étape assemble la chaîne finale. R est une liste de mots qui reçoit le moindre coût lorsqu'elle est comparée à la chaîne d'entrée. O ( n).

La première étape est la plus coûteuse. Il devrait probablement être possible d'en raser un ordre de grandeur, mais je ne vois pas comment. Vous pourriez aussi le combiner avec l'étape 2, mais vous n'en retireriez pas grand-chose.