Mercurial > hg > toys
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]; + }