즉석 검색 알고리즘

검색 대상을 검색하는 데 가장 빠른 알고리즘 유형은 무엇입니까? 나는 이것이 구글 인스턴트 검색이 어떻게 작동 하는지를 묻는 것에 아주 가깝다는 것을 알지만, 나는 알고리즘 전문가가 아니며 그들에게 점점 더 관심을 갖게되었다. 이와 같은 검색은 접미사 트리 또는 비슷한 것을 사용합니까? 나는 구글이하는 것처럼 많은 크롤링 된 데이터에 반대하는 것처럼 작은 문자열을 쿼리하는 데 관심이 있다고 생각한다.즉석 검색 알고리즘

모든 입력에 감사드립니다.

출처

2011-02-15 jphenow

: 나는 단계의 최대을 찾은 것 같아요. http://labs.google.com/papers/mapreduce.html도 역 색인이 될 수 있습니다. http://en.wikipedia.org/wiki/Reverse_index – Nishant

각 답변 및이 댓글별로 훌륭한 글을 읽었습니다. 나는 대답의 포럼에 대한 더 많은 설정 ... 나는 조금 더 읽고 내가 가장 좋아하는 하나를 선택하려고합니다. 이런 종류의 물건은 항상 나를 당황하게했고, 이제 마침내 약간의 이해를 얻습니다. – jphenow

이러한 유형의 쿼리의 경우 데이터를 Trie 또는 일종의 트리 트리에 저장할 수 있습니다.

출처

2011-02-15 04:47:23

단지 작은 문자열 집합을 시도하는 경우라면 standard search algorithms을 시작하는 것이 좋습니다. 한 번에 각 문자를 검색하고 두 세트 사이의 공통 문자 세트를 찾는 것이 동적 프로그래밍 기술을 사용하여 가장 잘 수행되며 그 중 하나는 Longest common subsequence입니다.

출처

2011-02-15 04:57:50

트리는 괜찮지 만 배열을 다차원 배열에 배치 할 필요는 없습니다. JS에서 큰 배열을 사용하여 수행하는 방법은 다음과 같습니다.

배열을 정렬해야합니다.

배열 중간으로 건너 뜁니다. 루프 : 배열 항목이 작고 tosearch 인 경우 위쪽 절반의 중간으로 점프합니다. 그렇지 않으면 배열 항목이 더 큰 경우 tosearch, 아래쪽 절반의 중간으로 점프합니다. 다른 사람을 찾았습니다.

var maxstep=Math.abs((Math.log(0.5)-Math.log(array.length))/Math.log(2)-1); 

function searchinterval(tosearch,array){ 
     var len=array.length, 
      pos=range=len/2, 
      index=Math.round(pos), 
      maxstep=.49999; 
     for(var i=0;i<=maxstep;i++){ 
       range/=2; 
       if(tosearch<array[index]){ 
       pos-=range; 
       } 
       else if(tosearch>array[index]){ 
       pos+=range; 
       } 
       else{ 
       return index; 
       //you found it 
       } 
       index=Math.round(pos); 
       } 
     return false; 
     }

배열에 tosearch가 없으면이 기능이 느립니다. 배열 길이 200에 대해 7 개의 루프를 의미합니다. ~~최대 스텝 수 또는 스텝 크기가 확실하지 않습니다.~~

PS : (감사 맥시마) 또한 구글 종이지도-감소 읽는 것을 좋아 할 수

Log(0.5)-Log(array_length))/Log(2) -1);

출처

2013-05-04 06:54:14

즉석 검색 알고리즘

답변

관련 문제