2

したがって、これは幅広いトピックをカバーしており、それらの一部は、この質問などの StackOverflow で以前にカバーされていることを認識しています。同様に、部分文字列一致と近似文字列一致は、人気のあるアルゴリズムの議論のようです。ただし、両方を議論する必要がある問題に合わせてこれらのアイデアを組み合わせて使用​​ することは、非常に非効率的です. 2 つの問題を 1 つのソリューションに効率的に結合する方法を探しています。

現在、Java と Persistent DataStore で AppEngine を使用しています。クエリで計算を簡単にするための算術使用がないように見えるため、これはやや面倒です。そのため、現在、事前計算を行ってデータベースに追加フィールドとして保存することを検討しています。本質的に、これは友人と私がマッチングのためのシステムを実装する方法について持っていたアイデアであり、それをより効率的にする方法についての提案を多かれ少なかれ望んでいました. すでに存在するより良いものを優先して破棄する必要がある場合は、それも処理できます。

まず、検索対象となるものの基本的な例から始めましょう。次のナンセンスな文を考えてみましょう。

隔離層は、あなたの偽善的なゴミの下にプリンシパルをラケットします.

ユーザーが検索を行う場合

isalatig pri

これは、文字列の最初の一致としてはかなり適切であり、値が返されるはずだと思います。私たちが使用を検討している現在の方法は、基本的に値を割り当てて分割可能性をテストします。基本的に、次のデータを含むテーブルがあります

A: 2        B: 3        C: 5
D: 7        E: 11       F: 13
...

各文字は素数にマッピングされます (複数の文字は違いを生まず、必要なのは 1 文字だけです)。また、クエリ文字列がデータベース内の文字列を分割する場合、値は可能な一致として返されます。

この後、ストップワードとしてリストされていないキーワードが検索文字列から比較され、編集距離の特定のしきい値 (現在はレーベンシュタイン距離を使用) の下で一致する可能性のある単語の部分文字列を開始しているかどうかが確認されます。

distance("isalatig", "isolating") == 2
distance("pri", "principal") == 0 // since principal has a starting 
                                  // substring of pri it passes

次に、各クエリの合計距離が昇順でランク付けされ、上位のn値がクエリ実行者に返されます。

これはアルゴリズムの背後にある基本的な考え方ですが、このようなシナリオを扱うのはこれが初めてなので、おそらく非常に重要なものが欠けていることに気付きました (または、私の考え全体が間違っている可能性があります)。私が実装しようとしている現在の状況を処理する最善の方法は何ですか。同様に、私がやろうとしていることに対抗するために AppEngine が現在提供しているユーティリティがあれば、教えてください。

4

1 に答える 1

0

まず、説明：App Engineは、任意の算術式の結果をクエリする効率的な方法がないため、クエリでの算術を許可していません。SQLデータベースでこれを行うと、プランナーは非効率的なクエリプランを選択することを余儀なくされます。これには通常、すべての候補レコードを1つずつスキャンすることが含まれます。

同じ理由で、スキームは機能しません。ターゲット番号で割り切れるすべての数値を効率的にクエリできるように、整数にインデックスを付ける方法はありません。その他の潜在的な問題には、固定長整数に格納するには大きすぎる数値に変換される単語や、「賃貸」、「学習」、「枝角」を区別できない単語が含まれます。

文字列の任意のプレフィックスを照合するための要件を今のところ破棄すると、検索しているのはフルテキストインデックスです。これは通常、転置インデックスとステミングを使用して実装されます。全文検索のサポートはAppEngineロードマップにありますが、まだリリースされていません。それまでの間、最善の選択肢はSearchableModelか、Googleサイト検索などの外部検索エンジンを使用しているようです。

于 2011-10-17T03:40:39.550 に答える