即時搜索算法

Question

什麼類型的算法可以最快地搜索正在搜索的內容？我意識到這個問題已經接近詢問谷歌即時搜索的工作原理了，但我不是算法專家，我對它們越來越感興趣。像這樣的搜索使用後綴樹或類似的東西嗎？我想我只是對查詢小字符串感興趣，而不是像Google那樣搜索大量抓取的數據。

非常感謝您的任何意見！

Answer 1

對於這些類型的查詢，您可以將數據存儲在Trie或某種Trie樹中。

Answer 2

如果只是嘗試一小組字符串，那麼standard search algorithms是一個很好的開始。一次搜索每個字符並找到兩組之間的通用字符集，最好使用動態編程技術來完成，其中一個例子是找到Longest common subsequence。

Answer 3

樹很好，但你不需要把你的數組放在一個多維數組中。 這是我用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的七個循環 我不確定最大步數或步長。

PS：想我發現了最大的步驟：（感謝千里馬）

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