Have Geek Brain

Order fulfillment using Jaro-Winkler distance algorithm?

I am wondering how I could execute a SQLite order this way

select * from contacts order by jarowinkler(contacts.name,'john smith');

I know Android has a bottleneck with user defined functions, do I have an alternative?

+2


a source to share


2 answers


Step # 1: execute the request minus ORDER BY

part



Step # 2: Create CursorWrapper

one that wraps yours Cursor

, calculates the Jaro-Winkler distance for each position, sorts the positions, then uses the sorted positions when overriding all methods requiring position (e.g. moveToPosition()

, moveToNext()

).

+1


a source


Pre-calculate the length of the lines and add them to a separate column. Then sort the table with that length. Add indices (if you can). Then add additional filters, for example you don't want to compare "Srivastava Brahmaputra" with "John Smith". The length is too distorted, so exclude such comparison in length as a percentage of the total length. So if your word is 10 characters long, only compare it to words with 10 + -2 or 10 + -3 characters.

This way you will significantly reduce the number of times this algorithm has to run.



Typically, in a vocal descent of 100,000 recordings, such filters reduce the number of comparisons to around 300. If you are not doing a full rearrangement of the recordings, then I wonder why use Android for this. You will still have to apply probabilistic methods for this and calculate the scores, and this is not a job for Android (at least not right now).

Also in MS SQL Server the Jaro Winkler string length wrapped in a CLR function performs much better as SQL Server does not support arays natively and most of the processing is around arrays. Thus, the T-SQL implementation adds too much overhead, but the SQL-CLR is very fast.

+1


a source






More articles:


All Articles