말이 되는 자바스크립트 퍼지 검색
배열을 필터링할 퍼지 검색 자바스크립트 라이브러리를 찾고 있습니다.fuzyset.js와 fuse.js를 사용해 보았지만 결과가 끔찍합니다(링크된 페이지에서 시도할 수 있는 데모가 있습니다).
Levenshtein 거리에 대한 판독을 좀 해본 결과, 사용자가 타자를 칠 때 무엇을 찾고 있는지에 대한 대략적인 정보가 부족하다는 생각이 듭니다.모르는 사람들을 위해 이 시스템은 두 문자열을 일치시키기 위해 얼마나 많은 삽입, 삭제, 대체가 필요한지 계산합니다.
Levenshtein-Demerau 모델에서 해결된 한 가지 명백한 결함은 블러브와 부브 모두 전구와 동일하게 유사한 것으로 간주된다는 것입니다(각각 두 가지 대체가 필요함).하지만 전구가 boob보다 boub와 더 비슷하다는 것은 분명하고, 방금 언급한 모델은 전이를 허용함으로써 그것을 인식합니다.
하고 싶어서에는 ['international', 'splint', 'tinder'], 그리고 제 질문은 int입니다. 비록 전자의 점수(worse=higher)가 후자의 3점에 비해 10점이지만, int는 스플린트보다 더 높은 순위를 차지해야 한다고 생각합니다.
그래서 제가 찾고 있는 것(존재하지 않을 경우 생성할 것)은 다음을 수행하는 라이브러리입니다.
- 여러 텍스트 조작의 가중치를 부여합니다.
- 각 조작의 가중치를 단어 내 나타나는 위치에 따라 다르게 부여합니다(초기 조작은 후기 조작보다 비용이 많이 듭니다).
- 관련성에 따라 정렬된 결과 목록을 반환합니다.
이런 일을 당한 사람이 있습니까?StackOverflow는 소프트웨어 권장 사항을 요청할 곳이 아니라는 것을 알고 있지만, 위의 내용에서 암시적으로(더 이상은 아님!) 다음과 같습니다. 올바른 방법으로 생각하고 있습니까?
편집
나는 그 주제에 대한 좋은 논문(pdf)을 발견했습니다.일부 노트 및 발췌:
아핀 편집 거리 함수는 일련의 삽입 또는 삭제에 상대적으로 낮은 비용을 할당합니다.
Monger-Elkan 거리 함수(Mongge & Elkan 1996)는 스미스-워터맨 거리 함수(Smith-Waterman distance function)(Durban et al. 1998)의 아핀 변형으로 특정 비용 변수를 사용합니다.
스미스-워터맨 거리(위키피디아)의 경우, "전체 시퀀스를 보는 대신 스미스-워터맨 알고리즘은 가능한 모든 길이의 세그먼트를 비교하고 유사성 측도를 최적화합니다."n-gram 접근 방식입니다.
편집 거리 모델에 기초하지 않은, 광범위하게 유사한 메트릭은 자로 메트릭(Jaro 1995; 1989; Winkler 1999)입니다.기록-링크 문헌에서는 두 문자열 사이의 공통 문자의 수와 순서에 기반한 이 방법의 변형을 사용하여 좋은 결과를 얻었습니다.
Winkler (1999)에 의한 이 변형은 또한 가장 긴 공통 접두사의 길이 P를 사용합니다.
(주로 짧은 문자열용으로 seem)
텍스트 완성을 위해 몽거-엘칸 및 자로-윙클러 접근 방식이 가장 타당해 보입니다.자로메트릭에 윙클러가 더해진 것은 단어의 시작에 더 큰 무게를 부여합니다.그리고 몽거엘칸의 애피닉한 측면은 단어를 완성해야 할 필요성(단순히 덧셈의 연속)이 단어를 지나치게 불리하게 만들지 않을 것이라는 것을 의미합니다.
결론:
TFIDF 순위는 여러 토큰 기반 거리 메트릭 중에서 가장 잘 수행되었으며, Mongge와 Elkan이 제안한 튜닝된 아핀 갭 편집 거리 메트릭은 여러 문자열 편집 거리 메트릭 중에서 가장 잘 수행되었습니다.놀랍도록 좋은 거리 측정법은 자로가 제안하고 나중에 윙클러가 확장한 빠른 휴리스틱 체계입니다.이것은 몽게-엘칸 계획과 거의 비슷하지만, 훨씬 빠른 속도입니다.TFIDF 방식과 Jaro-Winkler를 결합하는 한 가지 간단한 방법은 TFIDF에서 사용되는 정확한 토큰 매치를 Jaro-Winkler 방식에 기초한 대략적인 토큰 매치로 대체하는 것입니다.이 조합은 평균적으로 Jaro-Winkler나 TFIDF보다 약간 더 나은 성능을 발휘하며 때로는 훨씬 더 나은 성능을 발휘합니다.또한 이 문서에서 고려한 몇 가지 최고의 메트릭의 학습된 조합에 근접한 성능을 제공합니다.
fuse.js와 같은 기존 퍼지 라이브러리를 사용해보았고 또한 끔찍하다는 것을 발견하여 기본적으로 submarity의 search처럼 행동하는 라이브러리를 작성했습니다.https://github.com/farzher/fuzzysort
이것이 허용하는 유일한 유형은 전치(transpose.매우 견고하며(별 1,000개, 이슈 0개), 매우 빠르며 케이스를 쉽게 처리할 수 있습니다.
fuzzysort.go('int', ['international', 'splint', 'tinder'])
// [{highlighted: '*int*ernational', score: 10}, {highlighted: 'spl*int*', socre: 3003}]
좋은 질문!하지만 제 생각에는 Levenshtein-Demerau를 수정하려고 하기 보다는 다른 알고리즘을 시도하거나 두 알고리즘의 결과를 조합/가중하는 것이 더 나을 수 있습니다.
"시작 접두어"에 정확히 일치하거나 가까운 것은 Levenshtein-Demerau가 특별히 중요하게 생각하지 않지만, 사용자의 기대는 분명 중요할 것입니다.
"레븐슈테인보다 낫다"는 것을 찾아봤는데, 무엇보다도 다음과 같은 것을 발견했습니다.
http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/
여기에는 여러 가지 "스트링 거리" 측정이 언급됩니다.고객의 요구사항과 특히 관련이 있어 보이는 세 가지는 다음과 같습니다.
가장 긴 공통 부분 문자열 거리:결과 서브스트링이 동일할 때까지 두 문자열에서 제거해야 하는 최소 기호 수.
q그램 거리:두 문자열의 N-그램 벡터 간의 절대적인 차이의 합.
Jaccard 거리: 공유 N-gram과 관찰된 모든 N-gram의 몫을 1분으로 합니다.
어쩌면 여러분은 레벤쉬테인과 함께, 일반적인 부분 문자열, 일반적인 N-그램 또는 자카드 모두가 비슷한 문자열을 강하게 선호할 것입니다. 아니면 자카드만 사용해 볼 수도 있을까요?
목록/데이터베이스의 크기에 따라 이러한 알고리즘은 비용이 상당히 많이 들 수 있습니다.제가 구현한 퍼지 검색의 경우 DB에서 설정 가능한 개수의 N-그램을 "검색 키"로 사용한 다음 값비싼 문자열-거리 척도를 실행하여 선호 순서대로 정렬했습니다.
저는 SQL에서 Fuzzy String Search에 대해 몇 가지 노트를 작성했습니다.참조:
여기 제가 몇 번 사용한 기술이 있습니다.그것은 꽤 좋은 결과를 가져다 줍니다.당신이 요구한 모든 것을 다 하지는 못합니다.또한, 목록이 방대하다면 비용이 많이 들 수도 있습니다.
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
두 개의 문자열을 전달합니다.string_similarity 사이의 0그리고.1.0그들이 얼마나 비슷한지에 따라.에서는 Lo-Dash합니다를 합니다.
사용 예...
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);
}
InternalFx의 CoffeeScript bigram 솔루션의 문제점을 수정하여 일반적인 n그램 솔루션으로 만들었습니다(그램의 크기를 커스터마이징 할 수 있습니다).
이것은 TypeScript이지만 Type 주석을 제거할 수 있으며 바닐라 자바스크립트로도 잘 작동합니다.
/**
* Compares the similarity between two strings using an n-gram comparison method.
* The grams default to length 2.
* @param str1 The first string to compare.
* @param str2 The second string to compare.
* @param gramSize The size of the grams. Defaults to length 2.
*/
function stringSimilarity(str1: string, str2: string, gramSize: number = 2) {
function getNGrams(s: string, len: number) {
s = ' '.repeat(len - 1) + s.toLowerCase() + ' '.repeat(len - 1);
let v = new Array(s.length - len + 1);
for (let i = 0; i < v.length; i++) {
v[i] = s.slice(i, i + len);
}
return v;
}
if (!str1?.length || !str2?.length) { return 0.0; }
//Order the strings by length so the order they're passed in doesn't matter
//and so the smaller string's ngrams are always the ones in the set
let s1 = str1.length < str2.length ? str1 : str2;
let s2 = str1.length < str2.length ? str2 : str1;
let pairs1 = getNGrams(s1, gramSize);
let pairs2 = getNGrams(s2, gramSize);
let set = new Set<string>(pairs1);
let total = pairs2.length;
let hits = 0;
for (let item of pairs2) {
if (set.delete(item)) {
hits++;
}
}
return hits / total;
}
예:
console.log(stringSimilarity("Dog", "Dog"))
console.log(stringSimilarity("WolfmanJackIsDaBomb", "WolfmanJackIsDaBest"))
console.log(stringSimilarity("DateCreated", "CreatedDate"))
console.log(stringSimilarity("a", "b"))
console.log(stringSimilarity("CreateDt", "DateCreted"))
console.log(stringSimilarity("Phyllis", "PyllisX"))
console.log(stringSimilarity("Phyllis", "Pylhlis"))
console.log(stringSimilarity("cat", "cut"))
console.log(stringSimilarity("cat", "Cnut"))
console.log(stringSimilarity("cc", "Cccccccccccccccccccccccccccccccc"))
console.log(stringSimilarity("ab", "ababababababababababababababab"))
console.log(stringSimilarity("a whole long thing", "a"))
console.log(stringSimilarity("a", "a whole long thing"))
console.log(stringSimilarity("", "a non empty string"))
console.log(stringSimilarity(null, "a non empty string"))
TypeScript Playground에서 사용해 보기
아톰의 https://github.com/atom/fuzzaldrin/ lib를 보실 수 있습니다.
npm에서 사용 가능하고 간단한 API가 있고 잘 작동했습니다.
> fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int');
< ["international", "splint"]
저는 오랫동안 퍼지 매칭을 좋아했고, 이 스레드를 우연히 발견했습니다.여기서의 대화는 대부분의 사람들보다 훨씬 더 잡초가 무성하고 실행자들이 참여한 것으로 보입니다.저는 지난 몇 년간 이 알고리즘들 중 몇 가지를 다른 언어로 코딩해왔고, JS 버전을 쓰는 사람들에게 몇 가지 팁을 전하고 싶습니다.
몽게-엘칸 규칙!
자로-윙클러와 같은 최고의 짧은 문자열 비교 알고리즘과 n그램의 장점을 결합하면 환상적입니다. (제가 몽게-엘칸 코드에서 사용하는 것입니다.)몇 년 전, 저는 대략적인 텍스트 문자열 비교를 위한 일반화된 Mongue-Elkan Method라는 PDF로 온라인에서 찾을 수 있는 논문을 우연히 발견했습니다.산술 평균을 사용하는 것보다 2차 평균을 사용하는 것이 중요합니다.저는 그것을 시도해 보았고, 그것은 매우 다양한 텍스트에 걸쳐 검색 결과를 크게 향상시켰습니다.
N그램 룰!
다양한 소스 언어와 텍스트 유형에 걸쳐 매우 강력하고 고품질의 성능을 제공합니다.데이터베이스를 보고 있다면 Postgres에서 빠른 속도의 고품질 색인 K-NN 검색으로 구현할 수 있습니다.몇 가지 다른 기능을 적절히 줄 세우는 것이 필요하지만 그리 나쁘지는 않습니다.
어쨌든, n그램을 분할할 때, 프론트엔드 패딩을 처리하는 여러 가지 접근법이 있습니다.예를 들어, 전통적인 n(q 또는 k)이 3이라면, 'ander'를 이렇게 나누나요?
' a'
' an'
'and'
'nde'
'der'
'er '
'r '
아니면
' a'
' an'
'and'
'nde'
'der'
아니면
'and'
'nde'
'der'
본능적으로 항상 첫 번째 리스트가 가장 잘 작동할 것으로 기대했지만 실제로는 두 번째가 될 수도 있고 세 번째가 될 수도 있습니다.패딩과 윈도잉 규칙을 실험해보고, 이 규칙들이 사용자의 상황에서 어떻게 작동하는지 확인해 보는 것이 좋습니다.이 동작을 제어하는 기능을 제공하는 라이브러리는 거의 없습니다.힌트.
다음은 @InternalFX에서 제공하는 솔루션이지만 JS에서는 다음과 같이 제공됩니다(저는 이를 사용하여 공유했습니다).
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
}
2019년 11월 업데이트.퓨즈가 꽤 괜찮은 업그레이드를 할 수 있다는 걸 발견했어요.그러나 boole(즉, OR, AND 연산자 등)을 사용하거나 API 검색 인터페이스를 사용하여 결과를 필터링할 수 없었습니다.
https://github.com/nextapps-de/flexsearch 을 발견했습니다. 그리고 제가 시도했던 다른 많은 자바스크립트 검색 라이브러리들을 훨씬 능가한다고 생각합니다. 그리고 그것은 지원합니다.bool검색 및 페이지 필터링.
검색 데이터에 대한 자바스크립트 객체 목록(즉, 저장소)을 입력할 수 있으며, API는 상당히 잘 문서화되어 있습니다. https://github.com/nextapps-de/flexsearch#api-overview
지금까지 거의 10,000개의 레코드를 인덱싱했으며 검색 결과는 즉시 검색할 수 있습니다. 즉, 검색할 때마다 눈에 띄지 않을 정도의 시간이 소요됩니다.
(function (int) {
$("input[id=input]")
.on("input", {
sort: int
}, function (e) {
$.each(e.data.sort, function (index, value) {
if ( value.indexOf($(e.target).val()) != -1
&& value.charAt(0) === $(e.target).val().charAt(0)
&& $(e.target).val().length === 3 ) {
$("output[for=input]").val(value);
};
return false
});
return false
});
}(["international", "splint", "tinder"]))
jsfiddle http://jsfiddle.net/guest271314/QP7z5/
Fuzzy Sort는 많은 데이터 모음에서 문자열 일치를 수행하는 데 도움이 되는 자바스크립트 라이브러리입니다.
다음 코드는 react.js에서 퍼지 정렬을 사용하는 데 도움이 될 것입니다.
퍼지 정렬을 npm까지 설치합니다.
npm install fuzzysort기준 변수를 만들고,
const fuzzysort = require('fuzzysort')go() 메서드를 사용하여 일치하는 문자열을 찾습니다.
search(keyword, category) { return fuzzysort.go(keyword, data[category]); }
react.js의 전체 데모 코드
import React from 'react';
import './App.css';
import data from './testdata';
const fuzzysort = require('fuzzysort');
class App extends React.Component {
constructor(props){
super(props)
this.state = {
keyword: '',
results: [],
}
console.log("data: ", data["steam_games"]);
}
search(keyword, category) {
return fuzzysort.go(keyword, data[category]);
}
render(){
return (
<div className="App">
<input type="text" onChange={(e)=> this.setState({keyword: e.target.value})}
value={this.state.keyword}
/>
<button onClick={()=>this.setState({results: this.search(this.state.keyword, "steam_games")})}>Search</button>
{this.state.results !== null && this.state.results.length > 0 ?
<h3>Results:</h3> : null
}
<ul>
{this.state.results.map((item, index) =>{
return(
<li key={index}>{item.score} : {item.target}</li>
)
})
}
</ul>
</div>
);
}
}
export default App;
자세한 내용은 FuzzySort를 참조
이것은 Regex를 사용함으로써 달성할 수 있습니다.
예:
const fuzzySearch = (list, searchValue) => {
let buf = ".*" + searchValue.replace(/(.)/g, "$1.*").toLowerCase();
var reg = new RegExp(buf);
let newList = list.filter(function (e) {
return reg.test(e.title.toLowerCase());
});
return newList;
};
작동 예: https://codesandbox.io/s/jovial-fermat-cilh1?file=/src/App.js:28894-29167
언급URL : https://stackoverflow.com/questions/23305000/javascript-fuzzy-search-that-makes-sense
'programing' 카테고리의 다른 글
| 스프링 부트 오류 org.hibernate.예외.일반 JDB예외:DDL 실행을 위해 JDBC Connection을 열 수 없습니다. (0) | 2023.10.01 |
|---|---|
| 네이티브 앱에서 하이퍼링크를 표시하는 방법은? (0) | 2023.10.01 |
| Django, 업그레이드 후:내 SQL 서버가 사라졌습니다. (0) | 2023.09.26 |
| 팬더 데이터 프레임의 문자열 열에서 텍스트를 대체하는 방법은 무엇입니까? (0) | 2023.09.26 |
| jquery clone div 및 특정 div 뒤에 추가 (0) | 2023.09.26 |