Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
Check out the new SourceForge HTML5 internet speed test! No Flash necessary and runs on all devices. ×
Java

Journal jomama717's Journal: Java Trie Implementation

/******************************************
* The three classes below implement a    *
* "Trie" structure in java.  My favorite *
* application of this structure is a     *
* streaming keyword replacer where a     *
* keywords can be compared one character *
* at a time as a stream is read.  Enjoy! *
******************************************/

/**************
* LookupTree *
**************/

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Method;
import java.util.Iterator;

/**
* A collection of LookupTreeNodes that represents a list of words
* layed out in such a way that incremental lookup by letter is convenient.
*/
public class LookupTree
{
  private LookupTreeNode mRootNode = new LookupTreeNode();

  public void addWord(String word)
  {
    LookupTreeNode nodeIter = mRootNode, tempIter = null;
    char currentChar = (char)0;

    for(int i = 0; i < word.length(); i++)
    {
      currentChar = word.charAt(i);

      if( (tempIter = nodeIter.getNodeForLetter(currentChar)) == null )
      {
        nodeIter = nodeIter.addLetter( currentChar, false );
      }
      else
      {
        nodeIter = tempIter;
      }
    }

    if( nodeIter.getIsWord() )
    {
      System.out.println( "Word: " + word + " already exists in table" );
    }
    else
    {
      nodeIter.setIsWord(true);
    }
  }

  /**
   * Given a file containing a list or words seperated by newlines fill up the
   * tree with those words.
   * @param fileName The name of the file to read words from.
   */
  public void loadWordsFromFile(String fileName)
  {
    String tempStr = null;
    File inFile = null;
    BufferedReader br = null;

    try
    {
      inFile = new File(fileName);

      br = new BufferedReader(
            new InputStreamReader(
             new FileInputStream(inFile)));

    }
    catch(FileNotFoundException fe)
    {
      System.out.println( fe.toString() );
      return;
    }

    try
    {
      while( (tempStr = br.readLine()) != null )
      {
        this.addWord( tempStr );
      }
    }
    catch(IOException ioe)
    {
      System.out.println( ioe.toString() );
    }
  }

  /**
   * Given String return true if the word is in the tree, false otherwise.
   * @param word The word to check the existence of.
   * @returns boolean true if the word is in the tree, false otherwise.
   */
  public boolean wordExists( String word )
  {
    LookupTreeNode nodeIter = mRootNode;
    boolean returnVal = false;
    char currentChar = (char)0;

    for( int i = 0; i < word.length(); i++)
    {
      currentChar = word.charAt(i);
      nodeIter = nodeIter.getNodeForLetter(currentChar);
      if( nodeIter == null )
      {
        break;
      }
    }

    if( nodeIter != null && nodeIter.getIsWord() )
    {
      returnVal = true;
    }

    return returnVal;
  }

  /**
   * Walk the table and perform an action on each word. Order is not guaranteed.
   * @param node The node to start from.
   * @param currWord The starting String, used for recursion
   * @param action A method in the form void action(String arg) to be performed on each string found
   */
  private void walkTable(LookupTreeNode node, String currWord, Method action)
  {
    Iterator iter = node.getLetterIterator();
    LookupTreeNode nextNode = null;
    Object [] arg = new Object[1];
    StringBuffer currentWord = new StringBuffer(currWord);
    currentWord.setLength( currWord.length() + 1 );
    char currentChar = (char)0;

    while( iter.hasNext() )
    {
      currentChar = ((Character)(iter.next())).charValue();
      currentWord.setCharAt(currWord.length(), currentChar);
      nextNode = node.getNodeForLetter( currentChar );
      if( nextNode.getIsWord() )
      {
        arg[0] = currentWord.toString();
        if( action != null && this.validateActionMethod( action ) )
        {
          try
          {
            action.invoke( this, arg );
          }
          catch( Exception e )
          {
            System.out.println( "Error while trying to execute method: " + action.toString() +
                                ": " + e.toString() );
          }
        }
        else
        {
          System.out.println( "Action method null or invalid" );
        }
      }

      this.walkTable( nextNode, currentWord.toString(), action );
    }
  }

  /**
   * Make sure that the method passed as action to the walker is of the right format.
   */
  private boolean validateActionMethod( Method action )
  {
    Class [] params = action.getParameterTypes();
    boolean returnVal = true;

    try
    {
      if( params.length != 1 || !params[0].equals(Class.forName("java.lang.String")) )
      {
        returnVal = false;
      }
    }
    catch( Exception e )
    {
      System.out.println( "Invalid class for parameter found" );
      returnVal = false;
    }

    return returnVal;
  }

  /**
   * Walk the tree and print each word
   */
  public void printTable()
  {
    try
    {
      this.walkTable( mRootNode, new String(), this.getActionMethodFromName( "printWord" ) );
    }
    catch(Exception e)
    {
      System.out.println( e.toString() );
    }
  }

  protected void printWord( String arg )
  {
    System.out.println( arg );
  }

  /**
   * utility for retrieving the Method object from the method name from *this* class
   */
  private Method getActionMethodFromName( String funcName )
  {
    Method returnMethod = null;

    try
    {
      Class [] params = { new String().getClass() };
      returnMethod = this.getClass().getDeclaredMethod( funcName, params );
    }
    catch( Exception e )
    {
      System.out.println( "Warning - returning null method: " + e.toString() );
    }

    return returnMethod;
  }

  /**
   * Return an iterator that can be used to incrementally (letter by letter)
   * check if a word exists in the list.
   */
  public LookupTreeIterator getIterator()
  {
    return new LookupTreeIterator(mRootNode);
  }

  /**
   * Return an iterator that can be used to incrementally (letter by letter)
   * check if a word exists in the list.
   */
  public boolean isRootChar( char c)
  {
    return mRootNode.containsLetter( c );
  }

  public static void main( String [] args )
  {
    try
    {
      LookupTree LT = new LookupTree();
      LT.loadWordsFromFile("dictionary.txt");
      LT.printTable();

      BufferedReader stdReader = new BufferedReader(
                                 new InputStreamReader( System.in ));

      String tempStr = null;

      while(true)
      {
        System.out.print("Enter a word to lookup, or \"quit\" to quit: ");
        tempStr = stdReader.readLine();
        if(tempStr.equals("quit") )
        {
          break;
        }
        else
        {
          System.out.println( LT.wordExists( tempStr ) );
        }
      }
    }
    catch(Exception e)
    {
      e.printStackTrace();
      System.out.println( e.toString() );
    }
  }

}

/******************
* LookupTreeNode *
******************/

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;

/**
* Represents one node of a tree class that makes
* incremental word-lookup easy.
*/
public class LookupTreeNode
{
  //true when the word ending with the letter that is this
  //TreeNode's key is a complete word.
  private boolean isWord = false;
  private HashMap letterMap = new HashMap();

  public LookupTreeNode() {}

  /**
   * Returns an iterator over the set of keys in this Node.
   * The set of keys is the set of letters represented at this
   * level of the tree.
   * @returns Iterator The keySet iterator
   */
  public Iterator getLetterIterator()
  {
    return letterMap.keySet().iterator();
  }

  /**
   * Returns the Set of keys int his Node.  The keys represent
   * the letters represented at this level of the tree.
   * returns Set The set of letters in this Node.
   */
  public Set getLetterSet()
  {
    return letterMap.keySet();
  }
  /**
   * Returns the Set of keys int his Node.  The keys represent
   * the letters represented at this level of the tree.
   * returns Set The set of letters in this Node.
   */

  public boolean containsLetter( char c )
  {
    return letterMap.containsKey(new Character(c));
  }

  /**
   * Adds a new letter at this level, and returns the corresponding
   * Node that is created.
   * @param c The letter to be added
   * @param isword If true, the isWord flag will be set for true in the returned Node,
   *        indicating that the added letter completed a word.
   * @returns LookupTreeNode The added node.
   */
  public LookupTreeNode addLetter(char c, boolean isword)
  {
    LookupTreeNode newNode = new LookupTreeNode();

    letterMap.put(new Character(c), newNode);

    return newNode;
  }

  public boolean getIsWord() { return this.isWord; }
  public void setIsWord( boolean isword ) { isWord = isword; }

  /**
   * See if this node contains some letter c.  If it does, return the letter's
   * corresponding node.
   * @param c The letter to look up
   * @returns LookupTreeNode the Node corresponding to the letter c, or null
   */
  public LookupTreeNode getNodeForLetter(char c)
  {
    return (LookupTreeNode)letterMap.get(new Character(c));
  }
}

/**********************
* LookupTreeIterator *
**********************/

import java.util.Set;

/**
  * The iterator class.  Maintains state and can be reset.
  */
public class LookupTreeIterator
{
   private final int BUFFER_SIZE     = 1024;
   private LookupTreeNode mInitialTreeNode = null;
   private LookupTreeNode mCurrentTreeNode = null;
   private Set mCurrentNodeKeys      = null;
   private char [] mCurrentWord      = null;
   private int mCurrentWordCount     = 0;
   private boolean mValidState       = true;
   private boolean mIsWord           = false;

   /**
    * Start at node rootNode, initialize word buffer, set initial node for reset later.
    */
   public LookupTreeIterator( LookupTreeNode rootNode )
   {
     mCurrentTreeNode  = mInitialTreeNode = rootNode;
     mCurrentNodeKeys  = mCurrentTreeNode.getLetterSet();
     mCurrentWord      = new char [ BUFFER_SIZE ];
     mCurrentWordCount = 0;
   }

   /**
    * See if the character c exists at the iterator's current location in the tree.
    */
   public boolean tryCharacter( char c )
   {
     boolean returnVal = false;
     mCurrentWord[ mCurrentWordCount++ ] = c;
     if( mCurrentNodeKeys.contains( new Character(c) ) )
     {
       returnVal = true;
       gotoNextNode(c);
     }
     else
     {
       mValidState = false;
       mIsWord = false;
     }
     return returnVal;
   }

   /**
    * Iterate to the next letter, only called if that letter exists.
    */
   private void gotoNextNode( char c )
   {
     mCurrentTreeNode = mCurrentTreeNode.getNodeForLetter(c);
     mCurrentNodeKeys = mCurrentTreeNode.getLetterSet();
     mIsWord = mCurrentTreeNode.getIsWord();
   }

   /**
    * Get the current buffer containing all looked up letters, including any that didn't exist.
    */
   public String getCurrentBuffer()
   {
     //MJM return mCurrentWord.toString();
     return new String( mCurrentWord, 0, mCurrentWordCount );
   }

   /**
    * Is the word currently held in the buffer a complete word in the tree?
    */
   public boolean isWord()
   {
     return mIsWord;
   }

   /**
    * Is the iterator currently in a valid state?  i.e. did the last letter checked exist,
    * meaning that what is currently in the buffer can be traced in through the tree?
    */
   public boolean isValid()
   {
     return mValidState;
   }

   /**
    * Reset the iterator
    */
   public void reset()
   {
     mCurrentTreeNode = mInitialTreeNode;
     mCurrentNodeKeys = mCurrentTreeNode.getLetterSet();
     mCurrentWordCount = 0;
     mValidState = true;
   }

}
This discussion has been archived. No new comments can be posted.

Java Trie Implementation

Comments Filter:

Nothing ever becomes real until it is experienced. - John Keats

Working...