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中的有效搜索

回答

相关问题