// Create a spell checker that find all "misspelled" words (e.g. non-existing words). // Compare performance of the TST and Trie on various dictionary sizes.

// TODO: Create a Trie from the dictionary, and find all non-existing words in the input text file.

// TODO: Create a TST from the dictionary, and find all non-existing words in the input text file.

1 package algs52; // section 5.2 20 import java.util. HashSet; 3 import stdlib.*; 4 5 // Create a spell checker that find all "misspelled" words (e.g. non-existing words). 6 // Compare performance of the TST and Trie on various dictionary sizes. 7 8 // Download and install the following files into your algs4/data directory: 9 // - https://introcs.cs.princeton.edu/java/data/commonwords.txt 74K words 10 // - https://introcs.cs.princeton.edu/java/data/wordlist.txt 224K words 11 // - https://introcs.cs.princeton.edu/java/data/words.utf-8.txt 645K words 12 // 13 // Expected output should be similar in performance: 14 // 15 // Triest TST 16 // Words Time Words Time 17 // 23699 0.40 23699 0.18 43% 18 // 25913 0.53 25913 0.34 63% 19 // 18075 1.15 18075 0.86 74% 20 21 22 public class hw7 23 public 240 public static HashSet TrieFilter(String dictionary_file, String text_file) // TODO: Create a Trie from the dictionary, and find all non-existing words in the input text file. 28 HashSet filteredWords = new HashSet(); 29 return filteredWords; 30 31 320 public static HashSet TSTFilter(String dictionary_file, String text_file) 33 34 // TODO: Create a TST from the dictionary, and find all non-existing words in the input text file. 35 36 HashSet filteredWords = new HashSet(); 37 return filteredWords; 38 } 39 400 private static void runTest(String dictionary, String textfile) 41 { 42 Stopwatch stopwatch = new Stopwatch(); HashSet f1 = TrieFilter(dictionary, textfile); double t1 = stopwatch.elapsedTime(); 46 stopwatch = new Stopwatch(); 47 48 HashSet f2 = TSTFilter(dictionary, textfile); double t2 = stopwatch.elapsedTime(); 49 50 51 Stdout.printf("%100 %6.2f | %100 %6.2f $4d%% ", f1.size(), t1, f2.size(), t2, (int) (100* (t2/t1))); } 52 530 54 55 56 57 58 59 60 61 62 63 64 65 public static void main(String[] args) { String commonwords = "data/commonwords.txt"; String wordlist = "data/wordlist.txt"; String words - "data/words.utf-8.txt"; String textfile = "data/mobydick.txt"; Stdout.printf("%20s %165 ", "Triest | ", "TST"); Stdout.printf("%20s %20s ", "Words Time", "Words runTest (commonwords, textfile); runTest (wordlist, textfile); runTest (words, textfile); Time %"); 66 67 } 68