Lucene query: bla~* (match words that start with something fuzzy), how?

Question

In the Lucene query syntax I'd like to combine * and ~ in a valid query similar to: bla~* //invalid query

Meaning: Please match words that begin with "bla" or something similar to "bla".

Answer 1

I do not believe Lucene supports anything like this, nor do I believe it has a trivial solution.

"Fuzzy" searches do not operate on a fixed number of characters. bla~ may for example match blah and so it must consider the entire term.

What you could do is implement a query expansion algorithm that took the query bla~* and converted it into a series of OR queries

bla* OR blb* OR blc OR .... etc.

But that is really only viable if the string is very short or if you can narrow the expansion based on some rules.

Alternatively if the length of the prefix is fixed you could add a field with the substrings and perform the fuzzy search on that. That would give you what you want, but will only work if your use case is sufficiently narrow.

You don't specify exactly why you need this, perhaps doing so will elicit other solutions.

One scenario I can think of is dealing with different form of words. E.g. finding car and cars.

This is easy in English as there are word stemmers available. In other languages it can be quite difficult to implement word stemmers, if not impossible.

In this scenario you can however (assuming you have access to a good dictionary) look up the search term and expand the search programmatically to search for all forms of the word.

E.g. a search for cars is translated into car OR cars. This has been applied successfully for my language in at least one search engine, but is obviously non-trivial to implement.

Answer 2

You mean you wish to combine a wildcard and fuzzy query? You could use a boolean query with an OR condition to combine, for example:

BooleanQuery bq = new BooleanQuery();

Query q1 = //here goes your wildcard query
bq.Add(q1, BooleanClause...)

Query q2 = //here goes your fuzzy query
bq.Add(q2, BooleanClause...)

Answer 3

Hi Kris,

It's for an address search service, where I want to suggest addresses based on partially typed and possibly mistyped streetnames/citynames/etc (any combination). (think ajax, users typing partial street addresses in a text field)

For this case the suggested query expansion is perhaps not so feasible, as the partial string (street address) may become longer than "short" :)

Normalization

One possibility I can think of is to use string "normalization", instead of fuzzy searches, and simply combine that with wildcard queries. A street address of

"miklabraut 42, 101 reykjavík", would become "miklabrat 42 101 rekavik" when normalized.

So, building index like this:

1) build the index with records containing "normalized" versions of street names, city names etc, with one street address per document (1 or several fields).

And search the index like this:

2) Normalize inputstrings (e.g. mikl reyk) used to form the queries (i.e. mik rek). 3) use the wildcard op to perform the search (i.e. mik* AND rek*), leaving the fuzzy part out.

That would fly, provided the normalization algorithm is good enough :)

Answer 4

Hello, in the development trunk of lucene (not yet a release), there is code to support use cases like this, via AutomatonQuery. Warning: the APIs might/will change before its released, but it gives you the idea.

Here is an example for your case:

// a term representative of the query, containing the field. 
// the term text is not so important and only used for toString() and such
Term term = new Term("yourfield", "bla~*");

// builds a DFA that accepts all strings within an edit distance of 2 from "bla"
Automaton fuzzy = new LevenshteinAutomata("bla").toAutomaton(2);

// concatenate this DFA with another DFA equivalent to the "*" operator
Automaton fuzzyPrefix = BasicOperations.concatenate(fuzzy, BasicAutomata.makeAnyString());

// build a query, search with it to get results.
AutomatonQuery query = new AutomatonQuery(term, fuzzyPrefix);