(57)【要約】【課題】  検索語が登録語に部分的に一致する場合であっても検索が可能な柔軟性のあるリソース検索を可能とする。【解決手段】  ピア１（リソース検索装置）は、リソースの登録時、リソースの登録語を分割して得たそれぞれのユニグラムについて、登録するリソースと、該ユニグラムが登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成する。そして、登録語のそれぞれのユニグラムについて、該ユニグラムを検索キーとし、該ユニグラムに対応した前記２つ組を値として、分散ハッシュテーブルに登録する。また、リソースの検索時には、検索語を分割して得たそれぞれのユニグラムを検索キーとして分散ハッシュテーブルを検索して２つ組を取得する。そして、取得した２つ組の中でリソースが同じである２つ組に対し、出現位置によりユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とする。【選択図】      図１
2005234762.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介して接続されるリソース検索装置からなり、該リソース検索装置が保持する分散ハッシュテーブルによりリソースの検索を行うリソース検索システムにおけるリソース検索装置であって、
登録するリソースに関連する情報を示す登録語、または、リソースの検索に用いる検索語をユニグラムに分割するユニグラム分割手段と、
前記ユニグラム分割手段により前記登録語を分割して得たそれぞれのユニグラムについて、前記登録するリソースと、該ユニグラムが前記登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成する２つ組作成手段と、
上記ユニグラム分割手段により前記登録語を分割して得たそれぞれのユニグラムについて、該ユニグラムを検索キーとし、上記２つ組作成手段により作成され該ユニグラムに対応した前記２つ組を値として、前記分散ハッシュテーブルに登録する登録手段と、
上記ユニグラム分割手段により前記検索語を分割して得られたそれぞれのユニグラムを検索キーとして前記分散ハッシュテーブルを検索し、２つ組を取得する検索手段と、
前記検索手段が取得した２つ組の中でリソースが同じである２つ組に対し、該２つ組内で示される出現位置により前記検索語に応じたユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とする隣接判定手段、
を備えることを特徴とするリソース検索装置。
【請求項２】
ネットワークを介して接続されるリソース検索装置からなり、該リソース検索装置が保持する分散ハッシュテーブルによりリソースの検索を行うリソース検索システムにおけるリソース検索装置に用いられるリソース検索方法であって、
リソースの登録時には、
登録するリソースに関連する情報を示す登録語をユニグラムに分割し、
前記登録語を分割して得たそれぞれのユニグラムについて、前記登録するリソースと、該ユニグラムが前記登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成し、
前記登録語を分割して得たそれぞれのユニグラムについて、該ユニグラムを検索キーとし、該ユニグラムに対応した前記２つ組を値として、前記分散ハッシュテーブルに登録する一方、
リソースの検索時には、
リソースの検索に用いる検索語をユニグラムに分割し、
前記検索語を分割して得られたそれぞれのユニグラムを検索キーとして前記分散ハッシュテーブルを検索して２つ組を取得し、
取得した２つ組の中でリソースが同じである２つ組に対し、該２つ組内で示される出現位置により前記検索語に応じたユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とする、
ことを特徴とするリソース検索方法。
【請求項３】
ネットワークを介して接続されるリソース検索装置からなり、該リソース検索装置が保持する分散ハッシュテーブルによりリソースの検索を行うリソース検索システムにおけるリソース検索装置に用いられるコンピュータプログラムであって、
登録するリソースに関連する情報を示す登録語、または、リソースの検索に用いる検索語をユニグラムに分割するステップと、
前記登録語を分割して得たそれぞれのユニグラムについて、前記登録するリソースと、該ユニグラムが前記登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成するステップと、
前記登録語を分割して得たそれぞれのユニグラムについて、該ユニグラムを検索キーとし、該ユニグラムに対応した前記２つ組を値として、前記分散ハッシュテーブルに登録するステップと、
前記検索語を分割して得られたそれぞれのユニグラムを検索キーとして前記分散ハッシュテーブルを検索して２つ組を取得するステップと、
取得した２つ組の中でリソースが同じである２つ組に対し、該２つ組内で示される出現位置により前記検索語に応じたユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とするステップ、
の各処理をコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項４】
ネットワークを介して接続されるリソース検索装置からなり、該リソース検索装置が保持する分散ハッシュテーブルによりリソースの検索を行うリソース検索システムにおけるリソース検索装置に用いられるコンピュータプログラムを記緑したコンピュータ読み取り可能な記録媒体であって、
登録するリソースに関連する情報を示す登録語、または、リソースの検索に用いる検索語をユニグラムに分割するステップと、
前記登録語を分割して得たそれぞれのユニグラムについて、前記登録するリソースと、該ユニグラムが前記登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成するステップと、
前記登録語を分割して得たそれぞれのユニグラムについて、該ユニグラムを検索キーとし、該ユニグラムに対応した前記２つ組を値として、前記分散ハッシュテーブルに登録するステップと、
前記検索語を分割して得られたそれぞれのユニグラムを検索キーとして前記分散ハッシュテーブルを検索して２つ組を取得するステップと、
取得した２つ組の中でリソースが同じである２つ組に対し、該２つ組内で示される出現位置により前記検索語に応じたユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とするステップ、
の各処理をコンピュータに実行させるコンピュータプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ハッシュテーブル（Distributed Hash Table、以下「ＤＨＴ」と記載）を用いてリソース検索を行うリソース検索装置及び方法、ならびに、コンピュータプログラムに関する。
【背景技術】
【０００２】
リソース検索とは、利用者が手に入れたいリソースを大量のリソース群の中から探し出す技術である。リソースは、文書ファイル、音楽ファイル、画像ファイル、動画ファイル、ディスクの空き領域、計算機の余剰処理能力、オンラインチャットしたい相手、あるいは、それらがどこに存在するかを示す位置識別子など、何でもよい。
リソース提供者が、登録するリソースと当該リソースに関する登録語とをリソース検索システムに入力すると、当該登録語および当該リソースがリソース検索システムの索引に登録される。例えば、登録語としては、リソースのファイル名や、音楽の場合は曲名、動画の場合はタイトル名、計算機資源の場合は計算機名、人間の場合はユーザ名、位置識別子の場合はＵＲＬ（Universal Resource Locator）などが使用される。
そして、リソース利用者がリソース検索システムに対して利用したいリソースに関する検索語を入力すると、索引内にある既にリソース検索システムに登録されているリソースに関する登録語と比較され、登録語と一致するリソースが検索結果として返される。検索語は、登録語と同様に、利用したいリソースに関するファイル名やタイトル名、ＵＲＬなどが使用される。
【０００３】
ところで、ハッシュテーブルとは、検索キーＫと値Ｖのペアを、検索キーＫにハッシュ関数Ｈ（）を適用して得られるハッシュアドレスＨ（Ｋ）に登録した表である。具体的には、ハッシュテーブルからある検索キーＫに関する値Ｖを検索する場合、検索キーＫにハッシュ関数Ｈ（）を適用して得られるハッシュアドレスＨ（Ｋ）を参照することにより、目的とする値Ｖが得られる。ハッシュテーブルは、検索キーに対応する値を素早く参照するためのデータ構造である。そのため、リソース検索システムにおいても、登録語や検索語を検索キーとして、リソースを値として用いることで、ハッシュテーブルを索引として使用している。
ＤＨＴは、ネットワーク上に集中的に管理を行うサーバを持たず、ネットワークを構成するノード（ピア）間で直接情報をやり取りするＰ２Ｐ（ピア・ツー・ピア、あるいは、ポイント・ツー・ポイント）環境において、ネットワークを構成する全ピアがそれぞれ部分的にハッシュテーブルを保持し、それぞれが協調動作することで、ネットワーク全体で１つのハッシュテーブルを構成する形態をとる。
【０００４】
ＤＨＴ管理システムChordでは、ネットワークを循環１６０ｂｉｔハッシュＩＤ空間にオーバレイし、登録あるいは検索するリソース、及び、部分的な索引を保持するピアともにハッシュ関数ＳＨＡ−１を適用し、ＩＤ空間にマップする（例えば、非特許文献１）。リソースは登録語または検索語に対して、また、ピアはＩＰ（Internet Protocol）アドレスに対してハッシュ関数が適用され、求められたハッシュアドレスはＩＤ空間内のＩＤとして使用される。
【０００５】
ＤＨＴ管理システムChordにおいて各ピアは、ハッシュＩＤ空間上で自分の次に大きいＩＤを持つピア（successor）を知っており、自分の次に小さいＩＤを持つピア（predecessor）のＩＤより大きく、かつ、自分のＩＤ以下の領域を担当する。すなわち、ピアは、この領域に登録語のＩＤが含まれるリソースに関するハッシュテーブル、つまり、索引を保持する。
また、各ピアはFinger Tableと呼ばれるルーティング情報を持っており、登録語のＩＤが担当領域外であるリソースの検索要求に対しては、Finger Tableに基づいて検索要求メッセージを次のピアに転送する。Finger Tableは１６０個のエントリを持ち、各エントリはｎ＋２ｉ（ｎはピアのＩＤ、０≦ｉ≦１５９）のＩＤを担当するピアを指すようになっている。登録語のＩＤが担当領域外にあるリソースに対する検索要求メッセージは、Finger Tableのエントリのうち、当該ＩＤを超えない最大のｎ＋２ｉのＩＤを担当するピアに転送される。
このように検索要求メッセージが次々に転送され、最終的に検索対象リソースの登録語のＩＤを担当するピアに到着した時点で、そのピアの索引が参照され、最初に検索要求メッセージを発信したピアに当該リソースが検索結果として返される。
ＤＨＴ管理システムChordでは、Finger Tableのエントリがｎ＋２ｉのＩＤを担当するピアを指すので、二分木探索と同じ要領で検索要求メッセージをルーティングすることにより、ネットワークに参加しているピア数Ｎに対して検索要求のホップ数がO(LogＮ)、すなわち、高々logＮに比例する数で済む。
【０００６】
図６は、Chordを用いたリソース検索時のリソース検索システムにおけるピアの挙動例を示す説明図である。同図においては、説明しやすくするために、リソース検索システムのハッシュＩＤ空間を循環６ｂｉｔハッシュＩＤ空間としており、１０個のピアＰ’１，８，１４，２１，３３，３８，４２，４８，５１，５６からなる。なお、ピアＰ’８は、そのＩＰアドレスにハッシュ関数を適用したＩＤが８であるピアである。また、Ｋ５４は、その登録語にハッシュ関数を適用したＩＤが５４であるリソースである。そして、各ピアは、自分の次に小さいＩＤを持つピアのＩＤより大きく、かつ、自分のＩＤ以下の領域を担当するため、例えば、ピアＰ’８の担当領域は、ＩＤが２〜８であり、ピアＰ’５６の担当領域は、ＩＤが５２〜５６となる。すなわち、リソースＫ５４の索引は、ＩＤが５２〜５６までの領域を担当するピアＰ’５６に保持されている。
ここでは、ピアＰ’８がリソースＫ５４を検索する場合の挙動を示している。
【０００７】
ピアＰ’８はＩＤが５４の領域を担当していないので、自分のFinger Tableを参照して検索要求メッセージの転送先を決定する。ピアＰ’８のFinger Tableにおいて、５４を超えない最大のＩＤである４０を担当するのはピアＰ’４２であることわかるので、ピアＰ８’は、このピアＰ’４２にリソースＫ５４の検索要求メッセージを転送する。
検索要求メッセージを受信したピアＰ’４２は、ＩＤが５４の領域を担当していないので、自分のFinger Tableを参照して検索要求メッセージの転送先を決定する。ピアＰ’４２のFinger Tableにおいて、５４を超えない最大のＩＤである５０を担当するのはピアＰ’５１であることがわかるので、ピアＰ’４２はこのピアＰ’５１へリソースＫ５４の検索要求メッセージを転送する。
ピアＰ’５１はＩＤが５４の領域を担当していないので、自分のFinger Tableを参照して検索要求メッセージの転送先を決定する。ピアＰ’５１のFinger Tableにおいて、５４を超えない最大のＩＤである５３を担当するのはピアＰ’５６であることがわかるので、ピアＰ’５１はリソースＫ５４の検索要求メッセージをピアＰ’５６に転送する。
【０００８】
ピアＰ’５６は、ＩＤが５４の領域を担当しているので、自分が保持している索引を参照してリソースＫ５４を取り出し、このリソースＫ５４を検索の要求元であるピアＰ’８に対して検索応答メッセージとして送信する。ピアＰ’８は検索応答メッセージを受信して、目的とするリソースＫ５４を得る。
【非特許文献１】イオン・ストイカ、ロバート・モリス、デビット・カーガー、Ｍ．フランス・カーシューク及びハリ・バラクリシュナン（Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan），「コード：インターネットアプリケーションのためのスケーラブルなピア・ツー・ピア検索サービス（Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications）」，ACM SIGCOMM 2001，（米国）カリフォルニア州サンディエゴ（San Diego, CA），２００１年８月，ｐ．１４６−１６０
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかし、Chordを始めとする従来のＤＨＴでは、登録するリソースの登録語全体にハッシュ関数を適用しており、ハッシュ関数の「似たデータから近いハッシュ値が生成されない」という要件のため、検索語に厳密に一致する登録語で登録されているリソースしか検索できないという大きな問題点がある。
つまり、あるリソースが「ＡＢＣＤＥ」という登録語でＤＨＴに登録されている時、「ＡＢＣＤＥ」という検索語を用いた場合に当該リソースを検索できるだけで、「Ａ」や「ＣＤ」という検索語を用いた場合は当該リソースを検索することはできない。すなわち、リソースに関する正確な情報がわからない場合など、そのリソースの登録語に厳密に一致する検索語を類推するのは非常に困難であり、利用したいリソースを入手できない状況が発生する。
【００１０】
本発明は上記事情に鑑みてなされたものであり、検索語が登録語に部分的に一致する場合であっても検索が可能な柔軟性のあるリソース検索を行うことができるリソース検索装置及び方法、ならびに、コンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
この発明は、上記の課題を解決すべくなされたもので、請求項１に記載の発明は、ネットワークを介して接続されるリソース検索装置からなり、該リソース検索装置が保持する分散ハッシュテーブルによりリソースの検索を行うリソース検索システムにおけるリソース検索装置であって、登録するリソースに関連する情報を示す登録語、または、リソースの検索に用いる検索語をユニグラムに分割するユニグラム分割手段と、前記ユニグラム分割手段により前記登録語を分割して得たそれぞれのユニグラムについて、前記登録するリソースと、該ユニグラムが前記登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成する２つ組作成手段と、上記ユニグラム分割手段により前記登録語を分割して得たそれぞれのユニグラムについて、該ユニグラムを検索キーとし、上記２つ組作成手段により作成され該ユニグラムに対応した前記２つ組を値として、前記分散ハッシュテーブルに登録する登録手段と、上記ユニグラム分割手段により前記検索語を分割して得られたそれぞれのユニグラムを検索キーとして前記分散ハッシュテーブルを検索し、２つ組を取得する検索手段と、前記検索手段が取得した２つ組の中でリソースが同じである２つ組に対し、該２つ組内で示される出現位置により前記検索語に応じたユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とする隣接判定手段、を備えることを特徴とするリソース検索装置である。
【００１２】
この発明によれば、従来のように登録するリソースの登録語全体にハッシュ関数を適用して登録語とリソースをＤＨＴに登録するのではなく、登録語をユニグラムに分割してユニグラムごとにハッシュ関数を適用し、分割されたユニグラムの個数分だけユニグラムとリソースをＤＨＴに登録する。そして、検索時においても同様に検索語をユニグラムに分割してユニグラムごとに検索することにより、上記目的を達成する。
その構成として、登録語、または、検索語をユニグラムに分割するユニグラム分割手段と、それぞれのユニグラムに対して登録するリソースおよび当該ユニグラムの登録語の中での出現位置の２つ組＜リソース，出現位置＞を作成する２つ組作成手段と、リソースが同じ２つ組に対して出現位置によるユニグラムの隣接判定を行う隣接判定手段を備える。
そして、リソース登録時は、上記ユニグラム分割手段により登録語をユニグラムに分割し、それぞれのユニグラムを検索キー、上記２つ組作成手段により作成した２つ組＜リソース，出現位置＞を値とするペアをＤＨＴに登録する。
また、リソース検索時には、上記ユニグラム分割手段により検索語をユニグラムに分割し、それぞれのユニグラムを検索キーとしてＤＨＴを検索し、得られた２つ組＜リソース，出現位置＞に対して上記隣接判定手段により隣接を判定し、隣接していると判定された２つ組＜リソース，出現位置＞に含まれるリソースを検索結果とすることを特徴とするものである。
【００１３】
上述するように、登録語および検索語をユニグラムに分割するユニグラム分割手段により、検索語のユニグラムを任意の順番で含む登録語の２つ組を検索結果として得ることが可能となる。また、リソースおよびユニグラムの出現位置の２つ組＜リソース，出現位置＞を作成する２つ組作成手段およびユニグラムの隣接判定を行う隣接判定手段は、検索の結果得られた２つ組からユニグラムが正しい順序で隣接していないものを省く。
従って、検索語のユニグラムを任意の順番で含む登録語の２つ組から、ユニグラムが正しい順序で並んだ２つ組のみに検索結果を絞り込むことが可能になる。そして、その２つ組に含まれるリソースを取得することにより、本発明の目的である検索語が登録語に部分的に一致する場合でも検索が可能な柔軟性のあるリソース検索を提供することができるようになる。
なお、ここで、ユニグラムとはＮグラムでＮ＝１の場合であり、Ｎグラムとはある言語単位（音素、文字、単語、品詞など）のＮ個の連続を表記したものである。リソース検索システムにおいては、言語単位として文字が使用される。つまり、本発明においてユニグラムとは、文字の１個の連続を表記したものであり、１文字のことを指す。
【００１４】
請求項２に記載の発明は、ネットワークを介して接続されるリソース検索装置からなり、該リソース検索装置が保持する分散ハッシュテーブルによりリソースの検索を行うリソース検索システムにおけるリソース検索装置に用いられるリソース検索方法であって、リソースの登録時には、登録するリソースに関連する情報を示す登録語をユニグラムに分割し、前記登録語を分割して得たそれぞれのユニグラムについて、前記登録するリソースと、該ユニグラムが前記登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成し、前記登録語を分割して得たそれぞれのユニグラムについて、該ユニグラムを検索キーとし、該ユニグラムに対応した前記２つ組を値として、前記分散ハッシュテーブルに登録する一方、リソースの検索時には、リソースの検索に用いる検索語をユニグラムに分割し、前記検索語を分割して得られたそれぞれのユニグラムを検索キーとして前記分散ハッシュテーブルを検索して２つ組を取得し、取得した２つ組の中でリソースが同じである２つ組に対し、該２つ組内で示される出現位置により前記検索語に応じたユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とする、ことを特徴とするリソース検索方法である。
【００１５】
請求項３に記載の発明は、ネットワークを介して接続されるリソース検索装置からなり、該リソース検索装置が保持する分散ハッシュテーブルによりリソースの検索を行うリソース検索システムにおけるリソース検索装置に用いられるコンピュータプログラムであって、登録するリソースに関連する情報を示す登録語、または、リソースの検索に用いる検索語をユニグラムに分割するステップと、前記登録語を分割して得たそれぞれのユニグラムについて、前記登録するリソースと、該ユニグラムが前記登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成するステップと、前記登録語を分割して得たそれぞれのユニグラムについて、該ユニグラムを検索キーとし、該ユニグラムに対応した前記２つ組を値として、前記分散ハッシュテーブルに登録するステップと、前記検索語を分割して得られたそれぞれのユニグラムを検索キーとして前記分散ハッシュテーブルを検索して２つ組を取得するステップと、取得した２つ組の中でリソースが同じである２つ組に対し、該２つ組内で示される出現位置により前記検索語に応じたユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とするステップ、の各処理をコンピュータに実行させることを特徴とするコンピュータプログラムである。
【００１６】
請求項４に記載の発明は、ネットワークを介して接続されるリソース検索装置からなり、該リソース検索装置が保持する分散ハッシュテーブルによりリソースの検索を行うリソース検索システムにおけるリソース検索装置に用いられるコンピュータプログラムを記緑したコンピュータ読み取り可能な記録媒体であって、登録するリソースに関連する情報を示す登録語、または、リソースの検索に用いる検索語をユニグラムに分割するステップと、前記登録語を分割して得たそれぞれのユニグラムについて、前記登録するリソースと、該ユニグラムが前記登録語の中で出現する位置を示す出現位置の情報とからなる２つ組を作成するステップと、前記登録語を分割して得たそれぞれのユニグラムについて、該ユニグラムを検索キーとし、該ユニグラムに対応した前記２つ組を値として、前記分散ハッシュテーブルに登録するステップと、前記検索語を分割して得られたそれぞれのユニグラムを検索キーとして前記分散ハッシュテーブルを検索して２つ組を取得するステップと、取得した２つ組の中でリソースが同じである２つ組に対し、該２つ組内で示される出現位置により前記検索語に応じたユニグラムの隣接を判定し、隣接していると判定された２つ組に含まれるリソースを検索結果とするステップ、の各処理をコンピュータに実行させるコンピュータプログラムを記録した記録媒体である。
【発明の効果】
【００１７】
上記発明によれば、分散ハッシュテーブル（ＤＨＴ）を用いてリソース検索を行うリソース検索システムにおいて、登録語や検索語をユニグラムに分割してユニグラム単位でリソースの登録や検索を行うため、検索語が登録語に部分的に一致する場合でも検索が可能な柔軟性のある検索を実行することができる。
また、本発明は、リソースを柔軟に検索することが可能なので、完全分散型の検索システムなど、高度な検索要求が求められるアプリケーションヘ応用することもできる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を用いて本発明の実施の形態について詳細に説明する。
図１は、本発明の実施例の基本構成を示すブロック図である。
同図において、１はＰ２Ｐ（ピア・ツー・ピア、あるいは、ポイント・ツー・ポイント）によるリソース検索システムを構成するピア（リソース検索装置）であり、メッセージ送受信装置２、索引処理装置３、索引４を記憶する記憶装置、ルーティング情報処理装置５、ルーティング情報６を記憶する記憶装置、及び、リソース登録・検索装置７を備える。メッセージ送受信装置２は、通信ネットワーク８を経由して検索要求や検索応答などのメッセージを他のピア１と送受信し合う。索引処理装置３は、担当領域の検索要求メッセージをメッセージ送受信装置２から受け取り、索引４を参照してリソースを登録したり、検索結果をメッセージ送受信装置２に返す。索引４は、自身の担当領域内のリソースに関する情報である。ルーティング情報処理装置５は、自身の担当領域外の検索要求メッセージをメッセージ送受信装置２から受け取り、ルーティング情報６を参照して次にメッセージを転送すべき他のピア１をメッセージ送受信装置２に返す。ルーティング情報６は、検索要求メッセージのＩＤに応じた次に転送すべきピア１の情報である。リソース登録・検索装置７はリソースを登録または検索する時に検索要求や検索応答などのメッセージをメッセージ送受信装置２とやり取りする。
【００１９】
ピア１がリソースを登録あるいは検索する場合、リソース登録・検索装置７に対して登録要求や検索要求をかける。すると、メッセージ送受信装置２が登録要求メッセージや検索要求メッセージを作成し、ルーティング情報処理装置５がルーティング情報６を基に返してくる他のピア１に対して、通信ネットワーク８を経由してメッセージを送信する。メッセージを受信した他のピア１は、メッセージ送受信装置２により当該メッセージが担当領域であるか否かを判定し、担当領域外である場合はルーティング情報処理装置５がルーティング情報６を基に返してくるピア１に対してメッセージを送信する。一方、担当領域内である場合、索引処理装置３により、索引４に対してリソースの登録あるいは検索を行う。
【００２０】
このようにして、他のピア１は、メッセージが登録要求の場合はリソースの登録を行い、また、検索要求の場合は、リソースの検索を行うことで得られる検索結果をメッセージ送受信装置２で検索応答メッセージ化して検索要求元のピア１に送信する。
メッセージを受信した検索要求元のピア１は、検索応答メッセージから検索結果を取り出すことでリソースを手に入れることができる。
なお、ピア１を構成する装置のうち、リソース登録・検索装置７以外は、従来技術として示したＤＨＴ（Distributed Hash Table：分散ハッシュテーブル）の機能と同様であるため、以下ではリソース登録・検索装置７についてのみ説明する。
【００２１】
図２は、本発明の実施例のリソース登録・検索装置７の構成を示すブロック図である。
同図において、１４は登録するリソース（登録リソース）、１５は登録リソースに関する登録語、１６は利用したいリソースに関する検索語、１７は検索の結果得られる検索リソースを示している。
なお、リソース（登録リソース１４、検索リソース１７）は、例えば、文書ファイル、音楽ファイル、画像ファイル、動画ファイル、ディスクの空き領域、計算機の余剰処理能力、オンラインチャットしたい相手、あるいは、それらがどこに存在するかを示す位置識別子など、何でもよい。また、登録語１５は、例えば、リソースのファイル名や、音楽の場合は曲名、動画の場合はタイトル名、計算機資源の場合は計算機名、人間の場合はユーザ名、位置識別子の場合はＵＲＬ（Universal Resource Locator）などである。また、検索語１７は、登録語と同様、例えば、利用したいリソースに関するファイル名やタイトル名、ＵＲＬなどである。
【００２２】
そして、リソース登録・検索装置７は、ユニグラム分割部９、２つ組作成部１０、ＤＨＴ登録部１１、ＤＨＴ検索部１２、及び、隣接判定部１３からなる。
ユニグラム分割部９は、登録語１５や検索語１６をユニグラムに分割する。２つ組作成部１０は、登録リソース１４と、ユニグラム分割部９で分割されたユニグラムが登録語１５の中で出現する位置（以下、「出現位置」）との情報からなる２つ組＜リソース，出現位置＞を作成する。ＤＨＴ登録部１１は、ユニグラム分割部９で分割されたユニグラムと、２つ組作成部１０で作成された２つ組＜リソース，出現位置＞のペアとを、検索キーと値とのペアとしてＤＨＴに登録するようにメッセージ送受信装置２に依頼する。ＤＨＴ検索部１２は、ユニグラム分割部９で分割されたユニグラムを検索キーとしてＤＨＴを検索するようにメッセージ送受信装置２に依頼し、検索結果として２つ組＜リソース，出現位置＞を取得する。隣接判定部１３は、ＤＨＴ検索部１２で取得した２つ組＜リソース，出現位置＞のうちリソースが同じ２つ組に対して、出現位置によるユニグラムの隣接判定を行う。
【００２３】
なお、ユニグラムとはＮグラムにおいてＮ＝１の場合であり、Ｎグラムとはある言語単位（音素、文字、単語、品詞など）のＮ個の連続を表記したものである。ここでは、言語単位として文字が使用される。つまり、本実施例においてユニグラムとは、文字の１個の連続を表記したものであり、１文字のことを指す。
【００２４】
図３は、本発明の実施例のリソース登録時のフロー図である。
ピア１がリソースを登録する場合、ピア１のリソース登録・検索装置７に対して、登録リソース１４および当該リソースの登録語１５を与える。すると、まずは、ユニグラム分割部９が、リソースの登録語１５をユニグラムに分割する（ステップＳ１１０）。
続いて、２つ組作成部１０は、分割されたユニグラムを順番に１つずつ取り出し（ステップＳ１２０）、登録リソース１４と取り出した当該ユニグラムの出現位置との２つ組＜リソース，出現位置＞を作成する（ステップＳ１３０）。次に、ＤＨＴ登録部１１は、当該ユニグラムと２つ組＜リソース，出現位置＞のペアをＤＨＴに登録すべく、メッセージ送受信装置２に依頼する（ステップＳ１４０）。以上の操作を登録語１５が分割されたユニグラムの個数分だけ繰り返す（ステップＳ１５０、ステップＳ１６０）。なお、この一連の操作は、実行速度を考慮して、ユニグラムごとに並行して実行することでもよい。
このようにして、リソースの登録が完了する。
【００２５】
図５は、本発明の実施例を、ＤＨＴを構成するネットワーク全体で見た場合の挙動例を示す説明図である。ここでは、通信ネットワーク８に７つのピア１が接続されており、それぞれがピアＰ１，Ｐ２，…，Ｐ７であるとする。
ピアＰ１が「Ａ研究」という登録語１５で表されるリソース１４を登録する場合（Ｐｕｔ（“Ａ研究”，Ｐ１））、まず登録語１５「Ａ研究」をユニグラムごとに分割し、「Ａ」「研」「究」という３つのユニグラムを得る。そして、それぞれのユニグラムに対して２つ組を作成して、
「Ａ」を検索キー、２つ組＜Ｐ１，１＞を値としたペア、
「研」を検索キー、２つ組＜Ｐ１，２＞を値としたペア、
「究」を検索キー、２つ組＜Ｐ１，３＞を値としたペア、
の３つをＤＨＴに登録する。
なお、図５においては、ＤＨＴに登録する対象として当該リソース１４を保持するピアを特定する情報を使用しているが、リソース１４自体を直接使用することでもよい。
そして、図６において説明したように、ＤＨＴでは、各ユニグラムにハッシュ関数を適用したＩＤ（以下、「Ｕ」にハッシュ関数を適用したＩＤを「Ｕ＊」と表記する）を含む領域を担当するピア１が、ＤＨＴに登録されたペアの索引４を保持する。ここでは、「Ａ＊」を担当するピアはＰ７、「研＊」を担当するピアはＰ４、「究＊」を担当するピアはＰ３となっている。
【００２６】
同様に、ピアＰ６が「ＢＣ研究所」という登録語１５で表されるリソース１４を登録する場合（Ｐｕｔ（“ＢＣ研究所”，Ｐ６））、「ＢＣ研究所」から「Ｂ」「Ｃ」「研」「究」「所」という５つのユニグラムを得て、それぞれのユニグラムに対して２つ組を作成し、
「Ｂ」をキー、２つ組＜Ｐ６，１＞を値としたペア、
「Ｃ」をキー、２つ組＜Ｐ６，２＞を値としたペア、
「研」をキー、２つ組＜Ｐ６，３＞を値としたペア、
「究」をキー、２つ組＜Ｐ６，４＞を値としたペア、
「所」をキー、２つ組＜Ｐ６，５＞を値としたペア、
の５つをＤＨＴに登録する。ここでは、「Ｂ＊」を担当するピアＰ５、「Ｃ＊」を担当するピアＰ３、「研＊」を担当するピアＰ４、「究*」を担当するピアＰ３、「所＊」と担当するピアＰ２が、それぞれのペアの索引４を保持する。
【００２７】
また、ピアＰ７が「究研」という登録語１５で表されるリソース１４を登録する場合（Ｐｕｔ（“究研”，Ｐ７））、
「究」をキー、２つ組＜Ｐ７，１＞を値としたペア、
「研」をキー、２つ組＜Ｐ７，２＞を値としたペア、
の２つをＤＨＴに登録する。ここでは、「究＊」を担当するピアＰ３、「研*」を担当するピアＰ４が各ペアの索引４を保持する。
【００２８】
図４は、本発明の実施例のリソース検索時のフロー図である。
リソースを検索する場合、ピア１のリソース登録・検索装置７に対して、利用したいリソースに関する検索語１６を与える。すると、まずは、ユニグラム分割部９が、リソースの検索語１６をユニグラムに分割する（ステップＳ２１０）。
ＤＨＴ検索部１２は、分割されたユニグラムを順番に１つずつ取り出し（ステップＳ２２０）、当該ユニグラムを検索キーとしてＤＨＴを検索すべく、メッセージ送受信装置２に依頼する（ステップＳ２３０）。しばらくすると、メッセージ送受信装置２は検索キーが一致する２つ組＜リソース，出現位置＞を返してくるので、ＤＨＴ検索部１２はこれを取得する（ステップＳ２４０）。この操作を検索語１６が分割されたユニグラムの個数分だけ繰り返す（ステップＳ２５０、ステップＳ２６０）。なお、この一連の操作は、実行速度を考慮して、ユニグラムごとに並行して実行することでもよい。
【００２９】
この時点で、出現順序に関係なく各ユニグラムを含むリソースの２つ組＜リソース，出現位置＞が検索結果として取得されている。そこで、次に、隣接判定部１３により、リソースが同じ２つ組に対して出現位置に基づく隣接判定を行ない、ユニグラムが正しい順序で隣接していない２つ組を検索結果から除外する。これにより、最終的に正しい順序で隣接する２つ組のみが残り、当該２つ組の中に含まれるリソースが検索語１６に部分的に一致する検索リソース１７として得られる（ステップＳ２７０）。
このようにして、リソースの検索は行われる。
【００３０】
再び、図５を用いて、リソースの検索時の挙動を説明する。
ピアＰ５が「研究」という検索語１６を含むリソースを検索する場合（Ｇｅｔ（“研究”））、登録時と同様に検索語１６「研究」をユニグラムに分割し、「研」、「究」という２つのユニグラムを得る。そして、それぞれのユニグラムを検索キーとしてＤＨＴを検索すると、「研*」を含む領域を担当するピアＰ４が＜Ｐ１，２＞と＜Ｐ６，３＞と＜Ｐ７，２＞との３つの２つ組を返し、「究*」を含む領域を担当するピアＰ３が＜Ｐ１，３＞と＜Ｐ６，４＞と＜Ｐ７，１＞との３つの２つ組をピアＰ５へ返す。
【００３１】
この段階では、ピアＰ１、ピアＰ６、ピアＰ７が「研」および「究」を任意の順番で含むリソースを持つことが分かる。隣接判定部１３による隣接判定は、ＤＨＴを検索して得られた２つ組＜リソース，出現位置＞の出現位置を比較することにより行なわれる。すなわち、リソースが「Ｐ１」である２つ組＜Ｐ１，２＞と＜Ｐ１，３＞については、「研」に対応する２つ組で示される出現位置が２、「究」に対応する２つ組で示される出現位置が３と続いているため隣接していると判定する。また、リソースが「Ｐ６」である２つ組＜Ｐ６，３＞と＜Ｐ６，４＞についても、出現位置が３と４と続いているため、隣接していると判定する。しかし、リソースが「Ｐ７」である２つ組＜Ｐ７，２＞と＜Ｐ７，１＞については、出現位置が２と１であり、正しく隣接していないと判定する。
この判定により、２つ組＜Ｐ７，２＞と＜Ｐ７，１＞とを検索結果から除外し、最終的に、２つ組＜Ｐ１，２＞と＜Ｐ１，３＞とに含まれるリソース「Ｐ１」と、２つ組＜Ｐ６，３＞と＜Ｐ６，４＞とに含まれるリソース「Ｐ６」が、「研究」という検索語１６を含むリソース１７として得られる。
実際に、図５において、ピアＰ１は「Ａ研究」という登録語１５でリソース１４を登録しており、また、ピアＰ６は「ＢＣ研究所」という登録語１５でリソース１４を登録しており、ピアＰ５における「研究」という検索語１６に対して、「研究」を部分的に含む部分一致検索が実施されたことになる。
【００３２】
上述する実施例によれば、登録語や検索語をユニグラムに分割してユニグラム単位でリソースの登録や検索を行うため、検索語が登録語に部分的に一致する場合でも検索が可能な柔軟性のある検索を実行することができるという利点がある。
また、上述する実施例は、リソースを柔軟に検索することが可能なので、完全分散型の検索システムなど、高度な検索要求が求められるアプリケーションヘ応用することもできる。
【００３３】
なお、上述するピア１のメッセージ送受信装置２、索引処理装置３、索引４の記録装置、ルーティング情報処理装置５、ルーティング情報６の記録装置、及び、リソース登録・検索装置７のそれぞれで実行される手順をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって本実施の形態のピア１のメッセージ送受信装置２、索引処理装置３、索引４の記録装置、ルーティング情報処理装置５、ルーティング情報６の記録装置、及び、リソース登録・検索装置７を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺機器等のハードウェアを含む。
【００３４】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【００３５】
【図１】本発明の実施例の基本構成を示すブロック図である。
【図２】同実施例によるリソース登録・検索装置の構成を示すブロック図である。
【図３】同実施例によるリソース登録時のフロー図である。
【図４】同実施例によるリソース検索時のフロー図である。
【図５】同実施例によるＤＨＴを構成するネットワーク全体で見た場合の挙動例を示す説明図である。
【図６】従来技術によるリソース検索時のピアの挙動例を示す説明図である。
【符号の説明】
【００３６】
１、Ｐ１、Ｐ２、Ｐ３、Ｐ４、Ｐ５、Ｐ６…ピア
２…メッセージ送受信装置
３…索引処理装置
４…索引
５…ルーティング情報処理装置
６…ルーティング情報
７…リソース登録・検索装置
８…通信ネットワーク
９…ユニグラム分割部
１０…２つ組作成部
１１…ＤＨＴ登録部
１２…ＤＨＴ検索部
１３…隣接判定部
１４…登録リソース
１５…登録語
１６…検索語
１７…検索リソース
【図１】
2005234762.tif 000003
【図２】
2005234762.tif 000004
【図３】
2005234762.tif 000005
【図４】
2005234762.tif 000006
【図５】
2005234762.tif 000007
【図６】
2005234762.tif 000008