ML 107D07 d 412 Due 42 Project3-Fun with Spell Checkers pd-Adobe Aerobat Pro Dc
ID: 3828584 • Letter: M
Question
ML 107D07 d 412 Due 42 Project3-Fun with Spell Checkers pd-Adobe Aerobat Pro Dc View Window Help Tools Document 8 Q 1 4 In this project you will implement and explore the performance of different kinds of spell checkers. Ihave provided a text file containing about 110.000 English words on eCourseware for you to use. You can assume that all words contain only lower-case letters. Approach 1: Binary Search Tree One easy way of implementing a spell checker is to use a binary search tree. Given a list of valid words, you can insert them into a BST. Checking whether a word is spelled comectly simply involves searching the tree for that word. If the word is found, great-if not, it must be misspelled! Remember that finding items in a BST takes olog n) tine on average, where n is the number of elements in the tree. Thus, the expected time cost of using this spell checker depends on the number of words that it's storing. Binary SearchTree String to store its word list. You can use the BinarySearchTree CE code that we wrote in lecture. BSTSpellChecker should contain the following methods: a. void add(String s) Adds the specified word to the tree. b. an contains(String s) Retums whether the specified word is in the tree. c. A method that reads a list of words from a file and adds them all into the tree. Add the words to the tree in the same order that they appear in the file alphabetically). (Note you will probably have to use (ie..al non-recursive versions of the BST add and find methods to prevent stack overflows here!) d. Remember that adding things in order into a BST is a bad idea this will result in a linked list with o()Explanation / Answer
Due to time constraints : i implemented bstspellchecker and trie spell checker below : Please comment for queries
BSTSpellChecker
package Chegg;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class BSTSpellChecker {
class BST<T extends Comparable<? super T>> {
BST<String> bst;
public class BinaryNode {
// Local variables
public T element; // The data in the node
BinaryNode left; // Pointer to the left child
BinaryNode right; // Pointer to the right child
/**
* This constructor initializes a childless binary node.
*
* @param elem
* Any generic object that implements Comparable
* @post A childless binary node is initialized
*/
public BinaryNode(T elem) {
element = elem;
left = null;
right = null;
}
/**
* This constructor initializes a binary node with children.
*
* @param elem
* Any generic object that implements Comparable
* @param lt
* The left node to which this node points
* @param rt
* The right node to which this node points
* @post A binary node with two children is initialized
*/
public BinaryNode(T elem, BinaryNode lt, BinaryNode rt) {
element = elem;
left = lt;
right = rt;
}
}
// Local variables
public BinaryNode root; // Pointer to root node, if present
/**
* This constructor initializes an empty BST. An empty BST contains no
* nodes.
*
* @post An empty tree is initialized
*/
public BST() {
root = null;
}
/**
* This method determines if the BST is empty.
*
* @return Returns true if the BST contains no nodes
*/
public boolean isEmpty() {
return (root == null);
}
/**
* This method attempts to find an element in the BST.
*
* @param elem
* The element to find
* @return true if element is found or false
*/
public boolean find(T elem) {
BinaryNode found = find(root, elem);
return (found == null) ? false : true;
}
/**
* This method attempts to find an element in the BST.
*
* @param start
* The node from which to start the search
* @param elem
* The element to find
* @return Returns a pointer to the matching data element or null if no
* matching element exists in the BST
*/
public BinaryNode find(BinaryNode start, T elem) {
// If the element isn't found, return null
if (start == null) {
return null;
}
// Compare the current node's element to the element we're looking
// for
int comparison = start.element.compareTo(elem);
// If we should look down the left tree
if (comparison > 0) {
return find(start.left, elem);
}
// If we should look down the right tree
else if (comparison < 0) {
return find(start.right, elem);
}
// If we've found it
else {
return start;
}
}
/**
* This method inserts an element into the BST, unless it is already
* stored.
*
* @param elem
* The element to insert into the BST
* @return void
* @post The element will be inserted into the BST
*/
public void insert(T elem) {
insert(root, elem);
}
/**
* This method inserts an element into the BST, unless it is already
* stored.
*
* @param start
* The node from which to start the insertion
* @param elem
* The element to insert into the BST
* @return Returns true if the insertion is performed and false
* otherwise
*/
public boolean insert(BinaryNode start, T elem) {
// We've reached the point of insertion
if (start == null) {
// Insert our element into a new node
root = new BinaryNode(elem, null, null);
return true;
}
// Compare the current node's element to the element we're looking
// to
// delete
int comparison = start.element.compareTo(elem);
// If are insertion will happen somewhere down the left tree
if (comparison > 0) {
// If we've reached the point of insertion
if (start.left == null) {
// Insert our element into a new node
start.left = new BinaryNode(elem, null, null);
return true;
}
// Otherwise, keep traversing until we reach the point of
// insertion
return insert(start.left, elem);
}
// If are insertion will happen somewhere down the right tree
else if (comparison < 0) {
// If we've reached the point of insertion
if (start.right == null) {
// Insert our element into a new node
start.right = new BinaryNode(elem, null, null);
return true;
}
// Otherwise, keep traversing until we reach the point of
// insertion
return insert(start.right, elem);
}
// If the element is already in the tree
else {
// Don't insert the element
return false;
}
}
/**
* Add method to add strings to bst
*
* @param s
*/
void add(String s) {
bst.add(s);
}
/**
* method to check if word is present in tree or not
*
* @param s
* @return
*/
private boolean contains(String s) {
return bst.find(s);
}
/**
* Reads list of words from file into a set
* @throws FileNotFoundException
*/
private void readFile() throws FileNotFoundException {
Scanner fileScanner = new Scanner(new File("File.txt")).useDelimiter("[.,:;()?!" ]+~\s");
Set<String> words = new HashSet<String>();
while ((fileScanner.hasNext())) {
words.add(fileScanner.next());
}
fileScanner.close();
}
private void addToTree(Set<String> words) {
for (Iterator<String> it = words.iterator(); it.hasNext();) {
String f = it.next();
bst.add(f);
}
}
private void addToTreeModified(Set<String> words) {
List<String> list = (List) Arrays.asList(words);
String middleWord = list.get(list.size() / 2);
bst.add(middleWord);
List<String> leftList = list.subList(0, (list.size() / 2) - 1);
List<String> rightList = list.subList((list.size() / 2) + 1, list.size() - 1);
Set<String> leftWords = new HashSet<String>(leftList);
Set<String> rightWords = new HashSet<String>(rightList);
addToTreeModified(leftWords);
addToTreeModified(rightWords);
}
private Set<String> closeMatches(Set<String> words, String s) {
return null;
}
}
public static void main(String[] args) {
BSTSpellChecker bstSpellChecker = new BSTSpellChecker();
}
}
TrieSPellChecker
package Chegg;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class TrieSpellChecker {
public class TrieNode {
private TrieNode parent;
private TrieNode[] children;
private boolean isLeaf; // Quick way to check if any children exist
private boolean isWord; // Does this node represent the last character
// of a word
private char character; // The character this node represents
/**
* Constructor for top level root node.
*/
public TrieNode() {
children = new TrieNode[26];
isLeaf = true;
isWord = false;
}
/**
* Constructor for child node.
*/
public TrieNode(char character) {
this();
this.character = character;
}
/**
* Adds a word to this node. This method is called recursively and adds
* child nodes for each successive letter in the word, therefore
* recursive calls will be made with partial words.
*
* @param word
* the word to add
*/
protected void addWord(String word) {
isLeaf = false;
int charPos = word.charAt(0) - 'a';
if (children[charPos] == null) {
children[charPos] = new TrieNode(word.charAt(0));
children[charPos].parent = this;
}
if (word.length() > 1) {
children[charPos].addWord(word.substring(1));
} else {
children[charPos].isWord = true;
}
}
/**
* Returns the child TrieNode representing the given char, or null if no
* node exists.
*
* @param c
* @return
*/
protected TrieNode getNode(char c) {
return children[c - 'a'];
}
/**
* Returns a List of String objects which are lower in the hierarchy
* that this node.
*
* @return
*/
protected List getWords() {
// Create a list to return
List list = new ArrayList();
// If this node represents a word, add it
if (isWord) {
list.add(toString());
}
// If any children
if (!isLeaf) {
// Add any words belonging to any children
for (int i = 0; i < children.length; i++) {
if (children[i] != null) {
list.addAll(Arrays.asList(children));
}
}
}
return list;
}
/**
*
* Gets the String that this node represents.
*
* For example, if this node represents the character t, whose parent
*
* represents the charater a, whose parent represents the character
*
* c, then the String would be "cat".
*
* @return
*
*/
public String toString()
{
if (parent == null)
{
return "";
}
else
{
return parent.toString() + new String(new char[] { character });
}
}
}
public class Trie {
private TrieNode root;
/**
* Constructor
*/
public Trie() {
root = new TrieNode();
}
/**
* Adds a word to the Trie
*
* @param word
*/
public void addWord(String word) {
root.addWord(word.toLowerCase());
}
/**
* Get the words in the Trie with the given prefix
*
* @param prefix
* @return a List containing String objects containing the words in the
* Trie with the given prefix.
*/
public List getWords(String prefix) {
// Find the node which represents the last letter of the prefix
TrieNode lastNode = root;
for (int i = 0; i < prefix.length(); i++) {
lastNode = lastNode.getNode(prefix.charAt(i));
// If no node matches, then no words exist, return empty list
if (lastNode == null)
return new ArrayList();
}
// Return the words which eminate from the last node
return lastNode.getWords();
}
}
private Trie trie;
/**
* Add method to add strings to bst
*
* @param s
*/
void add(String s) {
trie.addWord(s);
}
/**
* method to check if word is present in tree or not
*
* @param s
* @return
*/
private boolean contains(String s) {
return trie.getWords(s) != null;
}
private void readFile() throws FileNotFoundException {
Scanner fileScanner = new Scanner(new File("File.txt")).useDelimiter("[.,:;()?!" ]+~\s");
Set<String> words = new HashSet<String>();
while ((fileScanner.hasNext())) {
words.add(fileScanner.next());
}
fileScanner.close();
}
private void addToTree(Set<String> words) {
for (Iterator<String> it = words.iterator(); it.hasNext();) {
String f = it.next();
trie.addWord(f);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.