Ранжирование строк на основе строки поиска в линейное время

Question

У меня есть база данных SQLite, в которой хранится несколько сотен или тысяч строк, я храню массив этих строк, который растет, чтобы я мог быстрее выполнять поиск в своей базе данных. Однако пользователь может выполнять поиск по строке поиска, и я буду оценивать строки в моей базе данных по их близости к строке поиска. Например, скажем, они ищут "Foo". Если у меня есть записи «foo», «foobar» и «foo foo» в моей базе данных, есть ли у кого-нибудь идеи для алгоритма, который будет ранжировать эти строки по порядку:

1. "foo" (точное совпадение)

2. "foo foo" (дважды содержит строку поиска)

3. "foobar" (содержит строку поиска один раз)

Кто-нибудь знает или имеет какие-либо идеи относительно алгоритма, который привел бы к такому результату? Я работаю как на Java, так и на C ++, если кто-то хочет опубликовать какие-либо фрагменты кода, однако я просто ищу идеи для алгоритмов.

Заметьте, я бы хотел, чтобы что-то вроде fobar или fuo также отображалось в результатах поиска, так как это 1 буква от поиска,

Answer 1

Существуют разные стратегии и требования для установления рейтинга.

http://wiki.apache.org/solr/SolrRelevancyCookbook

http://lucene.apache.org/java/2_4_0/scoring.html#Algorithm

Кстати, Solr - это решение само по себе, я уверен, что вы уже знаете, что к этому времени :-)

Solr, Sunspot, SQlite и Rails

Answer 2

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

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

Примером может быть то, что вы говорите точносовпадения набирают 100 баллов, в то время как строка поиска n число раз достигает балла 10n, а при содержании ее в другом слове n раз получает 5n, и так далее.Если вы реализуете свои правила довольно оторванным образом, вы можете несколько раз настроить свои правила и посмотреть, насколько хорошо они работают в реальных поисках, пока вы не будете довольны точностью поиска.

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

(Как примечание, этот метод очень облегчил бы реализацию расширенных функций поиска, таких как AND / OR / NOT, потому что выможно разделить анализ по поисковым запросам и объединить их оценки по результатам)