JS - 스마트 자동 완성 작성

Question

정렬 된 문자열 배열과 사용자 입력이 있으면 가장 관련성이 높은 결과를 반환해야합니다.

예 : 배열은 = ['Apple','Banana and Melon','Orange'] 및 사용자 입력 = 'Mellllon' 반환 된 값이 'Banana and Melon'

내가 효율적인 자동 완성 솔루션을 구현 할 수있는 권리 알고리즘을 찾고 있어요

및 하지 상자의 밖으로해야한다 하나.

Answer 1

Levenshtein distance이이 문제를 해결하는 것으로 보입니다. 당신은 배열의 모든 단어 사이의 거리를 계산해야합니다, 체크 아웃 할

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

글쎄, 같은 정교하게 퍼지 검색 정규식을 사용하면 검색 문자열의 모든 문자 (대소 문자 구분 "m"가 제공하는 편리한 올 수도 the topic cited in my comment 설명 , "e", "l", "o", "n")은 출현 순서에 따라 입력 문자열에 있습니다. 따라서 생성 된 /M[^e]*e[^l]*l[^o]*o[^n]*n/i에 따르면 "Melon", "Maellion", "MElllloon"또는 "nMelrNnon"의 정규식은 모두 true을 반환해야합니다. 당신이 실제로 꽤 합리적인 탄성 자동 완성 기능을 얻을 수있는 트라이 형 데이터 구조와 fuzzyMatch 기능을 결합

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);

.