Написание алгоритма пост-поиска

Question

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

Я использую расстояние редактирования (Левенштейна) "e (x, y) = e", чтобы вычислить оценку для каждого сообщения по сравнению со словом запроса "x" и словом сообщения "y" согласно: x, y) = 2 ^ (2 - e) (1 - min (e, | x |) / | x |), где "| x |" количество букв в слове запроса.

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

Я неправильно подхожу к этой проблеме или есть способ нормализовать счет, о котором я не думал?

Answer 1

Да. Есть много методов нормализации, которые вы можете использовать. Это хорошо изученная область!

Взгляните на модель векторного пространства . TDF / IDF может иметь отношение к тому, что вы делаете. Это не строго связано с методом, который вы используете, но может привести к нормализации.

Также обратите внимание, что сравнение каждого сообщения будет O (N) и может быть очень медленным. Вместо строкового расстояния вы можете получить лучшие результаты с stemmming . Затем вы можете поместить это в инвертированный индекс VSM.

Многие базы данных (включая MySQL и Postgres) имеют полнотекстовый поиск. Это, вероятно, более практично, чем делать это самостоятельно.