In this assignment you will implement a spell checker. Using the randomized dict
ID: 3912830 • Letter: I
Question
In this assignment you will implement a spell checker. Using the randomized dictionary (random_dictionary.txt) given in the list of files, read in the dictionary (words in the random_dictionary.txt file) into an array of 26 MyLinkedList objects, one for each letter of the alphabet. Thus the first Linked List would contain only those words starting with letter 'a', while the last would contain only those words starting with the letter 'z'. Notice that all words are in lowercase. Then, when you read in the book (oliver.txt), you examine the first character of each word, and traverse one of the 26 Linked Lists. Each word read from the book should be searched in the corresponding Linked List. If it is not found, this word is either misspelled, or not in the dictionary, then count it as a word not found. If the word is found, count it as a word found. You will also need to count the number of string comparisons that are done during search. Maintain two counters for this, one is for the number of comparisons for words that were found in the dictionary, and the other is for the number of comparisons for words that were not found in the dictionary. At the end of the program, compute and display the average number of string comparisons for words that were found and the words that were not found. (ex: average number of comparisons for words found = number of words found / total number of comparisons for words found, compute the average comparisons for words not found similarly).
AVGCOMPSFOUND = COMPSFOUND / WDFOUND
AVGCOMPSNOTFOUND = COMPSNOTFOUND / WDNOTFOUND
You are required to use the string parser method that you used in your previous assignments.
You are allowed to implement any other methods you see necessary.
To create and array of 26 MyLinkedLists.
MyLinkedList [] dictionay = new MyLinkedList[26];
Once the array is instantiated, all elements are null. We need to instantiate 26 MyLinkedLists to store data.
for (int i = 0; i < dictionary.length; i++)
dictionary[i] = new MyLinkedList<String>();
To insert a word in to a specific MyLinkedList
Assume that the word you want to insert is in a String type variable called wordstr.
dictionary [(int)wordstr.charAt(0) - 97].addFront(wordstr) ;
would allow you to jump to the correct linked list. I think addFront is better since it doesn't need to traverse the list.
To search a word in a specific MyLinkedList
Assume that the word you want to search is in a String type variable called wordstr.
dictionary [(int)wordstr.charAt(0) - 97].contains(wordstr) ;
would allow you to jump to the correct linked list, and the contains will return true/false depending if the word is in the list or not.
Sample output
Unaltered Dictionary letters 'a' & 'i' added to front letters 'a' & 'i' added to end
Ave. comps (found) 3254.287703516023 3131.5190488161506 3412.6989713464845
Ave. comp (not found) 7416.628860759493 7346.24100762989 7346.24100762989
Time 2 min 46 seconds 2 min 11 seconds 2 min 28 seconds
Explanation / Answer
import java.io.*;
import java.util.Scanner;
public class SpellChecker
{
private MyLinkedList [] dictionary = new MyLinkedList [26];
private long notFoundWords;
private long wordsFoundComparison;
private long foundWords;
private long wordsNotFoundComparison;
private final int [] stringComparisons = new int[1];
//Default constructor of SpellChecker objects. Putting all counters at 0
public SpellChecker()
{
notFoundWords = 0;
wordsFoundComparison = 0;
foundWords = 0;
wordsNotFoundComparison = 0;
for (int i =0; i < dictionary.length; i++)
{
dictionary[i] = new MyLinkedList<String>();
}
}
public void readDictionaryFile()
{
File df = new File("random_dictionary.txt");
try{
Scanner input = new Scanner(df);
while (input.hasNext ()){
String word = (input.nextLine().toLowerCase());
dictionary [(int)word.charAt(0) - 97].addFirst(word);
}
input.close();
}
catch (Exception e)
{ // nothing to add to dictionary
e.printStackTrace();
}
}
public void spellCheck()
{
try
{
FileInputStream inf = new FileInputStream(new File("oliver.txt"));
char let;
String str=""; //word to be processed
int n = 0;
while ((n = inf.read()) != -1)
{
let = (char)n;
if (Character.isLetter(let))
{
str += Character.toLowerCase(let);
}
if ((Character.isWhitespace(let) || let =='-') && !str.isEmpty())
{
if(dictionary[(int)str.charAt(0)-97].contains(str, stringComparisons))
{
foundWords++;
wordsFoundComparison += stringComparisons[0];
}
else
{
notFoundWords++;
wordsNotFoundComparison += stringComparisons[0];
}
str="";
}
}
inf.close();
}
catch (IOException e){
e.printStackTrace();
}
}// end of spellCheck
public static void main(String[] args)
{
SpellChecker newChecker = new SpellChecker();
newChecker.readDictionaryFile();
newChecker.spellCheck();
System.out.println("Number of misspelled words: " + newChecker.notFoundWords);
System.out.println("Number of correct spelled words: " +
newChecker.foundWords);
System.out.println("Number of misspelled words comparisons: " +
newChecker.wordsNotFoundComparison);
System.out.println("Number of correct spelled words comparisons: " +
newChecker.wordsFoundComparison);
System.out.println("The average number of comparisons for words "
+ "found: " + newChecker.wordsFoundComparison/newChecker.foundWords);
System.out.println("The average number of comparisons for words not"
+ "found: " + newChecker.wordsNotFoundComparison/newChecker.notFoundWords);
}
}
---------------------------------------------------------------------------------------------------------------------------
public abstract class MyAbstractList<E> implements MyList<E> {
protected int size = 0;
// Create a default list
protected MyAbstractList() {
}
//Create a list from an array of objects
protected MyAbstractList(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}
//Add a new element at the end of this list
public void add(E e) {
add(size, e);
}
//Return true if this list contains no elements
public boolean isEmpty() {
return size == 0;
}
//Return the number of elements in this list
public int size() {
return size;
}
// Remove the first occurrence of the element o from this list.
public boolean remove(E e) {
if (indexOf(e) >= 0) {
remove(indexOf(e));
return true;
}
else
return false;
}
}
--------------------------------------------------------------------------------------------
public class MyLinkedList<E> extends MyAbstractList<E> {
private Node<E> head, tail;
public MyLinkedList() {
}
//Create a list from an array of objects
public MyLinkedList(E[] objects) {
super(objects);
}
//Return the head element in the list
public E getFirst() {
if (size == 0) {
return null;
} else {
return head.element;
}
}
// Return the last element in the list
public E getLast() {
if (size == 0) {
return null;
} else {
return tail.element;
}
}
// Add an element to the beginning of the list
public void addFirst(E e) {
Node<E> newNode = new Node<E>(e); // Create a new node
newNode.next = head; // link the new node with the head
head = newNode; // head points to the new node
size++; // Increase list size
if (tail == null) // the new node is the only node in list
{
tail = head;
}
}
// Add an element to the end of the list
public void addLast(E e) {
Node<E> newNode = new Node<E>(e); // Create a new for element e
if (tail == null) {
head = tail = newNode; // The new node is the only node in list
} else {
tail.next = newNode; // Link the new with the last node
tail = tail.next; // tail now points to the last node
}
size++; // Increase size
}
// Add a new element at the specified index in this list
public void add(int index, E e) {
if (index == 0) {
addFirst(e);
} else if (index >= size) {
addLast(e);
} else {
Node<E> current = head;
for (int i = 1; i < index; i++) {
current = current.next;
}
Node<E> temp = current.next;
current.next = new Node<E>(e);
(current.next).next = temp;
size++;
}
}
// Remove the head node and return the object that is contained in the removed node.
public E removeFirst() {
if (size == 0) {
return null;
} else {
Node<E> temp = head;
head = head.next;
size--;
if (head == null) {
tail = null;
}
return temp.element;
}
}
//Remove the last node and return the object that is contained in the removed node. */
public E removeLast() {
if (size == 0) {
return null;
} else if (size == 1) {
Node<E> temp = head;
head = tail = null;
size = 0;
return temp.element;
} else {
Node<E> current = head;
for (int i = 0; i < size - 2; i++) {
current = current.next;
}
Node<E> temp = tail;
tail = current;
tail.next = null;
size--;
return temp.element;
}
}
// Remove the element at the specified position in this list.
public E remove(int index) {
if (index < 0 || index >= size) {
return null;
} else if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
previous.next = current.next;
size--;
return current.element;
}
}
// Override toString() to return elements in the list
public String toString() {
StringBuilder result = new StringBuilder("[");
Node<E> current = head;
for (int i = 0; i < size; i++) {
result.append(current.element);
current = current.next;
if (current != null) {
result.append(", "); // Separate two elements with a comma
} else {
result.append("]"); // Insert the closing ] in the string
}
}
return result.toString();
}
public void clear() {
head = tail = null;
}
public boolean contains (E e)
{
Node<E> current = head;
for (int i = 0; i < size; i++)
{
if (current.element == e)
{
return true;
}
current = current.next;
}
return false;
}
public boolean contains(E e, int [] count){
Node <E> current = head;
for (int i =0; i < size; i++){
if (current.element.equals(e)){
count[0] = i + 1;
return true;
}
current = current.next;
}
count[0]=size;
return false;
}
public E get(int index)
{
if (index < 0 || index >= size)
{
return null;
}
else
{
Node<E> current = head;
for (int i = 0; i == index; i++)
{
current = current.next;
}
return current.element;
}
}
public int indexOf(E e)
{
Node <E> current = head;
for (int i = 0; i < size; i++)
{
if (current.element.equals(e))
{
return i;
}
current = current.next;
}
return -1;
}
public int lastIndexOf (E e)
{
Node <E> current = head;
int index = -1;
for (int i = 0; i< size; i++)
{
if (current.element.equals(e))
{
index = i;
}
current = current.next;
}
return index;
}
public E set(int index, E e){
if (index < 0 || index >= size)
{
return null;
}
else
{
Node <E> current = head;
for (int i = 0; i != index; i++)
{
current = current.next;
}
E word = current.element;
current.element = e;
return word;
}
}
private static class Node<E>
{
E element;
Node<E> next;
public Node(E element)
{
this.element = element;
}
}
}
------------------------------------------------------------------------------------
public interface MyList<E> {
public void add(E e);
public void add(int index, E e);
public void clear();
public boolean contains(E e);
public E get(int index);
public int indexOf(E e);
public boolean isEmpty();
public int lastIndexOf(E e);
public boolean remove(E e);
public E remove(int index);
public E set(int index, E e);
public int size();
}