# Compute highest-scoring segmentation

I have the following problem:

There is a "clean" sequence of sequences, say:

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


And a "noisy" sequence which is not segmented:

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


I would like to partition segmented into exactly len(clean) parts such that the sum of the edit distances of each part and its clean counterpart is minimized.

For this example, one optimal solution would be:

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


It seems like a typical dynamic programming problem. My first thought was to use a similar algorithm to what TeX uses for line breaking, which brought me to SMAWK.

This is where I am stuck, because I cannot figure out the cost function. For regular line breaking, the function cost(i,j) is the cost of having a line go from index i to index j, like here. But for this problem, we would need a third parameter, namely which line in the clean reference to compare to.

Is this problem not conditioned correctly for SMAWK? Or is there a different cost function definition that I'm missing? Is there another, similar problem which has a more applicable solution?

I would suggest letting cost(i,j,k) be the cost of transforming [the first i-1 segments of clean, followed by the first j elements of the ith segment of clean] into [the first k elements of segmented].
You can then write a recurrence relation that expresses cost(i,j,k) in terms of values of cost(i,j-1,k), cost(i,j,k-1), and cost(i,j-1,k-1) (with a convention that cost(i,0,k) = cost(i-1,len(clean[i-1]),k)). Then, you can use dynamic programming to fill in these values.
The way I ended up doing it was storing a matrix of which edit operations were used in addition to the costs. In both matrices, mat[i,j] corresponds to "number of edit operations/final edit operation when using i entries of clean input and j entries of dirty input"