Calcola la segmentazione con il punteggio più alto

Question

Ho il seguente problema:

C'è una sequenza "pulita" di sequenze, diciamo:

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

E una sequenza "rumorosa" che non è segmentata:

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

Vorrei partire segmented In esattamente len(clean) Parti tale che la somma delle distanze di modifica di ciascuna parte e della sua controparte pulita è ridotta al minimo.

Per questo esempio, una soluzione ottimale sarebbe:

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

Sembra un tipico problema di programmazione dinamica. Il mio primo pensiero era quello di usare un algoritmo simile a Ciò che Tex usa per la rottura della linea, che mi ha portato a Smawk.

È qui che sono bloccato, perché non riesco a capire la funzione di costo. Per la rottura della linea regolare, la funzione cost(i,j) è il costo di avere una linea da indice I all'indice j, come qui. Ma per questo problema, avremmo bisogno di un terzo parametro, vale a dire quale riga nel riferimento pulito a cui confrontare.

Questo problema non è condizionato correttamente per Smawk? O esiste una definizione di funzione di costo diversa che mi manca? C'è un altro problema simile che ha una soluzione più applicabile?