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功能與特里數據結構類型，你實際上可能得​​到比較合理的彈性自動完成功能。