(57)【要約】  複数セグメントからなる文字列を検索する方法およびシステムが提供される。検索システムは、クエリセグメントとして突き合わせるセグメントの一部またはすべてを含んでいるクエリ文字列を受け取る。クエリ文字列を受け取ると、検索システムは、そのクエリ文字列で提供されたクエリセグメントを、以前に格納された文字列から収集されたセグメントと比較する。クエリセグメントと一致するセグメントがある場合、検索システムは、一致するセグメントを含んでいる文字列を検索結果として選択する。
2009520283.tif 000002
【特許請求の範囲】
【請求項１】
複数のクエリセグメントを有するクエリ文字列と一致する、複数のセグメントを有する文字列を選択するコンピューティングシステムにおける方法であって、
前記クエリ文字列を受け取るステップと、
前記クエリ文字列のセグメントを識別するステップと、
前記クエリ文字列中の各クエリセグメントを、前記文字列のセグメントと比較するステップと、
前記クエリセグメントと前記文字列のセグメントとの比較に基づいて、前記クエリ文字列に一致する前記文字列を検索結果として選択するステップと
を備えることを特徴とする方法。
【請求項２】
前記クエリ文字列を前記文字列と比較し、前記クエリ文字列と一致する前記文字列を検索結果として選択するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記クエリ文字列が前記クエリセグメントの最後に特殊文字を含んでいる場合、前記クエリセグメントと正確に一致するセグメントを含んでいる前記文字列のみが検索結果として選択されることを特徴とする請求項１に記載の方法。
【請求項４】
前記クエリ文字列が前記クエリ文字列の最後に特殊文字を含んでいる場合、前記クエリ文字列中の各クエリセグメントと正確に一致するセグメントを含んでいる文字列のみが検索結果として選択されることを特徴とする請求項１に記載の方法。
【請求項５】
前記文字列中のセグメントは、大文字表記の変化を使用して分割されることを特徴とする請求項１に記載の方法。
【請求項６】
前記文字列中のセグメントは、１つまたは複数の区切り文字を使用して分割されることを特徴とする請求項１に記載の方法。
【請求項７】
前記比較で大文字と小文字を区別すべきかどうかを示すフラグを受け取るステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記クエリ文字列中のいくつの前記クエリセグメントが各文字列中のセグメントと一致するかによって前記検索結果に順位を付けるステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
各文字列中のセグメントが前記クエリ文字列中の前記クエリセグメントと同じ順序で出現する度合いによって前記検索結果に順位を付けるステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１０】
複数の前記文字列は、ソフトウェア開発プロジェクトの記号を備えることを特徴とする請求項１に記載の方法。
【請求項１１】
前記記号は、公表されたＡＰＩによって公開された文字列を含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記クエリセグメントが前記文字列中のセグメントの冒頭と一致する時に一致が発生することを特徴とする請求項１に記載の方法。
【請求項１３】
前記クエリ文字列のセグメントを識別するステップは、前記文字列をセグメントに分割するカスタムコンポーネントを呼び出すことを含むことを特徴とする請求項１に記載の方法。
【請求項１４】
文字列を格納及び取り出すシステムであって、
各文字列が含んでいるセグメントによって複数の前記文字列を索引付ける文字列テーブルコンポーネントと、
前記文字列をセグメントに分割するセグメント抽出コンポーネントと、
クエリセグメントと各文字列のセグメントとの比較に基づいて、前記文字列テーブルから、クエリ文字列と一致する前記文字列を選択するクエリ処理コンポーネントと
を備えることを特徴とするシステム。
【請求項１５】
前記文字列テーブルの前記文字列を変更する文字列テーブル更新コンポーネントをさらに含むことを特徴とする請求項１４に記載のシステム。
【請求項１６】
外部のコンポーネントが前記文字列テーブルへの操作を行うことを可能にする文字列テーブルインタフェースコンポーネントをさらに含むことを特徴とする請求項１４に記載のシステム。
【請求項１７】
前記文字列テーブル更新コンポーネントはさらに、前記文字列テーブルのデータを要求する操作が行われるまで、前記文字列テーブルへの更新を格納する更新キャッシュコンポーネントを備えることを特徴とする請求項１４に記載のシステム。
【請求項１８】
文字列を格納するデータ構造を含むコンピュータ読取可能媒体であって、
前記データ構造は、複数の前記文字列と、セグメントエントリの索引とを含み、
各エントリは、少なくとも１つの前記文字列の中に含まれる一意のセグメントを識別するセグメント文字列と、前記識別されたセグメントを含んでいる前記文字列への参照とを含む
ことを特徴とするコンピュータ読取可能媒体。
【請求項１９】
前記データ構造は、操作が行われている間の前記文字列テーブルの変化を検出するためのバージョン番号を含むことを特徴とする請求項１８に記載のコンピュータ読取可能媒体。
【請求項２０】
前記セグメントエントリはＢ木に格納されることを特徴とする請求項１８に記載のコンピュータ読取可能媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
いくつかの状況で、ともにつながれた１つまたは複数のセグメントからなる文字列が生じることがある。例えば、Ｃ＋＋プログラミングでは、変数名はスペースを含むことはできないが、プログラマがその変数がどのように使用されるかを理解するのに十分に記述的でなければならない。必要な記述を提供するための一般的な方式の１つは、ＣａｍｅｌＣａｓｅと呼ばれるものであり、この方式では、変数名が、１つまたは複数の連結された単語または単語の代替（例えば「ｉｎｔｅｇｅｒ」を表す「ｉｎｔ」）からなり、各単語は大文字で始まり、それにより、ラクダのこぶのように名前の中にこぶのような見た目を作り出す（すなわちヒトコブラクダではなくフタコブラクダ）。例えば、コンピュータのディスクドライブの数を保持する変数は、ＤｉｓｋＤｒｉｖｅＣｏｕｎｔと命名することができる。ＣａｍｅｌＣａｓｅは、コンピュータ科学を越えて使用されている。例えば、多くの企業商標名は、この技法を採用して、複数のセグメントからなる単一の文字列を提供している（すなわちＥａｒｔｈＬｉｎｋ（登録商標）、ＰｌａｙＳｔａｔｉｏｎ（登録商標）、ＤａｉｍｌｅｒＣｈｒｙｓｌｅｒ（登録商標）等）。文字列の中でセグメントを区切る他の手法も一般的である。例えば、セグメントは、アンダーバー（すなわち上記のプログラミングの例ではｄｉｓｃ＿ｄｒｉｖｅ＿ｃｏｕｎｔ）などの特殊文字によって区切る、あるいは、．ＮＥＴプログラミングで一般的に使用されるように句読法で区切ることが可能である（すなわちＳｙｓｔｅｍ．ＩＯ。この場合はピリオドを使用してセグメントを区切っている）。
【発明の開示】
【発明が解決しようとする課題】
【０００２】
文字列が数個のセグメントから構成される場合、従来の検索方法では、検索者を最良の結果に導かない。例えば、ファイルを削除する関数を探しているプログラマが文字列「ｆｉｌｅ」で単純な部分文字列検索を使用した場合、検索は、ファイル操作関数だけでなく、プロファイルを操作するための関連のない関数も含んだ結果を返す（「ｐｒｏｆｉｌｅ」が部分文字列「ｆｉｌｅ」を含んでいるため）。プログラマは、探している関数が「Ｄｅ」で始まる単語及び単語「ｆｉｌｅ」の両方を含んでいることは分かっているかもしれないが、その関数の名称が「ＤｅｌＦｉｌｅ」であるか、「ＤｅｌｅｔｅＦｉｌｅ」であるか、「ＤｅｌｅｔｅＡＦｉｌｅ」であるかは覚えていないかもしれない。従来の検索方法を使用すると、「Ｄｅ」及び「ｆｉｌｅ」についての検索は、正しい関数名（例えば「ＤｅｌｅｔｅＦｉｌｅ」）を返すかもしれないが、多くの正しくない関数名（例えば「ＧｅｔＰｒｏｆｉｌｅＤｅｓｃｒｉｐｔｉｏｎ」や「ＬａｕｎｃｈＰｒｏｆｉｌｅＲｅａｄｅｒ」）をも返し、目的の関数を特定するのが難しい場合もある。
【課題を解決するための手段】
【０００３】
複数セグメントからなる文字列を検索する方法およびシステムが提供される。いくつかの実施形態では、検索システムは、クエリセグメントとして突き合わせるセグメントの一部またはすべてを含んでいるクエリ文字列を受け取る。クエリ文字列を受け取ると、検索システムは、そのクエリ文字列で提供されたクエリセグメントを、以前に格納された文字列から収集されたセグメントと比較する。クエリセグメントと一致するセグメントがある場合、検索システムは、一致するセグメントを含んでいる文字列を検索結果として選択する。あるいは、検索システムは、部分一致の文字列を検索結果に含めてもよい。部分一致は、クエリセグメントの一部と一致するが、すべてとは一致しないセグメントを有する文字列である。検索システムは、ユーザが最良の一致する文字列を識別することをより容易にするために一致の近さに基づいて検索結果に順位を付けてもよい。
【０００４】
この概要は、以下の発明を実施するための最良の形態においてさらに説明する概念のいくつかを簡略化した形態で紹介するために提供される。この概要は、クレーム主題の主要な特徴や本質的な特徴を明らかにすることや、クレーム主題の範囲を決定する助けとして使用されることを意図していない。
【発明を実施するための最良の形態】
【０００５】
複数セグメントからなる文字列を検索する方法およびシステムが提供される。いくつかの実施形態では、検索システムは、クエリセグメントとして突き合わせるセグメントの一部またはすべてを含んだクエリ文字列を受け取る。例えば、ファイルを削除する関数を探すプログラマは、「ＤｅＦｉ」と入力し、それにより各セグメントの最初の数文字を指定し、上記のようにＣａｍｅｌＣａｓｅを使用することによりそれらの文字を区切る。クエリ文字列を受け取ると、検索システムは、そのクエリ文字列で提供されたクエリセグメント（たとえば「Ｄｅ」と「Ｆｉ」）を、以前に格納された文字列から収集されたセグメントと比較する。例えば、文字列「ＤｅｌｅｔｅＦｉｌｅ」は、セグメント「Ｄｅｌｅｔｅ」とセグメント「Ｆｉｌｅ」を有し、文字列「ＣｏｐｙＦｉｌｅ」は、セグメント「Ｃｏｐｙ」とセグメント「Ｆｉｌｅ」を有する。いずれかのセグメントがクエリセグメントと一致した場合、検索システムは、一致したセグメントを含む文字列を検索結果として選択する。例えば、文字列にＤｅｌｅｔｅＦｉｌｅ、ＣｏｐｙＦｉｌｅ、ＤｅｌｅｔｅＰｒｏｆｉｌｅが含まれる場合は、ＤｅｌｅｔｅＦｉｌｅが「Ｄｅ」と「Ｆｉ」の両方で始まるセグメントを含んでいるため、一致として選択されることになる。
【０００６】
あるいは、検索システムは、「ＣｏｐｙＦｉｌｅ」および「ＤｅｌｅｔｅＰｒｏｆｉｌｅ」のような部分一致の文字列も検索結果に含めてもよい。部分一致は、クエリセグメントの一部と一致するが、すべてとは一致しないセグメントを有する文字列である。例えば、文字列「ＤｅｌｅｔｅＰｒｏｆｉｌｅ」は、クエリセグメント「Ｄｅ」とは一致するが、クエリセグメント「Ｆｉ」とは一致しない。検索システムは、ユーザが最良の一致する文字列を識別することをより容易にするために一致の近さに基づいて検索結果に順位を付けてもよい。このようにして、検索システムは、セグメントがクエリ文字列のクエリセグメントと最も一致する文字列を識別することができる。
【０００７】
いくつかの実施形態で、検索システムは、セグメントに基づく検索を行った後にクエリ文字列を使用して従来の検索を行い、一致があれば検索結果に追加する。この追加的な検索では、ユーザがクエリ文字列中のセグメントの１つを正しく綴らなかった状況、あるいはユーザがクエリ文字列中のセグメントを間違って分割した状況で文字列を見つけることができる。例えば、ユーザがファイルを回復する関数を探しており、その関数の名前が「ＵｎｄｅｌｅｔｅＦｉｌｅ」である場合に、ユーザは、その関数が「ＵｎＤｅｌｅｔｅＦｉｌｅ」等、３つの単語を含んでいたと考えて、「ＤｅｌｅｔｅＦｉｌｅ」を検索する可能性がある。この例では、検索システムがセグメントの冒頭だけを検索した場合には、正しい関数を検索結果に追加しないことになる。しかし、従来の文字列検索も行うことにより、検索システムは、正しい関数を結果に加える。
【０００８】
いくつかの実施形態では、検索システムは、文字列を文字列テーブルに格納する。文字列テーブルは、文字列のセグメントごとに１つのエントリを有する索引を有し、各エントリは、そのセグメントを含んでいる文字列を示す。ユーザが検索を行うと、検索システムは、クエリ文字列をクエリセグメントに分割し、各セグメントを索引中のセグメントと突き合わせる。一致するセグメントが見つかると、それらのセグメントを含んでいる文字列（部分一致と完全一致の両方）が検索結果に加えられる。
【０００９】
いくつかの実施形態では、検索システムは、文字列を文字列テーブルに追加、削除、および更新するためのインタフェースを公開する。例えば、ソフトウェアの開発プロジェクトは、しばしば、複数セグメントからなる文字列である関数名や変数名等の多くの記号とクラスなどの特殊な型を含む。プロジェクトの管理システムは、公開されたインタフェースを使用して自動的にそうした記号を文字列テーブルに追加することができ、プロジェクト管理システムのユーザは、検索システムを使用してプロジェクト内の記号を見つけることができる。ソフトウェアの開発プロジェクトは、公表されたアプリケーションプログラミングインタフェース（ＡＰＩ）を通じて利用可能な記号を利用する場合もあり、そうした記号も、公開されたインタフェースを使用して文字列テーブルに追加されることができ、ユーザは、プロジェクトで使用するための利用可能な関数や他の記号を容易に見つけることができる。文字列テーブルに文字列を追加または更新する際、検索システムによって公開されたインタフェースは、文字列自体と併せて、文字列の区切りを指定できるようにすることもできる。これにより、文字列をセグメントに分割するための、特定のプロジェクトまたは問題領域に固有のカスタムコンポーネントを提供することが可能になる。例えば、あるプロジェクトでは、セグメントはダッシュで区切られる（例えば「ｍｏｄ−ｕｐｄａｔｅ−１」）と定義し、別のプロジェクトでは、文字列はあらかじめ定義されたセグメントでのみ構成されることが許される（例えば「ＵｎＤｅｌＦｉｌｅ」。この場合あらかじめ定義されたセグメントには「Ｕｎ」、「Ｄｅｌ」、および「Ｆｉｌｅ」が含まれる）。
【００１０】
いくつかの実施形態では、検索システムは、文字列テーブルが変化するたびに変更されるバージョン番号を維持することにより、文字列テーブルへの同時の操作を可能にする。通常は文字列テーブルへの排他的なアクセス権を必要とする長い操作は、バージョンを監視して変化を検出することにより、他の操作と同時に行われ得る。例えば、あるユーザが文字列テーブルの文字列を列挙しており、別のユーザが文字列テーブルに文字列を追加する場合、文字列を列挙しているユーザは、バージョン番号を調べることにより、文字列が追加されたことを知り、追加された文字列を考慮するように列挙を修正することができる。
【００１１】
いくつかの実施形態では、検索システムは、セグメントを、セグメントの接頭辞に基づくＢ木として文字列テーブルに格納する。Ｂ木の枝ノードは、各自の子ノードを判別するために必要な最小の長さの、アルファベット表記のセグメント接頭辞を含んでいる。葉ノードは、セグメント全体を参照し、各セグメントを含んでいる文字列への参照のリストを保持する。木は、すべての葉ノードが同じレベルにあり、木をアルファベット順に横断するために線形に読み取れるように、均等に成長する。検索が行われると、検索システムは、各クエリセグメントを、根で始まる木ノードと比較する。検索システムは、ノードを固定記憶媒体に記憶し、メモリをより効率的に使用するために必要時のみノードをロードすることができる。検索システムは、すべての一致する葉ノードが見つかるまで木を横断する。そして、葉ノードで参照される一致セグメントが使用されて、検索結果に含める文字列を選択する。
【００１２】
いくつかの実施形態では、検索システムは、クエリ文字列と一致する度合いに従って検索結果に順位を付ける。文字列テーブルで一致するセグメントが見つかると、検索システムは、一致の度合いに基づいてスコアを割り当てる。例えば、文字列テーブル内の文字列のセグメントの冒頭で見つかったクエリ文字列中のクエリセグメントは、中間で見つかる一致セグメントよりも高いスコアを得ることができる。文字列が、２つ以上のクエリセグメントが一致するセグメントを含んでいる場合、検索システムは、その文字列についての検索結果のスコアを増して、１つの一致セグメントを有する文字列よりも高いスコアを与えることができる。最後に、検索システムは、文字列テーブル内での各一致セグメントの順序を基準とした、クエリ文字列中でクエリセグメントが現れる順序を調べ、順序の類似度に基づいて結果にスコアを割り当てることができる。
【００１３】
いくつかの実施形態では、クエリ文字列は、クエリセグメントまたはクエリ文字列全体が正確に一致しなければならないという指示を含む。例えば、クエリセグメントの後の「＼」の文字は、それがセグメント全体を指定しており、正確な一致だけを返すべきことを意味することができる。例えば、クエリ文字列「Ｄｅｌｅｔｅ＼Ｆｉ」の場合は、複数セグメントからなる文字列「ＤｅｌｅｔｅＦｉｌｅ」は有効な検索結果になるが、「ＤｅｌｅｔｅｄＦｉｌｅ」はそうでないことになる。クエリ文字列の後に置かれた「＼＼」は、文字列全体が完全に一致すべきことを意味することができる。例えば、クエリ文字列「ＤｅｌｅｔｅＦｉｌｅ＼＼」の場合は、複数セグメントの文字列「ＤｌｅｔｅＦｉｌｅ」と「ＵｎＤｅｌｅｔｅＦｉｌｅ」は有効な検索結果となるが、「ＤｅｌｅｔｅＡＦｉｌｅ」は、有効な検索結果にならない。
【００１４】
いくつかの実施形態で、検索システムは、指定された区切り条件のセットを使用してクエリ文字列をクエリセグメントに分割する。例えば、クエリ文字列は、上記のＣａｍｅｌＣａｓｅ（すなわち「ＤｅＦｉ」）や、特殊文字（すなわち「ｄｅ＿ｆｉ」や「ｄｅ．ｆｉ」）などの他の手法で分割されることが可能である。ユーザが、文字列中のセグメントおよびクエリ文字列中のクエリセグメントを区切るために使用される規則を設定してもよい。例えば、ユーザは、特定のソフトウェアプロジェクトの命名法に沿った規則を設定することができる。ユーザは、クエリ文字列と同じ区切り条件を含んだ文字列に検索結果を限定するように指定することもできる。例えば、「ｄｅ＿ｆｉ」と「ＤｅＦｉ」の両方を検索することによって「ＤｅｌｅｔｅＦｉｌｅ」を見つけられるかどうかは、その設定次第である。ユーザは、検索で大文字と小文字を区別するかどうか、および、指定されたクエリセグメントを格納されたリストにあるセグメントの冒頭と突き合わせるか、またはセグメント内の任意の部分文字列あるいはセグメントの末尾と突き合わせるかなどの何らかの他の基準に基づいて突き合わせるかどうかも設定することができる。
【００１５】
図１は、一実施形態における検索システムの構成要素を示すブロック図である。検索システム１００は、クエリプロセッサコンポーネント１１０、テーブルアップデータコンポーネント１２０、セグメントエクストラクタ（extractor）コンポーネント１３０、文字列テーブルコンポーネント１４０、およびテーブルクリエータコンポーネント１５０を含む。クエリプロセッサ１１０は、クエリ文字列を受け取り、セグメントエクストラクタ１３０を使用してクエリ文字列をクエリセグメントに分割し、指定されたクエリセグメントに基づいて文字列テーブル１４０から一致する文字列を検索する。テーブルアップデータ１２０は、文字列テーブル１４０に格納された文字列のリストを追加、削除、および更新する要求を処理する。セグメントエクストラクタ１３０は、クエリ文字列と格納された文字列をセグメントに分割するために、クエリプロセッサ１１０、テーブルクリエータ１５０、およびテーブルアップデータ１２０によって使用される。文字列テーブル１４０は、文字列のリストを格納し、文字列に含まれるセグメントに基づくクイック検索と取り出しを提供する。テーブルクリエータ１５０は、最初の文字列テーブルを作成する。
【００１６】
このシステムが実装されるコンピューティングデバイスは、中央演算処理装置、メモリ、入力装置（例えばキーボードやポインティングデバイス）、出力装置（例えば表示装置）、および記憶装置（例えばディスクドライブ）を備えることができる。メモリと記憶装置は、このシステムを実装する命令を含むことが可能なコンピュータ読取可能媒体である。また、データ構造とメッセージ構造は、格納されても、通信リンクの信号等のデータ伝送媒体を介して送信されてもよい。インターネット、ローカルエリアネットワーク、ワイドエリアネットワーク、２地点間ダイアルアップ接続、携帯電話網等の各種の通信リンクが使用されることができる。
【００１７】
本システムの実施形態は、パーソナルコンピュータ、サーバコンピュータ、携帯またはラップトップ機器、マルチプロセッサシステム、マイクロプロセッサを使用したシステム、プログラム可能な家電製品、デジタルカメラ、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたは機器のいずれかを含む分散コンピューティング環境等を含む、各種の動作環境で実装されることができる。コンピュータシステムは、携帯電話、携帯情報端末、スマートフォン、パーソナルコンピュータ、プログラム可能な家電製品、デジタルカメラ等である。
【００１８】
本システムは、１つまたは複数のコンピュータまたは他の機器によって実行されるプログラムモジュール等のコンピュータ実行可能な命令の一般的文脈で説明することができる。一般に、プログラムモジュールには、特定のタスクを行うか、特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造等が含まれる。通例、プログラムモジュールの機能は、各種の実施形態で適宜組み合わせても、分散させてもよい。
【００１９】
図２は、一実施形態におけるクエリ処理コンポーネントの動作を説明するフロー図である。クエリ処理コンポーネントは、検索システムがユーザのクエリ文字列を受け取った時に、検索結果を提供するために呼び出される。ブロック２１０で、コンポーネントがクエリ文字列を受け取る。ブロック２２０で、コンポーネントは、セグメントエクストラクタコンポーネントを使用して、クエリ文字列からクエリセグメントを抽出する。ブロック２３０で、コンポーネントは、文字列テーブルから指定されたクエリセグメントと一致するセグメントを検索し、対応する文字列を取得する。ブロック２４０で、検索の結果得られた文字列が、受け取られたクエリ文字列と一致する度合いに従って順位付けられる。ブロック２５０で、一致する文字列が検索結果として返される。そしてコンポーネントは完了する。
【００２０】
図３は、一実施形態における文字列テーブルクリエータコンポーネントの動作を説明するフロー図である。文字列テーブルクリエータコンポーネントは、文字列のリストから文字列テーブルを作成するために呼び出される。ブロック３１０で、コンポーネントは、文字列テーブルに入れるべき次の文字列を文字列のリストから選択する。判定ブロック３２０ですべての文字列が選択されている場合は、コンポーネントは完了し、そうでない場合は、コンポーネントはブロック３３０に進む。ブロック３３０で、コンポーネントは、エクストラクトセグメントコンポーネントを呼び出すことにより、選択された文字列からセグメントを抽出してセグメントリストに入れる。ブロック３４０〜３６０で、コンポーネントは、各文字列セグメントを文字列テーブルに追加する処理をループする。ブロック３４０で、コンポーネントは、セグメントリストの次のセグメントを選択する。判定ブロック３５０で、すべてのセグメントが選択されている場合は、コンポーネントはブロック３１０にループして次の文字列を選択し、そうでない限り、コンポーネントはブロック３６０に進む。ブロック３６０で、コンポーネントは、選択されたセグメントとそのセグメントを含んでいる文字列への参照とを文字列テーブルに追加する。コンポーネントは次いでブロック３４０にループして、セグメントリストの次のセグメントを選択する。
【００２１】
図４は、一実施形態におけるセグメントエクストラクタコンポーネントの動作を説明するフロー図である。このコンポーネントは、文字列を文字列セグメントに区切るために呼び出される。ブロック４０５で、コンポーネントは、セグメントに分割すべき文字列を受け取る。ブロック４１０で、コンポーネントは、現在のセグメントを初期化する。ブロック４２０で、コンポーネントはその文字列の次の文字を選択する。判定ブロック４３０で文字列にそれ以上文字がない場合は、コンポーネントは見つかったセグメントのリストを返し、そうでない限りコンポーネントはブロック４４０に進む。ブロック４４０で、コンポーネントは、選択された文字を現在のセグメントに追加する。判定ブロック４５０で、文字が現在のセグメントの最後である場合、コンポーネントはブロック４６０に進み、そうでない場合、コンポーネントはブロック４２０にループし、文字列の次の文字を選択する。ブロック４６０で、コンポーネントは、現在のセグメントを、見つかったセグメントのリストに追加する。次いで、コンポーネントはブロック４１０にループして次のセグメントを抽出する。
【００２２】
図５は、一実施形態におけるテーブルアップデータコンポーネントの動作を説明するフロー図である。このコンポーネントは、文字列テーブルの文字列が追加、削除、または更新される時に呼び出される。ブロック５１０で、コンポーネントは、追加、削除、または更新すべき文字列を受け取る。ブロック５２０で、コンポーネントは、セグメントエクストラクタを使用して文字列を構成セグメントに分割する。ブロック５３０で、コンポーネントは、例えば新しい文字列とその構成セグメントを文字列テーブルに追加することにより、文字列テーブルを変更する。次いでコンポーネントは完了する。
【００２３】
図６は、一実施形態で文字列テーブルを検索するクエリ処理コンポーネントの動作を説明するフロー図である。このコンポーネントは、所与のクエリセグメントのリストについて文字列テーブルを検索する。ブロック６１０で、コンポーネントは、セグメントエクストラクタコンポーネントから、クエリ文字列中のクエリセグメントのリストを受け取る。ブロック６２０で、コンポーネントは、クエリセグメントリストの次のセグメントを選択する。判定ブロック６３０で、リストのすべてのセグメントが選択されている場合は、コンポーネントは、一致するエントリのリストを返し、そうでない限り、コンポーネントはブロック６４０に進む。ブロック６４０で、コンポーネントは、選択されたセグメントと一致する文字列テーブルのエントリを見つける。ブロック６５０で、コンポーネントは、見つかったいずれものエントリを一致エントリのリストに追加する。コンポーネントは次いでブロック６２０にループして、クエリセグメントリストの次のセグメントを選択する。
【００２４】
図７は、一実施形態で、文字列テーブルを検索する際にセグメントの一致エントリを見つけるためのクエリ処理コンポーネントの動作を説明するフロー図である。このコンポーネントは、文字列テーブルから特定のクエリセグメントを検索するために呼び出される。ブロック７１０で、コンポーネントは、文字列テーブル中のすべてのエントリを選択する。ブロック７２０で、コンポーネントは、当該セグメントの次の文字を選択する。判定ブロック７３０で、そのセグメントの文字がすべて選択されている場合、コンポーネントは選択されたエントリを返し、そうでない場合コンポーネントはブロック７４０に進む。ブロック７４０で、コンポーネントは、次の文字が、当該セグメントの選択文字と一致しないエントリをいずれも選択から外す。コンポーネントは次いで、ブロック７２０にループしてセグメントの次の文字を選択する。
【００２５】
図８は、一実施形態で、検索結果を順位付けるクエリ処理コンポーネントの動作を説明する流れ図である。ブロック８１０で、コンポーネントは、重複する文字列がある結果を除去する。ブロック８２０で、コンポーネントは、次の検索結果を選択する。判定ブロック８３０ですべての検索結果が選択されている場合、コンポーネントは、スコア／識別子の対のリストを返し、そうでない限り、コンポーネントはブロック８４０に進む。ブロック８４０で、コンポーネントは、選択されたエントリのセグメントとクエリ文字列中のクエリセグメントとの一致の度合いと順序の類似度に基づいて、選択されたエントリにスコアを与える。ブロック８５０で、コンポーネントは、スコア／識別子の対を作成し、それをリストに追加する。次いで、コンポーネントは、ブロック８２０にループして次の検索結果を選択する。
【００２６】
図９は、一実施形態における、一致する文字列にスコアを与えるためのクエリ処理コンポーネントの動作を説明するフロー図である。ブロック９０５で、コンポーネントは、セグメントエクストラクタを使用して、クエリ文字列と一致文字列からセグメントのリストを入手する。ブロック９１０で、コンポーネントは、一致文字列中の次のセグメントを選択する。判定ブロック９１５で、すべてのセグメントが選択されている場合、コンポーネントは、一致文字列のスコアを返し、そうでない限り、コンポーネントはブロック９２０に進む。ブロック９２０で、コンポーネントは、クエリ文字列中の次のセグメントを選択する。判定ブロック９２５でクエリ文字列のセグメントがすべて選択されている場合、コンポーネントはブロック９１０にループして一致文字列中の次のセグメントを選択し、そうでない限り、コンポーネントはブロック９３０に進む。ブロック９３０で、コンポーネントは、現在選択されているセグメント対のスコアを初期化する。判定ブロック９３５で、それらセグメントの接頭辞が一致する場合、コンポーネントは、ブロック９４０に進み、そうでない場合、コンポーネントはブロック９４５に進む。ブロック９４０で、コンポーネントは、一致の長さに基づいてスコアを増分する。判定ブロック９４５で、２つのセグメントが正確に一致する場合、コンポーネントはブロック９５０に進み、そうでない場合、コンポーネントはブロック９５５に進む。ブロック９５０で、コンポーネントは、正確な一致に基づいてスコアを増分する。ブロック９５５で、コンポーネントは、一致する文字列中での当該セグメントの位置を基準とする、クエリ文字列中での当該セグメントの位置に基づいてスコアを増分する。ブロック９６０で、コンポーネントは、一致文字列の合計スコアに現在のセグメントのスコアを加算する。コンポーネントは次いでブロック９２０にループして、クエリ文字列中の次のセグメントを選択する。
【００２７】
図１０は、一実施形態における検索システムを使用した検索の例を示す。この例では、４つの文字列１０１０が文字列テーブル１０２０に追加されている。文字列テーブル１０２０は、セグメントエクストラクタを使用して４つの文字列１０１０から抽出された各セグメントを指定する列１０３０と、各セグメント１０３０を含んでいる文字列各々への参照１０４０とを含む。受け取られたクエリ文字列１０５０はクエリセグメントに分割され、各クエリセグメントは、文字列テーブル１０２０のセグメントと突き合わせられる。一致するセグメントについては、文字列テーブルで参照される文字列１０４０が、結果のリスト１０６０に加えられる。結果のリスト１０６０は、文字列テーブルから取り出された重複する文字列を除去するようにフィルタリングされている。
【００２８】
図１１は、一実施形態で文字列テーブルを索引付けるために使用されるＢ木を示す。木１１１５は、根ノード１１２０を含む。根ノードは、それら枝ノードの下位にある葉ノードに共通するテキストを指定する枝ノード１１３０を含む。枝ノード１１３０は、文字列テーブルに追加された文字列１１１０の一部である個々のセグメントを指定する葉ノード１１４０に接続する。葉ノード１１４０は、特定の葉ノードで表されるセグメントを含んでいる各文字列１１１０への参照を含んでいる。
【００２９】
前述の内容から、本明細書にこの検索システムの特定の実施形態が例示の目的で説明されたが、本発明の主旨および範囲から逸脱することなく各種の変更を加えてよいことが理解されよう。例えば、クエリセグメントを文字列テーブルのセグメントの冒頭と突き合わせる観点から付き合わせを説明したが、文字列セグメントの任意の部分に見つかるクエリセグメントに基づく突き合わせ等、他の突き合わせ基準が用いられてよい。ソフトウェア開発システムの文脈で検索システムを説明したが、この検索システムを、文字列が複数のセグメントに分割される場合がある他の分野で使用することも可能である。したがって、本発明は、添付の特許請求の範囲の記載に従う以外には限定されない。
【図面の簡単な説明】
【００３０】
【図１】一実施形態における検索システムの構成を示すブロック図である。
【図２】一実施形態におけるクエリ処理コンポーネントの動作を説明する流れ図である。
【図３】一実施形態における文字列テーブルクリエータコンポーネントの動作を説明するフロー図である。
【図４】一実施形態におけるセグメントエクストラクタコンポーネントの動作を説明するフロー図である。
【図５】一実施形態におけるテーブルアップデータコンポーネントの動作を説明するフロー図である。
【図６】一実施形態における文字列テーブルを検索するクエリ処理コンポーネントの動作を説明するフロー図である。
【図７】一実施形態における文字列テーブルを検索する際にセグメントの一致エントリを見つけるためのクエリ処理コンポーネントの動作を説明するフロー図である。
【図８】一実施形態における検索結果に順位を付けるクエリ処理コンポーネントの動作を説明するフロー図である。
【図９】一実施形態における一致する文字列にスコアを付けるクエリ処理コンポーネントの動作を説明する流れ図である。
【図１０】一実施形態における検索システムを使用した検索の例を示す図である。
【図１１】一実施形態における文字列テーブルを索引付けるために使用されるＢ木を示す図である。
【図１】
2009520283.tif 000003
【図２】
2009520283.tif 000004
【図３】
2009520283.tif 000005
【図４】
2009520283.tif 000006
【図５】
2009520283.tif 000007
【図６】
2009520283.tif 000008
【図７】
2009520283.tif 000009
【図８】
2009520283.tif 000010
【図９】
2009520283.tif 000011
【図１０】
2009520283.tif 000012
【図１１】
2009520283.tif 000013
【国際調査報告】
2009520283.tif 000014