DOC

SpellChecker Program Using Java Trie Implementation

By Sheila Howard,2014-04-24 13:55
13 views 0
SpellChecker Program Using Java Trie Implementation

SpellChecker Program Using Java Trie Implementation

1

// Author Julius Dichter

    // ? 2002

import java.util.*;

    import java.io.*;

    public class Speller {

Trie trie;

    public Speller() {

RandomAccessFile file = null;

     trie = new Trie();

try {

     file = new RandomAccessFile("words.all","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(); }

}

     2

public 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;

     3

     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");

     4

     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

     5

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; }}

     6

    public 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; } } // TrieNode

     7

Report this document

For any questions or suggestions please email
cust-service@docsford.com