[javascript] 의미있는 자바 스크립트 퍼지 검색

배열을 필터링하기 위해 퍼지 검색 JavaScript 라이브러리를 찾고 있습니다. fuzzyset.js 및 fuse.js 사용을 시도 했지만 결과가 끔찍합니다 (링크 된 페이지에서 시도 할 수있는 데모가 있습니다).

Levenshtein 거리에 대해 읽은 후 사용자가 입력 할 때 찾는 내용에 대한 근사치가 나쁘다는 생각이 듭니다. 모르는 사람들을 위해 시스템 은 두 개의 문자열을 일치시키는 데 필요한 삽입 , 삭제 및 대체 수를 계산합니다 .

Levenshtein-Demerau 모델에서 수정 한 명백한 결점은 양이다 BluB 효소 와 가슴이 똑같이 유사한 고려 전구 (각각 두 개의 치환을 요구하는). 그러나, 분명 전구는 더 유사하다 BluB 효소 보다 가슴이 , 그리고 내가 방금 언급 한 모델을 가능하게하여 해당 인식 트랜스 포지션 .

나는 이것을 텍스트 완성의 맥락에서 사용하고 싶다. 그래서 내가 array를 가지고 ['international', 'splint', 'tinder']있고 내 쿼리가 int 이라면 , 전자가 10 점 (higher = worse)을 가지고 있더라도 international 은 splint 보다 더 높은 순위를 가져야 한다고 생각 한다. 후자의 3.

그래서 내가 찾고있는 것은 (존재하지 않으면 만들 것입니다) 다음을 수행하는 라이브러리입니다.

• 다양한 텍스트 조작에 가중치 적용
• 단어에 나타나는 위치에 따라 각 조작에 가중치를 부여합니다 (초기 조작은 늦은 조작보다 비용이 많이 듭니다).
• 관련성별로 정렬 된 결과 목록을 반환합니다.

이런 걸 본 사람이 있습니까? StackOverflow가 소프트웨어 권장 사항을 요청하는 곳이 아니라는 것을 알고 있지만 위의 암시 적 (더 이상은 아닙니다!)은 다음과 같습니다. 올바른 방식으로 생각하고 있습니까?

편집하다

주제에 대한 좋은 논문 (pdf) 을 찾았습니다 . 일부 참고 및 발췌 :

Affine 편집 거리 기능은 일련의 삽입 또는 삭제에 상대적으로 낮은 비용을 할당합니다.

특정 비용 매개 변수가있는 Smith-Waterman 거리 함수 (Durban et al. 1998)의 유사 변형 인 Monger-Elkan 거리 함수 (Monge & Elkan 1996)

들어 스미스 – 워터맨 거리 (위키) “대신에 전체 시퀀스를 찾고, 스미스 – 워터맨 알고리즘은 모든 가능한 길이의 세그먼트를 비교하여 유사도 측정치를 최적화한다.” 그것은 n-gram 접근 방식입니다.

편집 거리 모델을 기반으로하지 않는 광범위하게 유사한 메트릭은 Jaro 메트릭입니다 (Jaro 1995; 1989; Winkler 1999). 레코드-연결 문헌에서 두 문자열 사이의 공통 문자 수와 순서를 기반으로하는이 방법의 변형을 사용하여 좋은 결과를 얻었습니다.

Winkler (1999)로 인한 변형은 또한 가장 긴 공통 접두사의 길이 P를 사용합니다.

(주로 짧은 문자열을위한 것으로 보임)

텍스트 완성을 위해 Monger-Elkan 및 Jaro-Winkler 접근 방식이 가장 합리적입니다. Jaro 메트릭에 Winkler의 추가는 효과적으로 단어의 시작 부분에 더 많은 가중치를 부여합니다. 그리고 Monger-Elkan의 affine 측면은 단어를 완성해야하는 필요성 (단순히 추가되는 순서)이 너무 많이 싫어하지 않을 것임을 의미합니다.

결론:

TFIDF 순위는 여러 토큰 기반 거리 메트릭 중에서 가장 잘 수행되었으며 Monge와 Elkan이 제안한 조정 된 affine-gap 편집 거리 메트릭은 여러 문자열 편집-거리 메트릭 중에서 가장 잘 수행되었습니다. 놀랍게도 좋은 거리 측정법은 Jaro가 제안하고 나중에 Winkler가 확장 한 빠른 휴리스틱 방식입니다. 이것은 Monge-Elkan 방식과 거의 비슷하지만 훨씬 더 빠릅니다. TFIDF 방법과 Jaro-Winkler를 결합하는 간단한 방법 중 하나는 TFIDF에서 사용되는 정확한 토큰 일치를 Jaro-Winkler 체계를 기반으로하는 대략적인 토큰 일치로 바꾸는 것입니다. 이 조합은 평균적으로 Jaro-Winkler 또는 TFIDF보다 약간 더 나은 성능을 제공하며 때로는 훨씬 더 나은 성능을 제공합니다. 또한이 백서에서 고려한 몇 가지 최고의 메트릭의 학습 된 조합에 가깝습니다.

답변

fuzzysort.go('int', ['international', 'splint', 'tinder'])
// [{highlighted: '*int*ernational', score: 10}, {highlighted: 'spl*int*', socre: 3003}]

get_bigrams = (string) ->
    s = string.toLowerCase()
    v = new Array(s.length - 1)
    for i in [0..v.length] by 1
        v[i] = s.slice(i, i + 2)
    return v

string_similarity = (str1, str2) ->
    if str1.length > 0 and str2.length > 0
        pairs1 = get_bigrams(str1)
        pairs2 = get_bigrams(str2)
        union = pairs1.length + pairs2.length
        hit_count = 0
        for x in pairs1
            for y in pairs2
                if x is y
                    hit_count++
        if hit_count > 0
            return ((2.0 * hit_count) / union)
    return 0.0

query = 'jenny Jackson'
names = ['John Jackson', 'Jack Johnson', 'Jerry Smith', 'Jenny Smith']

results = []
for name in names
    relevance = string_similarity(query, name)
    obj = {name: name, relevance: relevance}
    results.push(obj)

results = _.first(_.sortBy(results, 'relevance').reverse(), 10)

console.log results

function fuzzyMatch(pattern, str) {
  pattern = '.*' + pattern.split('').join('.*') + '.*';
  const re = new RegExp(pattern);
  return re.test(str);
}

> fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int');
< ["international", "splint"]

function get_bigrams(string){
  var s = string.toLowerCase()
  var v = s.split('');
  for(var i=0; i<v.length; i++){ v[i] = s.slice(i, i + 2); }
  return v;
}

function string_similarity(str1, str2){
  if(str1.length>0 && str2.length>0){
    var pairs1 = get_bigrams(str1);
    var pairs2 = get_bigrams(str2);
    var union = pairs1.length + pairs2.length;
    var hits = 0;
    for(var x=0; x<pairs1.length; x++){
      for(var y=0; y<pairs2.length; y++){
        if(pairs1[x]==pairs2[y]) hits++;
    }}
    if(hits>0) return ((2.0 * hits) / union);
  }
  return 0.0
}