<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">Dear Dave,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Dan Gusfield’s book (1997) is a really readable introduction to algorithms about string comparisons. Highly recommended.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><a href="https://www.amazon.com/dp/0521585198/">https://www.amazon.com/dp/0521585198/</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I also recommend Crochemore’s book:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><a href="https://www.amazon.com/dp/1107670993/">https://www.amazon.com/dp/1107670993/</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">These books are both written in a really insightful way, if you are wanting to learn more about this.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Esko Ukkonen is another person who came up with some mind-blowing ways to shorten the runtime of some algorithms, if you get into long string comparisons and heavy computations. There are slide decks by various people who discuss some
of Ukkonen’s innovative approaches.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I wrote my Ph.D. thesis on problems related to string comparisons, and I’m still interested in this area, but I don’t stay on top of every single innovation. It is a broad field. I hope that this is a useful starting point.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Warmest regards,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Mark<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Mark Daniel Ward, Ph.D.<o:p></o:p></p>
<p class="MsoNormal">Professor of Statistics and<o:p></o:p></p>
<p class="MsoNormal">(by courtesy) of Agricultural & Biological Engineering,<o:p></o:p></p>
<p class="MsoNormal">Mathematics, and Public Health;<o:p></o:p></p>
<p class="MsoNormal">Director of The Data Mine;<o:p></o:p></p>
<p class="MsoNormal">Interim Co-Director of the Integrative Data Science Initiative<o:p></o:p></p>
<p class="MsoNormal">Purdue University<o:p></o:p></p>
<p class="MsoNormal">1301 Third Street<o:p></o:p></p>
<p class="MsoNormal">West Lafayette, IN 47906-4206<o:p></o:p></p>
<p class="MsoNormal">mdw@purdue.edu<o:p></o:p></p>
<p class="MsoNormal">datamine@purdue.edu<o:p></o:p></p>
<p class="MsoNormal">phone: (765) 496-9563<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:12.0pt;color:black">From: </span></b><span style="font-size:12.0pt;color:black">Purdue-pm <purdue-pm-bounces+mdw=purdue.edu@pm.org> on behalf of Dave Jacoby <jacoby.david@gmail.com><br>
<b>Date: </b>Monday, January 18, 2021 at 8:59 PM<br>
<b>To: </b>Purdue Perl Mongers <purdue-pm@pm.org><br>
<b>Subject: </b>[Purdue-pm] Perl Challenge 96.2: Edit Distance<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal">I'm writing because I do not currently understand my next step. I may blog this. This is interesting because for most of the PWC challenges, there may be clever here or there, but mostly it's a simple matter of programming.<br>
<br>
<a href="https://perlweeklychallenge.org/blog/perl-weekly-challenge-096/" target="_blank">The Weekly Challenge - 096 (perlweeklychallenge.org)</a><b><br>
<br>
You are given two strings $S1 and $S2.</b><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><b>Write a script to find out the minimum operations required to convert $S1 into $S2.<br>
The operations can be insert, remove or replace a character.<br>
Please check out Wikipedia page (</b><a href="https://en.wikipedia.org/wiki/Edit_distance" target="_blank">Edit distance - Wikipedia</a><b>) for more information.</b><o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
The first example in the challenge and the wikipedia page is "kitten" and "sitting". There are three changes necessary to turn one to the other, shown by capitals.<br>
<br>
kitten<br>
Sitten<br>
sittIn<br>
sittinG<br clear="all">
<o:p></o:p></p>
<div>
<p class="MsoNormal"><br>
As mentioned in the Wikipedia article, we can get to the count of steps using the Levenshtein Distance. I know about that because I saw it in perlbrew internals: This is how it knows to <br>
suggest "exec" when you accidentally type "perlbrew esec", but I hadn't looked into HOW it works inside. So, I can say "there are three operations" but I can't, within the program, say we have to insert a G, replace K with S, and replace E with I.<br>
<br>
So I finally read to understand the LD algorithm, rather than restate it from Wikipedia and say that's that. To demonstrate, we'll start comparing "test" with "test". In the below examples, the first row and the first column are preset, counting up from zero.<br>
<br>
<span style="font-family:"Courier New""> t e s t</span><o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> [0,1,2,3,4]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">t [1,0,1,2,3]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">e [2,1,0,1,2]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">s [3,2,1,0,1]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">t [4,3,2,1,0]</span><o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><br>
If nothing is different in position [i,j], it simply copies the value of position i-1, j-i, and that transfers down,so that position [-1,-1], the last column of the last row, is 0, so there's no difference.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><br>
<span style="font-family:"Courier New""> t e s t</span><o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> [0,1,2,3,4]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">t [1,0,1,2,3]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">e [2,1,0,1,2]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">x [3,2,1,1,2]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">t [4,3,2,2,1]</span><o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt">Here we see that [3,3] is 1. It got that way because there is a difference, and took the minimum value of [2,2], [2,3], and [3,2], then added one.<o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> l i g h t s</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> [0,1,2,3,4,5,6]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">s [1,1,2,3,4,5,5]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">l [2,1,2,3,4,5,6]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">i [3,2,1,2,3,4,5]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">g [4,3,2,1,2,3,4]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">h [5,4,3,2,1,2,3]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">t [6,5,4,3,2,1,2]</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">This compares "slight" with "lights", which, given the add, remove or change rules, give us two. This would be removing the S from the beginning and adding S to the end. 2 changes, as [-1,-1] indicates.<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
I'm <i>thinking</i> that the way forward is to travel up and to the left with the minimum of those three values, making no change if the minimum equals the current and <br>
<br>
This Looks Like A Job For <i>RECURSION!</i> , but I believe most challenges look like that, until I think harder. Anyone else have thoughts about a better way to solve this?<o:p></o:p></p>
</div>
<p class="MsoNormal">-- <o:p></o:p></p>
<div>
<div>
<div>
<p class="MsoNormal">Dave Jacoby<br>
<a href="mailto:jacoby.david@gmail.com" target="_blank">jacoby.david@gmail.com</a><br>
<br>
“There is nothing obvious” <br>
— Theo<o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>