2a:null 2b:["$","title",null,{"children":"Minimum Edit Distance | Zihou Ng | Observable"}] 30:Tb3b,{ const colors = { red: 'rgb(255,210,210)', green: 'rgb(210,255,210)', grey: 'rgb(235,235,235)' }; const params = { size: 25, fill: { 'd': [colors.red, colors.red], 'i': [colors.green, colors.green], 's': [colors.red, colors.green], 'k': [colors.grey, colors.grey] } }; const svg = d3.select(DOM.svg(width, inputs.source.length * params.size + 60)); const grid = svg.append('g').classed('grid',true); grid.append('g').classed('source', true) .attr('transform', `translate(${params.size * 0.5},${params.size * 2.5})`) .selectAll('.char') .data(inputs.source.split('')) .join('text') .attr("font-family", "monospace") .attr('font-size', 16) .attr('text-anchor', 'middle') .attr('alignment-baseline', 'central') .attr('x', 0) .attr('y', (d, i) => i * params.size) .text(d => d); grid.append('g').classed('target', true) .attr('transform', `translate(${params.size * 2.5},${params.size * 0.5})`) .selectAll('.char') .data(inputs.target.split('')) .join('text') .attr("font-family", "monospace") .attr('font-size', 16) .attr('text-anchor', 'middle') .attr('alignment-baseline', 'central') .attr('x', (d, i) => i * params.size) .attr('y', 0) .text(d => d); const matrix = grid.append('g') .classed('matrix', true) .attr('transform',`translate(${params.size},${params.size})`); matrix.append('g').classed('path', true) .selectAll('seg').data(steps.concat([{ op: 'k', pos: [0, 0] }])) .join(enter => enter.append('g').call(g => { g.append('path') .attr('d', `M 0 ${params.size} L ${params.size} ${params.size} L 0 0 Z`) .attr('fill', d => params.fill[d.op][0]); g.append('path') .attr('d', `M 0 0 L ${params.size} ${params.size} L ${params.size} 0 Z`) .attr('fill', d => params.fill[d.op][1]); })) .attr('transform', d => `translate(${d.pos[1] * params.size},${d.pos[0] * params.size})`); matrix.append('g').classed('grid', true) .selectAll('.cell').data(distances) .join(enter => enter.append('g').call(g => { g.append('rect').classed('frame', true); g.append('text').classed('text', true); })) .classed('cell',true) .attr('transform', d => `translate(${d.pos[1] * params.size},${d.pos[0] * params.size})`) .call(g => { g.select('.frame') .attr('width', params.size) .attr('height', params.size) .attr('fill', 'none') .attr('stroke', '#aaaaaa'); g.select('.text') .text(d => d.val) .attr("font-family", "sans-serif") .attr('font-size', 12) .attr('text-anchor', 'middle') .attr('alignment-baseline', 'central') .attr('x', params.size * 0.5) .attr('y', params.size * 0.5); }); return svg.node(); }31:T5b3,results = { const compute = n => { let k = 0; const res = []; for (const { op, pos } of tx.take(n, steps)) { if (op == 'i') { res.push({ char: inputs.target[pos[1]-1], op: 'insert' }); } else if (op == 'd') { res.push({ char: inputs.source[pos[0]-1], op: 'delete' }); } else if (op == 's') { res.push({ char: inputs.target[pos[1]-1], old: inputs.source[pos[0]-1], op: 'substitute' }); } else { res.push({ char: inputs.source[pos[0]-1], op: 'keep' }); } k = pos[0]; } for (;k < inputs.source.length;k++) res.push({ char: inputs.source[k], op: 'keep' }); return res; }; const cleanup = d => { let last = -1; for (let i = d.length - 1; i >= 0; i--) { if (last < 0 && d[i].op != 'keep') { last = i; break; }; } const res = []; for (let i = 0; i < d.length; i++) { if (i < last && d[i].op == 'delete') { continue; } else if (i < last) { res.push({ char: d[i].char, op: 'keep' }); } else if (d[i].op == 'substitute') { res.push({ char: d[i].old, op: 'delete' }); res.push({ char: d[i].char, op: 'insert' }); } else { res.push(d[i]); } } return res; }; return tx.transduce( tx.comp( tx.indexed(1), tx.filter(([_,s]) => s.op != 'k'), tx.map(([n,_]) => compute(n)), tx.map(cleanup) ), tx.push(), steps ); }32:[] 2e:{"id":"7be7e89cd900a22c","slug":"minimum-edit-distance","title":"Minimum Edit Distance","thumbnail":"283af980baa6d3a01f258ba726becb3a283f27863cdb800e4582dc735a4d26c2","access_level":"public","create_time":"$D2019-10-06T14:13:37.361Z","update_time":"$D2020-09-11T00:27:05.825Z","view_time":null,"first_public_time":"$D2019-10-08T15:29:04.066Z","has_unpublished_edits":null,"fork":false,"stars":12,"starred":false,"owner":{"type":"team","id":"7fad80bf128915e9","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":"starter_2024"},"version":1433,"publish_version":1433,"role":null,"authored":false,"authors":[{"type":"individual","id":"dbb85afd665c9e5e","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":null}],"members":[{"type":"individual","id":"dbb85afd665c9e5e","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":{"id":"e318f8e4a22f544c","slug":"algorithms","title":"Algorithms","owner":{"id":"7fad80bf128915e9","login":"stwind","name":"Zihou Ng"}},"type":"notebook","body":{"titling":"auto","title":"Minimum Edit Distance","cells":[{"id":0,"value":"md`# Minimum Edit Distance`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":942,"value":"md`Definition from [Wikipedia](https://en.wikipedia.org/wiki/Edit_distance): \n\n> _The **edit distance** is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other._\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1006,"value":"md`By *operations*, it means the following:\n\n* Insert a character\n* Delete a character\n* Replace a character\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1220,"value":"md`For instance, if we want to transform the word *${inputs.source}* to *${inputs.target}*.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1090,"value":"viewof inputs = {\n const form = html``\n const source = d3.select(form.elements['source']),\n target = d3.select(form.elements['target']);\n const update = () => updateView({ \n source: source.property('value'),\n target: target.property('value')\n }, form);\n source.on('input', update);\n target.on('input', update);\n \n update();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":969,"value":"md`It will take the following ${results.length} steps:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1043,"value":"{\n const renderChar = ({ char, op }) => {\n if (op == 'delete') return `${char}`;\n else if (op == 'insert') return `${char}`\n else return char;\n };\n const renderRow = result => `${result.map(renderChar).join('')}`;\n \n return md`${results.map((r, i) => `${i+1}. ${renderRow(r)}\\n`).join('')}`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":955,"value":"md`The typical solution to this problem is the Levenshtein algorithm, which is also a classic dynamic programming algorithm. \n\nThe algorithm be summarized by the following equation:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":911,"value":"tex.block`\nlev_{a,b}(i,j) = \n\\begin{cases}\n max(i,j) & \\text{if }min(i,j) = 0, \\\\\n min \\begin{cases}\n lev_{a,b}(i-1,j) + 1 \\\\\n lev_{a,b}(i,j-1) + 1 \\\\\n lev_{a,b}(i-1,j-1) + 1_{a_i \\neq b_i}\n \\end{cases} & \\text{otherwise.}\n\\end{cases}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1178,"value":"md`To understand a DP algorithm, it is usually helpful to unroll the recursion, which results in this state transition diagram:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1243,"value":"md`## Implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1144,"value":"distances = editDistance(inputs.source, inputs.target).flat(1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":312,"value":"path = {\n const lookup = tx.lookup2d(distances, inputs.target.length + 1);\n const find = ([x, y]) => lookup([y, x]);\n const last = [inputs.source.length, inputs.target.length];\n \n return [...tx.takeWhile(x => !!x, tx.iterate(x => find(x.prev), find(last)))];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":432,"value":"steps = tx.transduce(\n tx.map(([cur, prev]) => {\n let op;\n if (cur.pos[1] == prev.pos[1]) op = 'd'; // delete\n else if (cur.pos[0] == prev.pos[0]) op = 'i'; // insert\n else op = cur.val == prev.val ? 'k' : 's'; // keep or substitute\n \n return { op, pos: cur.pos };\n }),\n tx.push(),\n tx.reverse(tx.partition(2, 1, path))\n);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":600,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"editDistance = (word1, word2) => {\n const m = word1.length, n = word2.length;\n const states = Array(m + 1).fill(0).map(x => Array(n + 1).fill(0));\n for (let i = 0; i <= m; i++) {\n for (let j = 0; j <= n; j++) {\n const pos = [i, j];\n if (i == 0) {\n states[i][j] = { prev: [0, j - 1], val: j, pos };\n } else if (j == 0) {\n states[i][j] = { prev: [i - 1, 0], val: i, pos };\n } else if (word1[i - 1] == word2[j - 1]) {\n states[i][j] = { prev: [i - 1, j - 1], val: states[i - 1][j - 1].val, pos };\n } else {\n const dirs = [[i, j - 1], [i - 1, j], [i - 1, j - 1]];\n const prev = dirs[argmin(dirs, ([x1, y1], [x2, y2]) => states[x1][y1].val < states[x2][y2].val)];\n states[i][j] = { prev, val: states[prev[0]][prev[1]].val + 1, pos };\n }\n }\n }\n return states;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"argmin = (arr, less) => arr.map((x, i) => [x, i]).reduce((a, b) => (less(a[0], b[0]) ? a : b))[1]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1098,"value":"updateView = (value, view) => {\n view.value = value;\n view.dispatchEvent(new CustomEvent(\"input\"));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1035,"value":"html`\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md`## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"tx = require('https://bundle.run/@thi.ng/transducers@7.3.0')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":930,"value":"md`## References`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":933,"value":"md`\n* [Edit distance - Wikipedia](https://en.wikipedia.org/wiki/Edit_distance)\n* [Levenshtein distance - Wikipedia](https://en.wikipedia.org/wiki/Levenshtein_distance)\n* [Understanding the Levenshtein Distance Equation for Beginners](https://medium.com/@ethannam/understanding-the-levenshtein-distance-equation-for-beginners-c4285a5604f0)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1"}} 2f:"$2e:body"