포럼 및 대화방과 같은 시나리오에서 사용자 경험을 보장하기 위해서는 종종 많은 나쁜 단어를 차단해야합니다. 단일 키워드 검색의 경우 자연스럽게 인덱스 및 일반 방법이 더 효율적입니다. 그러나 많은 키워드가있는 경우 전체 텍스트와 일치하는 Indexof 또는 일반 단어를 반복적으로 호출하면 성능 소비가 매우 높습니다. 대상 문자열의 크기는 일반적으로 크기 때문에 결과가 하나의 트래버스에서 얻어 지도록해야합니다. 이러한 요구에 따라 전체 텍스트의 각 문자를 순서대로 일치시키는 방법을 쉽게 생각할 수 있습니다. 예를 들어,이 텍스트의 경우 : "Mike Jordan은"그냥해라 "라고 말 했으므로 Mark는 코더였습니다." 키워드가 "Mike"및 "Mark"인 경우 전체 문장을 가로 질러 이동할 수 있습니다. "m"을 찾으면 "i"또는 "a"와 일치 할 수 있는지 확인하십시오. 끝까지 일치 할 수 있다면 키워드를 성공적으로 찾을 수 있습니다. 그렇지 않으면 계속 통과합니다. 그런 다음 키워드의 구조는 다음과 같아야합니다.
var keywords = {m : {i : {k : {e : {end : true}}}, a : {r : {k : {end : true}}}}}위에서, 우리는이 데이터가 트리 구조임을 알 수 있으며, 키워드 그룹을 기반으로 트리 구조를 만드는 것은 여전히 시간이 많이 걸리고 키워드는 이미 제공되므로 일치하기 전에 이러한 데이터 구조를 미리 만들 수 있습니다. 코드는 다음과 같습니다.
함수 buildTree (키워드) {var tblcur = {}, 키, str_key, 길이, j, i; var tblroot = tblcur; for (j = keywords.length -1; j> = 0; j - = 1) {str_key = 키워드 [j]; 길이 = str_key.length; for (i = 0; i <길이; i += 1) {key = str_key.charat (i); if (tblcur.hasownproperty (key)) {tblcur = tblcur [key]; } else {tblcur = tblcur [key] = {}; }} tblcur.end = true; // 마지막 키워드 TBLCUR = TBLROOT; } return tblroot;}이 코드는 연속 문을 사용합니다 : tblcur = tblcur [key] = {}. 여기서 실행 순서는 명세서의 실행 순서입니다. []의 작동 레벨이 =보다 높기 때문에 첫 번째는 TBLCUR 객체에서 키 속성을 만드는 것입니다. tblroot = tblcur = {}와 결합하여 실행 순서는 다음과 같습니다.
var tblroot = tblcur = {}; tblroot = tblcur; tblcur [ 'key'] = undefined; !위 코드를 통해 필요한 쿼리 데이터가 구성됩니다. 쿼리 인터페이스의 쓰기 방법을 살펴 보겠습니다.
대상 문자열의 각 단어에 대해이 키워드의 맨 위에서 시작합니다. 먼저 키워드 [A]. 있으면 키워드 [A] [B]를보십시오. 마지막 키워드 [a] [b]… [x] = true 인 경우 일치가 성공했음을 의미합니다. 키워드 [a] [b]… [x] = 정의되지 않은 경우 일치하는 것이 다음 위치에서 다시 시작됩니다.
function search (content) {var tblcur, p_star = 0, n = content.length, p_end, match, // match_key를 찾을 것인지, match_str, arrmatch = [], // 결과 arrlength = 0; // arrmatch의 길이 색인 while (p_star <n) {tblcur = tblroot; // 루트로 다시 추적 p_end = p_star; match_str = ""; 매치 = 거짓; do {match_key = content.charat (p_end); if (! 부서지다; } else {match_str += match_key; } p_end += 1; if (tblcur.end) // 꼬리와 일치할지 {match = true; }} while (true); if (match) {// maximum match arrmatch [arrlength] = {key : match_str, 시작 : p_star -1, end : p_end}; arrlength += 1; p_star = p_end; }} return arrmatch;}위는 전체 키워드 일치 시스템의 핵심입니다. 여기서 우리는 JS의 언어 기능을 매우 잘 사용하며 효율성은 매우 높습니다. 나는 50 만 단어의 "Soushen Ji"를 사용하여 테스트하고 주어진 300 개의 관용구를 발견했습니다. 일치 효과는 약 1 초입니다. 중요한 것은 대상 텍스트가 한 번에 통과되므로 대상 텍스트의 길이는 쿼리 시간에 거의 영향을 미치지 않습니다. 쿼리 시간에 더 큰 영향을 미치는 키워드 수는 키워드 수입니다. 대상 텍스트의 각 단어는 키워드를 가로 지르므로 쿼리에 특정 영향을 미칩니다.
간단한 분석
위의 기사를 언제 읽었는지 궁금합니다. 각 단어의 모든 키워드를 가로 질러 갈 수 있습니다. 일부 키워드가 부분적으로 동일하더라도 완전히 횡단하는 데 시간이 많이 걸립니다. 그러나 JS의 객체의 특성은 해시 테이블을 사용하여 구성됩니다. 이 구조의 데이터는 간단한 배열 트래버스와 매우 다르며, 효율은 순서 기반 어레이 트래버스의 효율보다 훨씬 높습니다. 일부 학생들은 데이터 구조에 익숙하지 않을 수 있으므로 해시 테이블의 관련 내용에 대해 간략하게 이야기하겠습니다.
먼저 데이터 저장을 살펴 보겠습니다.
메모리에서 데이터 저장은 두 부분으로 구성되며, 하나는 값이고 다른 하나는 주소입니다. 메모리를 Xinhua 사전으로 생각하면 단어의 설명이 값이며 디렉토리는 주소입니다. 예를 들어, 사전은 Pinyin에 의해 정렬됩니다. 예를 들어, 동일한 발음을 가진 "ni"는 같은 조각으로 배열됩니다. 즉, 배열은 메모리 영역에 깔끔하게 배열됩니다. 이 구조는 배열이며 "NI"번호 1 및 10을 지정하여 액세스 할 수 있습니다. 구조 다이어그램은 다음과 같습니다.
배열의 장점은 트래버스가 간단하고 첨자를 통해 해당 데이터에 직접 액세스 할 수 있다는 것입니다. 그러나 특정 항목을 추가하거나 삭제하는 것은 매우 어렵습니다. 예를 들어, 항목 6을 삭제하려면 항목 5의 데이터를 한 위치 씩 전진해야합니다. 첫 번째 비트를 삭제하려면 전체 배열을 이동해야하므로 많이 소비됩니다.
배열 추가 및 삭제 문제를 해결하기 위해 링크 된 목록이 나타납니다. 값을 두 부분으로 나누면 부품은 원래 값을 저장하는 데 사용되며 다른 부분은 다른 부분이 다른 구조를 가리키는 주소를 저장하는 데 사용됩니다. 구조는 다음과 같습니다.
위 그림에서 링크 된 목록을 추가하고 삭제하는 것이 매우 간단하다는 것을 명확하게 볼 수 있습니다. 대상 항목과 이전 항목의 다음 항목을 다시 작성하면 완료됩니다. 그러나 항목의 값을 쿼리하는 것은 매우 어렵습니다. 대상 위치에 액세스하려면 차례로 통과해야합니다.
이 두 구조의 장점을 통합하려면 다음 구조를 생각해야합니다.
이 데이터 구조는 해시 테이블 구조입니다. 링크 된 목록의 헤더 주소는 배열에 저장되며 2 차원 데이터 테이블을 형성 할 수 있습니다. 데이터가 분산되는 방법에 대해서는 해싱 알고리즘이며 일반 변환은 해싱 알고리즘이어야합니다. 많은 유형의 알고리즘이 있지만 원칙적으로는 함수를 통해 키를 해결 한 다음 솔루션에서 얻은 결과에 따라 데이터를 배치합니다. 다시 말해, 키와 실제 주소 사이에 매핑이 형성 되므로이 시점에서 배열을 위트하거나 단순히 트래 버는 대신 해시 함수의 역 함수로 데이터를 찾아 배열에 더 이상 배열에 액세스하지 못합니다. JS의 물체는 해시 구조입니다. 예를 들어, OBJ를 정의합니다. 해싱을 통한 OBJ.Name은 위의 그림에서 메모리의 위치가 90 일 수 있습니다. OBJ.Name을 작동하려면 기본 레이어가 자동으로 해시 알고리즘을 통해 90의 위치를 찾는 데 도움이됩니다. 즉, 전체 메모리 블록을 0에서 통과하는 대신 배열의 12 개 항목에서 링크 된 목록을 직접 찾기 시작합니다.
js에서 객체 obj {key : value}를 정의하십시오. 키는 문자열로 변환 된 다음 해시되어 메모리 주소를 얻은 다음 값을 넣습니다. 이를 통해 마음대로 속성을 추가 및 삭제할 수있는 이유와 JS의 배열에 속성을 할당 할 수있는 이유를 이해할 수 있으며 소위 국경 간 배열이 없습니다.
데이터 볼륨이 큰 상황에서 해시 테이블은 해시 알고리즘을 통해 많은 불필요한 계산을 줄이기 때문에 매우 명백한 이점이 있습니다. 소위 성능 최적화는 실제로 컴퓨터를 덜 컴퓨터로 만드는 것입니다. 가장 큰 최적화는 계산하지 않는 것입니다!
알고리즘 최적화
알고리즘의 기본 구현을 이해 했으므로 알고리즘 최적화를 회고하는 것을 고려할 수 있습니다. 그러나 최적화하기 전에 한 가지를 강조해야합니다. 맹목적으로 성능을 추구하지 마십시오! 예를 들어,이 경우 최대 5,000 단어까지 일치 할 수 있으므로 기존 알고리즘이 충분하고 모든 최적화가 불필요합니다. 내가 여전히 최적화에 대해 이야기하는 이유는 실제로 1MS 최적화를 수행하기보다는 알고리즘과 프로그램에 대한 이해를 향상시키는 것입니다.
우리는 키워드 중 어느 것도 한 단어가 없다는 것을 알았으므로 한 단어의 단위에 따라 키워드를 가로 지르는 낭비가 될 것입니다. 여기서 최적화는 키워드의 최대 및 최소 길이를 사전 상태로 유지하고 매번 최소 길이의 단위로 검색하는 것입니다. 예를 들어, 테스트 케이스의 키워드는 관용구이고 가장 짧은 문자는 4 자이므로 일치 할 때마다 4 자와 일치합니다. 내가 맞으면 최대 길이를 찾으려면 깊이있는 검색을 계속하십시오. 다시 말해서, 우리가 처음 나무를 구성 할 때, 그것은 먼저 최소 길이로 만들어진 다음 구두로 추가됩니다.
간단한 계산이 이루어집니다. 테스트 사례에 따르면 300 개의 관용구의 경우 한 단어 만 비교하면 한 번만 비교하면 4 번 비교해야하며 각 비교는 피할 수없는 성능 소비 인 트리 구조에 액세스해야합니다. 더 중요한 것은 여기서 비교는 문자열 비교가 아닙니다. 여기의 키워드는 모두 키로 존재하며, 효과는 키를 해시 한 다음 해당 주소에 액세스하는 OBJ의 키와 동일합니다! 따라서 한 단어를 비교하는 것과 네 단어를 비교하는 것의 차이에 대해 걱정하지 마십시오. 우리는 줄을 비교하지 않았습니다!
그것은 여러 키워드와 일치하는 것입니다. 일반적으로 사용할 수 없으므로 최적화 된 버전의 코드를 게시하지 않습니다.