I have the following problem:

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

clean = [
    [1, 2],
    [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.


I ended up finally solving this problem: I could not figure out how to use SMAWK for this, but I found a solution using the "typical" dynamic programming solution for edit distance.

The first observation was that the total edit distance of an ideal solution is equal to the edit distance of the unsegmented input and the concatenation of the clean segments. I have no mathematical proof, I just observed it.

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"

Then I backtrack the operations, decreasing i and j depending on which operation was taken. Whenever the i index crosses a boundary in the segmented clean input, I output one line. At the end, reverse the lines and I end up with an optimal solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.