Levenshtein transducers accept a query term and return all terms in a dictionary that are within n spelling errors away from it. They constitute a highly-efficient (space and time) class of spelling correctors that work very well when you do not require context while making suggestions. Forget about performing a linear scan over your dictionary to find all terms that are sufficiently-close to the user's query, using a quadratic implementation of the Levenshtein distance or Damerau-Levenshtein distance, these babies find all the terms from your dictionary in linear time on the length of the query term (not on the size of the dictionary, on the length of the query term).
If you need context, then take the candidates generated by the transducer as a starting place, and plug them into whatever model you're using for context (such as by selecting the sequence of terms that have the greatest probability of appearing together).
For a quick demonstration, please visit the Github Page, here.
The library is currently written in Java, CoffeeScript, and JavaScript, but I will be porting it to other languages, soon. If you have a specific language you would like to see it in, or package-management system you would like it deployed to, let me know.
When it comes to documentation, you have several options:
liblevenshtein has been developed against Java >= 1.8. It will not work with prior versions.
Add a dependency on com.github.dylon:liblevenshtein:2.1.2 to your project's build.gradle
:
// ...
dependencies {
compile 'com.github.dylon:liblevenshtein:2.1.2'
}
// ...
Add a dependency on com.github.dylon:liblevenshtein:2.1.2 to your project's POM:
<project>
<!-- ... -->
<dependencies>
<!-- ... -->
<dependency>
<groupId>com.github.dylon</groupId>
<artifactId>liblevenshtein</artifactId>
<version>2.1.2</version>
</dependency>
<!-- ... -->
</dependencies>
<!-- ... -->
</project>
You probably don't want this option unless you just want to dig through the source or help me with maintenance (yes, please!), but if you'd like to checkout the Git repo, clone it from GitHub:
$ git clone https://github.com/universal-automata/liblevenshtein-java.git
Cloning into 'liblevenshtein-java'...
remote: Counting objects: 1570, done.
remote: Compressing objects: 100% (23/23), done.
remote: Total 1570 (delta 4), reused 0 (delta 0), pack-reused 1541
Receiving objects: 100% (1570/1570), 245.49 KiB | 0 bytes/s, done.
Resolving deltas: 100% (664/664), done.
Checking connectivity... done.
Once you've checked out the library, use it:
package pkg.of.awesomeness;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import com.github.dylon.liblevenshtein.levenshtein.Algorithm;
import com.github.dylon.liblevenshtein.levenshtein.Candidate;
import com.github.dylon.liblevenshtein.levenshtein.ITransducer;
import com.github.dylon.liblevenshtein.levenshtein.factory.TransducerBuilder;
public class GetSpellingCandidates {
public static void main(final String... args) throws IOException {
int argsIdx = 0;
final String dictionaryPath = args[argsIdx ++];
final int maxDistance = Integer.parseInt(args[argsIdx ++]);
final Collection<String> dictionary = buildDictionary(dictionaryPath);
final ITransducer<Candidate> transducer = new TransducerBuilder()
.algorithm(Algorithm.TRANSPOSITION)
.defaultMaxDistance(maxDistance)
.dictionary(dictionary)
.build();
for (int i = argsIdx; i < args.length; ++i) {
final String queryTerm = args[i];
for (final Candidate candidate : transducer.transduce(queryTerm)) {
final String candidateTerm = candidate.term();
final int distance = candidate.distance();
System.out.printf("d(%s, %s) = %d%n", queryTerm, candidateTerm, distance);
}
}
}
private static Collection<String> buildDictionary(final String dictionaryPath)
throws IOException {
try (final Reader dictionaryReader = new FileReader(dictionaryPath);
final BufferedReader lineReader = new BufferedReader(dictionaryReader)) {
final List<String> dictionary = new ArrayList<>();
String line;
while (null != (line = lineReader.readLine())) {
dictionary.add(line);
}
return dictionary;
}
}
}
# Calls GetSpellingCandidates with the newline-delimited, dictionary of terms, a
# maximum distance of 2, and the following terms to find spelling candidates
# for: foo; bar; baz
java pkg.of.awesomeness.GetSpellingCandidates /path/to/dictionary.txt 2 foo bar baz
Please see the wiki for more details.
This library is based largely on the work of Stoyan Mihov, Klaus Schulz, and Petar Nikolaev Mitankin: "Fast String Correction with Levenshtein-Automata". For more details, please see the wiki.