(57)【特許請求の範囲】
【請求項１】
コンピュータによって実行される、文書インデックスを生成するための方法であって、
インデックス化される文書を取得し、
前記文書に対して単成分分割動作を実行して、複数の単成分パーティションを取得し、
前記複数の単成分パーティションの単成分パーティションに対して、
前記単成分パーティションがフィルタ文字ベースの単成分パーティションであるか否かを判定し、前記単成分パーティションがフィルタ文字ベースの単成分パーティションであるか否かの判定は、予め設定されているフィルタ文字リストと前記単成分パーティションを比較することを含み、
前記単成分パーティションが前記フィルタ文字ベースの単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションに対応する前記文書インデックスにエントリーを加えず、前記フィルタ文字ベースの単成分パーティションを前記複数の単成分パーティションにおける少なくとも１つの他の単成分パーティションと結びつけることによって多成分パーティションを形成し、前記少なくとも１つの他の単成分パーティションは前記文書中の前記フィルタ文字ベースの単成分パーティションに隣接し、前記多成分パーティションに対応する前記文書インデックスにエントリーを加え、
前記単成分パーティションが前記フィルタ文字ベースの単成分パーティションではない場合に、前記単成分パーティションに対応する前記文書インデックスにエントリーを加えること、
を備える、方法。
【請求項２】
請求項１に記載の方法であって、さらに、前記予め設定されているフィルタ文字リストを生成することを含み、前記予め設定されているフィルタ文字リストの生成は、
サンプル文書セットから単成分パーティションを決定し、
前記サンプル文書セットから、少なくとも前記単成分パーティションのサブセットのそれぞれについて出現頻度を決定し、
前記単成分パーティションのそれぞれに対応する出現頻度に少なくとも一部基づいて、前記単成分パーティションのサブセットを前記予め設定されているフィルタ文字リストに含ませること
を備える、方法。
【請求項３】
請求項１に記載の方法であって、前記単成分パーティションを前記予め設定されているフィルタ文字リストと比較することは、前記単成分パーティションが前記予め設定されているフィルタ文字リストにおけるエントリーと一致するか否かを判定することを含む、方法。
【請求項４】
請求項１に記載の方法であって、多成分パーティションの形成は、前記フィルタ文字ベースの単成分パーティションを少なくとも１つの他の単成分パーティションと結びつけることによって、二成分パーティションを形成することを含む、方法。
【請求項５】
請求項４に記載の方法であって、前記二成分パーティションの形成は、さらに、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最初の単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションを前記文書内の次の単成分パーティションと結びつけることによって、前記二成分パーティションを形成し、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最後の単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションを前記文書内の前の単成分パーティションと結びつけることによって、前記二成分パーティションを形成し、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最初の単成分パーティションでも最後の単成分パーティションでもない場合に、前記フィルタ文字ベースの単成分パーティションを前記文書内の前の単成分パーティションと結びつけることによって第１の二成分パーティションを形成し、前記フィルタ文字ベースの単成分パーティションを前記次の単成分パーティションと結びつけることによって第２の二成分パーティションを形成すること、
を含む、方法。
【請求項６】
コンピュータによって実行される、データをクエリングするための方法であって、
データクエリを受信し、
前記データクエリに対して単成分分割動作を実行して、複数の単成分パーティションを取得し、
前記複数の単成分パーティションの単成分パーティションに対して、
前記単成分パーティションがフィルタ文字ベースの単成分パーティションであるか否かを判定し、前記単成分パーティションがフィルタ文字ベースの単成分パーティションであるか否かの判定は、予め設定されているフィルタ文字リストと前記単成分パーティションを比較することを含み、
前記単成分パーティションが前記フィルタ文字ベースの単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションを用いる予め設定されているインデックスの検索を行わず、前記フィルタ文字ベースの単成分パーティションを前記複数の単成分パーティションにおける少なくとも１つの他の単成分パーティションと結びつけることによって多成分パーティションを形成し、前記少なくとも１つの他の単成分パーティションは前記データクエリ中の前記フィルタ文字ベースの単成分パーティションに隣接し、前記多成分パーティションを用いて、予め設定されているインデックスを検索して、前記多成分パーティションに対応する検索結果を取得し、
前記単成分パーティションが前記フィルタ文字ベースの単成分パーティションではない場合に、前記単成分パーティションを用いて、前記予め設定されているインデックスを検索して、前記単成分パーティションに対応する検索結果を取得し、
前記検索結果を結びつけて、最終的なクエリ検索結果を形成すること、
を備える、方法。
【請求項７】
請求項６に記載の方法であって、前記予め設定されているインデックスは、
インデックス化される文書を取得し、
前記文書に対してインデックス化単成分分割動作を実行して、第２の複数の単成分パーティションを取得し、
前記第２の複数の単成分パーティションの第１の単成分パーティションに対して、
前記第１の単成分パーティションが第１のフィルタ文字ベースの単成分パーティションであるか否かを判定し、前記第１の単成分パーティションが第１のフィルタ文字ベースの単成分パーティションであるか否かの判定は、予め設定されているフィルタ文字リストと前記第１の単成分パーティションを比較することを含み、
前記第１の単成分パーティションがフィルタ文字ベースの単成分パーティションである場合に、前記第１のフィルタ文字ベースの単成分パーティションに対応する前記予め設定されているインデックスにエントリーを加えず、前記第１のフィルタ文字ベースの単成分パーティションを前記第２の複数の単成分パーティションにおける少なくとも１つの他の単成分パーティションと結びつけることによって第２の多成分パーティションを形成し、前記少なくとも１つの他の単成分パーティションは前記文書中の前記第１のフィルタ文字ベースの単成分パーティションに隣接し、前記第２の多成分パーティションに対応する前記予め設定されているインデックスにエントリーを加え、
前記第１の単成分パーティションが第１のフィルタ文字ベースの単成分パーティションではない場合に、前記第１の単成分パーティションに対応する前記予め設定されているインデックスに前記エントリーを加える、方法。
【請求項８】
請求項６に記載の方法であって、前記単成分パーティションを前記予め設定されているフィルタ文字リストと比較することは、前記単成分パーティションが前記予め設定されているフィルタ文字リストにおけるエントリーと一致するか否かを判定することを含む、方法。
【請求項９】
請求項６に記載の方法であって、前記多成分パーティションの形成は、前記フィルタ文字ベースの単成分パーティションを前記少なくとも１つの他の単成分パーティションと結びつけることによって、二成分パーティションを形成することを含む、方法。
【請求項１０】
請求項９に記載の方法であって、前記二成分パーティションの形成は、さらに、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最初の単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションと前記文書内の次の単成分パーティションとを結びつけることによって、前記二成分パーティションを形成し、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最後の単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションと前記文書内の前の単成分パーティションとを結びつけることによって、前記二成分パーティションを形成し、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最初の単成分パーティションでも最後の単成分パーティションでもない場合に、前記フィルタ文字ベースの単成分パーティションを前の単成分パーティションと結びつけることによって第１の二成分パーティションを形成し、前記フィルタ文字ベースの単成分パーティションを後の単成分パーティションと結びつけることによって第２の二成分パーティションを形成すること、を含む、方法。
【請求項１１】
文書インデックス化システムであって、
インターフェースに接続されている１または複数のプロセッサであって、
インデックス化される文書を取得し、
前記文書に対して単成分分割動作を実行して、複数の単成分パーティションを取得し、
前記複数の単成分パーティションの単成分パーティションに対して、
前記単成分パーティションがフィルタ文字ベースの単成分パーティションであるか否かを判定し、前記単成分パーティションがフィルタ文字ベースの単成分パーティションであるか否かの判定は、予め設定されているフィルタ文字リストと前記単成分パーティションを比較することを含み、
前記単成分パーティションが前記フィルタ文字ベースの単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションに対応する前記インデックスにエントリーを加えず、前記フィルタ文字ベースの単成分パーティションを前記複数の単成分パーティションにおける少なくとも１つの他の単成分パーティションと結びつけることによって多成分パーティションを形成し、前記少なくとも１つの他の単成分パーティションは前記文書中の前記フィルタ文字ベースの単成分パーティションに隣接し、前記多成分パーティションに対応する前記文書インデックスにエントリーを加え、
前記単成分パーティションが前記フィルタ文字ベースの単成分パーティションではない場合に、前記単成分パーティションに対応する前記文書インデックスにエントリーを加えるよう構成されている１または複数のプロセッサと、
前記１または複数のプロセッサに接続され、前記プロセッサに命令を提供するよう構成されている１または複数のメモリと、
を備える、システム。
【請求項１２】
請求項１１に記載のシステムであって、前記１または複数のプロセッサは、さらに、前記予め設定されているフィルタ文字リストを生成するように構成され、前記予め設定されているフィルタ文字リストの生成は、
サンプル文書セットから単成分パーティションを決定し、
前記サンプル文書セットから、少なくとも前記単成分パーティションのサブセットのそれぞれについて出現頻度を決定し、
前記単成分パーティションのそれぞれに対応する出現頻度に少なくとも一部基づいて、前記単成分パーティションのサブセットを前記予め設定されているフィルタ文字リストに含ませることを含む、システム。
【請求項１３】
請求項１２に記載のシステムであって、前記単成分パーティションを前記予め設定されたフィルタ文字リストと比較することは、前記単成分パーティションが前記予め設定されているフィルタ文字リストにおけるエントリーと一致するか否かを判定することを含む、システム。
【請求項１４】
請求項１１に記載のシステムであって、多成分パーティションの形成は、前記フィルタ文字ベース単成分パーティションを前記少なくとも１つの他の単成分パーティションと結びつけることによって、二成分パーティションを形成することを含む、システム。
【請求項１５】
請求項１４に記載のシステムであって、前記二成分パーティションの形成は、さらに、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最初の単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションを前記文書内の次の単成分パーティションと結びつけることによって、前記二成分パーティションを形成し、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最後の単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションを前記文書内の前の単成分パーティションと結びつけることによって、前記二成分パーティションを形成し、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最初の単成分パーティションでも最後の単成分パーティションでもない場合に、前記フィルタ文字ベースの単成分パーティションを前記文書内の前の単成分パーティションと結びつけることによって第１の二成分パーティションを形成し、前記フィルタ文字ベースの単成分パーティションを前記次の単成分パーティションと結びつけることによって第２の二成分パーティションを形成すること、
を含む、システム。
【請求項１６】
データクエリシステムであって、
インターフェースに接続されている１または複数のプロセッサであって、
前記データクエリに対して単成分分割動作を実行して、複数の単成分パーティションを取得し、
前記複数の単成分パーティションの単成分パーティションに対して、
前記単成分パーティションがフィルタ文字ベースの単成分パーティションであるか否かを判定し、前記単成分パーティションがフィルタ文字ベースの単成分パーティションであるか否かの判定は、予め設定されているフィルタ文字リストと前記単成分パーティションを比較することを含み、
前記単成分パーティションが前記フィルタ文字ベースの単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションを用いる予め設定されているインデックスの検索を行わず、前記フィルタ文字ベースの単成分パーティションを前記複数の単成分パーティションにおける少なくとも１つの他の単成分パーティションと結びつけることによって多成分パーティションを形成し、前記少なくとも１つの他の単成分パーティションは前記データクエリ中の前記フィルタ文字ベースの単成分パーティションに隣接し、前記多成分パーティションを用いて、予め設定されているインデックスを検索して、前記多成分パーティションに対応する検索結果を取得し、
前記単成分パーティションが前記フィルタ文字ベースの単成分パーティションではない場合に、前記単成分パーティションを用いて、前記予め設定されているインデックスを検索して、前記単成分パーティションに対応する検索結果を取得し、
前記検索結果を結びつけて、最終的なクエリ検索結果を形成することを実行するよう構成されている１または複数のプロセッサと、
前記１または複数のプロセッサに接続され、前記プロセッサに命令を提供するよう構成されている１または複数のメモリと、
を備える、システム。
【請求項１７】
請求項１６に記載のシステムであって、前記予め設定されているインデックスは、
インデックス化される文書を取得し、
前記文書に対してインデックス化単成分分割動作を実行して、第２の複数の単成分パーティションを取得し、
前記第２の複数の単成分パーティションの第１の単成分パーティションに対して、
前記第１の単成分パーティションが第１のフィルタ文字ベースの単成分パーティションであるか否かを判定し、前記第１の単成分パーティションが第１のフィルタ文字ベースの単成分パーティションであるか否かの判定は、予め設定されているフィルタ文字リストと前記第１の単成分パーティションを比較することを含み、
前記第１の単成分パーティションがフィルタ文字ベースの単成分パーティションである場合に、前記第１のフィルタ文字ベースの単成分パーティションに対応する前記予め設定されているインデックスにエントリーを加えず、前記第１のフィルタ文字ベースの単成分パーティションを前記第２の複数の単成分パーティションにおける少なくとも１つの他の単成分パーティションと結びつけることによって第２の多成分パーティションを形成し、前記少なくとも１つの他の単成分パーティションは前記文書中の前記第１のフィルタ文字ベースの単成分パーティションに隣接し、前記第２の多成分パーティションに対応する前記予め設定されているインデックスにエントリーを加え、
前記第１の単成分パーティションが第１のフィルタ文字ベースの単成分パーティションではない場合に、前記第１の単成分パーティションに対応する前記予め設定されているインデックスに前記エントリーを加える、システム。
【請求項１８】
請求項１６に記載のシステムであって、前記単成分パーティションを前記予め設定さているフィルタ文字リストと比較することは、前記単成分パーティションが前記予め設定されているフィルタ文字リストにおけるエントリーと一致するか否かを判定することを含む、システム。
【請求項１９】
請求項１６に記載のシステムであって、前記多成分パーティションの形成は、前記フィルタ文字ベースの単成分パーティションを前記少なくとも１つの他の単成分パーティションと結びつけることによって、二成分パーティションを形成することを含む、システム。
【請求項２０】
請求項１９に記載のシステムであって、二成分パーティションの形成は、さらに、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最初の単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションと前記文書内の次の単成分パーティションとを結びつけることによって、前記二成分パーティションを形成し、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最後の単成分パーティションである場合に、前記フィルタ文字ベースの単成分パーティションと前記文書内の前の単成分パーティションとを結びつけることによって、前記二成分パーティションを形成し、
前記フィルタ文字ベースの単成分パーティションが前記文書内の最初の単成分パーティションでも最後の単成分パーティションでもない場合に、前記フィルタ文字ベースの単成分パーティションを前の単成分パーティションと結びつけることによって第１の二成分パーティションを形成し、前記フィルタ文字ベースの単成分パーティションを後の単成分パーティションと結びつけることによって第２の二成分パーティションを形成すること、
を含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本願は、すべての目的のために参照により本明細書に組み込まれる、２００９年７月２３日出願の発明の名称を「ＤＯＣＵＭＥＮＴ  ＩＮＤＥＸＩＮＧ  ＭＥＴＨＯＤ，  ＤＡＴＡ  ＱＵＥＲＹ  ＭＥＴＨＯＤ  ＡＮＤ  ＳＥＲＶＥＲ  ＦＯＲ  ＳＥＡＲＣＨ  ＥＮＧＩＮＥ（検索エンジンのための文書インデックス化方法およびデータクエリ方法並びにサーバ）」とする中国特許出願第２００９１０１５１４８７．２号に基づく優先権を主張する。
【０００２】
本発明は、情報技術の技術分野に関し、特に、文書インデックス化およびデータクエリングに関する。
【背景技術】
【０００３】
検索エンジンは、ワールドワイドウェブ上で情報を検索するように設計されている。検索エンジンは、しばしば、特定のポリシーに従って、特定のコンピュータプログラムによってインターネット上の情報を収集する。検索エンジンは、さらに、検索型サービスをユーザに提供する。すなわち、検索エンジンは、収集した情報を組織化して処理し、処理された情報をユーザに表示する。
【０００４】
ウェブ検索エンジンは、通常、多くのウェブページに関する情報を格納することによって機能する。これらのページは、ウェブクローラ（時にスパイダとしても知られる）と呼ばれる情報キャプチャシステムによって取得される。ウェブクローラは、組織的な自動化された方法あるいは規則的な方法で、ワールドワイドウェブをブラウズするコンピュータプログラムである。この処理は、ウェブクローリングまたはウェブスパイダリングと呼ばれる。ほとんどのウェブクローラは、迅速な検索を提供するためにダウンロード済みのページをインデックス化する検索エンジンによる後の処理に向けて、訪問したページすべてのコピーを作成するために用いられる。一般に、ウェブクローラは、シードと呼ばれる訪問すべきＵＲＬのリストから開始する。クローラは、これらのＵＲＬを訪問すると、ページ内のすべてのハイパーリンク（クロールフロンティアと呼ばれる）を特定し、訪問すべきＵＲＬのリストにそれらを追加する。フロンティアからのＵＲＬは、１組のポリシーに従って再帰的に訪問される。このクロール処理では、ハイパーリンクと共にウェブページがキャプチャされる。これらのウェブページは、ウェブページスナップショットと呼ばれる。ハイパーリンクはインターネット上で広く利用されているため、理論的に、特定のウェブページから開始して、ほとんどのウェブページを収集することができる。キャプチャされたウェブページが処理される時、検索サービスを提供するために、キーワードが抽出され、インデックスが構築される。次いで、ユーザが検索エンジンに（通例はキーワードを用いて）クエリを入力すると、検索エンジンは、そのインデックスを調べて、自身の基準に従って、最も良く一致するウェブページＵＲＬのリストを、通常は文書のタイトルおよび時にはテキストの一部を含む短い要旨と共に提供する。インデックスは、データと共に格納された情報と、その情報をインデックス化した方法から構築される。検索エンジンの有用性は、検索エンジンが返す結果群の妥当性によって決まる。特定の単語またはフレーズを含む多くのページが存在し得るが、一部のページが、他のページよりも関連性が高く、人気があり、または、信頼できるページである可能性がある。ほとんどの検索エンジンは、「最良の」結果を最初に提供するために、結果を順位付けする方法を用いる。どのページが最良一致であるか、および、どのような順番で結果を提示するのかを、検索エンジンが決定する方法は、検索エンジンごとに大きく異なっている。
【０００５】
特に、漢字を検索できる検索エンジンにとっては、インデックス化およびクエリング処理中に、漢字分割動作が必要とされる。従来の漢字分割方法は、文中の各漢字が一単位とみなされる単成分分割方法を用いている。例えば、「中国股市」（「中国株式市場」と翻訳される）という表現を単成分分割すると、結果セットは、以下の４つの単一文字を含む。それぞれ「中」（「中国の」）、「国」（「国」）、「股」（「株式」）、「市」（「市場」）。ここで、６００万の文書をインデックス化している単一の検索エンジンサーバにおける「市」（「市場」）という文字の出現確率は、９３％である。したがって、単成分分割方法を用いる場合、「市」（「市場」）というクエリは、「中国股市」（「中国株式市場」）というクエリの際に、検索エンジンサーバのリソースの大部分を消費する。かかる状況を避けるために、高頻度文字のリストが、検索エンジンに予め格納されており、高頻度文字は、クエリ実行前にフィルタリングされる。かかる高頻度文字は、「フィルタ文字」とも呼ばれる。同じ例を用いると、「中国股市」（「中国株式市場」）というクエリは、クエリ内の高頻度文字「市」（「市場」）をスキップするために、「中国股」（「中国株式」）というクエリに単純化される。
【０００６】
しかしながら、インデックス化およびクエリングは従来の単成分分割方法で高頻度文字を除外することによって実行されるため、結果セットが正確でない場合がある。再び、「中国股市」（「中国株式市場」）を一例として用いると、「市」（「市場」）がクエリにおいて除外されるため、クエリ結果セットは、「中国股民」（「中国株投資家」）および「中国股票」（「中国株式」）など、「中国股」（「中国株」）を含むが、ユーザのクエリと正確には一致しない多くの表現を含む場合がある。したがって、より正確かつ効率的なインデックス化およびクエリングの技術が必要とされる。
【図面の簡単な説明】
【０００７】
以下の詳細な説明と添付の図面に、本発明の様々な実施形態を開示する。
【０００８】
【図１Ａ】文書データのインデックス化およびクエリングのための技術を提供するプログラムされたコンピュータシステムの一実施形態を示す機能図。
【０００９】
【図１Ｂ】文書クエリおよびデータインデックス化システムの一実施形態を用いた検索エンジンを示す概略図。
【００１０】
【図２】文書インデックス化処理の一実施形態を示すフローチャート。
【００１１】
【図３】文書インデックス化処理の別の実施形態を示すフローチャート。
【００１２】
【図４】検索エンジンのデータクエリ処理の一実施形態を示すフローチャート。
【００１３】
【図５】検索エンジンのデータクエリ処理の別の実施形態を示すフローチャート。
【００１４】
【図６】文書をインデックス化するよう構成されたシステムの一実施形態を示すブロック図。
【００１５】
【図７】文書をインデックス化するよう構成されたシステムの別の実施形態を示すブロック図。
【００１６】
【図８】検索エンジンのためにデータクエリングを実行するよう適合されたシステムの一実施形態を示すブロック図。
【００１７】
【図９】検索エンジンのためにデータクエリングを実行するよう適合されたシステムの別の実施形態を示すブロック図。
【発明を実施するための形態】
【００１８】
本発明は、処理、装置、システム、物質の組成、コンピュータ読み取り可能な格納媒体上に具現化されたコンピュータプログラム製品、および／または、プロセッサ（プロセッサに接続されたメモリに格納および／またはそのメモリによって提供される命令を実行するよう構成されたプロセッサ）を含め、様々な形態で実装されうる。本明細書では、これらの実装または本発明が取りうる任意の他の形態を、技術と呼ぶ。一般に、開示された処理の工程の順序は、本発明の範囲内で変更されてもよい。特に言及しない限り、タスクを実行するよう構成されるものとして記載されたプロセッサまたはメモリなどの構成要素は、ある時間にタスクを実行するよう一時的に構成された一般的な構成要素として、または、タスクを実行するよう製造された特定の構成要素として実装されてよい。本明細書では、「プロセッサ」という用語は、１または複数のデバイス、回路、および／または、コンピュータプログラム命令などのデータを処理するよう構成された処理コアを指すものとする。
【００１９】
以下では、本発明の原理を示す図面を参照しつつ、本発明の１または複数の実施形態の詳細な説明を行う。本発明は、かかる実施形態に関連して説明されているが、どの実施形態にも限定されない。本発明の範囲は、特許請求の範囲によってのみ限定されるものであり、多くの代替物、変形物、および、等価物を含む。以下の説明では、本発明の完全な理解を提供するために、多くの具体的な詳細事項が記載されている。これらの詳細事項は、例示を目的としたものであり、本発明は、これらの具体的な詳細事項の一部または全てがなくとも特許請求の範囲に従って実施可能である。簡単のために、本発明に関連する技術分野で周知の技術事項については、本発明が必要以上にわかりにくくならないように、詳細には説明していない。
【００２０】
図１Ａは、文書データのインデックス化およびクエリングのための技術を提供するプログラムされたコンピュータシステムの一実施形態を示す機能図である。明らかに、他のコンピュータシステムアーキテクチャおよび構成が、文書データのインデックス化およびクエリングのための技術を実行するために用いられてもよい。以下に述べるような様々なサブシステムを備えるコンピュータシステム１００は、少なくとも１つのマイクロプロセッササブシステム（プロセッサまたは中央処理装置（ＣＰＵ）とも呼ばれる）１０２を備える。例えば、プロセッサ１０２は、シングルチッププロセッサまたはマルチプロセッサによって実装できる。いくつかの実施形態において、プロセッサ１０２は、コンピュータシステム１００の動作を制御する汎用デジタルプロセッサである。メモリ１１０から読み出された命令を用いて、プロセッサ１０２は、入力データの受信および操作、ならびに、出力デバイス（例えば、ディスプレイ１１８）上でのデータの出力および表示を制御する。いくつかの実施形態において、プロセッサ１０２は、例えば、メモリ１１０（または、その他のコンピュータ読み取り可能な記憶媒体要素／デバイス）と通信し、本明細書に述べるように文書データのインデックス化およびクエリングのための技術を備え、および／または、その技術を実装するために用いられる。
【００２１】
プロセッサ１０２は、メモリ１１０と双方向的に接続されており、メモリ１１０は、第１のプライマリストレージ（通例は、ランダムアクセスメモリ（ＲＡＭ））および第２のプライマリストレージ領域（通例は、読み出し専用メモリ（ＲＯＭ））を含みうる。当業者に周知のように、プライマリストレージは、一般的な記憶領域として、および、スクラッチパッドメモリとして利用可能であり、また、入力データおよび処理済みデータを格納するために利用可能である。プライマリストレージは、さらに、プロセッサ１０２上で実行される処理のための他のデータおよび命令に加えて、データオブジェクトおよびテキストオブジェクトの形態で、プログラミング命令およびデータを格納できる。また、当業者に周知のように、プライマリストレージは、通例、機能（例えば、プログラムされた命令）を実行するためにプロセッサ１０２によって用いられる基本的な動作命令、プログラムコード、データ、および、オブジェクトを備える。例えば、プライマリストレージデバイス１１０は、例えば、データアクセスが双方向である必要があるか、単方向である必要があるかに応じて、後述の任意の適切なコンピュータ読み取り可能な記憶媒体を含みうる。例えば、プロセッサ１０２は、頻繁に必要になるデータをキャッシュメモリ（図示せず）に直接的かつ非常に迅速に格納し取り出すことができる。
【００２２】
着脱可能なマスストレージデバイス１１２が、コンピュータシステム１００にさらなるデータ記憶容量を提供しており、プロセッサ１０２に対して双方向（読み出し／書き込み）または単方向（読み出しのみ）に接続されている。例えば、ストレージ１１２は、磁気テープ、フラッシュメモリ、ＰＣカード、携帯型マスストレージデバイス、ホログラフィックストレージデバイス、および、その他のストレージデバイスなどのコンピュータ読み取り可能な媒体も含みうる。固定マスストレージ１２０も、例えば、さらなるデータ記憶容量を提供しうる。マスストレージ１２０の最も一般的な例は、ハードディスクドライブである。マスストレージ１１２、１２０は、一般に、プロセッサ１０２によって通例はあまり利用されないさらなるプログラミング命令、データなどを格納する。当然のことながら、マスストレージ１１２、１２０内に保持された情報は、必要であれば、仮想メモリとしてのプライマリストレージ１１０（例えば、ＲＡＭ）の一部に標準的な方式で組み込まれてよい。
【００２３】
プロセッサ１０２がストレージサブシステムにアクセスできるようにすることに加えて、バス１１４は、その他のサブシステムおよびデバイスへのアクセスを可能にするために用いられてもよい。図に示すように、これらは、ディスプレイモニタ１１８、ネットワークインターフェース１１６、キーボード１０４、および、ポインティングデバイス１０６、ならびに、必要に応じて、補助入力／出力デバイスインターフェース、サウンドカード、スピーカ、および、その他のサブシステムを含みうる。例えば、ポインティングデバイス１０６は、マウス、スタイラス、トラックボール、または、タブレットであってよく、グラフィカルユーザインターフェースと相互作用するのに有用である。
【００２４】
ネットワークインターフェース１１６は、図に示すように、ネットワーク接続を用いて、別のコンピュータ、コンピュータネットワーク、または、遠隔通信ネットワークにプロセッサ１０２を接続することを可能にする。例えば、ネットワークインターフェース１１６を通して、プロセッサ１０２は、方法／処理ステップを実行する過程で、別のネットワークから情報（例えば、データオブジェクトまたはプログラム命令）を受信したり、別のネットワークに情報を出力したりすることができる。情報は、プロセッサ上で実行される一連の命令として表されることが多く、別のネットワークから受信されたり、別のネットワークへ出力されたりしうる。インターフェースカード（または同様のデバイス）と、プロセッサ１０２によって実装（例えば、実行／実施）される適切なソフトウェアとを用いて、コンピュータシステム１００を外部ネットワークに接続し、標準プロトコルに従ってデータを転送することができる。例えば、本明細書に開示された様々な処理の実施形態は、プロセッサ１０２上で実行されてもよいし、処理の一部を共有するリモートプロセッサと共に、ネットワーク（インターネット、イントラネットワーク、または、ローカルエリアネットワークなど）上で実行されてもよい。さらなるマスストレージデバイス（図示せず）が、ネットワークインターフェース１１６を通してプロセッサ１０２に接続されてもよい。
【００２５】
補助Ｉ／Ｏデバイスインターフェース（図示せず）が、コンピュータシステム１００と共に用いられてよい。補助Ｉ／Ｏデバイスインターフェースは、プロセッサ１０２がデータを送信すること、ならびに、より典型的には、他のデバイス（マイクロホン、タッチセンサ方式ディスプレイ、トランスデューサカードリーダ、テープリーダ、音声または手書き認識装置、バイオメトリクスリーダ、カメラ、携帯型マスストレージデバイス、および、他のコンピュータなど）からデータを受信することを可能にする汎用インターフェースおよびカスタマイズされたインターフェースを含みうる。
【００２６】
さらに、本明細書に開示された様々な実施形態は、さらに、様々なコンピュータ実装された動作を実行するためのプログラムコードを備えたコンピュータ読み取り可能な媒体を含むコンピュータストレージ製品に関する。コンピュータ読み取り可能な媒体は、データを格納できる任意のデータストレージデバイスであり、そのデータは、後にコンピュータシステムによって読み出されうる。コンピュータ読み取り可能な媒体の例は、以下の媒体すべてを含むがそれらに限定されない。ハードディスク、フレキシブルディスクおよび磁気テープなどの磁気媒体、ＣＤ−ＲＯＭディスクなどの光学媒体、光学ディスクなどの磁気光学媒体、ならびに、特定用途向け集積回路（ＡＳＩＣ）、プログラム可能論理デバイス（ＰＬＤ）およびＲＯＭ／ＲＡＭデバイスなど、特別に構成されたハードウェアデバイス。プログラムコードの例としては、例えば、コンパイラによって生成されるマシンコード、または、インタープリタを用いて実行できる高水準コード（例えば、スクリプト）を含むファイルが挙げられる。
【００２７】
図１Ａに示したコンピュータシステムは、本明細書に開示された様々な実施形態と共に利用するのに適切なコンピュータシステムの一例にすぎない。かかる利用に適した他のコンピュータシステムは、より多いまたは少ないサブシステムを含みうる。さらに、バス１１４は、サブシステムをリンクさせるよう機能する任意の相互接続スキームの例である。異なる構成のサブシステムを有する他のコンピュータアーキテクチャが利用されてもよい。
【００２８】
図１Ｂは、文書クエリングおよびデータインデックス化システムの一実施形態を用いた検索エンジンを示す概略図である。検索エンジン１５０は、以下のような１または複数の計算デバイスを用いて実装されてよい。パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたは携帯型デバイス、フラットパネルデバイス、マルチプロセッサシステム、マイクロプロセッサを用いたシステム、セットトップボックス、プログラム可能な消費者電子デバイス、ネットワークＰＣ、ミニコンピュータ、大規模コンピュータ、専用デバイス、任意の前述のシステムまたはデバイスを含む分散型計算環境、もしくは、１または複数のプロセッサと、プロセッサに接続されてプロセッサに命令を提供するよう構成されたメモリとを備えたその他のハードウェア／ソフトウェア／ファームウェアの組み合わせ。
【００２９】
図の例において、検索エンジン１５０は、クロールモジュール１５２、インデックス（インデックス化）モジュール１５４、クエリングモジュール１５６、および、ユーザインターフェースモジュール１５８を備える。クロールモジュールは、ウェブクローラを用いてインターネット上を巡回することによってウェブページ情報を発見および収集するよう適合される。インデックスモジュールは、クロールモジュールによって収集されたウェブページからインデックス項目を抽出するよう適合される。インデックスは、文書を表すために用いられ、文書データベースのインデックステーブルに格納される。クエリングモジュールは、ユーザのクエリに従って、インデックスデータベース内の文書を取得し、出力結果をソートし、ユーザのクエリ要求に従って出力フィードバック情報を合理的に出力するよう適合される。インターフェースモジュールは、ユーザのクエリ要求を受信し、ユーザにクエリ結果を戻すよう適合される。本発明の以下の実施形態では、主に、検索エンジンの文書インデックス化およびクエリング機能の処理について記載する。
【００３０】
図２は、文書インデックス化処理の一実施形態を示すフローチャートである。
【００３１】
工程２１０では、文書が取得される。この例では、ウェブページなどの文書が検索エンジンのウェブクローラによってインターネットから取得される。次いで、文書は、検索エンジンの一部であるかもしくは検索エンジンに接続されているデータストレージに格納される。データストレージの例としては、複数のデータベース、複数のディスクなどが挙げられる。検索エンジンは、インデックス化が行われる前に、データストレージから文書を読み出す。いくつかの実施形態において、文書は、中国語などの文字ベースの言語で表されている。
【００３２】
工程２２０では、単成分分割動作が文書に対して実行される。換言すると、各文字が、個々の分割単位を形成する。
【００３３】
工程２３０では、単成分パーティション内の文字は、フィルタ文字であるか否かを判定するために、フィルタ文字リストと比較される。
【００３４】
フィルタ文字は、クエリ処理中に検索エンジンによって除外される高頻度の文字である。検索エンジンに格納された文書内にフィルタ文字が高頻度で出現するために、フィルタ文字がクエリに含まれる場合には、大量のシステムリソースが消費されることになる。したがって、統計的に高頻度の文字が予め決定されて、検索エンジンのフィルタ文字リスト内に格納される。インデックス化またはクエリ動作を実行する前に、単成分パーティション内の文字は、フィルタ文字であるか否かを判定するために、フィルタ文字リスト内の文字と比較される。例えば、「中国股市」（「中国株式市場」）内の「市」（「市場」）は、検索エンジンのフィルタ文字リスト内に見出されるため、「市」（「市場」）は、フィルタ文字であり、クエリ動作またはインデックス化動作から除外される。
【００３５】
文書の単成分分割動作は、繰り返し実行される。それらの動作後に、一連の単成分パーティションが取得される。各単成分パーティションは、フィルタ文字か否かを判定するために、フィルタ文字リストと比較される。インデックス化される文書が、「市」（「市場」）などの高頻度文字（フィルタ文字とも呼ばれる）のみを有する場合、その文書に対してはインデックスが構築されない。
【００３６】
工程２４０では、単成分パーティション内の文字がフィルタ文字である場合、単成分パーティションをその単成分パーティションに隣接する少なくとも１つの単成分パーティションと結びつけることによって、多成分パーティション（Ｎ成分パーティションとも呼ばれる）が形成され、次いで、多成分パーティションはインデックス化される。本明細書で用いられているように、多成分パーティションとは、少なくとも２つの隣接する単成分パーティションによって形成されたパーティションを指す。
【００３７】
いくつかの実施形態では、単成分パーティションをそれに隣接する単成分パーティションと結びつけることによって、二成分パーティションが形成される。単成分パーティションＰが高頻度フィルタ文字であると判定されたとすると、Ｐが文書内の最初の単成分パーティションである場合、Ｐをその次の単成分パーティションと結びつけることによって、二成分パーティションが形成される。Ｐが文書内の最後の単成分パーティションである場合、Ｐをその前の単成分パーティションと結びつけることによって、二成分パーティションが形成される。Ｐが文書内の最初の単成分パーティションでも最後の単成分パーティションでもなく、文書の中ほどのどこかに出現する場合、Ｐをその前の単成分パーティションおよびその後の単成分パーティションとそれぞれ結びつけることによって、２つの二成分パーティションが形成される。１または複数の二成分パーティションはインデックス化される。例えば、「我」（「私」）は高頻度フィルタ文字であり、単成分パーティションである。「我」が文書内の最初の単成分パーティションである場合、「我」は、その後の単成分パーティション（「的」（「〜の」：所有を表す語）など）と結びついて、インデックス化される二成分パーティション「我的」（「私の」）を形成する。
【００３８】
同様に、いくつかの実施形態において、三成分パーティションが形成されてもよい。例えば、三成分パーティション「中国人」は、３つの単成分パーティション「中」、「国」、および、「人」から形成される。同様に、四成分以上のパーティションが形成されてもよい。
【００３９】
工程２５０では、単成分パーティション内の文字がフィルタ文字でない場合、この文字は直接インデックス化される。
【００４０】
工程２４０および工程２５０は、文書内のすべての単成分パーティションが処理されるまで繰り返されてよい。処理２００は、検索インデックスを作成するために、複数の文書に対して繰り返されてよい。
【００４１】
図３は、文書インデックス化処理の別の実施形態を示すフローチャートである。この実施形態では、文書のインデックス化処理を例示するために、二成分パーティションを用いる。三成分パーティションまたは四成分パーティションなど、他の多成分パーティションが、同様に実施されうる。
【００４２】
工程３１０では、フィルタ文字リストが予め決定される。いくつかの実施形態では、文字の出現頻度は、大量のサンプルインターネット文書から計算される。文字がフィルタ文字であるか否か、および、文字がフィルタ文字リストに含まれるべきか否かを判定するための基準は、サンプルセットの文書内での文字の出現頻度に従って設定されてよい。例えば、サンプルインターネット文書のセットは、６００万の文書からなる。単成分分割動作は、これら６００万の文書の各々において実行される。単成分パーティション内の文字は、これらの文書内での出現頻度に従ってソートされ、最も出現頻度の高いＸ個（例えば、１００個）の文字をリストに追加することによって、高頻度文字リストが構築される。フィルタ文字リストは、必要に応じて時間と共に動的に調整されてよく、例えば、さらなる文書がサンプルセットに追加された時、または、異なるサンプルセットを取得した時などに調整される。
【００４３】
工程３２０では、インデックス化される文書が取得される。
【００４４】
工程３３０では、文書の複数の単成分パーティションを取得するために、単成分分割動作が、文書に対して実行される。
【００４５】
工程３４０では、単成分パーティションがトラバース（詳細に検討）される。すなわち、文書内の各単成分パーティションに対して、工程３４２から工程３４６が実行される。
【００４６】
工程３４２では、フィルタ文字であるか否かを判定するために、文書の単成分パーティションが、フィルタ文字リスト内で検索される。
【００４７】
単成分パーティションがフィルタ文字である場合、工程３４４において、その単成分パーティションを当該単成分パーティションに隣接する単成分パーティションと結びつけることによって、二成分パーティションが形成され、この二成分パーティションは、キーワードインデックス化、ハッシュ値インデックス化などの標準的なインデックス化技術を用いてインデックス化される。
【００４８】
単成分パーティションがフィルタ文字でない場合、工程３４６では、この単成分パーティションは直接インデックス化される。
【００４９】
工程３４８では、すべての単成分パーティションがトラバースされた場合、文書のインデックス化処理は完了する。その場合、処理は工程３５０で終了する。そうでない場合、制御は、工程３４０に戻り、次の単成分パーティションが処理される。
【００５０】
いくつかの実施形態では、文書内の単成分パーティションは、以下の擬似コードの例に従って処理される：
Token token=getCurrentToken();    //現在のパーティションを取得する
If(isFreqWord(token))            //現在のパーティションが高頻度単語である場合
{
Token token2=mergeToken(prevToken,token);//前のパーティションと共に新しい単語を形成する
indexToken(token2);//インデックスを構築する
Token token3=mergeToken(nextToken,token);//次のパーティションと共に新しい単語を形成する
indexToken(token3);                      //インデックスを構築する
}
else
indexToken(token);                        //高頻度単語でない場合にインデックスを直接構築する
【００５１】
上記の処理で構築されたインデックスは、高頻度文字だけのためのインデックス項目を含まず、その代わり、高頻度文字およびそれらに隣接する文字から、二成分パーティションが形成され、これらの二成分パーティションがインデックス化される。したがって、その後のデータクエリの精度が、従来の方法に比べて大きく改善される。
【００５２】
様々な実施形態において、文書は、文書インデックス化方法の上記の実施形態によって構築されたインデックスを用いてクエリングされる。
【００５３】
図４は、検索エンジンのデータクエリ処理の一実施形態を示すフローチャートである。
【００５４】
工程４１０では、データクエリが受信される。例えば、クエリは、インターネットウェブサイトからユーザによって入力され、検索エンジンによって受信される。
【００５５】
工程４２０では、複数の単成分パーティションを取得するために、単成分分割動作が、データクエリに対して実行される。
【００５６】
工程４３０では、フィルタ文字であるか否かを判定するために、各単成分パーティションがフィルタ文字リストと比較される。フィルタ文字である場合、制御は工程４４０に進む。フィルタ文字でない場合、制御は工程４５０に進む。
【００５７】
単成分パーティションがフィルタ文字である場合、工程４４０では、多成分パーティションを形成するために、単成分パーティションを少なくとも１つの隣接する単成分パーティションと結びつけて、多成分パーティションが単成分パーティションに対して形成される。
【００５８】
工程４４５では、以前に構築されたインデックスが、この多成分パーティションを用いて検索され、クエリ結果が取得される。例えば、処理２００または３００と同様のインデックス化処理によって以前に構築されたインデックスが、クエリと一致する文書を特定するために、キーワードマッチングなど従来の技術を用いて検索される（ここで、多成分パーティションが検索キーワードとして用いられる）。
【００５９】
いくつかの実施形態では、単成分パーティションをそれに隣接する単成分パーティションと結びつけることによって、二成分パーティションが形成される。単成分パーティションＰが高頻度フィルタ文字であると判定されたとすると、Ｐが文書内の最初の単成分パーティションである場合、Ｐをその次の単成分パーティションと結びつけることによって、二成分パーティションが形成される。Ｐが文書内の最初の単成分パーティションでない場合、Ｐをその前の単成分パーティションと結びつけることによって、二成分パーティションが形成される。
【００６０】
単成分パーティションがフィルタ文字でない場合、工程４５０において、以前に構築されたインデックスがこの単成分パーティションについて検索され、クエリ結果が取得される。
【００６１】
工程４６０では、単成分パーティションおよび多成分パーティションからのクエリ結果が組み合わされて最終的な検索結果を形成し、その最終的な結果は、任意選択的にユーザに提示される。
【００６２】
図５は、検索エンジンのデータクエリ処理の別の実施形態を示すフローチャートである。この実施形態では、クエリング処理を例示するために、二成分および三成分パーティションを用いる。ただし、二成分パーティション以外の多成分パーティションを同様に利用できる。
【００６３】
工程５１０では、クエリが受信される。
【００６４】
工程５２０では、複数の単成分パーティションを取得するために、単成分分割動作が、クエリに対して実行される。
【００６５】
工程５３０では、クエリの単成分パーティションがトラバースされる。換言すると、文書内の各単成分パーティションに対して、工程５３２〜５３６が実行される。
【００６６】
工程５３２では、フィルタ文字であるか否かを判定するために、文書の単成分パーティションが、フィルタ文字リストと比較される。
【００６７】
工程５３４では、単成分パーティションがフィルタ文字である場合、単成分パーティションを当該単成分パーティションに隣接する少なくとも１つの他の単成分パーティションと結びつけることによって、二成分パーティションが形成され、インデックスにおいて、この二成分パーティションが検索され、クエリ結果が取得される。
【００６８】
単成分パーティションがフィルタ文字でない場合、工程５３６において、インデックスがこの単成分パーティションについて検索され、クエリ結果が取得される。
【００６９】
いくつかの実施形態では、工程５３８が完了した後、単成分パーティションの処理と同様の方法で、二成分パーティションがさらに処理される。二成分パーティションを含む以前に構築されたリストに基づいて、各二成分パーティションがフィルタ単語またはフレーズであるか否かが判定され、そうである場合、さらなる検索は必要でない。そうでない場合、いくつかの実施形態では、二成分パーティションと、１または複数の隣接する単成分パーティションとに基づいて、１または複数の新たな三成分パーティションが形成され、いくつかの実施形態では、二成分パーティションと、１または複数の隣接する二成分パーティションとに基づいて、１または複数の新たな四成分パーティションが形成される。
【００７０】
工程５４０では、すべてのパーティションのクエリ結果が組み合わされる。クエリ結果は、任意選択的に、事前設定された条件（例えば、上位２０個の独自の結果が戻されるなど）に従ってユーザに返され表示される。
【００７１】
いくつかの実施形態では、クエリの単成分パーティションは、以下の擬似コードの例に従って処理される：
Token token=getCurrentToken();    //現在のパーティションを取得する
If(isFreqWord(token))            //現在のパーティションが高頻度フィルタ文字である場合
｛
Token token2;
If(isFirstWord(token))
token2=mergeToken(nextToken,token);//トークンが文章の始めにあれば後方と結びつける
else
token2=mergeToken(prevToken,token);//トークンが文章の始めになければ前方と結びつける
doTokenSearch(token2);            //新たに結びつけられたパーティションをクエリする
｝
else
doTokenSearch(token);              //高頻度フィルタ文字でない場合に直接クエリを行う
【００７２】
上記の実施形態に従って実行されたクエリについては、インデックスが構築される前に、すべての高頻度文字が他の単成分パーティションと結びつけられて、多成分パーティションが形成されるため、高頻度文字がインデックス内に単独で存在しないことが保証される。したがって、高頻度文字の検索が避けられることから、検索エンジンリソースが節約され、クエリ結果の精度も改善される。
【００７３】
実施形態は、インデックス化およびクエリの例として漢字を用いているが、本方法は、中国語以外の言語におけるインデックス化およびクエリング動作を実行する検索エンジンにも適用される。例えば、中国語に基づく検索エンジンでは、単成分パーティションは、文書またはクエリ内の各漢字を指す。データクエリ「中国股市」（「中国株式市場」）に対する分割動作を実行することによって取得される単成分パーティションは、「中」「国」「股」（「株式」）、および、「市」（「市場」）である。同様に、英語に基づく検索エンジンでは、「Ｃｈｉｎｅｓｅ  Ｓｔｏｃｋ  Ｍａｒｋｅｔ」というクエリは、単成分パーティション「Ｃｈｉｎｅｓｅ」、「Ｓｔｏｃｋ」、および、「Ｍａｒｋｅｔ」に分割できる。「ｓｔｏｃｋ」が、１組の文書内での単語の出現頻度に従って構築されたフィルタ文字リスト内の高頻度単語である場合、「ｓｔｏｃｋ」は、「Ｃｈｉｎｅｓｅ」および「Ｍａｒｋｅｔ」とそれぞれ結びついて、２つの新たな多成分パーティション「Ｃｈｉｎｅｓｅ  Ｓｔｏｃｋ」および「Ｓｔｏｃｋ  ｍａｒｋｅｔ」を形成する。したがって、クエリの最終的なパーティションは、それぞれ、「Ｃｈｉｎｅｓｅ」、「Ｃｈｉｎｅｓｅ  Ｓｔｏｃｋ」、「Ｓｔｏｃｋ  Ｍａｒｋｅｔ」、および、「Ｍａｒｋｅｔ」である。「Ｃｈｉｎｅｓｅ  Ｓｔｏｃｋ  Ｍａｒｋｅｔ」というフレーズが検索エンジンによってクエリされる時、検索エンジンは、「Ｃｈｉｎｅｓｅ」、「Ｃｈｉｎｅｓｅ  Ｓｔｏｃｋ」、「Ｓｔｏｃｋ  Ｍａｒｋｅｔ」、および、「Ｍａｒｋｅｔ」をクエリして、クエリ結果が組み合わせられ、組み合わせたクエリ結果からの独自の項目が、ユーザに対して表示される。
【００７４】
上記の文書インデックス化およびデータクエリ処理の実施形態に対応して、本願は、さらに、文書インデックスシステムおよびデータクエリシステムの実施形態を提供する。文書インデックス化およびデータクエリのためのシステムの実施形態の実装例について、以下で説明する。システムは、複数のモジュールまたはユニットを備えるものとして記載される。モジュールまたはユニットは、１または複数のプロセッサ上で実行されるソフトウェアコンポーネントとして、特定の機能を実行するよう設計されたプログラム可能論理デバイスおよび／または特定用途向け集積回路などのハードウェアとして、もしくは、それらの組み合わせとして実装することができる。いくつかの実施形態において、モジュール／ユニット／サブユニットは、コンピュータデバイス（パーソナルコンピュータ、サーバ、ネットワーク装置など）に本発明の実施形態に記載された方法を実行させるための複数の命令など、不揮発性記憶媒体（光学ディスク、フラッシュ記憶装置、携帯用ハードディスクなど）に格納することができるソフトウェア製品の形態で具現化されてよい。モジュールまたはユニットは、単一のデバイス上に実装されてもよいし、複数のデバイスにわたって分散されてもよい。モジュールまたはユニットの機能は、互いに統合されてもよいし、複数のサブモジュールまたはサブユニットにさらに分割されてもよい。
【００７５】
図６は、文書をインデックス化するよう構成されたシステムの一実施形態を示すブロック図である。システム６００は、以下のような１または複数の計算デバイスを用いて実装されてよい。パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたは携帯型デバイス、フラットパネルデバイス、マルチプロセッサシステム、マイクロプロセッサを用いたシステム、セットトップボックス、プログラム可能な消費者電子デバイス、ネットワークＰＣ、ミニコンピュータ、大規模コンピュータ、専用デバイス、任意の前述のシステムまたはデバイスを含む分散型計算環境、もしくは、１または複数のプロセッサと、プロセッサに接続されてプロセッサに命令を提供するよう構成されたメモリとを備えたその他のハードウェア／ソフトウェア／ファームウェアの組み合わせ。
【００７６】
図の例において、システム６００は、取得ユニット６１０、分割ユニット６２０、判定ユニット６３０、および、インデックス化ユニット６４０を備える。取得ユニット６１０は、インデックス化される文書を取得するよう適合される。分割ユニット６２０は、単成分パーティションを得るために、取得ユニット６１０によって取得された文書に対して分割動作を実行するよう適合される。判定ユニット６３０は、各単成分パーティションがフィルタ文字であるか否かを判定するよう適合される。単成分パーティションがフィルタ文字である場合、インデックス化ユニット６４０は、単成分パーティションとその単成分パーティションに隣接する少なくとも１つの単成分パーティションとを結びつけることによって多成分パーティションを形成した後に、多成分パーティションのためのインデックスを構築するよう適合される。単成分パーティションがフィルタ文字でない場合、インデックス（化）ユニット６４０は、単成分パーティションのためのインデックスを直接構築するよう適合される。
【００７７】
図７は、文書をインデックス化するよう構成されたシステムの別の実施形態を示すブロック図である。
【００７８】
図の例において、システム７００は、事前設定ユニット７１０、ロードユニット７２０、取得ユニット７３０、分割ユニット７４０、判定ユニット７５０、および、インデックス（化）ユニット７６０を備える。
【００７９】
事前設定ユニット７１０は、フィルタ文字リストを予め設定するよう適合される。ロードユニット７２０は、事前設定ユニット７１０内のフィルタ文字リストをロードするよう適合される。取得ユニット７３０は、インデックス化される文書を取得するよう適合される。分割ユニット７４０は、単成分パーティションを得るために、取得ユニット７３０によって取得された文書に対して分割動作を実行するよう適合される。判定ユニット７５０は、各単成分パーティションがフィルタ文字であるか否かを判定するよう適合される。いくつかの実施形態において、判定ユニット７５０は、さらに、単成分パーティションをトラバースするためのパーティショントラバースユニットと、フィルタ文字リストを検索することによって各単成分パーティションがフィルタ文字であるか否かを判定するためのフィルタ文字検索ユニットとを備えてよい。
【００８０】
インデックス化ユニット７６０は、単成分パーティションとその単成分パーティションに隣接する少なくとも１つの単成分パーティションとを結びつけることによって多成分パーティションを形成した後に、単成分パーティションがフィルタ文字である場合、多成分パーティションのためのインデックスを構築し、単成分パーティションがフィルタ文字でない場合、単成分パーティションのための索引を直接構築するよう適合される。いくつかの実施形態において、インデックス化ユニット７６０は、単成分パーティションとその単成分パーティションに隣接する単成分パーティションとを結びつけることによって二成分パーティションを形成し、その二成分パーティションに対してインデックスが構築される。
【００８１】
上記の文書インデックス化システムによって構築されたインデックスは、検索エンジン内のデータクエリのためのシステムが検索動作を実行するために利用する。  
【００８２】
図８は、検索エンジンのためにデータクエリを実行するよう適合されたシステムの一実施形態を示すブロック図である。システム８００は、取得ユニット８１０、分割ユニット８２０、判定ユニット８３０、検索ユニット８４０、および、結合ユニット８５０を備える。
【００８３】
取得ユニット８１０は、クエリされるデータを取得するよう適合される。分割ユニット８２０は、単成分パーティションを得るために、取得ユニットによって取得されたデータに対して分割動作を実行するよう適合される。判定ユニット８３０は、各単成分パーティションがフィルタ文字であるか否かを判定するよう適合される。検索ユニット８４０は、単成分パーティションとその単成分パーティションに隣接する少なくとも１つの単成分パーティションから多成分パーティションを形成し、単成分パーティションがフィルタ文字であると判定ユニット８３０によって判定された場合、多成分パーティションに従ったインデックスを検索し、単成分パーティションがフィルタ文字でない場合、システム８００は、単成分パーティションに従ったインデックスを直接検索するよう適合される。結合ユニット８５０は、インデックスを検索した後、検索ユニット８４０によって取得されたクエリ結果を組み合わせるよう適合される。
【００８４】
図９は、検索エンジンのためにデータクエリングを実行するよう適合されたシステムの別の実施形態を示すブロック図である。システム９００は、ロードユニット９１０、取得ユニット９２０、分割ユニット９３０、判定ユニット９４０、検索ユニット９５０、および、結合ユニット９６０を備える。
【００８５】
ロードユニット９１０は、予め設定されたフィルタ文字リストをロードするよう適合される。取得ユニット９２０は、クエリされるデータを取得するよう適合される。分割ユニット９３０は、取得ユニット９２０によって取得されたデータに対して分割動作を実行して、単成分パーティションを得るよう適合される。判定ユニット９４０は、各単成分パーティションがフィルタ文字であるか否かを判定するよう適合される。いくつかの実施形態において、判定ユニット９４０は、さらに、単成分パーティションをトラバースするよう適合されたパーティショントラバースユニットと、フィルタ文字リストを検索することによって各単成分パーティションがフィルタ文字であるか否かを判定するよう適合されたフィルタ文字検索ユニットとを備えてよい。
【００８６】
検索ユニット９５０は、単成分パーティションとその単成分パーティションに隣接する少なくとも１つの単成分パーティションとを結びつけることによって多成分パーティションを形成し、単成分パーティションがフィルタ文字であると判定ユニット９４０によって判定された場合、多成分パーティションに従うインデックスを検索し、また、単成分パーティションがフィルタ文字ではないと判定ユニット９４０によって判定された場合、単成分パーティションに従うインデックスを検索するよう適合される。いくつかの実施形態において、検索ユニット９５０は、単成分パーティションとその単成分パーティションに隣接する単成分パーティションとを結びつけることによって二成分パーティションを形成するよう適合され、検索ユニットは二成分パーティションに従ったインデックスを検索する。結合ユニット９６０は、インデックスを検索した後、検索ユニット９５０によって取得されたクエリ結果を組み合わせるよう適合される。
【００８７】
上述のシステムの実施形態は、高頻度単成分パーティションから、限られた多成分パーティションを形成することによって、高頻度文字のクエリを低頻度文字のクエリに変換する。したがって、各クエリによって利用されるシステムリソースを削減することができるが、クエリ結果の精度は犠牲にならない。検索エンジンのクエリ性能は、従来の方法と比較して大幅に改善される。
【００８８】
本願は、本願の実施形態に従った方法、システム、および、コンピュータプログラム製品のフローチャートおよび／またはブロック図を参照して説明されている。フローチャートおよび／またはブロック図内の各フローおよび／またはブロック、ならびに、フローチャートおよび／またはブロック図内のフローおよび／またはブロックの組み合わせは、コンピュータプログラム命令で実現されうることを理解されたい。実際に、本願全体は、コンピュータによって実行されるコンピュータ実行可能な命令（例えば、プログラムモジュールなど）の一般的な文脈で説明できる。一般に、プログラムモジュールは、特定のタスクの実行または特定の抽象データ型の実施のためのルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを備える。あるいは、本発明は、分散型コンピュータ環境に実装されてよく、その場合、通信ネットワークを介して接続されたリモート処理デバイスがタスクを実行する。分散型コンピュータ環境において、プログラムモジュールは、ストレージデバイスを備えるローカルあるいはリモートの記憶媒体に格納されてよい。
【００８９】
上述の実施形態は、理解しやすいようにいくぶん詳しく説明されているが、本発明は、提供された詳細事項に限定されるものではない。本発明を実施する多くの代替方法が存在する。開示された実施形態は、例示であり、限定を意図するものではない。
適用例１：文書インデックスを生成するための方法であって、インデックス化される文書を取得し、前記文書に対して単成分分割動作を実行して、複数の単成分パーティションを取得し、前記複数の単成分パーティションの各単成分パーティションに対して、前記各単成分パーティションがフィルタ文字であるか否かを判定し、前記各単成分パーティションがフィルタ文字である場合に、前記単成分パーティションを前記単成分パーティションに隣接する少なくとも１つの他の単成分パーティションと結びつけることによって多成分パーティションを形成し、前記多成分パーティションをインデックス化し、前記単成分パーティションがフィルタ文字ではない場合に、前記単成分パーティションをインデックス化すること、を備える、方法。
適用例２：適用例１に記載の方法であって、さらに、複数の文書内の文字の出現頻度に従って、フィルタ文字リストを予め設定することを備える、方法。
適用例３：適用例２に記載の方法であって、単成分パーティションがフィルタ文字であるか否かの判定は、前記単成分パーティションを前記予め設定されたフィルタ文字リストと比較することを含む、方法。
適用例４：適用例１に記載の方法であって、多成分パーティションの形成は、前記単成分パーティションを前記単成分パーティションに隣接する少なくとも１つの他の単成分パーティションと結びつけることによって、二成分パーティションを形成することを含む、方法。
適用例５：適用例４に記載の方法であって、二成分パーティションの形成は、さらに、前記単成分パーティションが前記文書内の最初の単成分パーティションである場合に、前記単成分パーティションを次の単成分パーティションと結びつけることによって、二成分パーティションを形成し、前記単成分パーティションが前記文書内の最後の単成分パーティションである場合に、前記単成分パーティションを前の単成分パーティションと結びつけることによって、二成分パーティションを形成し、前記単成分パーティションが前記文書内の最初の単成分パーティションでも最後の単成分パーティションでもない場合に、前記単成分パーティションを前の単成分パーティションと結びつけることによって第１の二成分パーティションを形成し、前記単成分パーティションを後の単成分パーティションと結びつけることによって第２の二成分パーティションを形成すること、を含む、方法。
適用例６：データをクエリングするための方法であって、データクエリを受信し、前記データクエリに対して単成分分割動作を実行して、複数の単成分パーティションを取得し、前記複数の単成分パーティションの各単成分パーティションに対して、前記各単成分パーティションがフィルタ文字であるか否かを判定し、前記単成分パーティションがフィルタ文字である場合に、前記単成分パーティションを前記単成分パーティションに隣接する少なくとも１つの単成分パーティションと結びつけることによって多成分パーティションを形成し、前記多成分パーティションを用いて、予め設定されたインデックスを検索して、前記多成分パーティションに対応する検索結果を取得し、前記単成分パーティションがフィルタ文字ではない場合に、前記単成分パーティションを用いて、前記予め設定されたインデックスを検索して、前記単成分パーティションに対応する検索結果を取得し、前記検索結果を結びつけて、最終的なクエリ検索結果を形成すること、を備える、方法。
適用例７：適用例６に記載の方法であって、前記予め設定されたインデックスは、インデックス化される文書を取得し、前記文書に対してインデックス化単成分分割動作を実行して、第２の複数の単成分パーティションを取得し、前記第２の複数の単成分パーティションの各単成分パーティションに対して、前記各単成分パーティションがフィルタ文字であるか否かを判定し、前記各単成分パーティションがフィルタ文字である場合に、前記各単成分パーティションを前記単成分パーティションに隣接する少なくとも１つの他の単成分パーティションと結びつけることによって第２の多成分パーティションを形成し、前記第２の多成分パーティションをインデックス化し、前記各単成分パーティションがフィルタ文字ではない場合に、前記各単成分パーティションをインデックス化することによって構築される、方法。
適用例８：適用例６に記載の方法であって、前記単成分パーティションがフィルタ文字であるか否かの判定は、前記単成分パーティションを予め設定されたフィルタ文字リストと比較することを含む、方法。
適用例９：適用例６に記載の方法であって、前記多成分パーティションの形成は、前記単成分パーティションを前記単成分パーティションに隣接する単成分パーティションと結びつけることによって、二成分パーティションを形成することを含む、方法。
適用例１０：適用例９に記載の方法であって、二成分パーティションの形成は、さらに、前記単成分パーティションが前記文書内の最初の単成分パーティションである場合に、前記単成分パーティションと次の単成分パーティションとを結びつけることによって、二成分パーティションを形成し、前記単成分パーティションが前記文書内の最後の単成分パーティションである場合に、前記単成分パーティションと前の単成分パーティションとを結びつけることによって、二成分パーティションを形成し、前記単成分パーティションが前記文書内の最初の単成分パーティションでも最後の単成分パーティションでもない場合に、前記単成分パーティションを前の単成分パーティションと結びつけることによって第１の二成分パーティションを形成し、前記単成分パーティションを後の単成分パーティションと結びつけることによって第２の二成分パーティションを形成すること、を含む、方法。
適用例１１：文書インデックス化システムであって、インターフェースに接続されている１または複数のプロセッサであって、インデックス化される文書を取得し、前記文書に対して単成分分割動作を実行して、複数の単成分パーティションを取得し、前記複数の単成分パーティションの各単成分パーティションに対して、前記各単成分パーティションがフィルタ文字であるか否かを判定し、前記各単成分パーティションがフィルタ文字である場合に、前記単成分パーティションを前記単成分パーティションに隣接する少なくとも１つの他の単成分パーティションと結びつけることによって多成分パーティションを形成し、前記多成分パーティションをインデックス化し、前記単成分パーティションがフィルタ文字ではない場合に、前記単成分パーティションをインデックス化することを実行するよう構成されている１または複数のプロセッサと、前記１または複数のプロセッサに接続され、前記プロセッサに命令を提供するよう構成されている１または複数のメモリと、を備える、システム。
適用例１２：適用例１１に記載のシステムであって、前記１または複数のプロセッサは、さらに、複数の文書内の文字の出現頻度に従って、フィルタ文字リストを予め設定するよう構成されている、システム。
適用例１３：適用例１２に記載のシステムであって、単成分パーティションがフィルタ文字であるか否かの判定は、前記単成分パーティションを前記予め設定されたフィルタ文字リストと比較することを含む、システム。
適用例１４：適用例１１に記載のシステムであって、多成分パーティションの形成は、前記単成分パーティションを前記単成分パーティションに隣接する少なくとも１つの他の単成分パーティションと結びつけることによって、二成分パーティションを形成することを含む、システム。
適用例１５：適用例１４に記載のシステムであって、二成分パーティションの形成は、さらに、前記単成分パーティションが前記文書内の最初の単成分パーティションである場合に、前記単成分パーティションを次の単成分パーティションと結びつけることによって、二成分パーティションを形成し、前記単成分パーティションが前記文書内の最後の単成分パーティションである場合に、前記単成分パーティションを前の単成分パーティションと結びつけることによって、二成分パーティションを形成し、前記単成分パーティションが前記文書内の最初の単成分パーティションでも最後の単成分パーティションでもない場合に、前記単成分パーティションを前の単成分パーティションと結びつけることによって第１の二成分パーティションを形成し、前記単成分パーティションを後の単成分パーティションと結びつけることによって第２の二成分パーティションを形成すること、を含む、システム。
適用例１６：データクエリシステムであって、インターフェースに接続されている１または複数のプロセッサであって、前記データクエリに対して単成分分割動作を実行して、複数の単成分パーティションを取得し、前記複数の単成分パーティションの各単成分パーティションに対して、前記各単成分パーティションがフィルタ文字であるか否かを判定し、前記単成分パーティションがフィルタ文字である場合に、前記単成分パーティションを前記単成分パーティションに隣接する少なくとも１つの単成分パーティションと結びつけることによって多成分パーティションを形成し、前記多成分パーティションを用いて、予め設定されたインデックスを検索して、前記多成分パーティションに対応する検索結果を取得し、前記単成分パーティションがフィルタ文字ではない場合に、前記単成分パーティションを用いて、前記予め設定されたインデックスを検索して、前記単成分パーティションに対応する検索結果を取得し、前記検索結果を結びつけて、最終的なクエリ検索結果を形成することを実行するよう構成されている１または複数のプロセッサと、前記１または複数のプロセッサに接続され、前記プロセッサに命令を提供するよう構成されている１または複数のメモリと、を備える、システム。
適用例１７：適用例１６に記載のシステムであって、前記予め設定されたインデックスは、インデックス化される文書を取得し、前記文書に対してインデックス化単成分分割動作を実行して、第２の複数の単成分パーティションを取得し、前記第２の複数の単成分パーティションの各単成分パーティションに対して、前記各単成分パーティションがフィルタ文字であるか否かを判定し、前記各単成分パーティションがフィルタ文字である場合に、前記各単成分パーティションを前記単成分パーティションに隣接する少なくとも１つの他の単成分パーティションと結びつけることによって第２の多成分パーティションを形成し、前記第２の多成分パーティションをインデックス化し、前記各単成分パーティションがフィルタ文字ではない場合に、前記各単成分パーティションをインデックス化することによって構築される、システム。
適用例１８：適用例１６に記載のシステムであって、前記単成分パーティションがフィルタ文字であるか否かの判定は、前記単成分パーティションを前記予め設定されたフィルタ文字リストと比較することを含む、システム。
適用例１９：適用例１６に記載の方法であって、前記多成分パーティションの形成は、前記単成分パーティションを前記単成分パーティションに隣接する単成分パーティションと結びつけることによって、二成分パーティションを形成することを含む、方法。
適用例２０：適用例１９に記載の方法であって、二成分パーティションの形成は、さらに、前記単成分パーティションが前記文書内の最初の単成分パーティションである場合に、前記単成分パーティションと次の単成分パーティションとを結びつけることによって、二成分パーティションを形成し、前記単成分パーティションが前記文書内の最後の単成分パーティションである場合に、前記単成分パーティションと前の単成分パーティションとを結びつけることによって、二成分パーティションを形成し、前記単成分パーティションが前記文書内の最初の単成分パーティションでも最後の単成分パーティションでもない場合に、前記単成分パーティションを前の単成分パーティションと結びつけることによって第１の二成分パーティションを形成し、前記単成分パーティションを後の単成分パーティションと結びつけることによって第２の二成分パーティションを形成すること、を含む、方法。
【図１Ａ】
0005616444.tif 000002
【図１Ｂ】
0005616444.tif 000003
【図２】
0005616444.tif 000004
【図３】
0005616444.tif 000005
【図４】
0005616444.tif 000006
【図５】
0005616444.tif 000007
【図６】
0005616444.tif 000008
【図７】
0005616444.tif 000009
【図８】
0005616444.tif 000010
【図９】
0005616444.tif 000011