visualizing edit distance

Last time we implemented edit distance in BKO, and gave a couple of simple examples. Today I just want to visualize that.

Recall from last time:

-- Levenshtein distance:
sa: insert[g,6] substitute[i,e,4] substitute[s,k,0] |kitten>
|sitting>

-- LCS distance:
sa: insert[g,6] insert[i,4] delete[e,4] insert[s,0] delete[k,0] |kitten>
|sitting>

First, we need a little bit of work to convert this to a pretty graph. First, in the console:

  context visualizing edit distance
  op1 |kitten> => substitute[s,k,0] |_self>
  op2 substitute[s,k,0] |kitten> => substitute[i,e,4] |_self>
  op3 substitute[i,e,4] substitute[s,k,0] |kitten> => insert[g,6] |_self>

  op4 |kitten> => delete[k,0] |_self>
  op5 op4 |kitten> => insert[s,0] |_self>
  op6 op5 op4 |kitten> => delete[e,4] |_self>
  op7 op6 op5 op4 |kitten> => insert[i,4] |_self>
  op8 op7 op6 op5 op4 |kitten> => insert[g,6] |_self>

Now, see what we have:

sa: dump
----------------------------------------
|context> => |context: visualizing edit distance>

op1 |kitten> => |sitten>
op4 |kitten> => |itten>

op2 |sitten> => |sittin>
op6 |sitten> => |sittn>

op3 |sittin> => |sitting>
op8 |sittin> => |sitting>

op5 |itten> => |sitten>

op7 |sittn> => |sittin>
----------------------------------------
sa: save visualizing-edit-distance--raw.sw
sa: q

$ ./sw2dot-v2.py sw-examples/visualizing-edit-distance--raw.sw

$ cat graph-examples/visualizing-edit-distance--raw.dot
digraph g {
"context" -> "visualizing edit distance"
"kitten" -> "sitten" [label="op1",arrowhead=normal]
"kitten" -> "itten" [label="op4",arrowhead=normal]
"sitten" -> "sittin" [label="op2",arrowhead=normal]
"sitten" -> "sittn" [label="op6",arrowhead=normal]
"sittin" -> "sitting" [label="op3",arrowhead=normal]
"sittin" -> "sitting" [label="op8",arrowhead=normal]
"itten" -> "sitten" [label="op5",arrowhead=normal]
"sittn" -> "sittin" [label="op7",arrowhead=normal]
}

Now, we need to tweak the operator labels to this:

$ cat graph-examples/visualizing-edit-distance.dot
digraph g {
"context" -> "visualizing edit distance"
"kitten" -> "sitten" [label="substitute[s,k,0]",arrowhead=normal]
"kitten" -> "itten" [label="delete[k,0]",arrowhead=normal]
"sitten" -> "sittin" [label="substitute[i,e,4]",arrowhead=normal]
"sitten" -> "sittn" [label="delete[e,4]",arrowhead=normal]
"sittin" -> "sitting" [label="insert[g,6]",arrowhead=normal]
"sittin" -> "sitting" [label="insert[g,6]",arrowhead=normal]
"itten" -> "sitten" [label="insert[s,0]",arrowhead=normal]
"sittn" -> "sittin" [label="insert[i,4]",arrowhead=normal]
}

And graph it with graphviz:

Which is a very pretty picture, and neatly shows how operators step through "brain space". And unlike in our previous graphs, these are not literal operators, these are function operators. It also clearly shows how kets map to nodes, and operators to links between nodes.

And a brief comment. I wonder if we want to write some code to auto-map op-sequences to pretty graphs? How easy would it be, and would there be enough use for it? Don't know yet.