Add support for "fuzzy" Levenshtein distance matching

[jobergum]

We get a few questions on how to do fuzzy matching with Vespa. Current support for 'fuzzy' is through:

• Regular expressions, only exposed through YQL query syntax using 'matches' instead of 'contains' and only supported for string attribute fields
• n-gram matching with configurable gram size for indexed fields

It could seem like people by fuzzy means matching strings where the Levenshtein distance is below some run time threshold. (https://lucene.apache.org/core/7_1_0/core/org/apache/lucene/search/FuzzyQuery.html)

I think we should consider implementing a simple edit distance matcher, which matches a field if the distance is below some run time threshold.

field name type string {
  indexing: summary|attribute
  attribute:fast-search
}

Example query:

select * from sources * where name contains [{"distance":3}fuzzy("levenstein"); 

If there exist indexing techniques for speeding up evaluation we can consider adding a match setting with a configured max distance on the field setting as well.

[geirst]

Adding support for fuzzy matching is a rather comprehensive task as it involves changes in many parts of the code base. On a high level this is what needs to be done:

Overall:

• Decide on YQL syntax for fuzzy matching and semantics of the operator.
• Decide on a new query item (com.yahoo.prelude.query.Item.java) and serialisation format. The fuzzy matching feature has similarities with REGEX matching (https://docs.vespa.ai/en/reference/query-language-reference.html#matches) in how the search backend will handle it, so RegExpItem.java can be used as inspiration.

Java:

• Extend YQL parser.
• Implement new query item with serialisation.
• Add validator to ensure fuzzy matching is only used for string attribute fields.

C++:

• Extend search::ParseItem::ItemType.
• Integrate new item in search::SimpleQueryStackDumpIterator, search::query::StackDumpQueryCreator and search::query::QueryBuilder.
• Integrate new item in search::query::QueryVisitor and all implementations.
• Integrate new item in search::QueryTermSimple that is used by the attribute matching code.
• Implement an algorithm for Levenshtein distance calculation between two strings. Details regarding if this should be handled as UTF8 or UCS4 must be decided.
• Integrate the Levenshtein algorithm in the string attribute matching code. If the string attribute has fast-search this is handled by fuzzy matching the query term against all unique terms in the dictionary (similar to how regex matching is currently done) building a union posting list. If the string attribute doesn't have fast-search, brute force fuzzy matching is performed against the string value of all documents that are evaluated. This code path can also trigger in the fast-search case when the query tree consists of other limiting query terms. Various parts of the string matching code that must be extended: search::attribute::StringPostingSearchContext, search::SingleValueStringAttributeT::StringTemplSearchContext, search::StringSearchHelper, MultiValueStringAttributeT::StringTemplSearchContext.

[geirst]

Decision after architect meeting regarding YQL syntax:

• Create a new function (fuzzy) that is used together with contains (https://docs.vespa.ai/en/reference/query-language-reference.html#contains). The fuzzy function supports an optional annotation maxEdits that has default value (and max value) of 2. YQL example: select * from sources * where name contains ({"maxEdits":1}fuzzy("levenstein"))
• Create a new item class FuzzyItem that extends com.yahoo.prelude.query.TermItem, which is used when building the query tree when parsing the YQL query. This class will have similarities with RegExpItem.

[leiless]

Hi, @geirst. cc @bratseth, @alexeyche, @andreer.

I check the https://github.com/vespa-engine/vespa/pull/21689/files PR, but I haven't found the ranking result part. So I assume the text recall and ranking score are separated.

I try to implement fzf fuzzy match (Smith-Waterman) algorithm into vespa, like in form of SELECT foo FROM bar WHERE gee CONTAINS fzf("myterm"), yet I have no idea to deal with it. fzf fuzzy match algorithm combine recall & ranking together (since it's a standalone cli tool). But the vespa separates them, where I can attach the match positions and rank score?

(FYI, I have no previous knowledge of Vespa)

[jobergum]

This is complete and available https://docs.vespa.ai/en/reference/query-language-reference.html#fuzzy