DOC/Algorithm

   1
   2 This directory previously contained a copy of
   3    An O (ND) Difference Algorithm and Its Variations
   4 by EUGENE W. MYERS
   5
   6 However it isn't clear that I have the right to redistrubute this so
   7 I've removed it.  It can easily be found by searching the internet.
   8
   9 The code in wiggle differs from the algorithm presented in that paper
  10 in one fairly minor way.
  11
  12 The paper describes how to find an optimal path or "snake" through the
  13 edit graph, but only stores the end-point and cost of the snake, not
  14 the full path (as that would require order-n^2 space).
  15
  16 It then suggests that you run the same algorithm concurrently but in
  17 reverse from the end of the graph towards the start.  When you find
  18 that the longest snakes in both directions cross, you have a midpoint
  19 on the path.
  20
  21 This is more useful than an end-point as you can recurse on either
  22 side and build up the full path using linear space and only doubling
  23 your work.
  24
  25 Wiggle takes a different approach.  Finding where the snakes cross
  26 seemed awkward to me, and having two blocks of similar but not
  27 identical code (one to search forward, one to search backwards) didn't
  28 appeal at all.
  29
  30 So wiggle only searches forward, but it remembers where the half-way
  31 line was crossed.  i.e. it remembers the 'x' value when x+y
  32 changed from below to above (max_x + max_y)/2.
  33 This uses much the same amount of storage, but significantly less code.