Advertisements. FuzzyQuery is used to search documents using fuzzy implementation that is an approximate search based on the edit distance algorithm.
Fuzzy logic is an abstract concept that is completely independant of programming lanuages. The basic idea is that instead of boolean logic where any statement is either "true" or "false", you use a continuum where a statement can be anywhere between "100% true" and "0% true".
For example, if a user types "Misissippi" into Yahoo or Google -- both of which use fuzzy matching -- a list of hits is returned along with the question, "Did you mean Mississippi?" Alternative spellings and words that sound the same but are spelled differently are given.
A fuzzy search searches for text that matches a term closely instead of exactly. Fuzzy searches help you find relevant results even when the search terms are misspelled. To perform a fuzzy search, append a tilde (~) at the end of the search term.
Commons Lang has an implementation of Levenshtein distance.
Commons Codec has an implementation of soundex and metaphone.
If you are mostly comparing short strings and want something portable and lightweight you can use the well known python algorithm fuzzywuzzy ported to Java.
You can read more about it here
You can use Apache Lucene, but depending on the use case this may be too heavy weight. For very simple fuzzy searches it may be a bit complex to use and (correct me if I'm wrong) it requires you to build an index.
If you need a simple online (= not maintaining an index) algorithm you can use the fuzzy Bitap algorithm. I found an implementation in Java here. It's code fits in a single relatively short method with an almost self-explaining signature:
public static List<Integer> find(String doc, String pattern, int k)
Apache Commons StringUtils
has an implementation of the Levenshtein algorithm for fuzzy String matching. It can be seen as the fuzzy version of String.equals
, Bitap is like the fuzzy version of String.indexOf
and still uses the Levenshtein distance measure. It is generally more efficient than naively using Levenshtein to compare the search pattern with each substring that could possibly match.
Notes:
ArrayIndexOutOfBoundsException
on non-ASCII characters (>= 128) so you will have to filter these out.I tried using Bimap in an application to search an in-memory list of persons by name. I found that a Levenhstein distance of 2 gives way too many false positives. A Levenhstein distance of 1 works better, but it cannot detect a typo where you swap two letters, e.g. "William" and "Willaim". I can think of a few ways to solve this, e.g.
ArrayIndexOutOfBoundsException
If you are going to do 2 or 4, it may be better to use a proper full-text search library like Lucene anyway.
BitapOnlineSearcher
,
but requires you to use java.io.Reader
together with an Alphabet
class. It's Javadoc is written in Russian.SimMetrics is probably what you need: http://sourceforge.net/projects/simmetrics/
It has several algorithms for calculating various flavours of edit-distance.
Lucene is a very powerful full-text search engine, but FT search isn't exactly the same thing as fuzzy string matching (eg. given a list of strings find me the one that is most similar to some candidate string).
To Lucene I would add SOLR http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With