用於在文本中搜索單詞的最有效的數據結構Java

我有一個程序，它讀取文檔並搜索給定搜索詞的每個頁面。然後，它返回一個頁面的單詞出現在用於在文本中搜索單詞的最有效的數據結構Java

即「豔」字出現在以下網頁：1,4,6,8

在我的文件分割成頁的時刻，這個存儲到一個ArrayList。 ArrayList的每個元素都包含文檔的一個頁面

然後，我將頁面上的每個單詞分割並存儲到一個hashMap中，KEY是文本中該單詞出現的位置（我需要知道這一點爲其他功能）和價值是單詞。然後我使用HashMap進行搜索;

if (map.containsValue(searchString) == true) 
       return true; 
      else 
       return false;

我對每個頁面都這樣做。

一切正常，但我想知道是否有一個更有效的數據結構，我可以使用它存儲在給定的頁面上的所有單詞以及它出現在頁面上的位置？（因爲搜索中的值沒有給出密鑰的映射是0（n））。

我需要能夠搜索這個結構並找到一個單詞。記住我也需要這個位置供以後使用。

我用來填充地圖的文字中的單詞的位置的代碼是;

// text is the page of text from a document as a string 
int key = 1; // position of the word in the text 
    for (String element : text.split(" ")) 
      { 
       map.put(key, element); 
       key++; 
      }

來源

2014-07-13 Steve

爲什麼不使用一個單一的HashMap<String,ArrayList<Position>>將單詞映射到出現位置？文本中的每個單詞都將是地圖中的一個鍵，頁碼和位置將形成條目列表。

插入稍微棘手，因爲列表值：

ArrayList<Position> positions = words.get(word); 
if (positions == null) { 
    positions = new ArrayList<Position>(); 
    words.put(word, positions); 
} 
positions.add(position);

Alernatively，你可以使用一個番石榴Multimap之：http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Multimap.html（特別是如果你使用的是番石榴用於其他目的已經 - 我可能會避免只是爲此拉入庫依賴關係）

編輯：將整數更改爲位置（並將列表設置爲列表），但忽略了確切的位置是必需的。位置應類似於

class Position { 
    int page; 
    int index; 
}

來源

2014-07-13 15:04:18

感謝您的答覆，你是說在店裏用字符爲每個頁面上的文本和設置作爲頁碼一個HashMap中的文件？ – Steve

該字符串將是單個單詞，整數集將包含該單詞出現的頁碼（我試圖在答案文本中澄清此問題） –

但爲了計算頁碼，單詞出現在我需要使用類似的算法，在我原來的文章中，這將需要0（n）。我希望避免這種情況，並儘可能使用效率更高的產品 – Steve

我可能會使用Lucene或東西從Guava collections自己，但除非我認爲最有效的結構將是：

HashMap<String, TreeMap<Integer, TreeSet<Integer>>> words; 

     ^^^^^^   ^^^^^^^   ^^^^^^^ 
     word   page   position

使用words.get("brilliant").keySet();會立刻給你所有的出現「輝煌」的頁面。如果我沒有弄錯，那就是O(log n)而不是O(n)。

在你還需要之前檢索詞的意見和各搜索詞後，看完後，我想你會需要第二個數據結構爲查找：

TreeSet<Integer, TreeMap<Integer, String>> positions; 

     ^^^^^^^   ^^^^^^^ ^^^^^^ 
     page   position word

或者，使用兩個列表的頁面和位置的相應指標：

ArrayList<ArrayList<String>> positions;

來源

2014-07-13 15:21:57

我會嘗試實施這個歡呼！ – Steve

用於在文本中搜索單詞的最有效的數據結構Java

回答

相關問題