0

I am working on this spellchecker and one of the methods I use to suggest corrections to the user is inserting multiple characters into the word. This allows for words like exmpl to be corrected to example Here's the actual code:

public static Set<String> multiInsert(String word, int startIndex) {
    Set<String> result = new HashSet<>();

    //List of characters to insert
    String correction = "azertyuiopqsdfghjklmwxcvbnùûüéèçàêë";

    for (int i = startIndex; i <= word.length(); i++) {
        for (int j = i + 1; j <= word.length(); j++) {
            for (int k = 0; k < correction.length(); k++) {
                String newWord = word.substring(0, j) + correction.charAt(k) + word.substring(j);

                result.addAll(multiInsert(newWord, startIndex + 2));

                if(dico.contains(newWord)) result.add(newWord);
            }
        }
    }

    return result;
}

The problem with this function is that it takes A LOT of time to process especially when the word is long or when I have too many words to correct. Is there any better way to implement this function or optimize it?

vbtheory
  • 373
  • 3
  • 17
  • I suggest looking more in optimization and algorithms for example this is a great guide for beginners into [big o notation](https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/). Basically, every cycle you add will make an algorithm more difficult and with each recursion step going through 3 different for-loops will take A LOT time. So i'll suggest on re-coding your own algorithm (make it simpler) or searching for already created algorithm. – Banana Dec 05 '15 at 14:26

2 Answers2

2

What's making it slow is you're testing for strings that are not in the dictionary. There are lots more possible misspellings than there are words in the dictionary. You need to be guided by the dictionary.

This is the general spelling correction problem. I've programmed it several times.

In a nutshell, the method is to store the dictionary as a trie, and do bounded depth-first walk of the trie. At each step, you keep track of the distance between the word in the trie and the original word. Whenever that distance exceeds the bound, you prune the search.

So you do it in cycles, increasing the bound each time. First you do it with a bound of 0, so it will only find an exact match. That is equivalent to ordinary trie search. If that did not yield a match, do the walk again with a bound of 1. That will find all dictionary words that are distance 1 from the original word. If that didn't yield any, increase the bound to 2, and so on. (What constitutes an increment of distance is any transformation you choose, like insertion, deletion, replacement, or more general re-writings.)

The performance is bounded by the true distance times the dictionary size. Short of that, it is exponential in the true distance. Since each walk costs a factor times the previous walk, the time is dominated by the final walk, so the prior walks do not add much time.

There is an advantage to organizing the dictionary as a trie, since a trie is just a particular form of Finite State Machine. You can add sub-machines to it to handle common prefixes and suffixes, without massively expanding the dictionary. Consider these words: nation, national, nationalism, nationalistic, nationalistical, nationalisticalism, ... Such words may not be common, but they are not impossible. A suffix trie handles them easily. Similarly prefixes like pre-, post-, un-, de-, in-, etc.

Community
  • 1
  • 1
Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135
0

You can have a look at Jazzy which is a Java spellchecker API.

You might also want to consider Fuzzy String Matching.

StephenG - Help Ukraine
  • 959
  • 6
  • 12
  • You see this is a school project and the goal is to make the spell checker from scratch so I can't use Jazzy, however from the question you linked, I'll look into the levenshtein fuzzy matching method – vbtheory Dec 05 '15 at 15:03
  • Here's a possibly useful question on [efficient distance calculation] (http://stackoverflow.com/questions/3183149/most-efficient-way-to-calculate-levenshtein-distance#3183199) – StephenG - Help Ukraine Dec 05 '15 at 15:09