Làm thế nào để in tất cả các từ được lưu trữ trong một Tree, trong đó trie đã được thực hiện bằng cách sử dụng Hashmap trong Java?

Question

Tôi muốn in hoặc truy xuất tất cả các từ được lưu trữ trong Cấu trúc dữ liệu Trie. Điều này là do tôi muốn tính khoảng cách Chỉnh sửa giữa từ sai chính tả và một từ trong Từ điển. Vì vậy, tôi đã nghĩ đến việc lấy từng từ từ Trie và tính khoảng cách Chỉnh sửa. Nhưng tôi không thể truy xuất. Tôi muốn một số đoạn mã cho việc này. Đây là cách tôi đã triển khai Trie bằng cách sử dụng HashMap trong Java

Bây giờ, hãy cho tôi biết cách viết mã để in tất cả các từ được lưu trữ trong Trie. Bất kỳ sự giúp đỡ được rất nhiều đánh giá cao

TrieNode.java

package triehash; 
import java.io.Serializable; 
import java.util.HashMap; 

public class TrieNode implements Serializable { 

HashMap<Character, HashMap> root; 

public TrieNode() { 
    root = new HashMap<Character, HashMap>(); 
    } 
} 

TrieDict.java

package triehash; 

import java.io.FileOutputStream; 
import java.io.ObjectOutputStream;; 
import java.io.Serializable; 
import java.util.HashMap; 
import java.io.Serializable; 

public class TrieDict { 
public TrieNode createTree() 
{ 
    TrieNode t = new TrieNode(); 
    return t; 
} 

public void add(String s, TrieNode root_node) { 
    HashMap<Character, HashMap> curr_node = root_node.root; 
    s = s.toLowerCase(); 
    for (int i = 0, n = s.length(); i < n; i++) { 
     Character c = s.charAt(i); 
     if (curr_node.containsKey(c)) 
      curr_node = curr_node.get(c); 
     else { 
      curr_node.put(c, new HashMap<Character, HashMap>()); 
      curr_node = curr_node.get(c); 
     } 
    } 
    curr_node.put('\0', new HashMap<Character, HashMap>(0)); // term 
    } 

public void serializeDict(TrieNode root_node) 
{  
    try{ 
     FileOutputStream fout = new FileOutputStream("/home/priya/NetBeansProjects/TrieHash/dict.ser"); 

    ObjectOutputStream oos = new ObjectOutputStream(fout); 
    oos.writeObject(root_node); 
    oos.close(); 
    System.out.println("Done"); 

    }catch(Exception ex){ 
     ex.printStackTrace(); 
    } 
} 

public void addAll(String[] sa,TrieNode root_node) { 
    for (String s: sa) 
     add(s,root_node); 
} 

public static void main(String[] args) 
{ 
    TrieDict td = new TrieDict(); 
    TrieNode tree = td.createTree(); 

    String[] words = {"an", "ant", "all", "allot", "alloy", "aloe", "are", "ate", "be"}; 
    for (int i = 0; i < words.length; i++) 
     td.add(words[i],tree);  
    td.serializeDict(tree); /* seriliaze dict*/ 
} 
} 

Answer 1

Đầu tiên, nó là đáng chú ý là kiểu tuyên bố của biến dụ root là một hơi kỳ quặc. (Cụ thể, loại giá trị của HashMap<Character,HashMap> không bao gồm một số các generics bạn muốn nó được sử dụng.) Mã dưới đây sẽ làm việc, nhưng bạn sẽ nhận được một số cảnh báo như là kết quả của việc này. Bạn có thể thử tái cấu trúc mã của mình để sử dụng loại HashMap<Character,TrieNode> thay thế. Xin lỗi nếu đó là pedantic. :)

Hãy thử điều này, thêm vào như là phương pháp để TrieNode:

public Set<String> computeWords() { 
    Set<String> result; 

    if(root.size() == 0) 
     result = new HashSet<String>(); 
    else 
     result = computeWords(root, ""); 

    return result; 
} 

protected static Set<String> computeWords(HashMap tree, String prefix) { 
    Set<String> result=new HashSet<String>(); 

    if(tree.size() == 0) 
     result.add(prefix); 
    else 
     for(Object o : tree.keySet()) { 
      Character c=(Character) o; 
      prefix = prefix+c; 
      result.addAll(computeWords((HashMap) tree.get(c), prefix)); 
      prefix = prefix.substring(0, prefix.length()-1); 
     } 

    return result; 
} 

Đối với một trao TrieNode đối tượng t, t.computeWords() sẽ quay trở lại các thiết lập của tất cả các từ từ mã hóa trong t.

Tôi tin rằng điều này sẽ trả lời câu hỏi bạn đang cố hỏi. Tuy nhiên, để trả lời câu hỏi như đã nêu trong tiêu đề, bạn muốn in tất cả các từ trong cùng t như thế này:

for(String word : t.computeWords()) 
    System.out.println(word); 

Ngoài ra, đây chắc chắn không phải là việc thực hiện hiệu quả nhất, đặc biệt là kể từ khi chúng ta tạo ra một bó của HashSet đối tượng trong computeWords(HashMap,String), nhưng nó sẽ hoạt động!

EDIT: Mã này cũng giả định rằng bạn chấm dứt các từ có dấu trống HashMap. Nếu bạn chấm dứt các từ với số null thay thế, bạn cần cập nhật séc if(tree.size() == 0) theo phương thức static với if(tree == null). Xin lỗi, nên đã gọi nó ra.

EDIT: Giải thích cách in tất cả các từ, chỉ trong trường hợp không rõ.

CHỈNH SỬA: Đã sửa lỗi vỏ trie trống.