Rosetta Code

Levenshtein distance/Alignment: Difference between revisions

Page Discussion

Levenshtein distance/Alignment (view source)

Revision as of 23:55, 14 May 2021

13,443 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
mNo edit summary
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 629:
=={{header|Phix}}==
{{trans|Kotlin}} plus the indicator from Go
<!--<lang Phix>function LevenshteinAlignment(string a, bphixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">LevenshteinAlignment</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
integer la = length(a)+1,
<span style="color: #004080;">integer</span> <span style="color: #000000;">la</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
lb = length(b)+1
<span style="color: #000000;">lb</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
sequence costs = repeat(repeat(0,lb),la)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">costs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lb</span><span style="color: #0000FF;">),</span><span style="color: #000000;">la</span><span style="color: #0000FF;">)</span>
for j=1 to lb do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lb</span> <span style="color: #008080;">do</span>
costs[1][j] = j
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for i=2 to la do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">la</span> <span style="color: #008080;">do</span>
costs[i][1] = i
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
for j=2 to lb do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lb</span> <span style="color: #008080;">do</span>
integer tmp1 = 1+min(costs[i-1][j], costs[i][j-1]),
<span style="color: #004080;">integer</span> <span style="color: #000000;">tmp1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]),</span>
tmp2 = costs[i-1][j-1] + (a[i-1]!=b[j-1])
<span style="color: #000000;">tmp2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
costs[i][j] = min(tmp1, tmp2)
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp2</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- walk back through matrix to figure out the path</span>
string arev = "",
<span style="color: #004080;">string</span> <span style="color: #000000;">arev</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span>
brev = ""
<span style="color: #000000;">brev</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
integer i = la, j = lb
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">la</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lb</span>
while i>1 and j>1 do
<span style="color: #008080;">while</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
integer tmp = costs[i-1][j-1] + (a[i-1]!=b[j-1])
<span style="color: #004080;">integer</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
switch costs[i][j] do
<span style="color: #008080;">switch</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
case tmp: i -= 1; arev &= a[i]
<span style="color: #008080;">case</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">arev</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
j -= 1; brev &= b[j]
<span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">brev</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
case 1 + costs[i-1][j]: i -= 1; arev &= a[i]
<span style="color: #008080;">case</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]:</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">arev</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
brev &= '-'
<span style="color: #000000;">brev</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'-'</span>
case 1 + costs[i][j-1]: arev &= '-'
<span style="color: #008080;">case</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]:</span> <span style="color: #000000;">arev</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'-'</span>
j -= 1; brev &= b[j]
<span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">brev</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
end switch
<span style="color: #008080;">end</span> <span style="color: #008080;">switch</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return {reverse(arev),reverse(brev)}
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arev</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">brev</span><span style="color: #0000FF;">)}</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure test(string a,b)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
{a,b} = LevenshteinAlignment(a,b)
<span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">LevenshteinAlignment</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
string c = sq_add(repeat(' ',length(a)),sq_mul(sq_ne(a,b),'|'-' '))
<span style="color: #004080;">string</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_ne</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'|'</span><span style="color: #0000FF;">-</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">))</span>
printf(1,"%s\n%s\n%s\n\n",{a,b,c})
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n%s\n%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">})</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
test("rosettacode", "raisethysword")
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"rosettacode"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"raisethysword"</span><span style="color: #0000FF;">)</span>
test("place", "palace")</lang>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"place"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"palace"</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
<pre>
Petelomax
7,795

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/230649"