自動完成服務器端實現

Question

在html輸入框中實現服務器端組件的自動完成功能的快速高效的方法是什麼？

我正在我們的Web界面的主搜索框中寫一個自動完成用戶查詢的服務，並且完成顯示在ajax-powered下拉菜單中。我們正在運行查詢的數據只是一個我們系統知道的大概念表，它大致與維基百科頁面標題集相匹配。對於這項服務，顯然速度是最重要的，因爲網頁的響應對用戶體驗很重要。

當前實現只是將所有概念加載到有序集合的內存中，並對用戶按鍵執行簡單的log（n）查找。然後用尾部組合提供超出最接近匹配的附加匹配。這個解決方案的問題是它不能縮放。它目前正在滿足VM堆空間限制（我已經設置了-Xmx2g，這是我們可以在32位機器上推動的最多的），並且這妨礙了我們擴展概念表或增加更多功能。切換到具有更多內存的計算機上的64位虛擬機不是直接選項。

我一直在猶豫是否開始使用基於磁盤的解決方案，因爲我擔心磁盤尋道時間會導致性能下降。有沒有可能的解決方案可以讓我更好地擴展，無論是內存還是一些快速的磁盤備份實現？

編輯：

@Gandalf：對於我們的使用情況下，重要的是自動完成的是全面的，是不是用戶只需額外的幫助。至於我們正在完成的內容，它是一個概念類型對的列表。例如，可能的條目是[（「Microsoft」，「Software Company」），（「Jeff Atwood」，「Programmer」），（「StackOverflow.com」，「Website」）]。一旦用戶從自動完成列表中選擇一個項目，我們正在使用Lucene進行全面搜索，但我還不確定Lucene對於自動完成本身是否適用。

@Glen：這裏沒有使用數據庫。當我談論一張桌子時，我只是指我的數據的結構化表示。

@Jason Day：我對這個問題的原始實現是使用Trie，但由於需要大量的對象引用，因此內存膨脹實際上比有序集合更差。我會閱讀三元搜索樹，看它是否可以使用。

Answer 1

有了這麼大的設置，我會嘗試一些類似於Lucene索引的命令來查找所需的條件，並設置一個計時器任務，在每次擊鍵後重置，延遲時間爲.5秒。通過這種方式，如果用戶快速輸入多個字符，則只有在用戶暫停一秒鐘時纔會對每個筆劃查詢索引。可用性測試會讓您知道暫停應該停留多久。

Timer findQuery = new Timer(); 
... 
public void keyStrokeDetected(..) { 
    findQuery.cancel(); 
    findQuery = new Timer(); 
    String text = widget.getEnteredText(); 
    final TimerTask task = new TimerTask() { 
     public void run() { 
     ...query Lucene Index for matches 
     } 
    }; 
    findQuery.schedule(task, 350); //350 ms delay 
} 

那裏有一些pseduocode，但這就是主意。另外，如果設置了查詢條件，則可以預先創建和優化Lucene索引。

Answer 2

如果您無法將所有數據物理加載到RAM中，那麼您將不得不處理在磁盤上存在一些數據。

你在使用什麼數據庫？

例如，Oracle有一個選項，您可以將整個表保存在內存中，並針對該表執行查詢。

MySQL還聲稱有一些內存中的功能，但我對MySQL不太瞭解。

然後，您可以廢除基於Java的緩存，也可以將緩存用於最常用/最近的搜索。

很明顯，當你用完RAM時，有些數據將在磁盤上查詢時發現，但根據系統的負載情況，這隻會是第一次按鍵的問題，而不是後續的問題，因爲在那之後該行將在內存中。

如果磁盤尋道使您放慢速度，那麼您可以使用SSD驅動器進行調查以加快讀取速度。

Answer 3

我有類似的要求。

我將關係數據庫與單索引良好的合成表（避免連接和視圖加速查找）以及內存中緩存（Ehcache）存儲最常用的條目。

通過使用MRU緩存，您可以對大多數查找具有即時響應時間，並且在訪問存儲在磁盤上的大表中的索引列時，可能沒有任何事情可以擊敗關係數據庫。

這是您不能存儲在客戶端上的大數據集的解決方案，它工作得非常快（在我的情況下，總是在0.5秒內檢索非緩存查找）。它也可以橫向擴展 - 您可以隨時添加額外的服務器和數據庫服務器。

你也可以使用客戶端上最常用的結果進行緩存，特別是如果你已經實現了它。就我而言，服務器端解決方案足夠快，並且客戶端加載時間足夠慢，因此不保證。

P.S.只有當用戶暫停一段時間才能進行客戶端查詢以避免重複查找，這是一個很好的解決方案。在我的客戶端上，只有在輸入了前三個字符後，我才查詢數據庫，因爲在所有實例中返回的結果都不足以返回太多結果。

Answer 4

也許我誤解了你的問題，但難道你不能使用JQuery插件Ajax的信息到你的應用程序？

Ajax Auto Suggest v2

Answer 5

我做這個了使用Ternary search tree小數據集：

我以前使用過這一個。 DDJ代碼不難轉換爲Java，但是它假定整個數據集都可以放入內存。有三元搜索樹的磁盤實現（here是python中的一個），但當然它們的性能會降低。由於三元搜索樹擅長於部分匹配，但性能可能適合您的需求。

Answer 6

是否有可行的解決方案，這將 讓我變得更好

是，甲骨文。這就是數據庫的目的。只需索引相關列。如果您正在運行內存解決方案，那麼磁盤尋道時間或網絡延遲的折衷可能是沒有意義的。特別是如果你在兩者之間插入一個緩存層。

另外，如果稍微調整客戶端代碼，則可能會減少點擊次數。如在查詢運行之前設置最小數量的類型字符，或者在用戶停止鍵入之後設置延遲的一小部分。如果您已經在使用這些設置，請將它們設置得更高一些。

Answer 7

我最終通過Lucene解決了這個問題;初始性能測試對我們的用例來說似乎已經足夠了。爲了使前綴查詢能夠正常工作，我需要進行一些黑客行爲，因爲我在擴展諸如「Jeff At *」之類的查詢時遇到了TooManyClauses異常。我最終用一個FilterIndexReader封裝了我的IndexReader，並設置了在前綴字詞調用上返回的術語數量的上限。這裏是我的代碼：

Directory directory = FSDirectory.getDirectory(indexDir); 
IndexReader reader = IndexReader.open(directory); 
FilterIndexReader filteredReader = new FilterIndexReader(reader) { 
    @Override public TermEnum terms(Term t) throws IOException { 
    final TermEnum origEnum = super.terms(t); 

    return new TermEnum() { 
     protected int count = 0; 
     @Override public boolean next() throws IOException { 
     if (count++ < (BooleanQuery.getMaxClauseCount() - 10)) 
      return origEnum.next(); 
     else return false; 
     } 

     @Override public Term term() { 
     return origEnum.term(); 
     } 

     @Override public int docFreq() { 
     return origEnum.docFreq(); 
     } 

     @Override public void close() throws IOException { 
     origEnum.close(); 
     } 
    }; 
    } 
}; 

IndexSearcher searcher = new IndexSearcher(filteredReader); 

Answer 8

對於那些在這個問題誰絆倒......

我剛剛發佈了server-side autocomplete implementation在谷歌代碼。該項目包括一個可以集成到現有應用程序中的Java庫和一個獨立的HTTP AJAX自動完成服務器。

我希望能讓人們將高效的自動完成功能整合到他們的應用程序中。踢輪胎！

Answer 9

我用哈希表和mmap（） 和10,000,000+記錄術語列表是沒有問題的。 觀看演示在這裏：http://olegh.ath.cx/autocomplete.html

Answer 10

利用特里數據結構在這裏是 http://en.wikipedia.org/wiki/Trie