Intelligent Computing / 2022 / Article / Alg 4

Research Article

Fractal Parallel Computing

Algorithm 4

Edit distance.
Require: Input string ; Let
Ensure: Edit distance
1: function EditDist
2:  if is leaf and then                   End of recursion
3:   fordo
4:    
5:   end for
6:  else ifthen       Recursively compute a diagonal of the DP matrix
7:   fracop EditDist
8:   fracop EditDist
9:  else ifthen                  Entry point, initialization
10:   
11:   if then           , start diagonal computations
12:    fracop EditDist
13:   else ifthen            Swap so that
14:    fracop EditDist
15:   else                     Special case of empty strings
16:    
17:   end if
18:  else ifthen                End of computation
19:   
20:  else      Main iteration implemented as tail recursion, divided into three cases:
21:   ifthen                  1. Left upper triangle area
22:    fracop EditDist
23:    fracop EditDist
24:   else ifthen        2. Middle parallelogram area
25:    fracop EditDist
26:    fracop EditDist
27:   else               3. Right lower triangle area
28:    fracop EditDist
29:    fracop EditDist
30:   end if
31:  end if
32: end function