WAP to Spell Checking Using Trie

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