Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to implement fuzzy search with SQLite's FTS3?

I have already integrated search based on the official Android documentation and I'm using the following SQLite schema and query:

CREATE VIRTUAL TABLE Search USING FTS3 (
    _id,
    name,
    location
);

select * from Search where name MATCH ?
-- where ? is the user typed exact "query"
-- or if it doesn't have spaces or stars I append a star to search prefix: "query*"

I'm wondering how can I extend it? to allow the following:

Say I have some items named:

  • My Fancy Item
  • My Secret Item
  • Item #1
  • Your Fancy Item

When the user types blah in the search box the search results would show:

  • my
    • My Fancy Item
    • My Secret Item
  • mfi
    • My Fancy Item
  • fan item, fanit, fit
    • My Fancy Item
    • Your Fancy Item
  • it, item, im, itm
    • My Fancy Item
    • My Secret Item
    • Item #1
    • Your Fancy Item

The results should be ranked based on how good the match is, for example if the letters are farther away they should rank lower than an exact match, like for mfi: "My Fancy Item" should rank last and "MFI thingy" should rank first (if there was such an item).

Note: my min SDK is API level 10, which means it has to work SQLite 3.6.22.

Similar functionality can be found mostly in IDEs:

  • Eclipse: Open Type and Open Resource
  • IntelliJ IDEA Navigate to *
  • Sublime Text Go to anything
like image 413
TWiStErRob Avatar asked Dec 19 '14 10:12

TWiStErRob


People also ask

What is FTS in SQLite?

Sqlite’s FTS module creates a virtual table. Think of it as a normal table in a database but on steroids i.e. powered with a blazing fast text search capabilities. You can’t specify the column types (like schema), every column would be mapped as a text (string) column.

How to use full-text search in SQLite?

To use full-text search in SQLite, you use FTS5 virtual table module. The following CREATE VIRTUAL TABLE statement creates an FTS5 table with two columns:

What is fuzzy search&how to implement?

What is Fuzzy Search & how to implement Fuzzy Search Technique for a Report Program using AMDP Class ? What is Fuzzy Search ? A technique of finding the strings that match a pattern approximately (rather than exactly).

What is the use of auxilary functions in SQLite?

Following queries would demonstrate the use of available auxilary functions in sqlite. highlight as the name suggest is useful to highlight the selected text using given values. snippet is used to extract the given search query from the text. Below, we extract upto three words around the search query.


2 Answers

SQLite's FTS allows searches only for entire words, or for word prefixes.

There is no built-in functionality for fuzzy searches like this. (And the Android database API does not allow you to add custom virtual table implementations.)

like image 169
CL. Avatar answered Oct 16 '22 19:10

CL.


I went with relaxing my criteria to search all word beginnings:

private static String fixQuery(String query) {
    return query.trim().replaceAll("\\s+", "*") + "*";
}

it works pretty well. Not typo-resistant, but it feels natural when I'm using it.

like image 1
TWiStErRob Avatar answered Oct 16 '22 21:10

TWiStErRob