****YOU CAN DOWNLOAD THOSE FILES FROM HERE*** https://drive.google.com/open?id=0
ID: 3826579 • Letter: #
Question
****YOU CAN DOWNLOAD THOSE FILES FROM HERE***
https://drive.google.com/open?id=0B2gb5h869g2aaVNYMjAzeDRMRjQ
Create a spell checker that uses dictionary that stores its words in a balanced binary tree.
Tasks and Requirements
NOTE: Naming is critical in the tasks and requirements described below. If the names don't match those described below exactly, your project will not be graded.
Create a copy of the Java SE Project Template. The project name must follow this pattern: {FLname}_SpellChecker_{TERM}, where {FLname} is replaced by the first letter of your first name plus your last name, and {TERM} is the current semester and year. E.g. if your name is Maria Marciano and it's Fall 2014, your project name must be MMarciano_SpellChecker_F14.
Create a package named spellchecker in your project.
BinaryTreeNode class:
Download BinaryTreeNode.java, and put it in the spellchecker package.
Your BinaryTree class must use BinaryTreeNode to store its words.
Do not modify BinaryTreeNode.java.
BasicDictionary class:
Download the Dictionary.java interface and put it in the spellchecker package.
Read the comments above each method to understand what they are supposed to do.
Create a new class named BasicDictionary in the spellchecker package. In the class creation wizard, click the Add (interface) button, and search for Dictionary. Check the "Inherited abstract methods" box. Click Finish. Eclipse will create the class and automatically add method stubs that meet the Dictionary interface.
You do not modify the Dictionary interface. You add your code to the BasicDictionary class.
BasicDictionary must use a binary tree to store the words in the dictionary. BasicDictionary can hold the root of the binary tree, but a stronger design would use a separate BinaryTree class.
You must write your own binary tree code.
BasicSpellChecker class:
Download the SpellChecker.java interface and put it in the spellchecker package.
Read the comments above each method to understand what they are supposed to do.
In BasicSpellChecker, modify the public class BasicSpellChecker to include implements SpellChecker.
You can use Eclipse's QuickFix support to add the required methods to BasicSpellChecker.
You do not modify the SpellChecker interface. You add your spell-checking code to BasicSpellChecker's methods.
Add the unit testing classes. These classes will be used to test the code that you write.
Create a new package in the src folder called sbccunittest. To be clear: sbccunittest should be a child of the src folder, not of the spellchecker package.
Download SpellCheckerTester.java into sbccunittest.
Download test_files.zip into your project root and unzip them into your project's root folder.
Spell-checking notes
Be sure to read the SpellChecker.spellCheck() documentation carefully. It specifies the regular expression that you must use for iterating through words in the document.
It also describes an instance variable of BasicSpellChecker that you need to create and update - the current spell checking index.
Also be sure to read the SpellChecker.replaceText() documentation carefully. It describes how the spell checking index is to be adjusted when replaceText() is called.
Note that the test documents are Windows files, which means that each line ends with (i.e. two characters).
Ignore case when comparing words.
Unit Testing
Debug all java compilation Errors (see the Problems view). The unit tests can't be run until these errors are fixed.
In the Package Explorer, right-click on the sbccunittest package | Run As... | JUnit Test.
Initially, all of the tests will probably fail. However, as you add functionality to the BasicDictionary class, tests will begin to pass.
Work on BasicDictionary first. Continue adding functionality to the BasicDictionary until all of the dictionary tests (see Scoring section below) pass. Then start working on BasicSpellChecker and its associated tests.
There is no user interface requirement for this assignment. However, you might find it interesting to build a simple console interface that allows the user to specify a dictionary and a text document to spell check. When an unknown word is found, give the user options to ignore the word, change it themselves, replace it with the preceeding/succeeding word, or end the spell checking. When spell checking is completed, overwrite the original text document with the spell-checked version.
*** When importing the dictionary, build a complete tree.
Explanation / Answer
I am trying to implementing a simple spellchecker which is simply determine if all the words in the tet file being checked existed in a dictionary of words. if the word existed in the dictionary it would be interpreted by the program and if it is not, a list of suggestion was to be provided from the dictionary.
We will use AVL tree for indexing data which means it must be checked and rebalanced after every modification. All operation take O(logn) average case performance, it is good for large data set.
there are three classes used in the implementation. Spellchecker uses an instance of AVLTree, which uses a custom collection of zero or more AVLNodes.
AVLNode.java
public class AVLNode {
private String key = null;
private String originalData = null;
private AVLNode leftChild = null;
private AVLNode rightChild = null;
private int height = 0;
public AVLNode (String key, String originalData){
this.key = key;
this.originalData = originalData;
leftChild = null;
rightChild = null;
height = 0;
}
public String getKey(){
return key;
}
public String getOriginalData(){
return originalData;
}
public AVLNode getLeftChild (){
return leftChild;
}
public void setLeftChild (AVLNode n)
{
leftChild = n;
}
public AVLNode getRightChild (){
return rightChild;
}
public void setRightChild (AVLNode n){
rightChild = n;
}
public int getHeight (){
return height;
}
public void setHeight (int h){
height = h;
}
}
AVLTree.java
import java.util.*;
public class AVLTree {
private AVLNode root = null;
private int size = 0;
public AVLTree (){
root = null;
size = 0;
}
public void insert (String key){
root = insert(key.toLowerCase(), key, root);
}
private AVLNode insert (String key, String originalData, AVLNode node){
if (node == null){
node = new AVLNode (key, originalData);
size++;
return node;
}
else{
if (key.compareTo (node.getKey()) < 0){
node.setLeftChild (insert (key, originalData, node.getLeftChild ()));
if (height (node.getLeftChild ()) - height (node.getRightChild ()) == 2){
if (key.compareTo ((node.getLeftChild ()).getKey ()) < 0)
node = rotateWithLeft (node);
else
node = doubleWithLeft (node);
}
}
else{
if (key.compareTo (node.getKey ()) > 0){
node.setRightChild (insert (key, originalData, node.getRightChild ()));
if (height (node.getRightChild ()) - height (node.getLeftChild ()) == 2){
if (key.compareTo ((node.getRightChild ()).getKey ()) > 0)
node = rotateWithRight (node);
else
node = doubleWithRight (node);
}
}
}
}
node.setHeight (max (height (node.getLeftChild ()), height (node.getRightChild ())) + 1);
return node;
}
public AVLNode root(){
return root;
}
public int size (){
return size;
}
public int height (){
return height (root);
}
private int height (AVLNode node){
if (node == null)
return -1;
return node.getHeight ();
}
public boolean isEmpty (){
return (size == 0);
}
private AVLNode rotateWithLeft (AVLNode node){
AVLNode newNode = node.getLeftChild ();
node.setLeftChild (newNode.getRightChild ());
newNode.setRightChild (node);
node.setHeight (max (height (node.getLeftChild ()), height (node.getRightChild ())) + 1);
newNode.setHeight (max (height (newNode.getLeftChild ()), node.getHeight ()) + 1);
return newNode;
}
private AVLNode rotateWithRight (AVLNode node){
AVLNode newNode = node.getRightChild ();
node.setRightChild (newNode.getLeftChild ());
newNode.setLeftChild (node);
node.setHeight (max (height (node.getLeftChild ()), height (node.getRightChild ())) + 1);
newNode.setHeight (max (height (newNode.getRightChild ()), node.getHeight ()) + 1);
return newNode;
}
private AVLNode doubleWithLeft (AVLNode node){
node.setLeftChild (rotateWithRight (node.getLeftChild ()));
return rotateWithLeft (node);
}
private AVLNode doubleWithRight (AVLNode node){
node.setRightChild (rotateWithLeft (node.getRightChild ()));
return rotateWithRight (node);
}
public static int max (int first, int second){
if (first >= second)
return first;
else
return second;
}
public boolean isInTree (String key){
return isInTree (key, root);
}
private boolean isInTree (String key, AVLNode node){
if (node == null)
return false;
if (key.compareTo (node.getKey ()) < 0)
return isInTree (key, node.getLeftChild ());
if (key.compareTo (node.getKey ()) > 0)
return isInTree (key, node.getRightChild ());
return true;
}
public String[] getBestMatches(String word, int limit) {
if (isInTree(word.toLowerCase(), root))
return new String[] { word };
if (word.length() <= 1)
return new String[0];
// strip off last letter and search for first node that "starts with" the term
String searchTerm = word;
AVLNode bestPartialMatchedNode = null;
do {
searchTerm = searchTerm.substring(0, word.length() - 1).toLowerCase();
bestPartialMatchedNode = getBestPartialMatch(searchTerm, root);
}
while (searchTerm.length() > 1 && bestPartialMatchedNode == null);
if (bestPartialMatchedNode == null)
return new String[0]; // nothing to suggest
LinkedList<String> bestMatches = new LinkedList<String>();
LinkedList<AVLNode> currentLevel = new LinkedList<AVLNode>();
LinkedList<AVLNode> nextLevel = new LinkedList<AVLNode>();
currentLevel.push(bestPartialMatchedNode);
while(!currentLevel.isEmpty() && bestMatches.size() < limit){
AVLNode node = currentLevel.pollLast();
if (node != null) {
if (node.getKey().startsWith(searchTerm))
bestMatches.add(node.getOriginalData());
if(node.getLeftChild() != null)
nextLevel.push(node.getLeftChild());
if(node.getRightChild() != null)
nextLevel.push(node.getRightChild());
if (currentLevel.isEmpty()) {
LinkedList<AVLNode> temp = nextLevel;
nextLevel = currentLevel;
currentLevel = temp;
}
}
}
Collections.sort(bestMatches);
return bestMatches.toArray(new String[bestMatches.size()]);
}
private AVLNode getBestPartialMatch(String key, AVLNode node) {
if (node == null)
return null;
if (node.getKey().startsWith(key))
return node;
if (key.compareTo (node.getKey ()) < 0)
return getBestPartialMatch (key, node.getLeftChild ());
if (key.compareTo (node.getKey ()) > 0)
return getBestPartialMatch (key, node.getRightChild ());
return null;
}
public void remove (String key) {
AVLNode parent = null;
AVLNode target = null;
AVLNode node = root;
// need a non-recusrive search alogorithm, because we have to
// not only find the target node, but it's parent as well
while (target == null && node != null){
if (key.compareTo(node.getKey()) < 0){
parent = node;
node = node.getLeftChild ();
}
else if (key.compareTo(node.getKey()) > 0){
parent = node;
node = node.getRightChild ();
}
else{
// ok, we've found the node we want to delete
target = node;
}
}
if (target == null) // target not found, nothing to delete
return;
// we need to find a replcement node to our target node
// in the tree.
AVLNode replacement = null;
// seek a replacement node if there are two children
if (target.getLeftChild() != null || target.getRightChild() != null){
replacement = getReplacementRecursive(target.getLeftChild(), target, target);
}
else{
// the replacement node is the node that exists
if (target.getLeftChild() != null)
replacement = target.getLeftChild();
else
replacement = target.getRightChild();
}
if (replacement != null){ // the replacement was a leaf node, so we can safely
// dock the target's children on to the replacement
replacement.setLeftChild(target.getLeftChild());
replacement.setRightChild(target.getRightChild());
updateHeight(replacement);
}
if (root == target){
root = replacement;
}
else{
if (parent.getLeftChild() == target)
parent.setLeftChild(replacement);
else
parent.setRightChild(replacement);
}
size--;
}
private AVLNode getReplacementRecursive(AVLNode node, AVLNode parent, AVLNode target){
if (node == null)
return parent;
AVLNode replacement = getReplacementRecursive(node.getRightChild(), node, target);
if (parent.getRightChild() == replacement){
parent.setRightChild(null);
if (parent.getLeftChild() == null && parent != target)
parent.setHeight(parent.getHeight() -1);
}
else{
updateHeight(parent);
}
return replacement;
}
private void updateHeight(AVLNode node){
int iLeftHeight = -1;
int iRightHeight = -1;
if (node.getLeftChild() != null)
iLeftHeight = node.getLeftChild().getHeight();
if (node.getRightChild() != null)
iRightHeight = node.getRightChild().getHeight();
node.setHeight(max(iLeftHeight, iRightHeight) + 1);
}
}
SpellChecker.java
The SpellChecker class is provided with a main() entry point to test AVLTree:
import java.io.*;
public class SpellChecker {
public static void main(String[] args) {
SpellChecker dict = new SpellChecker();
dict.loadDictionary("dictionary.txt");
String word = "test";
System.out.println(" Checking+ word + ""...");
String[] suggestions = dict.checkWord(word, 100);
for (String suggestion: suggestions) {
System.out.println(suggestion);
}
}
private AVLTree tree = null;
public boolean loadDictionary(String strFileName){
// open the file for reading
File fpFile = new File(strFileName);
if ((!fpFile.exists()) || (!fpFile.canRead()) || (fpFile.isDirectory()))
return false;
tree = new AVLTree();
FileReader fileReader = null;
BufferedReader bufferedReader = null;
boolean successful = false;
try {
// open the file fo reading
fileReader = new FileReader(strFileName);
// get the buffered reader "helper" class
bufferedReader = new BufferedReader(fileReader);
// get a line from the text file
String strNextLine;
String[] arrWords = null;
while ((strNextLine = bufferedReader.readLine()) != null){
arrWords = strNextLine.split(" ");
for (int i = 0; i < arrWords.length; i++)
// add the word to the dictionary
if (arrWords[i] != null && arrWords[i].length() > 0)
tree.insert(arrWords[i]);
}
}
catch(Exception e){
successful = false;
}
finally {
if (bufferedReader != null) {
try {
bufferedReader.close();
}
catch (Exception doNothing) {
}
}
bufferedReader = null;
fileReader = null;
}
return successful;
}
public boolean saveDictionary(String strFileName){
try {
// make sure if a file is there, delete it first
File fpFile = new File(strFileName);
if (fpFile.exists())
fpFile.delete();
// open a new file for writing
FileWriter fwFile = new FileWriter(strFileName);
BufferedWriter bwFile = new BufferedWriter(fwFile);
// do an inorder traversal (alphabetic order)
inorderRecurse(bwFile, tree.root());
// close the file
bwFile.close();
}
catch(Exception e) { // catch exceptions
return false;
}
return true;
}
private void inorderRecurse(BufferedWriter bwFile, AVLNode node){
if (node == null)
return;
inorderRecurse(bwFile, node.getLeftChild());
try{
bwFile.write(node.getKey().toString());
bwFile.newLine();
bwFile.flush();
}
catch (Exception e){
return;
}
inorderRecurse(bwFile, node.getRightChild());
}
public void add(String word){
if (word == null)
return;
if (tree == null){
tree = new AVLTree();
}
tree.insert(word);
}
public void remove(String word){
if (word == null || tree == null)
return;
tree.remove(word);
}
public String[] checkWord(String word, int limit){
if (word == null)
return null;
if (tree == null)
return new String[0];
return tree.getBestMatches(word, limit);
}
}
All these three classes can be compiled together to create the SpellChecker app.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.