import java.util.*;
import java.io.*;
public class Speller {
Trie trie;
public Speller() {
RandomAccessFile file = null;
trie = new Trie();
try {
file = new RandomAccessFile("C:/Documents and Settings/gur25950/My Documents/Downloads/words.txt","r"); }
catch (IOException ioe) { System.err.println("File not found"); }
try {
for (int i=0; ; i++) {
String word = file.readLine();
if (word == null) break;
if (word.indexOf((int)'\'')!= -1) continue;
trie.insert(word); }
trie.insert("aardvark");
}
catch (EOFException eofe) { }
catch (IOException ioe) { ioe.printStackTrace(); }}
public void insert (String string) {
trie.insert(string); }
public boolean search(String string) {
return trie.search(string); }
public static void main(String [] s)
{
Speller speller = new Speller();
}
}
class Trie {
// make private in implementation
public TrieNode root;
public Trie() {
root = new TrieNode(); }
// returns index 1-26 for valid words, -1 for
public static int getIndex(char ch) {
if (ch >= 'a' && ch <= 'z')
return (int)ch - 'a' + 1;
else if (ch >= 'A' && ch <= 'Z')
return (int)ch - 'A' + 1;
else
return -1; }
public boolean insert(String string) {
if (string == null) return false;
char ch = string.charAt(0);
TrieNode curr = root.getNext(ch);
if (curr == null) { // 1st word starting with given letter
return addNodesFromRoot(string); }
TrieNode prev = null;
// for each character in the string
for (int i = 0; curr != null && i < string.length(); i++) {
ch = string.charAt(i);
// set node value to character
curr.setValue(ch);
if (curr != null) { // curr NOT null: we have a character match
// is it the end of the string (a match)
if (i == string.length() -1) { // end of string
if (curr.getTerminator() != null) // already exists
return false;
else // terminator for word does not exist
curr.setTerminator(); }
else { // not end of string yet
// select next current
// create a new TrieNode for next iteration if one does not exist
if (curr.getNext(string.charAt(i+1)) == null)
curr.setNext(string.charAt(i+1), new TrieNode());
prev = curr;
curr = curr.getNext(string.charAt(i+1)); } }
else // curr IS null
return addNodes(prev, null, string.substring(i)); } // for
return true; }
public boolean search(String string) {
if (string == null) return false;
char ch = string.charAt(0);
// eliminate non-alpha characters
if ( ! Character.isLetter(ch)) return true; // assume correct
TrieNode node = root.getNext(ch);
boolean found = true;
for (int i = 0; node != null && i < string.length(); i++) {
ch = string.charAt(i);
if (! String.valueOf(node.getValue()).equalsIgnoreCase(String.valueOf(ch))) {
found = false;
break; }
else {
if ( i == string.length() -1) {
return node.isTerminatorSet(); }
else { // keep search going
// System.out.println("CC");
if (! Character.isLetter(string.charAt(i+1)))
return false;
node = node.getNext(string.charAt(i+1)); }
} // else
} // for
if (node == null)
return false;
else
return found; } // search
// completes a word which partially exists in the trie
private boolean addNodes(TrieNode prev, TrieNode curr, String substring) {
curr = prev;
// System.out.println("adding: " + substring);
for (int i =0; i < substring.length(); i++) {
// System.out.println("adding character: " + substring.charAt(i));
curr.setValue(substring.charAt(i));
// curr = new TrieNode(substring.charAt(i));
// now advance prev/curr and test if need to set terminator
if (i == substring.length() -1) { // end of string
// System.out.println("terminating with " + substring.charAt(i));
curr.setTerminator(); }
else { // not end of string yet
// select next current from upcoming character
prev = curr;
curr.setNext(substring.charAt(i+1), new TrieNode());
curr = curr.getNext(substring.charAt(i+1)); } } // for
return true; }
// method adds a new word which is 1st starting with its letter
// need this method since it is the only one which modifies the trie root
private boolean addNodesFromRoot(String string) {
TrieNode node = new TrieNode(string.charAt(0));
root.setNext(string.charAt(0),node);
// determine if word is a one letter word
if (string.length() == 1) {
// System.out.println("setting terminator");
node.setTerminator(); }
else {
node.setNext(string.charAt(1), new TrieNode());
return addNodes(node.getNext(string.charAt(1)), null, string.substring(1)); }
return true; }}
class TrieNode {
TrieNode [] next; // index 0 reserved for terminator value
char value;
public TrieNode(char object) {
value = object;
next = new TrieNode[27]; }
public TrieNode() {
next = new TrieNode[27]; }
public void setValue (char ch) {
value = ch; }
public char getValue() { return value; }
public TrieNode getNext(char ch) {
return next[Trie.getIndex(ch)]; }
public TrieNode getNext(int i) {
if ( ! ( i > 0 && i <= 27 )) return null;
return next[i]; }
public boolean setNext(char ch, TrieNode node) {
next[Trie.getIndex(ch)] = node;
return true; }
public TrieNode getTerminator() {
return next[0]; }
// marks terminator as non null (the TrieNode is just a placeholder)
public void setTerminator() {
next[0] = new TrieNode(); }
public boolean isTerminatorSet() {
return next[0] != null; }
public String toString() {
String string = "";
for (int i=0; i < 27; i++)
if ( next[i] == null ) string += " null";
else string += " +++";
return string; } } // TrieNod
Algo & program Developed By: Julius Dichter
