수만 개의 키워드_javascript 기술에 대한 JavaScript 인스턴트 매칭 코드

키워드 검색을 할 때 가장 먼저 떠오르는 것은 indexOf, 바꾸기 등의 일부 문자 함수를 사용하거나 기껏해야 일부 정규식을 추가하는 것뿐입니다. 구현하기는 매우 간단하지만, 주의 깊게 생각해 본 적이 있습니까? 그 뒤에 효율성 문제가 있습니까? 예를 들어, 포럼의 키워드 필터링에서는 일반적으로 필터링할 키워드 수와 감지할 텍스트 길이가 크지 않기 때문에 이 순간적인 프로세스에서는 별로 주목할 가치가 없습니다. 그러나 키워드 수가 더 이상 소수가 아니라 수천 개가 되고 감지할 텍스트도 길다면 결과는 더 이상 낙관적이지 않습니다. 모든 추가 키워드에 대해 전체 텍스트 검색이 추가되고 최종 소요 시간이 허용 가능한 범위를 훨씬 초과한다는 것을 누구나 알고 있습니다.
　
극단적인 키워드 검색을 고려하고 있기 때문에 일반적인 일대일 순회 검색은 당연히 불가능합니다. 요즘에는 JavaScript를 사용하는데, 해시 테이블을 사용하지 않는다면 이 언어는 부끄러울 것입니다. 시계에 대한 독특한 지원으로 많은 시간을 소비하는 대신 작은 공간을 차지할 수도 있습니다.
　
먼저 예를 살펴보겠습니다. 예를 들어 foo1, foo2, bar1, bar2라는 키워드가 있습니다. 공백은 시간과 교환되므로 검색하기 전에 전처리를 해야 합니다. 앞서 언급했듯이 JS의 유연하고 효율적인 테이블은 트리 구조를 사용하는 것이 가장 유리한 점입니다. 이해하지 못해도 상관없습니다. 최종 구현 구조는 다음 코드와 같습니다.

코드 복사 코드는 다음과 같습니다.

var Root =
{
f:
{
o:
o:
: 참 ,
: 참
}
}
},
b:
{
a:
r :
{
: true,
: true
}
}
}
};



이 레이어별 구조는 단지 나무처럼 각 문자는 나무의 가지이고 마지막 문자는 잎이며 새 노드가 없습니다.

이 시점에서 해야 할 일은 기사의 각 단어를 트리 아래로 검색하는 것뿐이라는 점을 이해해야 합니다. 나뭇잎에 도달할 수 있다면 현재 문자가 키워드 중 하나라는 뜻입니다. 해당 분기를 중간에 찾을 수 없다면 당연히 키워드가 아닙니다.

예를 들어 foo1은 Root 구조를 따라 아래쪽으로 액세스하고 마침내 Root['f']['o']['o']['1']에 도달합니다. 즉 일치가 완료됩니다. . 그런 다음 foo1의 길이를 건너뛰고 나중에 계속 검색하세요.

따라서 전체 기사를 한 번만 검색하면 각 키워드의 위치를 ​​알 수 있습니다.
JS의 해시 테이블 성능이 매우 높기 때문에 소위 브랜치 검색이 매우 빠릅니다. JS의 유연성으로 인해 이 효과를 달성하는 코드도 매우 짧습니다.
　
실제로 키워드 수는 검색 시간과 거의 관계가 없음을 알 수 있습니다. 기사의 길이만이 검색 시간을 결정합니다.
　
한계 테스트를 해보자:
키워드: 관용구 전체 모음(19830개 항목)
내용: Zhuxian.txt 전체 모음(1659219단어)
시간: 935ms
( Chrome26 / i3- 2312 CPU)
160만 단어로 구성된 기사를 20,000개의 키워드와 매칭하는 데 1초도 채 걸리지 않습니다. JavaScript의 유연성을 최대한 활용하면 여전히 큰 잠재력이 있음을 알 수 있습니다.