// ************************************************************************** // // // // eses eses // // eses eses // // eses eseses esesese eses Embedded Systems Group // // ese ese ese ese ese // // ese eseseses eseseses ese Department of Computer Science // // eses eses ese eses // // eses eseses eseseses eses University of Kaiserslautern // // eses eses // // // // ************************************************************************** // // The edit (Levenshtein) distance of sequences a[0..M-1] and b[0..N-1] is // // defined as the minimum number of insertions, deletions, or substitutions to// // transform one string into the other one. The definition of the distance as // // directly implemented in module DistanceLevenshtein shows that the matrix // // elements d[i][j] that will store the distance between prefixes a[0..i] and // // b[0..j] have data dependencies such that d[i][j] depends on d[i-1][j-1], // // d[i-1][j], and d[i][j-1]. Therefore, one can compute the elements of matrix// // d step by step where in each step, a diagonal of the matrix is computed. // // In the implementation below, the O(M*N) operations are scheduled to O(M+N) // // dependent macro steps where each step executes between 1 and min(M,N) many // // micro steps (note that min(M,N) is the length of the longest diagonal). // // Note that the space requirement can be reduced to O(min(M,N)) since each // // diagonal only refers to value of the two previously computed diagonals. // // ************************************************************************** // macro M = 4; // size of sequence a macro N = 5; // size of sequence b macro C = 8; // sequence elements have type nat{C} macro max(x,y) = (x<y ? y : x); macro min(x,y) = (x<y ? x : y); macro min3(x,y,z) = min(x,min(y,z)); macro minMN = min(M,N); module EditDistanceParallel([M]nat{C} ?a,[N]nat{C} ?b,nat{C} dist,event !rdy) { [M+1][N+1]nat{max(M,N)+1} d; // distances from a[0..i-1] to b[0..-1] (i.e., b is empty) for(i=0..M) d[i][0] = i; // distances from a[0..-1] to b[0..j-1] (i.e., a is empty) for(j=0..N) d[0][j] = j; // define diagonals step-by-step for(k=2..M+N) { for(i=abs(max(1,+k-N))..min(M,k-1)) { let(j=k-i) next(d[i][j]) = min3(d[i-1][j-1] + (a[i-1]==b[j-1] ? 0 : 1), d[i][j-1] + 1, d[i-1][j] + 1); } pause; } // final result dist = d[M][N]; emit(rdy); } drivenby { // dist=3 since a[0]=0;a[2]=3;a[4]=6; a = [1,2,2,3]; b = [0,2,3,3,6]; await(rdy); assert(dist==3); }