Abstract
在文件檢索的問題中，我們給定一個總長度為 D 的文件（長字串）集合，目標是要對此文件集合建立索引，使得對任意一個 P 字串，我們能夠快速地知道哪些文件有包含 P。在這篇論文，我們提出了以上問題的一個延伸，名為 top-k 文件檢索。在此問題，我們並不會列出所有包含 P 的文件，而是只把 P 出現次數最多的 k 個文件列出。這個問題是搜尋引擎的根基。 Muthukrishnan 曾提出一個相關問題。他是要找出哪些文章 P 出現的次數超過 f 次。然而從資訊檢索的觀點來看，使用者很難知道要令 f 為多少，才能得到一個合理的或有意義的文件輸出量。在此論文，我們針對以上情形提出一些解法，並藉此得到有效率的 top-k 文件檢索的索引。我們的索引能夠在 O(|P| + logDloglogD + k) 時間內檢索，且只花 O(DlogD) 空間。我們的方法是根據廣為使用的字尾樹 (Suffix Tree) 的變形，在此我們稱之為導出字尾樹 (Induced Generalized Suffix Tree)。