Расчет релевантности прогнозируемого поиска на стороне клиента с несколькими параметрами

Я пишу прогнозирующий поиск, который для требований производительности сервера (все кэшируется) должен выполняться в браузере клиента. Это телешоу и фильмы, которые сопоставляются по названию, именам актеров и режиссеров. После выполнения поиска возвращается список совпавших элементов с двумя значениями для каждого результата:

1. Количество совпадающих слов (n): пользователь может ввести 4 слова, но только 2 из них соответствуют элементу. Чем больше, тем лучше.

2. Дополнение Levenshtein Edit Distance (ld). Пользователь может ввести 3 слова, но в 2 из них есть опечатка или другая небольшая разница с проиндексированными. Я использую расстояние редактирования, чтобы найти ближайшее проиндексированное слово. Добавление всех расстояний Левенштейна возвращается как индикатор близости. Чем меньше, тем лучше.

Требования

1. На стороне клиента. Никаких Sphinx, Lucene или любых других серверных решений.

2. Скорость важнее точности. Алгоритм запускается при каждом нажатии клавиши, и мы не хотим утомлять пользователя. Держите большой O не таким большим .

3. Нерекурсивным. Расчет релевантности каждого элемента не должен зависеть от расчета других элементов. Я не Я не хочу превзойти Google, только сначала предоставьте лучший результат из небольшого набора.

4. Ограниченная форма от 0 до 1, от 0 до 100 или что-то в этом роде. Не является обязательным, но возможность показать «процент релевантности» - это плюс.

5. Идеи важнее реализаций. Я ищу алгоритм / формулу лучше, чем для конкретной реализации.

Мой подход

На основе экспоненциального распада (например, разложения радиоактивного периода полураспада) я составил эту формулу.

Где:

• T - количество слов, предоставленных пользователем.
• n - количество совпадающих слов.
• ld - это сложение расстояния Левенштейна для этих совпадающих слов.

В псевдокод.

function lambda(n, ld) {
    lambda = (n/T) * e^(-ld * 1/n);
    return lambda;
}

Небольшое пояснение:

• -ld * 1 / n - это ядро ​​меры релевантности. Если ld низкий, а n большой, он приближается к нулю (сторона -0) и указывает на то, что этот результат более уместен.

• n / T - это коэффициент точности. Соответствующие слова против всех слов. Уточняет предыдущую релевантность, принимая во внимание общий ввод пользователя.

Экспоненциальная функция для отрицательных степеней ограничивает результат между 0 и 1.

И, наконец, вопрос

Я не хочу уточнить алгоритм поиска на основе этого ответа с дополнительным вычислением расстояния редактирования, но для улучшения сортировки возвращаемых элементов по релевантности путем присвоения значения релевантности каждому из них. Если требуется и легко вычисляется любой параметр, кроме n и ld . В своем решении я добавил T , количество слов, предоставленных пользователем.