Trie數據結構和Java中的有效搜索

我有一個關於數據結構和高效搜索的任務。第一個輸入參數是一些包含字符串的大文本文件，每行都是一個新字符串。第二個輸入參數是一些前綴。輸出是在該大文件中找到的以給定前綴開頭的最短單詞。因此，我使用HashMap並使用每個字母作爲關鍵字構建了一個Trie。所以，我只是查找而不是迭代，這樣可以節省時間和內存。唯一不利於我的是搜索最短的單詞。我的意思是現在我得到以給定前綴開頭的單詞列表。然後我搜索遍歷列表中最短的一個。有沒有其他的方式來獲得最短的單詞？任何建議如何使這個更好，真的很感激，因爲這是我生命中第一次與Trie合作。請參閱我下面的代碼：Trie數據結構和Java中的有效搜索

TrieNode

class TrieNode { 

HashMap<Character, TrieNode> child; 

boolean isLast; 

public TrieNode() { 
    child = new HashMap<Character, TrieNode>(); 
    // Initialize all the Trie nodes with NULL 
    for (char i = 'a'; i <= 'z'; i++) 
     child.put(i, null); 
    isLast = false; 
}}

特里

public class Trie { 

TrieNode root = new TrieNode(); 
ArrayList<String> words = new ArrayList<>(); 

public void insertIntoTrie(ArrayList<String> newWords) { 

    int n = newWords.size(); 
    for (int i = 0; i < n; i++) { 
     insert(newWords.get(i)); 
    }} 


public void getWordsList(TrieNode curNode, 
         String prefix) { 

    if (curNode != null) { 

     if (curNode.isLast) 
      words.add(prefix); 

     for (char i = 'a'; i <= 'z'; i++) { 
      TrieNode nextNode = curNode.child.get(i); 
      if (nextNode != null) { 
       getWordsList(nextNode, prefix + i); 
      }}}} 


public void getShortest(String str) { 
    TrieNode prevNode = root; 
    TrieNode found = null; 

    String prefix = ""; 
    int len = str.length(); 

    for (int i = 0; i < len; i++) { 

     prefix += str.charAt(i); 

     char lastChar = prefix.charAt(i); 

     TrieNode curNode = prevNode.child.get(lastChar); 
     found = curNode; 

     if (curNode == null) { 
      System.out.println("No Results Found!"); 
      i++; 
      break;} 
    prevNode = curNode; } 

    getWordsList(found, prefix); 

    if (words.size() != 0) { 

     String shortestWord = words.get(0); 

     for (int j = 1; j < words.size(); j++) { 
      String nextWord = words.get(j); 
      if (nextWord.compareTo(shortestWord) < 0) { 
       shortestWord = nextWord; 

      }} 

     System.out.println("The shortest word is: " + shortestWord); 
    }}}

來源

2017-10-09 Boris

在第一次迭代時，您可以保存諸如最短和最長單詞之類的東西，當地圖生成時。閱讀過程中會耗費你一些時間。 –

問題是我在建立地圖時不知道前綴。前綴會在一段時間後出現。 – Boris

除非你需要保存所有相關的話，有沒有真正的理由來拯救他們在HashMap中。此外，HashMap對於迭代實際上是無用的，因爲無論如何您都需要訪問每個單詞。對於您的具體問題，我建議使用簡單的分鐘搜索，即搜索前綴，並且每次運行時都要保存它，只有當它短於當前存儲的單詞時才保存它。

來源

2017-10-09 17:20:16

我將所有相關單詞保存到ArrayList並且不會迭代 – Boris

Trie數據結構和Java中的有效搜索

回答

相關問題