Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

31
LINES

< > BotCompany Repo | #1023873 // levenSubstringIC_withIndex - find leven-closest substring in larger string. complexity O(m*n). return rough index of substring & distance

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (302L/3K).

// Calculates the fuzzy match of needle in haystack,
// using a modified version of the Levenshtein distance algorithm.
// ported from: http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/

static Pair<Int> levenSubstringIC_withIndex(S haystack, S needle) {
  int m = strL(needle), n = strL(haystack);

  // base cases
  if (m == 1) {
    int idx = indexOfIC(haystack, needle);
    ret idx < 0 ? pair(0, 1) : pair(idx, 0);
  }
  if (m == 0)
    ret pair(0, m);

  int[] row1 = new int[n+1], row2 = new int[n+1];
  for i to m: {
    row2[0] = i+1;
    for j to n: {
      int cost = neqic(needle.charAt(i), haystack.charAt(j)) ? 1 : 0;
      row2[j+1] = min3(row1[j+1]+1,   // deletion
                       row2[j]+1,     // insertion
                       row1[j]+cost); // substitution
    }
    int[] temp = row1;
    row1 = row2;
    row2 = temp;
  }
  Pair<Int> p = minOfIntArray_withIndex(row1);
  ret pair(max(0, p.a-m), p.b);
}

Author comment

Began life as a copy of #1023862

download  show line numbers  debug dex  old transpilations   

Travelled to 6 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt

No comments. add comment

Snippet ID: #1023873
Snippet name: levenSubstringIC_withIndex - find leven-closest substring in larger string. complexity O(m*n). return rough index of substring & distance
Eternal ID of this version: #1023873/4
Text MD5: 8148251608469a0749475c3b3f2bcfab
Transpilation MD5: a05f7293185a2aac2acce6338168ce6d
Author: stefan
Category: javax / a.i.
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2019-07-11 00:10:34
Source code size: 1017 bytes / 31 lines
Pitched / IR pitched: No / No
Views / Downloads: 199 / 301
Version history: 3 change(s)
Referenced in: #1006654 - Standard functions list 2 (LIVE, continuation of #761)