Calculer la segmentation la plus score

Question

J'ai le problème suivant:

Il y a une séquence "propre" de séquences, disons:

clean = [
    [1, 2],
    [3],
    [4, 5]
]

Et une séquence "bruyante" qui n'est pas segmentée:

segmented = [1, 100, 2, 3, 3, 101, 4, 5]

Je voudrais partitionner segmented exactement len(clean) des parties telles que la somme des distances de modification de chaque partie et de son homologue propre est minimisée.

Pour cet exemple, une solution optimale serait:

optimal = [
    [1, 100, 2], # edit distance 1
    [3, 3],      # edit distance 1
    [101, 4, 5]  # edit distance 1
]                # total 3

Cela semble être un problème de programmation dynamique typique. Ma première pensée a été d'utiliser un algorithme similaire pour Ce que Tex utilise pour la rupture de ligne, qui m'a amené à Faille.

C'est là que je suis coincé, car je ne peux pas comprendre la fonction de coût. Pour la rupture de ligne régulière, la fonction cost(i,j) Le coût de la ligne passe de l'index I à l'index j, comme ici. Mais pour ce problème, nous aurions besoin d'un troisième paramètre, à savoir quelle ligne dans la référence propre à comparer.

Ce problème n'est-il pas correctement conditionné pour SMAWK? Ou existe-t-il une définition de fonction de coût différente qui me manque? Y a-t-il un autre problème similaire qui a une solution plus applicable?