31:Ted9,class Levenshtein{ constructor(mismatch_cost=1, delete_insert_cost=1){ this.mismatch_cost = mismatch_cost; this.delete_insert_cost = delete_insert_cost; } edit_path(dist_matrix){ const nrows = dist_matrix.length; const ncols = dist_matrix[0].length; const edit_matrix = [...dist_matrix]; for(var i=0; i=1 && j>=1){ const moves = new Map([ ["m", [i-1,j-1]], ["d", [i-1,j]], ["i", [i,j-1]], ]) const costs = new Map([ ["m", dist_matrix[i-1][j-1]], ["d", dist_matrix[i-1][j]], ["i", dist_matrix[i][j-1]], ]); const best_cost = argMin(Array.from(costs.entries()), (x) => x); const best_move = moves.get(best_cost[0]); //console.log(i, j, best_cost, best_move); edits.push(best_cost[0]); edit_matrix[i][j] = best_cost[0]; i = best_move[0]; j = best_move[1]; } return { edit_matrix: edit_matrix, edits: edits.reverse() }; } distance(str1, str2){ var dist_matrix = new Array(str1.length+1); for(var i=0; i<=str1.length; i++){ dist_matrix[i] = new Array(str2.length+1); dist_matrix[i].fill(null); } dist_matrix[0][0] = 0 const mismatch_cost=this.mismatch_cost; const delete_insert_cost=this.delete_insert_cost; function compute(i, j){ if(i==0){ dist_matrix[i][j] = j*delete_insert_cost; } if(j==0){ dist_matrix[i][j] = i*delete_insert_cost; } if(dist_matrix[i][j] != null){ return dist_matrix[i][j]; } var current_dist = mismatch_cost; if(i > 0 && j > 0 && str1[i-1] == str2[j-1]){ current_dist=0; } //const current_dist = (str1[i-1] == str2[j-1] ? 0: 1); const mismatch_dist = current_dist + compute(i-1, j-1); const delete_dist = delete_insert_cost + compute(i-1, j); const insert_dist = delete_insert_cost + compute(i, j-1); const best_dist = Math.min(mismatch_dist, delete_dist, insert_dist); dist_matrix[i][j] = best_dist; return best_dist; } const best_dist = compute(str1.length, str2.length); const edit_path = this.edit_path(dist_matrix); return { best_dist: best_dist, dist_matrix: dist_matrix, edit_matrix: edit_path.edit_matrix, edits: edit_path.edits }; } distanceLoop(str1, str2){ var dist_matrix = new Array(str1.length+1); for(var i=0; i<=str1.length; i++){ dist_matrix[i] = new Array(str2.length+1); dist_matrix[i].fill(null); for(var j=0; j<=str2.length; j++){ if(i==0){ dist_matrix[i][j] = j*this.delete_insert_cost; continue; } if(j==0){ dist_matrix[i][j] = i*this.delete_insert_cost; continue; } const current_dist = (str1[i-1] == str2[j-1] ? 0: this.mismatch_cost); const mismatch_dist = current_dist + dist_matrix[i-1][j-1]; const delete_dist = this.delete_insert_cost + dist_matrix[i-1][j]; const insert_dist = this.delete_insert_cost + dist_matrix[i][j-1]; const best_dist = Math.min(mismatch_dist, delete_dist, insert_dist); dist_matrix[i][j] = best_dist; } } const best_dist = dist_matrix[str1.length][str2.length]; const edit_path = this.edit_path(dist_matrix); return { best_dist: best_dist, dist_matrix: dist_matrix, edit_matrix: edit_path.edit_matrix, edits: edit_path.edits } //return [dist_matrix[str1.length][str2.length], dist_matrix, this.edit_path(dist_matrix)]; } }32:T99e,function show(result, str1, str2, title=null){ const dist_matrix = result.dist_matrix; const edit_matrix = result.edit_matrix; const edited_str1 = ["\t",].concat(str1); const edited_str2 = ["\t", "\t"].concat(str2); // str1 = ["\t",].concat(str1); // str2 = ["\t", "\t"].concat(str2); const div = d3.create("div"); title = (title == null) ? "Levenshtine distances" : title; //console.log(edit_matrix); const heading = div.append("h2").text(title); const edits_table = showStringEdits(result, str1, str2, div); const table = div.append("table"); const color = d3.scaleSequential([0, d3.max(dist_matrix.flat())], d3.interpolateGreys).unknown("#ccc"); const move_color = d3.scaleOrdinal(d3.schemeSet1).domain(["m", "d", "i"]); const move_border = new Map([ ["m", "solid solid none none"], ["i", "none none solid none"], ["d", "none solid none solid"], ]); const num_cols = edited_str2.length; const header = table.append('thead').append('tr') .selectAll('th') .data(edited_str2).enter() // 2 tabs to skip first 2 cols .append('th') // .style("width", `${1/num_cols}%`) // .style("padding-bottom", `${1/num_cols}%`) // .style("height", 0) .text(d => d); const body = table.append('tbody') .selectAll('tr') .data(edited_str1).enter() .append('tr') .attr("data-index", (d, i) => i) .selectAll("td") .data((d, i) => [d].concat(dist_matrix[i])).enter() .append("td") .text((d, i) => i==0 ? d : Number((d).toFixed(2))) .style("font-weight", (d, i) => i==0 ? "bold" : "normal") .style("background-color", (d, i) => i==0 ? null: color(d)) .style("border-style", function(d, i){ if(i==0) return null; const parent_idx = +this.parentNode.getAttribute("data-index"); const move = edit_matrix[parent_idx][i-1]; if(move == null) return null; return move_border.get(move); }) .style("border-color", function(d, i){ if(i==0) return null; const parent_idx = +this.parentNode.getAttribute("data-index"); const move = edit_matrix[parent_idx][i-1]; //console.log(parent_idx, i, move, move_color(move)); if(move == null) return null; return move_color(move); }) .style("color", (d, i) => i==0 ? null: invertColor(d3.color(color(d)).hex(), true)) .style("mix-blend-mode", (d, i) => i==0 ? "normal": "difference"); //mix-blend-mode: difference; return div.node() }33:[] 2f:{"title":"Levenshtein Distance","cells":[{"id":0,"value":"md`# Levenshtein Distance\n\nCode based on: https://www.cuelogic.com/blog/the-levenshtein-algorithm\n\n $\"Creative$
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":57,"value":"viewof form_input = form(html`

\n str1\n str2\n split string\n

\n mismatch_cost\n delete_insert_cost\n

\n`)","pinned":false,"hidden":false,"mode":"ojs"},{"id":34,"value":"show(result_loop, data.str1, data.str2, \"Levenshtine distances (loop)\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":352,"value":"md`\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n|\n\n\n\n\n\n\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":92,"value":"show(result, data.str1, data.str2, \"Levenshtine distances (recursive)\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":178,"value":"data = {\n const split = form_input.split;\n const data = {...form_input}\n data.str1 = data.str1.split(split);\n data.str2 = data.str2.split(split);\n return data;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":300,"value":"getStringEdits(result, data.str1, data.str2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":108,"value":"form_input","pinned":false,"hidden":false,"mode":"ojs"},{"id":193,"value":"function argMax(array, indexer=(x, i) => [i, x]) {\n // Taken from: https://gist.github.com/engelen/fbce4476c9e68c52ff7e5c2da5c24a28\n return [].map.call(array, indexer).reduce((r, a) => (a[1] > r[1] ? a : r));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":236,"value":"function argMin(array, indexer=(x, i) => [i, x]) {\n // Taken from: https://gist.github.com/engelen/fbce4476c9e68c52ff7e5c2da5c24a28\n return [].map.call(array, indexer).reduce((r, a) => (a[1] < r[1] ? a : r));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":204,"value":"costs = new Map([\n [\"d\", 10],\n [\"i\", 50],\n [\"m\", 20]\n])","pinned":false,"hidden":false,"mode":"ojs"},{"id":196,"value":"argMax([10,50,20])","pinned":false,"hidden":false,"mode":"ojs"},{"id":227,"value":"argMax(Array.from(costs.entries()), (x) => x)","pinned":false,"hidden":false,"mode":"ojs"},{"id":238,"value":"argMin(Array.from(costs.entries()), (x) => x)","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"lev = new Levenshtein(\n form_input.mismatch_cost,\n form_input.delete_insert_cost,\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"result = lev.distance(data.str1, data.str2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"result_loop = lev.distanceLoop(data.str1, data.str2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":292,"value":"function getStringEdits(result, str1, str2){\n const edits = result.edits;\n const str1_edits = new Array();\n const str2_edits = new Array();\n var str1_i = 0;\n var str2_i = 0;\n for(var i=0; i i)\n .selectAll(\"td\")\n .data(d => d).enter()\n .append(\"td\")\n .text((d,i)=>d)\n .style(\"background-color\", (d,i) => {\n if(edits[i]==\"m\" && data[0][i] != data[1][i]){\n return \"#ffffbf\"\n }\n return colors.get(edits[i]);\n })\n \n return edit_table;\n \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":145,"value":"// Taken from: https://stackoverflow.com/a/35970186\n\nfunction padZero(str, len) {\n len = len || 2;\n var zeros = new Array(len).join('0');\n return (zeros + str).slice(-len);\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":143,"value":"// Taken from: https://stackoverflow.com/a/35970186\n\nfunction invertColor(hex, bw) {\n if (hex.indexOf('#') === 0) {\n hex = hex.slice(1);\n }\n // convert 3-digit hex to 6-digits.\n if (hex.length === 3) {\n hex = hex[0] + hex[0] + hex[1] + hex[1] + hex[2] + hex[2];\n }\n if (hex.length !== 6) {\n throw new Error('Invalid HEX color.');\n }\n var r = parseInt(hex.slice(0, 2), 16),\n g = parseInt(hex.slice(2, 4), 16),\n b = parseInt(hex.slice(4, 6), 16);\n if (bw) {\n // http://stackoverflow.com/a/3943023/112731\n return (r * 0.299 + g * 0.587 + b * 0.114) > 186\n ? '#000000'\n : '#FFFFFF';\n }\n // invert color components\n r = (255 - r).toString(16);\n g = (255 - g).toString(16);\n b = (255 - b).toString(16);\n // pad each with zeros and return\n return \"#\" + padZero(r) + padZero(g) + padZero(b);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":55,"value":"import {form} from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"d3 = require(\"d3@v5\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}