Dictonary Program

[programmer 101]

Can somebody please direct me to source code for a simple CUI dictionary program (english please). Any help would be greatly appreciated!!!

Thanks so much!!

[John]

You need to find a dictionary file, then you can implement a Trie to search through the file.

[programmer 101]

what do u mean by a "file" as in a .txt containing words?
What would be easier, the trie or hash table...?

I think the trie is faster.. Thanks alot for the help, But what do you mean as in a "File?"

[John]

It doesn't have to be a txt file, its just any file that contains words. When I implemented a dictionary into my last program the file didn't even have an extention. It was just called "words." Just google "dictionary file" or something similar and download a txt, doc, or any type of file that contains words.

And as for the searching algorithm, when it comes to dictionary's I believe the Trie is the fastest you can get. I believe it is O(1) where a hash table would be O(n).

Below is a Trie class one of my dev teams made for a project, its been a while since I've looked at the code - its pretty complex, but if you are good with Java you should be able to work your way through it.

package codecall.net

import java.util.ArrayList;
import java.util.List;

/**
 * Provides a trie structure for an implementation of a dictionary. Since words 
 * never need to be removed from a dictionary during play, there is no option in 
 * this trie to remove a word.
 *
 * 
 *
 * Created on: Apr 13, 2006
 *
 */
public class Trie {
	
	private TrieRecursive[] _trie = new TrieRecursive[26];
	
	//	is the ASCII value of 'A'. When subtracted from a char's value, will provide the char's index value.
	private static final int ASCII_MOD = 65;

	/**
	 * Creates a new Trie structure, base case, which contains no datum, but only contains 
	 * 26 references to recursive trie structures.
	 */
	public Trie() {
	}
	
	/**
	 * Adds the given word into the trie structure.
	 * @param word The word to be added to the trie.
	 * @return true if the word was successfully added.
	 */
	public boolean addWord(String word) {
		if ((word.equals(""))||(!Character.isLetter(word.charAt(0)))) {
			return false;
		}
		
		char firstLetter = Character.toUpperCase(word.charAt(0));
		int index = (int)firstLetter - ASCII_MOD;
		
		if (_trie[index] == null) {
			_trie[index] = new TrieRecursive(firstLetter);
		}
		return _trie[index].addWord(word.substring(1));
		
	}
	
	/**
	 * Checks to see if the given word is in the trie.
	 * @param word The word to be checked.
	 * @return true if the word is in the trie.
	 */
	public boolean isWord(String word) {
		if ((word.equals(""))||(!Character.isLetter(word.charAt(0)))) {
			return false;
		}
		
		int index = (int)(Character.toUpperCase(word.charAt(0))) - ASCII_MOD;
		if (_trie[index] == null) {
			return false;
		}
		return _trie[index].isWord(word.substring(1));
		
	}
	
	/**
	 * Returns an ArrayList containing all words that are stored in the trie.<br><br>
	 * 
	 * An equivalent method can be performed by calling <tt>getWords("");</tt>
	 * @return All words, in the form of an ArrayList<String>.
	 */
	public List<String> getAllWords() {
		List<String> wordList = new ArrayList<String>();
		
		for (int i = 0; i < 26; i++) {
			if (_trie[i] != null)
				_trie[i].getAllWords(wordList, "");
		}
		
		return wordList;
	}
	
	/**
	 * Returns an ArrayList containing all words stored in the trie that begin with the specified letters.
	 * @param initial The first letters of the words to be found.
	 * @return All words beginning with the specified letters, in the form of an ArrayList<String>.
	 */
	public List<String> getWords(String initial) {
		List<String> wordList = new ArrayList<String>();
		
		if (initial.equals("")) {
			for (int i = 0; i < 26; i++) {
				if (_trie[i] != null)
					_trie[i].getWords(wordList, initial, "");
			}
		}
		else if (Character.isLetter(initial.charAt(0))) {
			int index = (int)(Character.toUpperCase(initial.charAt(0))) - ASCII_MOD;
			if (_trie[index] != null) {
				_trie[index].getWords(wordList, initial.substring(1), "");
			}
		}
		
		return wordList;
	}
	
	/**
	 * The recursive structure of the Trie superclass.
	 *
	 * @author Team S
	 *
	 * Created on: Apr 13, 2007
	 *
	 */
	private class TrieRecursive {
		private char _datum;
		private boolean _isEndOfWord = false;
		private TrieRecursive[] _subtrie = new TrieRecursive[26];
		
		/**
		 * Creates a new recursive Trie object. Each object contains a datum and
		 * an array of 26 potential subTries. 
		 * @param c The char representation of the Trie object.
		 */
		public TrieRecursive(char c) {
			_datum = c;
		}
		
		/**
		 * Adds the given word into the trie structure.
		 * @param word The word to be added to the trie.
		 * @return true if the word was successfully added.
		 */
		public boolean addWord(String word) {
			if (word.equals("")) {
				if (_isEndOfWord)
					return false;
				_isEndOfWord = true;
				return true;
			}
			if ( !Character.isLetter( word.charAt(0) )) {
				return false;
			}
			
			char firstLetter = Character.toUpperCase(word.charAt(0));
			int index = (int)firstLetter - ASCII_MOD;
			
			if (_subtrie[index] == null) {
				_subtrie[index] = new TrieRecursive(firstLetter);
			}
			return _subtrie[index].addWord(word.substring(1));
			
		}
		
		/**
		 * Checks to see if the given word is in the trie.
		 * @param word The word to be checked.
		 * @return true if the word is in the trie.
		 */
		public boolean isWord(String word) {
			if (word.equals("")) {
				return _isEndOfWord;
			}
			if ( !Character.isLetter( word.charAt(0) )) {
				return false;
			}
			
			int index = (int)(Character.toUpperCase(word.charAt(0))) - ASCII_MOD;
			if (_subtrie[index] == null) {
				return false;
			}
			return _subtrie[index].isWord(word.substring(1));
		}
		
		/**
		 * If a word ends at this level, adds the word to the wordList. Then, calls 
		 * this method on all the subTries.
		 * @param wordList The List to which valid words are added.
		 * @param stub A string representing the word formed by the path of parent nodes.
		 */
		public void getAllWords(List<String> wordList, String stub) {
			stub += _datum;
			if (_isEndOfWord) 
				wordList.add(stub);
			
			for (int i = 0; i < 26; i++) {
				if (_subtrie[i] != null)
					_subtrie[i].getAllWords(wordList, stub);
			}
		}
		
		/**
		 * Adds to the wordList all words that begin with the specified letters.
		 * @param wordList The List to which valid words are added.
		 * @param initial The first letters of the words to be found.
		 * @param stub A string representing the word formed by the path of parent nodes.
		 */
		public void getWords(List<String> wordList, String initial, String stub) {
			if (initial.equals("")) {
				this.getAllWords(wordList, stub);
			}
			else {
				stub += _datum;
				int index = (int)(Character.toUpperCase(initial.charAt(0))) - ASCII_MOD;
				if (_subtrie[index] == null) {
					return;
				}
				_subtrie[index].getWords(wordList, initial.substring(1), stub);
			}
		}
		
	}
}

Implementation

package codecall.net;

import java.io.BufferedInputStream;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * Checks validation of submitted words.
 */
public class Dictionary {

	/**
	 * Takes the List of words provided and has them checked by calling the check method. If check determines it is not a word, IllegalWordException is thrown.
	 * 
	 * @param wordList The list of words that a player has created with the tiles they have added on a certain turn.
	 * @throws IllegalWordException
	 */
	public static void checkAll(ArrayList<Word> wordList, Trie dictionary) throws IllegalWordException{
		Iterator<Word> iter = wordList.iterator();
		while(iter.hasNext()){
			String temp = iter.next().toString();
			if(!dictionary.isWord(temp)){
				throw new IllegalWordException(temp + " is not a valid word.");
			}
		}
	}

	
	/**
	 * Adds all the words in the given file path to the given Trie dictionary.
	 * @param dictionary the Trie into which the words will be added
	 * @param path the path of the file containing the word list
	 */
	@SuppressWarnings("deprecation")
	public static void initializeDictionary(Trie dictionary, String path) {
		File f = new File(path);
		try {
			FileInputStream fis = new FileInputStream(f);
			BufferedInputStream bis = new BufferedInputStream(fis);
			DataInputStream dis = new DataInputStream(bis);
			while(dis.available() != 0){
				//
				dictionary.addWord(dis.readLine());
			}
			fis.close();
			bis.close();
			dis.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

[programmer 101]

i tried to compile, it compiles no error but doesnt run... i need a main.. but what should i put there.. sorry im a bit nooby..

thanks for the help so far though!

[John]

I provided you with two classes. One an ADT (abstract data type) [Trie] and another [Dictionary] which is the implementation of the Trie. You simply need to instantiate the objects, call the proper methods, and pass in the correct arguments which are nicely documented in the source code. You shouldn't need to write more than 10 lines of code to fully integrate it.

After you spend several hours understanding every line of code in the above snippets you should have no problem implementing it, if not - then I will have sympathy and help you further.

[programmer 101]

um sorry to be noobish, but i might need help with the classes ... this is a new subject to me.. i wasnt in class for the past few weeks nd its comming to the end of the year...

Can you please help me!?! thanks so much

[John]

Sure I will help you, but I will not do it for you. If you ask a specific question other than saying you are a noob and dont know what you are doing -- I would love to help you.

Have you looked over the code I gave you yet? What arent you sure about?
Have you found a dictionary file yet?

[kajal88]

thanks for all the info

[brian]

Ok, well I went through and completed the code given above, seeing as it didn't seem complete, and didn't look like it would run.

Here are the files along with the code:

File: Dictionary.java

package codecall.net;

import java.io.BufferedInputStream;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * Checks validation of submitted words.
 */
public class Dictionary {

	/**
	 * Takes the List of words provided and has them checked by calling the check method. If check determines it is not a word, IllegalWordException is thrown.
	 * 
	 * @param wordList The list of words that a player has created with the tiles they have added on a certain turn.
	 * @throws IllegalWordException
	 */
	public static void checkAll(ArrayList<Word> wordList, Trie dictionary) throws IllegalWordException{
		Iterator<Word> iter = wordList.iterator();
		while(iter.hasNext()){
			String temp = iter.next().toString();
			if(!dictionary.isWord(temp)){
				throw new IllegalWordException(temp + " is not a valid word.");
			}
		}
	}

	
	/**
	 * Adds all the words in the given file path to the given Trie dictionary.
	 * @param dictionary the Trie into which the words will be added
	 * @param path the path of the file containing the word list
	 */
	@SuppressWarnings("deprecation")
	public static void initializeDictionary(Trie dictionary, String path) {
		File f = new File(path);
		try {
			FileInputStream fis = new FileInputStream(f);
			BufferedInputStream bis = new BufferedInputStream(fis);
			DataInputStream dis = new DataInputStream(bis);
			while(dis.available() != 0){
				//
				dictionary.addWord(dis.readLine());
			}
			fis.close();
			bis.close();
			dis.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

File: Driver.java

/*
 * Driver.java
 *
 * Created on July 1, 2007, 1:10 PM
 *
 */

package codecall.net;

import java.util.ArrayList;

/**
 *
 * @author brian
 */
public class Driver 
{
    
    /** Creates a new instance of Driver */
    public Driver() 
    {
        
    }
     public static void main (String args[])
     {
        
        Trie dictionary = new Trie (); // creates a new Trie object
        String path = "dictionary.txt"; //the path to your dictionary file
        
        Dictionary.initializeDictionary(dictionary,path); // initialize the dictionary
        
        ArrayList<Word> wordList = new ArrayList();
        
        wordList.add(new Word("test")); // replace test with your word, or add more lines with wordList.add with additional words
        
        try
        {
            Dictionary.checkAll(wordList,dictionary);
        }
        catch (IllegalWordException ilwe)
        {
            System.out.println("Oops: " + ilwe); // the word wasn't found'
        }

        System.out.println("All Done!");
    }
    
}

File: IllegalWordException.java

/*
 * IllegalWordException.java
 *
 * Created on July 1, 2007, 1:10 PM
 *
 */
package codecall.net;

/**
 *
 * @author brian
 */
public class IllegalWordException extends java.lang.Exception
{
    public  IllegalWordException ( )
    {
        super ( "Not A Valid Word" );
    }
    
    public IllegalWordException (String exceptionText)
    {
        super (exceptionText);
    }
    
}

File: Trie.java

package codecall.net;

import java.util.ArrayList;
import java.util.List;

/**
 * Provides a trie structure for an implementation of a dictionary. Since words 
 * never need to be removed from a dictionary during play, there is no option in 
 * this trie to remove a word.
 *
 * 
 *
 * Created on: Apr 13, 2006
 *
 */
public class Trie {
	
	private TrieRecursive[] _trie = new TrieRecursive[26];
	
	//	is the ASCII value of 'A'. When subtracted from a char's value, will provide the char's index value.
	private static final int ASCII_MOD = 65;

	/**
	 * Creates a new Trie structure, base case, which contains no datum, but only contains 
	 * 26 references to recursive trie structures.
	 */
	public Trie() {
	}
	
	/**
	 * Adds the given word into the trie structure.
	 * @param word The word to be added to the trie.
	 * @return true if the word was successfully added.
	 */
	public boolean addWord(String word) {
		if ((word.equals(""))||(!Character.isLetter(word.charAt(0)))) {
			return false;
		}
		
		char firstLetter = Character.toUpperCase(word.charAt(0));
		int index = (int)firstLetter - ASCII_MOD;
		
		if (_trie[index] == null) {
			_trie[index] = new TrieRecursive(firstLetter);
		}
		return _trie[index].addWord(word.substring(1));
		
	}
	
	/**
	 * Checks to see if the given word is in the trie.
	 * @param word The word to be checked.
	 * @return true if the word is in the trie.
	 */
	public boolean isWord(String word) {
		if ((word.equals(""))||(!Character.isLetter(word.charAt(0)))) {
			return false;
		}
		
		int index = (int)(Character.toUpperCase(word.charAt(0))) - ASCII_MOD;
		if (_trie[index] == null) {
			return false;
		}
		return _trie[index].isWord(word.substring(1));
		
	}
	
	/**
	 * Returns an ArrayList containing all words that are stored in the trie.<br><br>
	 * 
	 * An equivalent method can be performed by calling <tt>getWords("");</tt>
	 * @return All words, in the form of an ArrayList<String>.
	 */
	public List<String> getAllWords() {
		List<String> wordList = new ArrayList<String>();
		
		for (int i = 0; i < 26; i++) {
			if (_trie[i] != null)
				_trie[i].getAllWords(wordList, "");
		}
		
		return wordList;
	}
	
	/**
	 * Returns an ArrayList containing all words stored in the trie that begin with the specified letters.
	 * @param initial The first letters of the words to be found.
	 * @return All words beginning with the specified letters, in the form of an ArrayList<String>.
	 */
	public List<String> getWords(String initial) {
		List<String> wordList = new ArrayList<String>();
		
		if (initial.equals("")) {
			for (int i = 0; i < 26; i++) {
				if (_trie[i] != null)
					_trie[i].getWords(wordList, initial, "");
			}
		}
		else if (Character.isLetter(initial.charAt(0))) {
			int index = (int)(Character.toUpperCase(initial.charAt(0))) - ASCII_MOD;
			if (_trie[index] != null) {
				_trie[index].getWords(wordList, initial.substring(1), "");
			}
		}
		
		return wordList;
	}
	
	/**
	 * The recursive structure of the Trie superclass.
	 *
	 * @author Team S
	 *
	 * Created on: Apr 13, 2007
	 *
	 */
	private class TrieRecursive {
		private char _datum;
		private boolean _isEndOfWord = false;
		private TrieRecursive[] _subtrie = new TrieRecursive[26];
		
		/**
		 * Creates a new recursive Trie object. Each object contains a datum and
		 * an array of 26 potential subTries. 
		 * @param c The char representation of the Trie object.
		 */
		public TrieRecursive(char c) {
			_datum = c;
		}
		
		/**
		 * Adds the given word into the trie structure.
		 * @param word The word to be added to the trie.
		 * @return true if the word was successfully added.
		 */
		public boolean addWord(String word) {
			if (word.equals("")) {
				if (_isEndOfWord)
					return false;
				_isEndOfWord = true;
				return true;
			}
			if ( !Character.isLetter( word.charAt(0) )) {
				return false;
			}
			
			char firstLetter = Character.toUpperCase(word.charAt(0));
			int index = (int)firstLetter - ASCII_MOD;
			
			if (_subtrie[index] == null) {
				_subtrie[index] = new TrieRecursive(firstLetter);
			}
			return _subtrie[index].addWord(word.substring(1));
			
		}
		
		/**
		 * Checks to see if the given word is in the trie.
		 * @param word The word to be checked.
		 * @return true if the word is in the trie.
		 */
		public boolean isWord(String word) {
			if (word.equals("")) {
				return _isEndOfWord;
			}
			if ( !Character.isLetter( word.charAt(0) )) {
				return false;
			}
			
			int index = (int)(Character.toUpperCase(word.charAt(0))) - ASCII_MOD;
			if (_subtrie[index] == null) {
				return false;
			}
			return _subtrie[index].isWord(word.substring(1));
		}
		
		/**
		 * If a word ends at this level, adds the word to the wordList. Then, calls 
		 * this method on all the subTries.
		 * @param wordList The List to which valid words are added.
		 * @param stub A string representing the word formed by the path of parent nodes.
		 */
		public void getAllWords(List<String> wordList, String stub) {
			stub += _datum;
			if (_isEndOfWord) 
				wordList.add(stub);
			
			for (int i = 0; i < 26; i++) {
				if (_subtrie[i] != null)
					_subtrie[i].getAllWords(wordList, stub);
			}
		}
		
		/**
		 * Adds to the wordList all words that begin with the specified letters.
		 * @param wordList The List to which valid words are added.
		 * @param initial The first letters of the words to be found.
		 * @param stub A string representing the word formed by the path of parent nodes.
		 */
		public void getWords(List<String> wordList, String initial, String stub) {
			if (initial.equals("")) {
				this.getAllWords(wordList, stub);
			}
			else {
				stub += _datum;
				int index = (int)(Character.toUpperCase(initial.charAt(0))) - ASCII_MOD;
				if (_subtrie[index] == null) {
					return;
				}
				_subtrie[index].getWords(wordList, initial.substring(1), stub);
			}
		}
		
	}
}

File: Word.java

/*
 * Word.java
 *
 * Created on July 1, 2007, 1:10 PM
 *
 */

package codecall.net;

/**
 *
 * @author brian
 */
public class Word
{
    private String myWord;
    
    public Word ()
    {
        myWord = "";
    }
    
    public Word (String word)
    {
        myWord = word;
    }
    
    public String toString ()
    {
        return myWord;
    }
}

I left the two classes given above alone, and simply created the other ones. And I didn't have a dictionary file to test this on, so I am not 100% sure if it works or not.