JS - 创建智能自动完成

Question

给定一个有序的数组字符串和用户输入，我需要返回最相关的结果。

例：数组= ['Apple','Banana and Melon','Orange']和用户输入= 'Mellllon'返回的值应该是'Banana and Melon'

我在寻找实现高效的自动完整的解决方案正确的算法，并不是一个开箱即用一个。

Answer 1

Levenshtein距离似乎是正确的这个问题。你需要在阵列的每一个字之间计算距离，检查出来

function findClosestString(arr, inputvalue) { 
    let closestOne = ""; 
    let floorDistance = 0.1; 

    for (let i = 0; i < arr.length; i++) { 
    let dist = distance(arr[i], inputvalue); 
    if (dist > floorDistance) { 
     floorDistance = dist; 
     closestOne = arr[i]; 
    } 
    } 

    return closestOne; 
} 

function distance(val1, val2) { 
    let longer, shorter, longerlth, result; 

    if (val1.length > val2.length) { 
    longer = val1; 
    shorter = val2; 
    } else { 
    longer = val2; 
    shorter = val1; 
    } 

    longerlth = longer.length; 

    result = ((longerlth - editDistance(longer, shorter))/parseFloat(longerlth)); 

    return result; 
} 

function editDistance(val1, val2) { 
    val1 = val1.toLowerCase(); 
    val2 = val2.toLowerCase(); 

    let costs = []; 

    for(let i = 0; i <= val1.length; i++) { 
    let lastVal = i; 
    for(let j = 0; j <= val2.length; j++) { 
     if (i === 0) { 
     costs[j] = j; 
     } else if (j > 0) { 
     let newVal = costs[j - 1]; 
     if (val1.charAt(i - 1) !== val2.charAt(j - 1)) { 
      newVal = Math.min(Math.min(newVal, lastVal), costs[j]) + 1; 
     } 
     costs[j - 1] = lastVal; 
     lastVal = newVal; 
     } 
    } 
    if (i > 0) { costs[val2.length] = lastVal } 
    } 

    return costs[val2.length]; 
} 

findClosestString(['Apple','Banana and Melon','Orange'], 'Mellllon'); 

Answer 2

一种可能的解决方案是：

1）的每一个值转换成一些简单的代码（使用相同的简单的规则，例如转换大写字符为小写，如果一个字符是相同的所述预览，也不会拿到书面等..），所以你必须['aple','banana and melon', 'orange']

2），那么你转换用户输入，Mellllon =>melon

3）现在你可以简单的运行

return match_array.filter((x) => { x.indexOf(match_input)!=-1) );

Answer 3

嗯，精心在the topic cited in my comment解释模糊搜索，正则表达式可能来得心应手只要你有搜索的字符串的所有字母（不区分大小写“M” ，“e”，“l”，“o”，“n”）以出现顺序出现在输入字符串中。因此，根据生成的来自“Melon”，“Maellion”，“MElllloon”或“nMelrNnon”的/M[^e]*e[^l]*l[^o]*o[^n]*n/i正则表达式应都返回true。

function fuzzyMatch(s,p){ 
 
    p = p.split("").reduce((a,b) => a+'[^'+b+']*'+b); 
 
    return RegExp(p,"i").test(s); 
 
} 
 

 
var arr = ['Apple','Banana and Melon','Orange'], 
 
    inp = "MaellL;loin", 
 
    res = arr.filter(s => s.split(" ").some(w => fuzzyMatch(inp,w))); 
 
console.log(res);

结合fuzzyMatch功能与特里数据结构类型，你实际上可能得​​到比较合理的弹性自动完成功能。