リニア時間での検索文字列に基づくランキング文字列

Question

私は数百または数千の文字列を格納するSQLiteデータベースを使用しています。しかし、ユーザーは検索文字列で検索することができ、私は検索文字列との親密性のためにデータベース内の文字列をランク付けします。たとえば、「foo」を検索するとします。私のデータベースに "foo" "foobar"と "foo foo"というエントリがある場合、誰でも次の文字列を順番に並べるアルゴリズムのアイディアはありますか？

1. "foo" ）

2.「FOO fooの」（それが二回検索文字列が含まれています）

3.「foobarには、」（それが一度検索文字列が含まれています）

誰のための任意のアイデアを知っているか持っていますこの結果を持つアルゴリズムですか？誰かがコードスニペットを投稿したいのであれば、私はJavaとC++の両方で作業していますが、実際にはアルゴリズムのアイデアを探しています。それは1通の手紙オフ検索からであるので、あなたは順位が線形時間でなりたいと言うとき

注、私は、私も、検索結果に表示する

Answer 1

をfobarやFUOのような何かをしたいと思いますあなたは一度セット内の各文字列を一度分析したいと思います。

あなたが定義するいくつかのルールに基づいて得点を計算するのが比較的簡単な方法です。もちろん、ルールが長くなるほど時間がかかりますが、分析をうまく実装する限り、何千もの文字列でも時間がかかるはずはありません。

例では、正確な一致が100のスコアを獲得し、n回の検索文字列を含むと10nのスコアを達成し、別の単語のn回に5nを含むなどのようになります。かなりデカップルな方法でルールを実装する場合は、ルールを数回微調整し、検索の精度に満足するまで実際の検索でどれくらい効果があるかを確認できます。

スコアのセットを取得したら、いくつかの非常に高速のソートアルゴリズムを使用して、スコアを最悪から最悪の順に並べ替えることができます。もちろん、xより小さいスコアの結果は除外します。

（このテクニックでは、AND/OR/NOTなどの高度な検索機能を実装するのが非常に簡単です）検索用語の分析を分割し、結果ごとのスコアを組み合わせることができるため

Answer 2

ランキングを確立するためのさまざまな戦略と要件があります。

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

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

がところでSolrには、それ自体で解決策ですが、私はあなたが知っているかなり確信している、すでにこの時点で:-)

Solr, Sunspot, SQlite, and Rails