Member Avatar for nisaa15

Hi all,

I would like some ideas as to how I would go about developing a trie to store a very small dictionary (of about 10 words). How would I get the program to get each word and make the relevant nodes and edges? Also dela with compressing it?

Thanks for any help in advance.

  • 4 Contributors
  • 3 Replies
  • 219 Views
  • 5 Days Discussion Span
  • Latest Post Latest Post by jim mcnamara

Dani AI

Generated

For : for a tiny dictionary (about 10 words) the simplest, most reliable approach is a node-based trie: each node holds a Map of children keyed by a character and a boolean that marks "end of word". That follows 's Map idea (and the java.util.Map mention by ) and, as implied, you normally implement the trie yourself rather than expect a core "Trie" class. This keeps insert/search trivial and is perfectly lightweight for ten words.

Simple Java implementation (insert, contains, prefix check):

class Trie {
  static class Node {
    Map<Character,Node> children = new HashMap<>();
    boolean isWord = false;
  }
  private final Node root = new Node();

  public void insert(String s) {
    Node cur = root;
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      Node next = cur.children.get(c);
      if (next == null) { next = new Node(); cur.children.put(c, next); }
      cur = next;
    }
    cur.isWord = true;
  }

  public boolean contains(String s) {
    Node cur = root;
    for (int i = 0; i < s.length(); i++) {
      cur = cur.children.get(s.charAt(i));
      if (cur == null) return false;
    }
    return cur.isWord;
  }

  public boolean startsWith(String p) {
    Node cur = root;
    for (int i = 0; i < p.length(); i++) {
      cur = cur.children.get(p.charAt(i));
      if (cur == null) return false;
    }
    return true;
  }
}

Compression note (radix/compact trie): to compress, convert edges to labeled strings and merge any node that has exactly one child and isWord == false. Do a post-order traversal; when a node has a single child and does not terminate a word, splice the child up by concatenating the labels. This reduces node count but makes insertion/matching compare string segments instead of single characters.

Practical tips: for ten words a plain trie or even a HashSet<String> may be simplest unless you need prefix queries. Normalize case and strip unwanted characters before insert/search. Test with edge cases (empty string, overlapping prefixes such as "be" and "bear") and print the structure (edge labels) to verify correctness after compression.

Recommended Answers

All 3 Replies

Member Avatar for server_crash

Do you mean a tree? ;)
I'd say use a map or something along those lines. If there's a java equivalent of the c++ multimap, then go that route.

Member Avatar for jim mcnamara

The OP wants the tries data structure.
I don't know of any class that supports it.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.