31:T624,editDistance = function (strA, strB) { let aLength = strA.length, bLength = strB.length // fail-fast if (aLength === 0) { return bLength } if (bLength === 0) { return aLength } // If the limit is not defined it will be calculate from this and that args. let limit = (bLength > aLength ? bLength : aLength) + 1 if (Math.abs(aLength - bLength) > (limit || 100)) { return limit || 100 } // init the array let matrix = [] for (let i = 0; i < limit; i++) { matrix[i] = [i] matrix[i].length = limit } for (let i = 0; i < limit; i++) { matrix[0][i] = i } // Calculate matrix. let j, a_index, b_index, cost, min, t for (let i = 1; i <= aLength; ++i) { a_index = strA[i - 1] for (j = 1; j <= bLength; ++j) { // Check the jagged distance total so far if (i === j && matrix[i][j] > 4) { return aLength } b_index = strB[j - 1] cost = a_index === b_index ? 0 : 1 // Step 5 // Calculate the minimum (much faster than Math.min(...)). min = matrix[i - 1][j] + 1 // Deletion. if ((t = matrix[i][j - 1] + 1) < min) min = t // Insertion. if ((t = matrix[i - 1][j - 1] + cost) < min) min = t // Substitution. // Update matrix. let shouldUpdate = i > 1 && j > 1 && a_index === strB[j - 2] && strA[i - 2] === b_index && (t = matrix[i - 2][j - 2] + cost) < min if (shouldUpdate) { matrix[i][j] = t } else { matrix[i][j] = min } } } // return number of steps return matrix[aLength][bLength] }32:[] 2f:{"title":"Compromise-fuzzy-matching","cells":[{"id":0,"value":"md`# Compromise-fuzzy-matching\n[Compromise](https://observablehq.com/@spencermountain/nlp-compromise) supports a form of *fuzzy matching*, or edit-distance comparison. (Since \\`13.9.0\\` (Feb 2021))\n\nOn their own, [compromise matches](https://observablehq.com/@spencermountain/compromise-match) act independently of punctuation, case, and whitespace. This form of soft-matching though is intended to allow typos, or close-matches.\n\nCompromise uses [Damerau–Levenshtein distance](https://en.m.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance) to compute approximate string matches.\n\nYou can enable it like this:\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"{\n let doc = nlp('i went on a talk') //a text with a typo\n let m = doc.match('. ~walk~', null, { fuzzy: 0.7 }) //enable fuzzy-match\n return m.text()\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":18,"value":"md`\n### Considerations\n\n**1)** - Fuzzy-matching is slow. It is not advised to do this on a large document.\n\n**2)** - Only text-matches **[in ~tildes~](https://observablehq.com/@spencermountain/compromise-match-syntax)** will be fuzzy. \\`#Tags\\` and \\`@methods\\` will be unaffected.\n\n**3)** - The lexicon will not be fuzzy. The POS-tagger will not be fuzzy. \n\nIn general, compromise assumes all the input text is correct. Any input with a typo may be tagged incorrectly to begin with, so may behave unexpectedly in the sentence.\n\n\n---\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"md`you can include fuzzy matches inside or outside OR and AND matches:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":69,"value":"nlp('bart simpson').has('(foo|~bort~)', null, {fuzzy:0.75})","pinned":true,"hidden":false,"mode":"ojs"},{"id":80,"value":"{\n let doc = nlp('bart simpson')\n let m = doc.match('~(foo|bort)~', null, {fuzzy:0.75})\n return m.text()\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":22,"value":"md`\n---\n### Implementation\nThe scoring for fuzzy matching is edit distance (including transposition) divided by the legnth of the string.\nIt will be between 0-1, and will get closer to 1, the fewer the mistakes, and the longer the string. As an optimization, very-short strings are not fuzzed.\n\nYou can play with the implementation here:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"viewof a = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":37,"value":"viewof b = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":40,"value":"html`

\n fuzzy score: ${round(fuzzyMatch(a, b))}\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":84,"value":"md`\nThe implementation is relatively fast, compared to other fuzzy comparisons. But adding fuzzy-matching to your lookups will effect the performance of your matches. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":25,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"round = n => Math.round(n * 100) / 100","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"fuzzyMatch = function (strA, strB, minLength = 3) {\n if (strA === strB) {\n return 1\n }\n //don't even bother on tiny strings\n if (strA.length < minLength || strB.length < minLength) {\n return 0\n }\n const steps = editDistance(strA, strB)\n let length = Math.max(strA.length, strB.length)\n let relative = length === 0 ? 0 : steps / length\n let similarity = 1 - relative\n return similarity\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"nlp=require('compromise')","pinned":false,"hidden":false,"mode":"ojs"},{"id":54,"value":"style = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"nlp.version","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}