How to implement fuzzy search with SQLite's FTS3?

Question

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

Answer 1

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.)

Answer 2

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.