2
\$\begingroup\$

This program takes in a list of 275k or so words from '/usr/share/dict/words' and loads them into HashSet. It then takes in a list of 1000 words (taken from the dictionary and are scrambled (vowel replacements, additional characters added, etc) that are in some way misspelled. The program find the best guess and prints it out. I wrote this program twice, first with pure arrays and second displayed below. I'm attempting to speed up my first implementation, but the program below is actually slower. It seems to hang on certain word inputs.

To find 1000 words the program below took roughly 247.361 seconds.

The same program using only ArrayLists took 41.485 seconds.

Any suggestions on how I can speed it up? Removing for loops, cutting down array usage, etc.

The Program

import java.io.*;
import java.util.*;
import java.lang.*;
import java.nio.file.*;
import java.nio.file.Path;
import java.util.stream.Collectors;


public class SpellChecker {

    private static HashSet<String> dictionary = new HashSet<>();
    private static ArrayList<String> guessList = new ArrayList<>();
    private static List<String> vowelList = new ArrayList<>();
    //private static Set<String> removeCopies = new HashSet<>();
    private static Scanner u = new Scanner(System.in);

    public static void main(String[] args) {

        String usrInput;
        vowelList.add("a");
        vowelList.add("e");
        vowelList.add("i");
        vowelList.add("o");
        vowelList.add("u");

       // Path dictOpen = Paths.get("/Users/sam/IdeaProjects/wordSpell/src/newWords.txt");
        Path openDict = Paths.get("/usr/share/dict/words");
        try{
            //try opening file
            loadDictWords(openDict);
        } catch(Exception e) {
            System.out.println("Failed path");
        }

        try {
            u = new Scanner(new File("testing.txt"));
        } catch (FileNotFoundException e) {
            System.out.println("File not found.");
        }

        long startTime;
        long endTime;
        long duration;
        startTime = System.currentTimeMillis();
        try{
            while(true) {

                if (!u.hasNext()) {
                    break;
                }
                System.out.printf("> ");
                usrInput = u.next();
                System.out.println(checkForRepeatCharacters(usrInput.toLowerCase()));
                //System.out.println(bestResult(usrInput.toLowerCase()));
            }
        } catch(NoSuchElementException e) {
            System.out.println("Error - NoSuchElementException");
            e.printStackTrace();
        }

        endTime = System.currentTimeMillis();
        duration = (endTime - startTime);
        System.out.println("Running time in second: " + duration / 1000.0);

    }

    private static void loadDictWords(Path dictFile) throws Exception{
        dictionary = Files.lines(dictFile).map(String::toLowerCase).collect(Collectors.toCollection(HashSet::new));
    }

    private static void createVowelCombos(String word, int start, ArrayList<String> checkList) {
        StringBuilder sbAddWord = new StringBuilder(word);
        String[] splitWord = word.split("");

        if (start==splitWord.length) {
            checkList.add(word);
            return;
        }

        if (splitWord[start].matches(".*[aeiou]")) {
            for (int j = 0; j < 5; j++) {
                sbAddWord.setCharAt(start, vowelList.get(j).charAt(0));
                createVowelCombos(sbAddWord.toString(),start+1, checkList);
                //System.out.println(sbAddWord.toString());
            }
        }
        else
            createVowelCombos(sbAddWord.toString(),start+1, checkList);
    }

    private static String checkForRepeatCharacters(String word) {
        ArrayList<String> checkList = new ArrayList<>();
        String temp = word.replaceAll("(.)\\1{2,}", "$1$1");
        String temp2 = word.replaceAll("(.)\\1+", "$1");

       // checkList.clear();
        checkList.add(temp2);
        checkList.add(temp);

        int index = temp.length();
        // System.out.println(index);

        for (int i = 0; i < index; i++) {
            try{
                if(temp.charAt(i) == temp.charAt(i+1)) {
                    StringBuilder sb = new StringBuilder(temp);
                    checkList.add(temp);
                    sb.deleteCharAt(i);
                    temp = sb.toString();
                }
            } catch (Exception e) {
                //print.stackTrace(e);
            }
        }
/*
        removeCopies.addAll(guessList);
        guessList.clear();
        guessList.addAll(removeCopies);
        */

        createVowelCombos(word, 0, checkList);
        return bestResult(word, checkList);
    }

    private static String bestResult(String word, ArrayList<String> checkList) {
        ArrayList<String> dist = new ArrayList<>();
        String suggestion = "no suggestion";
        Map<Integer, String> wordAndDistanceMap = new HashMap<>();
/*
        removeCopies.addAll(guessList);
        guessList.clear();
        guessList.addAll(removeCopies);
        */

        for (String temp : checkList) {
            if(dictionary.contains(temp)) {
                dist.add(temp);
            }
        }

        if(dist.size() > 0) {
            dist.forEach(s -> wordAndDistanceMap.put(distance(s, word), s));
            suggestion =  wordAndDistanceMap.get(Collections.min(wordAndDistanceMap.keySet()));
        }

       // System.out.println(guessList.size());
        //System.out.println(dist.size());
        return suggestion;
    }

    /*
     *  Levenshtein distance algorithm as presented on wikipedia
     *  Calculates the shortest distance between two Strings by looking at the min number
     *  of insertions, deletions, and substitutions
     */
    private static int distance(String a, String b) {
        a = a.toLowerCase();
        b = b.toLowerCase();

        int [] costs = new int [b.length() + 1];
        for (int j = 0; j < costs.length; j++)
            costs[j] = j;
        for (int i = 1; i <= a.length(); i++) {
            costs[0] = i;
            int nw = i - 1;
            for (int j = 1; j <= b.length(); j++) {
                int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]), a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
                nw = costs[j];
                costs[j] = cj;
            }
        }
        return costs[b.length()];
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.