6

ランク付けされていないブール検索を実装しようとしています。このためには、ツリーを構築し、DFS を実行してドキュメントを取得する必要があります。リーフ ノードはありますが、ツリーを構築するのが困難です。

例: query = OR ( AND (マリア・シャラポワ) テニス)

結果：

      また
     | | | |
     そしてテニス
     | | | |
  マリアシャラポワ

DFS を使用してツリーをトラバースし、特定のドキュメント ID に相当するブール値を計算して、コーパスから必要なドキュメントを識別します。誰かがPythonを使用してこれを設計するのを手伝ってくれますか? クエリを解析し、今のところリーフ ノードを取得しました。

編集：私はここに新しいので、明確さを欠いて申し訳ありません。私は基本的に非常に素朴な検索エンジンを構築しようとしています。したがって、ユーザーは OR ( AND (マリア シャラポワ) テニス) のようなブールクエリを入力します。入力したクエリに応じてユーザーに表示されるウィキペディア ドキュメントのコーパスがあります。

これまで、クエリを解析して個々の演算子 (OR、AND など) を取得しました。そして、個々の検索用語 (マリア、テニスなど)。解析用のコードは、基本的にすべての演算子とクエリ用語を入力どおりにグループ化する単なる関数です。すなわち、(マリア・シャラポワ)、(テニス)、OR、AND。ツリーのボトムアップを作成するために、この関数をこのように解析しました。ここで、テニス、マリア、シャラポワなどの対応するキーワードの転置リストを使用して、転置リストを使用してブール演算を実行し、特定の「documentid」を取得します。次に、この documentid が API に渡され、API が正しいウィキペディア ページを取得します。

トピックをより詳細に説明するために、私の問題の詳細については、このドキュメントを参照してください: http://www.ccs.neu.edu/home/jaa/CSG339.06F/Lectures/boolean.pdf

4

2 に答える 2

5

まず、多くの演算子、範囲クエリ、またはワイルドカードをサポートするクエリ言語の高度な構文が必要な場合は、Joran が指摘したように、lex/yacc ソリューションを参照する必要があります。

第二に、あなたが投稿した講義スライドから、python でツリーを構築することよりもブールクエリモデルを実装する方法に関心があると思います。その後、クエリ自体について心配する必要はありません。クエリが次のように適切にフォーマットされているとします。

"OR ( AND ( maria sharapova ) tennis )"

つまり、演算子 (AND/OR) とキーワード/括弧の間にスペースがあります。次に、クエリを解析し、それらから結合された検索結果を取得するために必要なスタックは 2 つだけです (tree-data-structure で DFS を使用する必要はありません)。

最初のスタックは、演算子 (AND/OR) とオペランド (例: maria、tennis) を保持します。括弧を開閉条件として扱い、現在のオペランドをスタックの一番上で処理します。閉じ括弧が表示された場合にのみ、検索操作を処理します)。

2 番目のスタックには、現在の検索結果が保持されます。

上記の例を使用して、段階的なデモを行いましょう。クエリを左から右にスキャンします。

ステップ 1. 「OR」演算子をスタックにプッシュします。

+               +
+               +
+    OR         +
+ + + + + + + + +

ステップ 2. 左括弧が表示されます(が、スキップしてください。

ステップ 3. 「AND」演算子をスタックにプッシュします。スタックは次のようになります。

+               +
+    AND        +
+    OR         +
+ + + + + + + + +

ステップ 4. 別の をスキップし(ます。

ステップ 5. 「maria」をスタックにプッシュします。

ステップ 6. 「sharapova」をスタックにプッシュします。スタックは次のようになります。

+   sharapova   +
+    maria      +
+    AND        +
+    OR         +
+ + + + + + + + +

ステップ 7. 閉じ括弧が表示されます)。それでは、最初の操作を行います。オペレーターが表示されるまで、スタックの一番上にあるすべてのアイテムをポップします。演算子もポップして、現在の演算子を取得します。ここで、「sharapova」と「maria」の検索を別々に処理し、演算子「AND」を使用して検索結果を結合します。「maria」の場合、次の 3 つのドキュメント ID を取得するとします[1, 2, 3]。「sharapova」の場合、さらに 5 つのドキュメント ID を取得します[2, 3, 8, 9, 10]。結果を「AND」で結合すると 、現在の検索結果を保持する 2 番目のスタックになります[2,3]。
現在の状況は次のようになります。右側は結果バッファです。

+               +           +         +
+               +           +         +
+               +           +         +
+    OR         +           +  [2,3]  +
+ + + + + + + + +           + + + + + +

ステップ 8. テニスをスタックにプッシュします。

+               +           +         +
+               +           +         +
+    tennis     +           +         +
+    OR         +           +  [2,3]  +
+ + + + + + + + +           + + + + + +

ステップ 9. 別の閉じ括弧が表示されます)。繰り返しますが、「OR」が表示されるまで、スタックの一番上にあるすべてのアイテムをポップします。「tennis」を使用して検索を開始し、結果としてドキュメント ID: が得られたとします[3, 5, 7]。この時点で、演算子「OR」を使用してこの結果をバッファー内の前の結果と結合し、最終的にドキュメント ID: を取得します[2,3,5,7]。

私のサンプルコードはこちらです。len(word)注:整数をランダムにサンプリングして、ドキュメント ID を検索して返すことをシミュレートします。

コードからの出力は、現在のクエリ項目 (1 列目) を処理する前のシステムの様子 (1 列目)、結果バッファーの状態 (2 列目)、スタック内の項目 (3 列目)、および即時検索結果 (4 列目)。

于 2012-10-24T20:25:15.033 に答える
2

リストのリストは、Python でツリーを表す自然な方法です (クラスを作成する必要はありません)。

>>> query = ['OR', ['AND', 'maria', 'sharapova'], 'tennis']
于 2012-09-08T06:32:19.397 に答える