Saturday, April 10, 2010

TRIE data structure Part 6 : A Sample UI



Lets have a look at a sample application in Swing. We load the TRIE data structure using a dictionary word list. And using the application we can perform a search. This application is a very much prototypical just to check the insert() and search() operations.

Input file : words.txt

Sample Application


There are two possible outcomes to our search criteria, one true and another false. The following is the dialog shown when a word "article" is entered.

And when a word something like "dasdsa" is entered the following dialog is shown.


The Java code for the Trie Loader,

package dsa.tries;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class TrieLoader {
 
 public static Trie trieDSA;

 public static void main(String[] args) {
  TrieLoader trieLoader = new TrieLoader();
  trieLoader.load();
  new TrieTestFrame();
 }
 
 public void load(){
  trieDSA = new Trie();
  BufferedReader br = null;
  try {
   br = new BufferedReader(new FileReader(new File("src/properties/words.txt")));
   String eachLine = null;
   while((eachLine=br.readLine())!=null){
    trieDSA.insert(eachLine);
   }
  } catch (Exception e) {
   e.printStackTrace();
  } finally{
   if(br!=null){
    try {
     br.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
   }
  }
 }
}

The TrieTestFrame,

package dsa.tries;

import java.awt.Dimension;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JTextField;

public class TrieTestFrame extends JFrame {

 private static final long serialVersionUID = 1L;
 
 private JPanel basePanel = new JPanel();
 private JTextField textField = new JTextField(20);
 private JButton button = new JButton("Check");

 public TrieTestFrame(){
  designUI();
 }
 
 private void designUI(){
  this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  this.setTitle("TRIE Test");
  
  button.addActionListener(new ActionListener() {
   @Override
   public void actionPerformed(ActionEvent e) {
    if(TrieLoader.trieDSA.search(textField.getText())){
     JOptionPane.showMessageDialog(basePanel, "The word you entered exist!!");
    }else{
     JOptionPane.showMessageDialog(basePanel, "The word you entered does not exist!!","Error",JOptionPane.ERROR_MESSAGE);
    }
   }
  });
  
  basePanel.add(textField);
  basePanel.add(button);
  
  add(basePanel);
  
  this.setSize(400,100);
  
  Toolkit tk = Toolkit.getDefaultToolkit();
     Dimension screenSize = tk.getScreenSize();
     int screenHeight = screenSize.height;
     int screenWidth = screenSize.width;
     setLocation(screenWidth / 2 - 200, screenHeight / 2 - 50);
  
  this.setVisible(true);
 }
}

For the Node and Trie class please click here.

Cheers,
Bragaadeesh.

9 comments:

Maulish Soni said...

very memory consuming and time to buid trie is very large

b said...

@Maulish: I would tend to disagree with you. Memory for a TRIE is not huge as you think it is. In fact, we can optimize this by using external memory and fetch only the ones that we require on a need to know basis. And, regarding the construction of a TRIE, it is still efficient. Its like constructing a binary search tree. Every insert in a BST takes log n times (assuming a balanced tree). Same is the case here. Every word will be in the order of the word's length.
Hope this helped.

shoba said...

i want to print the contents of this trie tree for a string. but cant make it. can u provide code for displaying the contents of trie.

b said...

@shoba: Sure I can do that. Is it ok if I do that during this weekend ?

shoba said...

@bragadeesh: its okie. do at ur convenience.

Niraj said...

Hey! Thanks for this. However, like shoba said, could you show how to print the contents of the trie. Possibly start from a given node n and print all the words below it?

sony said...

I am generating a trie tree for a set of keyword sets.as soon as the INPUT string matches the keyword in the tree it should return the index of th e file containing that keyword.
one file may contain many keywords.
so i need to get the file index as soon as string match is found ..is there any method to have an index(FILE INDEX) for the end node(*). if soo can a set of nodes have same index ??
Thank you :)

Partha said...

hi, ur presentation is really very useful for beginners.i have some queries about Radix tree, can u please send me ur email id , thanks - partha. my email id is j.parthasarathy@gmail.com

Nikhil Bhardwaj said...

Great posts.
I was able to follow through and now understand Tries.
Thanks,
Nikhil