changeset 4:de7bbee608ee

Abandon narrowing idea -- no actual benefit
author Jordi Gutiérrez Hermoso <jordigh@gmail.com>
date Thu, 30 Dec 2010 02:30:29 -0600
parents 56c58a177cde
children 49a1f3e7eff2
files levenshtein.c++
diffstat 1 files changed, 11 insertions(+), 44 deletions(-) [+]
line wrap: on
line diff
--- a/levenshtein.c++
+++ b/levenshtein.c++
@@ -26,53 +26,19 @@
     return m;
   }
 
-  //Narrowing won't help, let's do the full matrix, easier to handle
-  //this special case here.
-  if( bsize <= m/2)
-  {
-    //Just need two rows at a time
-    vector<size_t> prevrow(bsize+1), thisrow(bsize+1);
-
-    for(size_t i = 0; i <= bsize; i++)
-      prevrow[i] = i;
+  //Just need two rows at a time
+  vector<size_t> prevrow(bsize+1), thisrow(bsize+1);
 
-    for(size_t i = 1; i <= asize; i ++)
-    {
-      thisrow[0] = i;
-      for(size_t j = 1; j <= bsize; j++)
-      {
-        thisrow[j] = min(prevrow[j-1] + size_t(a[i-1] != b[j-1]),
-                         1 + min(prevrow[j],thisrow[j-1]) );
-      }
-      swap(thisrow,prevrow);
-    }
-
-    if(swapped)
-      swap(a,b); //unswap
+  for(size_t i = 0; i <= bsize; i++)
+    prevrow[i] = i;
 
-    return prevrow[bsize];
-  }
-  //Otherwise, we do the narrower algorithm...
-
-  //Only need to look at the diagonal of width 2m+1.
-  size_t diag = 2*m+1;
-
-  //Pad on each side in order to make edge cases easier, fill
-  //everything with our max allowed value, can only go down from
-  //there.
-  vector<size_t> thisrow(diag+2,100), prevrow(diag+2,100);
-
-  for(size_t i = m+1, j = 0; i < diag+2; i++, j++)
-    prevrow[i] = j;
-
-  for(size_t i = 1; i <= asize; i++)
+  for(size_t i = 1; i <= asize; i ++)
   {
-    for(size_t j = max(size_t(1), m + 1 - i);
-        j <= min(diag, diag + bsize - m - i); j++)
+    thisrow[0] = i;
+    for(size_t j = 1; j <= bsize; j++)
     {
-      //This one handles all possible cases, thanks to padding.
-      thisrow[j] = min(prevrow[j-1] + size_t(a[i-1] != b[j-1-m-i]),
-                       1 + min(prevrow[j], thisrow[j-1]) );
+      thisrow[j] = min(prevrow[j-1] + size_t(a[i-1] != b[j-1]),
+                       1 + min(prevrow[j],thisrow[j-1]) );
     }
     swap(thisrow,prevrow);
   }
@@ -80,5 +46,6 @@
   if(swapped)
     swap(a,b); //unswap
 
-  return min(prevrow[diag+1],m);
+  return prevrow[bsize];
+
 }