Делать заказ с помощью алгоритма расстояния Яро-Винклера?

Question

Мне интересно, как бы я мог выполнить заказ SQLite таким образом

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

Я знаю, что в Android есть узкое место с пользовательскими функциями, у меня есть альтернатива?

Answer 1

Предварительно вычислите длины строк и добавьте их в отдельный столбец. Затем сортируйте таблицу по этой длине. Добавьте индексы (если можете). Затем добавьте дополнительные фильтры, например, вы не хотите сравнивать «Шривастава Брахмапутра» с «Джоном Смитом». Длина слишком велика, поэтому исключите такие сравнения по длине в процентах от общей длины. Поэтому, если ваше слово состоит из 10 символов, сравните его только со словами с 10 + -2 или 10 + -3 символами.

Таким образом вы значительно сократите количество раз, которое необходимо запустить этому алгоритму.

Как правило, в словарном запасе из 100 000 записей такие фильтры уменьшают количество сравнений примерно до 300. Если вы не выполняете полноценную связь с записями, а затем я задаюсь вопросом, зачем использовать для этого Android. Вам все равно придется применять вероятностные методы для этого и подсчитывать баллы, а для Android это не работа (по крайней мере, пока).

Также в MS SQL Server расстояние строк в Jaro Winkler, заключенное в функцию CLR, работает намного лучше, поскольку SQL Server не поддерживает исходные массивы и большая часть обработки выполняется вокруг массивов. Таким образом, реализация в T-SQL добавляет слишком много накладных расходов, но SQL-CLR работает очень быстро.

Answer 2

Шаг # 1: Выполнить запрос за вычетом ORDER BY порции

Шаг # 2: Создайте CursorWrapper, который обернет ваш Cursor, вычислит расстояние Яро-Винклера для каждой позиции, отсортирует позиции, затем использует отсортированные позиции при переопределении всех методов, которые требуют позицию (например, moveToPosition(), moveToNext()).