Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Implement fuzzy search #100

Closed
vicb opened this issue Jan 31, 2014 · 13 comments
Closed

Implement fuzzy search #100

vicb opened this issue Jan 31, 2014 · 13 comments
Assignees
@jkozera
Labels
scope/docset-registry status/done type/feature
Milestone
0.4.0

Comments

@vicb
Copy link

vicb commented Jan 31, 2014

Devdocs.io has a feature called fuzzy search, for example "pmsg" would autocomplete to "window.postMessage".

I would like to see this implemented in Zeal.

Thanks for this project, really good !
@zoli
Copy link
Contributor

zoli commented Mar 4, 2014

I saw the code it seems that qsqlite doesn't support something like SOUNDEX does any one have idea about how implementing this feature

@zoli
Copy link
Contributor

zoli commented Mar 4, 2014

My first attempt is to build sqlite with soundex feature enabled and embed it in qt but this may cause some difficulties in other platforms

@vicb
Copy link
Author

vicb commented Mar 11, 2014

I didn't check the implementation before creating this ticket... might be harder than expected ?

@zoli
Copy link
Contributor

zoli commented Mar 12, 2014

It could be very easy if the sqlite had some features, I will try to implement sth close to fuzzy search with usual queries

@Kapeli
Copy link
Contributor

Kapeli commented Mar 14, 2014

Dash does fuzzy search by doing a LIKE %q%u%e%r%y%. SOUNDEX or similar would be nice to see in action, although I'm not sure how well they'd work with code-related naming.

@k3rni
Copy link

k3rni commented Oct 13, 2014

Currently trying to do that in Zeal by swapping sqlite's LIKE operator for one that does regex, and then transforming the pattern like above: from Foo to F.*?o.*?o.*?. However, this makes searching fairly slow (especially on the first letter, since there are many matches). Might try again with TRE, which should be better and faster.

@k3rni
Copy link

k3rni commented Oct 14, 2014

Tried and dumped TRE, moved to sqlite builtin sqlite3_strglob and it's somewhat faster. But the result list is now confusing - sorted alphabetically instead of by relevance.

result list

@trollixx trollixx changed the title [Feature] Implement fuzzy serach Implement fuzzy search Jan 9, 2015
@joaomsa joaomsa mentioned this issue Feb 23, 2015
Closed
@vicb vicb closed this as completed Jun 24, 2015
@trollixx
Copy link
Member

@vicb Why did you close this issue? It hasn't been implemented yet.

@trollixx trollixx reopened this Jun 25, 2015
@vicb
Copy link
Author

vicb commented Jun 26, 2015

because it has been opened 18 months ago and I think it was stall.
happy to learn this is still considered.

@klonos klonos mentioned this issue Jan 28, 2016
Closed
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
38c9d17 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
965ba42 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
581d1da 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
af18b1d 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
452d6b1 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
1897f22 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
2cfeb37 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
79ff445 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 7, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
f28ad96 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit that referenced this issue Oct 8, 2016
@jkozera
Better sorting of search results (#613, #100)
df47804 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR #281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 8, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
8a1862c 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 8, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
245eab1 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 8, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
6580cf7 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 8, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
afa7cd2 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 8, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
acea11a 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 9, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
f001b4b 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 9, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
47f62ab 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 9, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
f35c216 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 9, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
8d5570d 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 9, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
d239c15 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 9, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
78ced7b 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 9, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
7e0efb9 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 21, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
29baef1 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 21, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
19ea667 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
jkozera added a commit to jkozera/zeal that referenced this issue Oct 27, 2016
@jkozera
Better sorting of search results (zealdocs#613, zealdocs#100)
40d626d 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch
- should be faster than the one initially proposed in PR zealdocs#281.
@trollixx trollixx added this to the 0.4.0 milestone Oct 29, 2016
jkozera added a commit to jkozera/zeal that referenced this issue Oct 31, 2016
@jkozera
Better sorting of search results (zealdocs#603, zealdocs#100)
b8cb3b7 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch.

Also adds sqlite3_mutex_enter and sqlite3_mutex_leave calls to prevent
crashes inside sqlite3 which occurred while testing.
@vicb
Copy link
Author

vicb commented Oct 31, 2016

👍

@NicolasWebDev NicolasWebDev mentioned this issue Dec 30, 2016
Open
spike008t pushed a commit to spike008t/zeal that referenced this issue Jan 12, 2017
@jkozera @spike008t
Better sorting of search results and fuzzy search (zealdocs#614)
57bde0f 
Uses an O(m+n) algorithm based on https://github.com/bevacqua/fuzzysearch.

Also adds sqlite3_mutex_enter and sqlite3_mutex_leave calls to prevent
crashes inside sqlite3 which occurred while testing.

Fixes zealdocs#100.
Fixes zealdocs#603.
@trollixx trollixx mentioned this issue Oct 7, 2017
Closed
@jrappen
Copy link

jrappen commented Jan 9, 2018

Dropping a reference here to: https://github.com/forrestthewoods/lib_fts and the fuzzy_match there. Haven't done any performance comparisons.

@trollixx
Copy link
Member

trollixx commented Jan 13, 2018 •
edited
Loading

@jrappen Thanks, we know about the fts_fuzzy_match project. IIRC @jkozera had some concerns about potential performance if integrated in Zeal.

@lock
Copy link

lock bot commented Sep 16, 2018

This thread has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.

@lock lock bot locked and limited conversation to collaborators Sep 16, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees

@jkozera jkozera

Labels
scope/docset-registry status/done type/feature
Milestone
0.4.0
Development

No branches or pull requests
7 participants
@jkozera @k3rni @vicb @trollixx @Kapeli @zoli @jrappen