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

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

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

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


android sqlite sql-order-by jaro-winkler
person Pentium10    schedule 17.05.2010    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Шаг 1. Выполните запрос без части ORDER BY.

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

person CommonsWare    schedule 17.05.2010
comment
Я делаю что-то подобное на Java, но при вычислении шагов N x M требуется так много времени, что скрипт работает 2-3 минуты для 300 x 500. - person Pentium10; 17.05.2010
comment
Я не понимаю, откуда берутся шаги N x M. Если вычисления на Java слишком медленные, используйте NDK. - person CommonsWare; 17.05.2010
comment
Я работаю над базой данных синхронизации людей, на одном конце есть N записей, на другом — M записей, я запускаю алгоритм расстояния Яро-Винклера для их имен, чтобы они соответствовали лучшему. - person Pentium10; 17.05.2010

arrow_upward
1
arrow_downward

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

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

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

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

person Ivan    schedule 31.05.2011