Homophone.java

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;

import java.util.ArrayList;

public class Homophone {

public static void main(String[] args) {

UALDictionary PDict = new UALDictionary();

File file = new File("cmudict.0.7a.txt");

//File file = new File("shuffledDictionary.txt");

final int len = 5; // we start with words of length 5 characters

long start = System.currentTimeMillis();

try {

Scanner scanner = new Scanner(file);

while (scanner.hasNextLine()) {

String line = scanner.nextLine();

if (line.substring(0, 3).equals(";;;"))

continue; // skip comment lines

Pronunciation p = new Pronunciation(line);

if ((p.getWord().length()

|| (p.getWord().length() > len))

continue;

if ((p.getWord().length() == len - 1)

|| (p.getWord().length() == len))

PDict.insert(p.getWord(), p);

}

scanner.close();

} catch (FileNotFoundException e) {

e.printStackTrace();

}

long middle = System.currentTimeMillis();

System.out.println("Loaded dictionary.");

for (Pronunciation p : PDict.values()) {

String w = p.getWord();

if (w.length() == len) {

String w1 = w.substring(1); // word obtained by removing first letter

String w2 = w.substring(0, 1) + w.substring(2); // and removing second letter

Pronunciation p1 = PDict.find(w1);

Pronunciation p2 = PDict.find(w2);

if ((p1 != null)

&& (p2 != null)

&& (p.getPhonemes().equals(p1.getPhonemes()))

&& (p1.getPhonemes().equals(p2.getPhonemes()))) {

System.out.println("An answer is: " + w);

}

}

}

long end = System.currentTimeMillis();

System.out.println("Run times: load dictionary= " + (middle - start)

+ " process= " + (end - middle) + " total= " + (end - start));

}

}

Dictionary.java

public interface Dictionary {

public void clear();

public void insert(Key k, E e);

public E remove(Key k); // Null if none

public E removeAny(); // Null if none

public E find(Key k); // Null if none

public Iterable findAll(Key k);

public Iterable values();

public int size();

};

KVpair.java

/** Container class for a key-value pair */

class KVpair {

private Key k;

private E e;

/** Constructors */

KVpair() {

k = null;

e = null;

}

KVpair(Key kval, E eval) {

k = kval;

e = eval;

}

/** Data member access functions */

public Key key() {

return k;

}

public E value() {

return e;

}

}

OALDictionary.java

import java.util.ArrayList;

class OALDictionary implements Dictionary {

private static final int defaultSize = 10;

private ArrayList> list;

// Constructors

OALDictionary() {

this(defaultSize);

}

OALDictionary(int sz) {

list = new ArrayList>(sz);

}

public void clear() {

list.clear();

}

/** Insert an element: append to list */

public void insert(Key k, E e) {

KVpair temp = new KVpair(k, e);

int i = 0;

while ((i 0))

++i;

list.add(i, temp);

}

/** Remove element with key k, return element */

public E remove(Key k) {

E temp = find(k);

if (temp != null)

list.remove(new KVpair(k, temp));

return temp;

}

/** Remove any element */

public E removeAny() {

return list.remove(list.size()-1).value();

}

/**

* Find k using sequential search

*

* @return Record with key value k

*/

public E sfind(Key k) {

for (KVpair t : list)

if (k.compareTo(t.key()) == 0)

return t.value();

return null; // "k" does not appear in dictionary

}

/**

* Find k using binary search

*

* @return Record with key value k

*/

public E find(Key k) {

int low = 0;

int hi = list.size() - 1;

int mid = (low + hi) / 2;

while (low

if (k.compareTo(list.get(mid).key()) == 0)

return list.get(mid).value();

else if (k.compareTo(list.get(mid).key()) > 0)

low = mid+1;

else

hi = mid-1;

mid = (low + hi) / 2;

}

return null; // "k" does not appear in dictionary

}

/* findAll implementation using inefficient sequential search.

*

*/

public Iterable sfindAll(Key k) {

ArrayList al = new ArrayList();

for (KVpair t : list)

if (k.compareTo(t.key()) == 0)

al.add(t.value());

return al;

}

public Iterable findAll(Key k) {

ArrayList al = new ArrayList();

int fidx = -1;

int low = 0;

int hi = list.size() - 1;

int mid = (low + hi) / 2;

while ((low

if (k.compareTo(list.get(mid).key()) == 0)

fidx = mid;

else if (k.compareTo(list.get(mid).key()) > 0)

low = mid+1;

else

hi = mid-1;

mid = (low + hi) / 2;

}

if(fidx

int i = fidx;

for(i=fidx; i>=0;--i)

if(k.compareTo(list.get(i).key()) != 0)

break;

fidx = i+1; // the first instance of key k

for(i=fidx; i

{

if(k.compareTo(list.get(i).key()) == 0)

al.add(list.get(i).value());

else

break;

}

return al;

}

public int size() {

return list.size();

}

/** Returns an iterable collection of the dictionary. */

public Iterable values() {

ArrayList elements = new ArrayList(list.size());

for (KVpair t : list)

elements.add(t.value());

return elements;

}

}

Pronounciation.java

import java.util.LinkedList;

import java.util.Scanner;

public class Pronunciation {

private String word;

private String pronounce;

Pronunciation(String p) {

int i = p.indexOf(' ');

word = p.substring(0, i);

pronounce = p.substring(i+1);

}

public String getWord() {

return word;

}

public String getPhonemes() {

return pronounce;

}

public String toString() {

String s = word + " " + pronounce;

return s;

}

}

UALDictionary.java

import java.util.ArrayList;

import java.util.Collections;

class UALDictionary implements Dictionary {

private static final int defaultSize = 10;

private ArrayList> list;

// Constructors

UALDictionary() {

this(defaultSize);

}

UALDictionary(int sz) {

list = new ArrayList>(sz);

}

public void clear() {

list.clear();

}

/** Insert an element: append to list */

public void insert(Key k, E e) {

KVpair temp = new KVpair(k, e);

list.add(temp);

}

/** Remove element with key k, return element */

public E remove(Key k) {

E temp = find(k);

if (temp != null)

list.remove(new KVpair(k, temp));

return temp;

}

/** Remove any element */

public E removeAny() {

return list.remove(list.size()-1).value();

}

/**

* Find k using sequential search

*

* @return Record with key value k

*/

public E find(Key k) {

for (KVpair t : list)

if (k.compareTo(t.key())==0)

return t.value();

return null; // "k" does not appear in dictionary

}

public Iterable findAll(Key k) {

ArrayList al = new ArrayList();

for (KVpair t : list)

if (k.compareTo(t.key()) == 0)

al.add(t.value());

return al;

}

public int size(){

return list.size();

}

/** Returns an iterable collection of the dictionary. */

public Iterable values() {

ArrayList elements = new ArrayList(list.size());

for(KVpair t : list)

elements.add(t.value());

return elements;

}

}

Write a Java program that uses one of the implementations of the dictionary interface (UALDictionary or OALDictionary on Moodle) to find all words that are homophones of an input word. Use only UALDictionary and/or OALDictionary, and do not use data structures that we have not covered so far in the course The file "cmudict.0.7a.txt in the Dictionaries folder on Moodle contains a pro- nunciation dictionary downloaded from http://www.speech.cs.cmu.edu/cgi-bin/cmudict The page also contains a detailed description of the pronunciation dictionary ile consists of lines of the form ABUNDANT AHO B AH1 ND AHO N T The first string is the word, which is followed by one or more phonemes (or phones) that describe the pronunciation of the word. There are 39 phonemes occurring in North American English that are used in the dictionary. The collection of 39 sym- bols is known as the Arpabet, for the Advanced Research Projects Agency (ARPA), which developed it in the 1970's in connection with research on speech understand- ing The The Dictionaries directory on Moodle contains several files you can use. UALD- tionary.java is a class that implements the dictionary interface using an unordered array list. The array list stores (key, value) pairs as described in the class KV- pair.java. Pronunciation.java is a class that stores and manages access to a (word, phonemes) pair There is also a program Homophones.java that shows how you can read in the cmu dictionary (skipping comments and so on). You can modify that progranm so that when you read in a pronunciation entry you store it in an appropriate dictionary Call your program AllHomophones. The input is a single word, in al upper case The output is all words in the pronunciation dictionary that are homophones of the input word, including the input word, in alphabetical order. Both input and output should be all upper case since that is what the pronunciation dictionary uses For example, if the inout is LAX then the output should be: LAC'S LACKS LAX