30:T5af,{ const h = 24, w = 26, M = L.M; let svg = `Red steps show where something happens:\n- down: addition\n- right: deletion\n- diagonal: substitution.\n\nThe distance is indicated in the bottom-right cell, in **bold**.\n\n----\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"L = (replay, levenshtein(A, B))","pinned":false,"hidden":false,"mode":"ojs"},{"id":453,"value":"md`Cost matrix:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":411,"value":"pt(L.M)","pinned":false,"hidden":false,"mode":"ojs"},{"id":457,"value":"md`Predecessors matrix:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":388,"value":"pt(L.path)","pinned":false,"hidden":false,"mode":"ojs"},{"id":386,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":121,"value":"function levenshtein_path(A, B) {\n const transition = [],\n L = [...levenshtein(A, B)].pop(),\n M = L.M,\n path = L.path;\n let i = B.length,\n j = A.length;\n\n let w = B;\n\n transition.push(w);\n\n while (i > 0 || j > 0) {\n [i, j] = path[i][j];\n let w0 = B.substring(0, i) + A.substring(j);\n if (w0 !== w) {\n w = w0;\n transition.push(w);\n }\n }\n\n return transition.reverse();\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":343,"value":"md`You can chose a different cost for the substitution (some applications prefer to count a substitution as 2 operations).`","pinned":false,"hidden":false,"mode":"ojs"},{"id":312,"value":"function substitution_cost(a, b) {\n return +(a !== b) * 1; // try * 1.5 or 2\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":465,"value":"md`If you don't need precedecessors nor animation, the following code is simpler:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"function levenshtein_matrix(A, B) {\n const rows = A.length + 1,\n cols = B.length + 1,\n M = Array.from({ length: rows }).map(() =>\n Array.from({ length: cols }).map(() => \"?\")\n );\n for (let i = 0; i < rows; i++) M[i][0] = i;\n for (let i = 1; i < cols; i++) M[0][i] = i;\n\n for (let i = 1; i < cols; i++) {\n for (let j = 1; j < rows; j++) {\n // Same letter in both words?\n const c = substitution_cost(A[j - 1], B[i - 1]);\n M[j][i] = Math.min(\n M[j - 1][i] + 1, // delete\n M[j][i - 1] + 1, // insert\n M[j - 1][i - 1] + c // substitute for a cost\n );\n }\n }\n return M;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":657,"value":"md`Animating the words in a SVG is tricky — here’s my (probably over-complicated) solution: https://observablehq.com/@fil/levenshtein-transition-animated`","pinned":false,"hidden":false,"mode":"ojs"},{"id":291,"value":"md`----\n_boring zone_`","pinned":false,"hidden":false,"mode":"ojs"},{"id":41,"value":"import {pt} from \"@fil/pt\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":294,"value":"signature","pinned":false,"hidden":false,"mode":"ojs"},{"id":293,"value":"import {signature} from \"@fil/signature\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}