3

壁の特定の投稿を見つけるためのフリーテキスト検索アルゴリズムを作成しようとしています（Facebookが使用するのと同様の種類の壁）。ユーザーは、検索フィールドにいくつかの単語を書き込んで、その単語を含む投稿にヒットすることができると想定されています。一番上に最もよく一致し、次に他の投稿が一致スコアに従って降順で表示されます。

編集距離（Levenshtein） "e（x、y）= e"を使用して、クエリワード「x」および投稿ワード「y」と比較した場合の各投稿のスコアを次のように計算しています：score（x、y ）= 2 ^（2-e）（1-min（e、| x |）/ | x |）、ここで "| x |" クエリワードの文字数です。

投稿内の各単語は、その特定の投稿の合計スコアに影響します。このアプローチは、投稿のサイズがほぼ同じである場合にうまく機能するように見えますが、実際にはクエリに関連していないのに、特定の大きな投稿が多くの単語を含むだけでスコアを上げることができる場合があります。

私はこの問題に間違った方法でアプローチしていますか、それとも私が考えていなかったスコアを正規化する方法がありますか？

4

1 に答える 1

1

はい。使用できる正規化方法はたくさんあります。これはよく研究された分野です！

ベクトル空間モデルを見てください。TDF / IDFは、あなたがしていることに関連している可能性があります。使用している方法と厳密には関係ありませんが、正規化の手がかりになる可能性があります。

また、各投稿の比較はO（N）になり、非常に遅くなる可能性があることに注意してください。string-distanceの代わりに、 stemmmingを使用するとより良い結果が得られる場合があります。次に、それをVSM転置インデックスに入れることができます。

多くのデータベース（MySQLおよびPostgresを含む）には全文検索があります。それはおそらく自分でやるよりも実用的です。

于 2010-05-27T08:34:56.700 に答える