次のようなcouchdbドキュメントがあるとします。

タグから転置インデックスを作成したいので、次のようになります。

私が読んで試したことから、couchdbは私にそれをさせないかもしれません。マップフェーズでは実行できず、カウチ削減フェーズでは実行できないようです。これは、アプリの別のレイヤーで実行する必要があることですか？

私が出力しているものは次のとおりです。

単語、ファイル ----- ------ wordx Doc2、Doc1、Doc1、Doc1、Doc1、Doc1、Doc1、Doc1

私が欲しいのは：

単語、ファイル ----- ------ wordx Doc2、Doc1

最高のパフォーマンスを得るには - 繰り返されるファイル名をどこでスキップする必要がありますか? マップ、リデュース、またはその両方？ps: 私は MR タスクの作成の初心者であり、質問でプログラミング ロジックを理解しようとしています。

Doug Cutting の論文を読みました。「合計ランキングのスペース最適化」。

ずいぶん前に書いたものなので、luceneがどんなアルゴリズムを使っているのか気になります(投稿リストのトラバーサルやスコア計算、ランキングに関して)。

特に、そこで説明されている総合ランキング アルゴリズムでは、各クエリ タームの投稿リスト全体をトラバースする必要があるため、「yellow dog」のような非常に一般的なクエリ タームの場合、2 つのタームのいずれかが非常に長い投稿リストを持つ可能性があります。ウェブ検索。それらはすべて、現在の Lucene/Solr で本当にトラバースされていますか? または、採用されているリストを切り捨てるためのヒューリスティックはありますか?

上位k件の結果しか返ってこない場合は、投稿リストを複数のマシンに分散させて、それぞれの上位k件をまとめればいいのは理解できますが、「100件目の結果ページ」を返さなければならない場合は、つまり、結果が 990 から 1000 番目にランク付けされた場合、各パーティションは依然として上位 1000 を見つける必要があるため、パーティショニングはあまり役に立ちません。

全体として、Lucene で使用される内部アルゴリズムに関する最新の詳細なドキュメントはありますか?

今のところ、MongoDB をいじって、どのような優れた機能があるかを確認しています。投稿、作成者、およびコメントを含む、非常に基本的な単純なブログ システムを表す小さなテスト スイートを作成しました。

MongoRegEx クラス (PHP ドライバー) を使用する検索機能を試してみました。ここでは、「/I」で大文字と小文字を区別して、「lorem ipsum」という文の後のすべての投稿コンテンツと投稿タイトルを検索しています。

私のコードは次のようになります。

しかし、私は何が起こるかについて混乱し、唖然としています。すべてのクエリの実行時間をチェックします (クエリの前後にマイクロタイムを設定し、小数点以下 15 桁で時間を取得します)。

最初のテストでは、110.000 のブログ ドキュメントと 5000 人の著者を追加しました。すべてランダムに生成されました。検索すると、「lorem ipsum」という文を含む 6824 件の投稿が見つかり、検索に 0.000057935714722 秒かかります。これは、MongoDB サービスを (Windows を使用して) リセットした後のもので、_id のデフォルト以外のインデックスはありません。

MongoDB は B ツリー インデックスを使用しますが、これは全文検索にはあまり効率的ではありません。投稿コンテンツ属性にインデックスを作成すると、上記と同じクエリが 0.000150918960571 で実行されます。これは、インデックスがない場合よりもかなり遅くなります (0.000092983245849 倍遅くなります)。これは、B ツリー カーソルを使用するため、いくつかの理由で発生する可能性があります。

しかし、どのようにしてクエリを高速に実行できるかについての説明を検索しようとしました。おそらくすべてが RAM に保存されていると思います (4GB あり、データベースは約 500MB です)。これが、完全な結果を得るために mongodb サービスを再起動しようとする理由です。

MongoDB の経験がある人なら誰でも、この種の全文検索で何が起こっているのかを理解するのに役立ちますか?

敬具 - メスティカ

アップデート2020-02-18

私はこの質問に再び出くわし、受け入れられた答えは同じままですが、今日それを最適化する方法を共有することを考えました（ここでもサードパーティのライブラリやツールを使用せずに-つまり、元の質問で述べたように最初から車輪を再発明します） 。

このシステムを簡素化および最適化するために、ドメインロジック層で「転置インデックスマップ」の代わりにTrie（プレフィックスツリー）を使用し、 「テーブルクエリ」 SQLテーブルの悪い習慣を完全に破棄します。例を挙げて説明します。

• アプリの一部のユーザーがすでにデータベースにいくつかのオブジェクトを追加したとします：w、wo、woo、wood、woodx。
• これらのオブジェクト（文字列/ラベル）はメモリ内のTrieによって表され、各Trieノードには、ツリー内のレベル（Think Associative Array）でそのオブジェクトのデータベース発行IDが含まれます。
• ユーザーが単語をクエリすると、Trieでその単語が検索され、検索された単語から下に向かって（つまり、そこから順番に）、関連するすべてのIDが蓄積されます。これらのIDから、必要なすべてのオブジェクトデータを取得します（キャッシュまたはDBのどちらからでも）。

これが説明するための写真です：

• 次に、ユーザーがデータベースに新しい単語、たとえば「woodxe」を追加すると、それに応じてTrieが更新されます。
• ユーザーが「woodx」をクエリすると、以前と同じプロセスが発生し、さらに新しいIDが蓄積されます（「woodxe」の発行されたID）
• 英語の辞書には、特定の文字シーケンスで始まる単語の有限リストがあるため、下に移動してすべてのサブノードを取得することは、O（1）の複雑さの有限プロセスです。たとえば、Trieで「wood」で始まる場合、英語辞書の接頭辞として「wood」を持つサブノードのリストは有限の定数です。これらすべてのサブノードをユーザーに返すか、制限を定義するか（遅延読み込み/ページング）、上位10ヒットのみを表示するかは、個人的なアーキテクチャ上の好みです。

これが説明のための写真です（緑色で追加されているものを確認してください）

• ユーザーのクエリが複数の単語の文字列である場合、つまり「木製家具」の場合、各単語は個別に解析/トライに追加され、それに応じて一致するIDのリストが表示されます。

* Trie *は以前のアーキテクチャをどのように改善しますか？

• 「テーブルクエリ」は面倒で、悪い習慣であり、データベースに正比例して大きくなる大きなオーバーヘッドでした。削除されました。
• 私たちが持っていた「転置インデックスマップ」は、余分なメモリオーバーヘッドを作成し、新しい単語で簡単に拡張できませんでした（上記の「woodx」の例のように）。ハッシュマップのクエリはO（1）であると主張することもできますが、メモリ内にいくつかの大きなハッシュマップがあると、実際には特定のレベルで処理速度が低下し、エンジニアリング設計としては不適切と見なされます。
• トライの検索の複雑さはO（m）です。ここで、mは提供されたアルファベットの文字数です。ユーザーが照会するのは純粋に英語のアルファベットを使用した単語であるため、最大のサブツリーは使用可能な最大の英語の単語と等しくなります（定数、つまりO（1））。さらに、前述のように、英語辞書で定義された単語プレフィックスで始まるサブノードの数も一定数であるため、すべての組み合わせでのトラバーサルはO（1）です。したがって、TotalではO（1）操作です。
  • したがって、Trie = Get key from Hashmap = O（1）をクエリすると、同じくらい高速になります。
  • その上、このシステムでのトライの利点は次のとおりです。
    • 複数の転置インデックスハッシュマップをメモリ内で実行するよりもメモリオーバーヘッドが小さい
    • 一元化されたクエリツリー
    • データベースに新しい単語を追加するだけで、メモリ内の既存のTrieにいくつかの新しいノードを追加するだけで簡単に拡張できます。つまり、データベースの増加と検索クエリの数の増加に関する問題はもうありません（スケーラビリティの悪夢）。

2015年10月15日更新

2012年に、私は個人的なオンラインアプリケーションを構築していましたが、学習目的で、アルゴリズムとアーキテクチャのスキルを強化するために、本質的に好奇心が強いため、実際に車輪の再発明をしたいと考えていました。Apache luceneなどを使用することもできましたが、前述したように、独自のミニ検索エンジンを構築することにしました。

質問：では、elasticsearch、luceneなどの利用可能なサービスを使用する以外に、このアーキテクチャを強化する方法は本当にありませんか？

元の質問

私は、ユーザーが特定のタイトル（たとえば、本x、本yなど）を検索するWebアプリケーションを開発しています。このデータは、リレーショナルデータベース（MySQL）にあります。

私は、データベースからフェッチされた各レコードがメモリにキャッシュされるという原則に従っています。これにより、アプリはデータベースへの呼び出しを減らすことができます。

私は、次のアーキテクチャを使用して、独自のミニ検索エンジンを開発しました。

これがその仕組みです。

• a）ユーザーがレコード名を検索する
• b）システムは、クエリがどの文字で始まるかをチェックし、そこにクエリがあるかどうかをチェックします：レコードを取得します。存在しない場合は、それを追加し、次の2つの方法を使用してデータベースから一致するすべてのレコードを取得します。
  • テーブル「クエリ」（一種の履歴テーブル）にすでに存在するクエリは、IDに基づいてレコードを取得します（高速パフォーマンス）
    
  • または、Mysql LIKE%%ステートメントを使用してレコード/IDを取得します（また、ユーザーが使用したクエリを、マップ先のIDとともに履歴テーブルクエリに保持します）。
    ->次に、レコードとそのIDを キャッシュに追加し、IDのみを転置インデックスマップに追加します。
• c）結果がUIに返される

システムは正常に動作しますが、2つの主要な問題があります。それは、（過去1か月間試行していた）適切な解決策が見つからなかったことです。

最初の問題：
ポイント（b）をチェックすると、クエリ「履歴」が見つからず、Like %%ステートメントを使用する必要がある場合：クエリがデータベース内の多数のレコード（1つまたは2）：

• Mysqlからレコードを取得するには時間がかかります（これが、特定の列でINDEXESを使用した理由です）
• 次に、クエリ履歴を保存します
• 次に、レコード/IDをキャッシュおよび転置インデックスマップに追加します。

2番目の問題：
アプリケーションを使用すると、ユーザーは新しいレコードを自分で追加できます。このレコードは、アプリケーションにログインしている他のユーザーがすぐに使用できます。
ただし、これを実現するには、転置インデックスマップとテーブルの「クエリ」を更新して、古いクエリが新しい単語に一致する場合に備えておく必要があります。たとえば、新しいレコード「woodX」が追加されている場合でも、古いクエリ「wood」はそれにマップされます。したがって、クエリ「wood」をこの新しいレコードに再フックするために、私が今行っていることは次のとおりです。

• 新しいレコード「woodX」が「records」テーブルに追加されます
• 次に、Like %%ステートメントを実行して、テーブル "queries"に既に存在するクエリがこのレコード（たとえば "wood"）にマップされているかどうかを確認し、新しいレコードIDを使用してこのクエリを新しい行として追加します：[wood、new id]。
• 次に、メモリ内で、このリストに新しいレコードIDを追加して、転置インデックスマップの「wood」キーの値（つまりリスト）を更新します。

->したがって、リモートユーザーが「wood」を検索すると、メモリから取得されます：woodとwoodX

ここでの問題は時間の消費でもあります。（テーブルクエリ内の）すべてのクエリ履歴を新しく追加された単語と一致させるには、多くの時間がかかります（一致するクエリが多いほど、時間がかかります）。次に、メモリ内の更新にも多くの時間がかかります。

今回の問題を修正するために私が考えているのは、最初に目的の結果をユーザーに返し、次にアプリケーションに必要なデータを使用してajax呼び出しをPOSTさせて、これらすべてのUPDATEタスクを実行することです。しかし、これが悪い習慣なのか、それとも専門的でないやり方なのかはわかりません。
そのため、この1か月間（もう少し）、このアーキテクチャに最適な最適化/変更/更新を考えようとしましたが、ドキュメント検索分野の専門家ではありません（実際には、これまでに構築した最初のミニ検索エンジンです）。

この種のアーキテクチャを実現するために私が何をすべきかについてのフィードバックやガイダンスをいただければ幸いです。
前もって感謝します。

PS：

• サーブレットを使用したj2eeアプリケーションです。
• MySQL innodbを使用しています（したがって、全文検索オプションを使用できません）

いくつかの圧縮アルゴリズムをテストしたいのでinverted index、上記のようないくつかの標準データセットが必要です。

これらのデータセットは無料でダウンロードできますか？

私の知る限り、これらのデータセットはグラスゴー大学によって配布されており、他のほとんどのTRECテストデータセットと同様に無料ではありません。

与えられたn文字列S1, S2, ..., SnとアルファベットセットA={a_1,a_2,....,a_m}。各文字列のアルファベットはすべて異なると想定します。次に、それぞれに転置インデックスを作成しますa_i (i=1,2...,m)。私の転置インデックスにも特別なものがあります。転置インデックスにa_iに1つの文字列が含まれている場合（たとえば）、のアルファベットはA順番に並んでいます。これ以上含める必要はありません。つまり、すべての文字列が転置リストに表示されるのは1回だけです。私の質問は、そのようなリストを迅速かつ効率的な方法で構築する方法ですか？複雑さには限界がありますか？S_2a_j (j=i+1,i+2,...,m)S_2

たとえば、A={a,b,e,g}, S1={abg}, S2={bg}, S3={gae}, S4={g}。次に、私の転置リストは次のようになります。

100,000 から 100Million にスケールする可能性のある文字列またはフレーズの膨大なリストがあるという問題があります。フレーズを検索すると、データベースへの ID またはインデックスが表示され、さらに操作を行うことができます。これにハッシュテーブルを使用できることは知っていますが、文字列に基づいてインデックスを生成するのに役立ち、オートコンプリートなどの他の機能にも役立つ他のアルゴリズムを探しています.

いくつかの SO スレッドに基づいてサフィックス ツリー/配列を読みましたが、それらは目的を果たしますが、余裕があるよりも多くのメモリを消費します。これに代わるものはありますか？

私の検索は、何百万もの文字列の巨大なリストにしか含まれていないためです。lucene などの検索エンジンに関心のないドキュメントやウェブページはありません。

また、転置インデックスについてもお読みください。役に立ちますが、どのアルゴリズムを勉強する必要がありますか?.

私は非常に大きな転置インデックス用語の作成に取り組んでいます。どのような方法を提案しますか？

初め

2番

psLuceneはオプションではありません

デフォルトでは、SOLR は XML ファイルを受け入れます。何百万ものクロールされた URL (html) で検索を実行したいと考えています。