12

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:

Community
  • 1
  • 1
TWiStErRob
  • 44,762
  • 26
  • 170
  • 254
  • There is not 1 way to implement fuzzy search. Your requirements are much too vague to come up with a proper answer. – wvdz Dec 19 '14 at 10:40
  • 1
    `*l*i*k*e*t*h*i*s*` ... but i do worry about efficiency of this solution – Selvin Dec 19 '14 at 10:41
  • @popovitsj User types anything and if it matches some part of the name it shows the result. – TWiStErRob Dec 19 '14 at 10:41
  • If it's that simple than @Selvin is right, but that's hardly useful. It will give a lot of 'unexpected' matches from the user's perspective. – wvdz Dec 19 '14 at 10:43
  • If that's a requirement you should edit it into your question. – wvdz Dec 19 '14 at 10:46
  • @popovitsj if you know a better strategy then please put it as an answer (without re-implementing FTS3 in Java), I'm open to anything that's better than case insensitive "prefix/contains" matching. – TWiStErRob Dec 19 '14 at 10:46
  • well, i think that there is no build-in rank function ... it is hard to add new functions to SQLite on android(the only way is to recompile - like sqlcipher) – Selvin Dec 19 '14 at 10:47
  • 1
    You can use sim metric for fuzzy search, useful for limited numbers of entry Link: http://sourceforge.net/projects/simmetrics/ – Karioki Dec 19 '14 at 11:14
  • Did you find a solution/answer to this? – theGreenCabbage Jul 14 '15 at 16:37
  • @theGreenCabbage see my new answer – TWiStErRob Jul 14 '15 at 17:14

2 Answers2

4

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

CL.
  • 173,858
  • 17
  • 217
  • 259
1

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.

TWiStErRob
  • 44,762
  • 26
  • 170
  • 254
  • Can you explain a bit what this does? – theGreenCabbage Jul 14 '15 at 17:17
  • @theGreenCabbage "search all word beginnings", `\\s+` regex means "any contiguous whitespace" so `ab cd ef` will become `ab*cd*ef*` and [see the docs what `*` means](https://sqlite.org/fts3.html#termprefix) – TWiStErRob Jul 14 '15 at 18:07
  • Thanks. I think that's what an article of a Python-implemented fuzzy search does. I'm using Laravel, and found I could simply use scope queries for this. If that doesn't work, I'll come back to your solution. THank you. – theGreenCabbage Jul 14 '15 at 18:08
  • 1
    I think * can only appear at the end of search term it can't appear in the middle – Mohammad Yahia Sep 20 '17 at 12:39
  • @MohammadYahia I know it works in the middle as well, I'm using this in my inventory app: `fixQuery("but saf") -> "but*saf*"` matches *"Random Buttons and Safety Pins"*. – TWiStErRob Sep 21 '17 at 13:54