"パッセージの第1の集合を含む文書のコレクションを選択することと、前記パッセージの第1の集合を基礎としてパッセージシーケンスモデルを構築することと、パッセージの第2の集合を含む新しい文書を受信することと、前記構築されたパッセージシーケンスモデルを基礎として、前記文書のコレクションに対して前記新しい文書に関連づけられる動作シーケンスを決定することを含む方法。前記決定される動作シーケンスを基礎として、前記新しい文書と前記コレクション内の少なくとも1つの文書との間の類似性を推定することをさらに含む、請求項1に記載の方法。前記パッセージシーケンスモデルは隠れマルコフモデルHMMであり、かつ前記方法は、前記パッセージの第1の集合のフィンガープリントを生成することをさらに含み、少なくとも1つのフィンガープリントはHMMの1つの状態に対応する、請求項1に記載の方法。前記HMMの状態間の遷移確率を決定することをさらに含む、請求項3に記載の方法。本発明の一実施形態は、文書類似性を推定するためのシステムを提供する。動作の間、本システムは、パッセージの第1の集合を含む文書コレクションを選択し、パッセージの第1の集合を基礎としてパッセージシーケンスモデルを構築し、パッセージの第2の集合を含む新しい文書を受信し、かつ構築されたパッセージシーケンスモデルを基礎として文書のコレクションに対して新しい文書に関連づけられる動作シーケンスを決定する。この実施形態の一変形例では、本システムはさらに、決定される動作シーケンスを基礎として、新しい文書と文書コレクション内の少なくとも1つの文書との間の類似性を推定する。この実施形態の一変形例では、パッセージシーケンスモデルは隠れマルコフモデルHMMである。さらに、本システムはパッセージの第1の集合のフィンガープリントを生成し、少なくとも1つのフィンガープリントはHMMの1つの状態に対応する。さらなる変形例では、本システムは、HMMの状態間の遷移確率を決定する。さらなる変形例では、遷移確率は、パッセージの第1の集合に関連づけられる連続的関係を基礎として決定される。さらなる変形例では、本システムはパッセージの第2の集合のフィンガープリントを生成し、パッセージの第2の集合のこのフィンガープリントはHMMの観測シーケンスに対応する。さらなる変形例では、本システムは、パッセージの第2の集合のフィンガープリントをパッセージの第1の集合のフィンガープリントと比較することによってパッセージの類似性を計算する。さらなる変形例では、本システムは、計算されたパッセージの類似性を基礎として、HMMの放出確率を決定する。さらなる変形例では、本システムは、HMMに属する他の状態の最大放出確率を基礎として、新しいパッセージの生成に対応する追加的状態の放出確率を設定する。さらなる変形例では、パッセージの第1の集合のフィンガープリントは視覚的な2次元フィンガープリントを含む。この実施形態の一変形例において、動作シーケンスを決定することは、HMMにビタビアルゴリズムを適用することを含む。諸図を通じて、類似の参照数字は同じ図エレメントを指す。本発明の実施形態は、所定の文書が生成されると実行される動作シーケンスを検出することによって文書類似性を推定するためのシステムを提供する。動作の間、本システムは、幾つかのパッセージを含む文書コレクションを選択し、かつパッセージの発生を基礎として文書コレクションの隠れマルコフモデルHMMを構築する。新しい文書は、HMMの観測可能な出力シーケンスとして見られることが可能である。システムは次に、ビタビアルゴリズムを用いて、新しい文書を生成するための最も可能性の高い動作シーケンスを計算する。システムはさらに、この動作シーケンスを基礎として、古い文書のうちの1つまたはそれ以上に対する新しい文書の類似性を推定する。本発明の実施形態では、文書は文書パッセージのシーケンスとして見られる。文書パッセージはより小さい文書単位であり、これらのより小さい文書単位のシーケンスが文書を構成する。例えば、テキストレポートの場合、文書パッセージは個々の段落である可能性があり、かつレポートは段落のシーケンスと見なされる可能性がある。または、スライドを含むプレゼンテーションの場合、文書パッセージは個々のスライドである可能性があり、よってプレゼンテーションはスライドのシーケンスと見なされる可能性がある。既存の文書からの個々のパッセージまたはパッセージシーケンスは、新しい文書を生成する際にユーザによって再使用されてもよい。例えば、ユーザは、既存の文書からのパッセージまたはパッセージの修正版をコピーして新しい文書へ貼り付けてもよく、ユーザは既存の文書から1つまたは複数のパッセージを削除し及び/または既存の文書へ新しいパッセージを挿入してもよく、またはユーザは複数の既存文書からのパッセージを結合して新しい文書を生成してもよい。新しい文書を生成するためにユーザにより実行される可能性のある動作を調べることにより、本システムは、この文書と大規模な文書コレクション内の複数の文書との比較を可能にし、かつ大規模なコレクションにおいて文書がどのように生成されて経時的に展開してきたかについて仮説を提供する。次に、各文書パッセージまたはそのフィンガープリントは状態として見られることが可能であり、かつ文書コレクションに関して隠れマルコフモデルHMMを構築することができる。HMMは、モデリングされているシステムが、状態が観測されていないマルコフ過程であると想定される統計的モデルである。通常のマルコフモデルでは、観測者は状態を直に目にすることができ、よって、状態遷移確率が唯一のパラメータである。HMMでは、状態を直に目にすることはできないが、状態に依存する出力は見える。各状態は、可能な出力トークンに渡る確率分布を有する。従って、HMMによって生成されるトークンのシーケンスは、状態のシーケンスに関する何らかの情報を与える。HMMのパラメータ、及び特定の出力シーケンスを所与とすれば、その出力シーケンスを生成した可能性が最も高い状態シーケンスを発見することができる。隠れとは、モデルのパラメータではなく、モデルが通過する状態シーケンスを指すことに留意されたい。図1Aは、例示的な隠れマルコフモデルHMMの全体構造を示す図を提示している先行技術。楕円102等の各楕円形は、幾つかの値のうちの任意のものをとることができる確率変数を表す。確率変数xtは、時間tにおける隠れ状態である。確率変数ytは、時間tにおける観測である。矢印104等の図内の矢印は、条件付き依存を示す。図1Bは、3つの隠れ状態と4つの観測とを有する定常HMMの例示的事例の確率的パラメータを示す図を提示している先行技術。図1Bにおいて、X1、X2及びX3は隠れ状態図1Aにおけるxtの確率変数xの可能な値であり、Y1、Y2、Y3及びY4は観測確率変数y図1Aにおけるytの可能な値を表し、a11,...,a33は隠れ状態間の状態遷移確率であり、かつb11,...,b34は出力または放出確率である。より一般的には、非定常HMMは、時間tに依存する状態遷移確率a及び放出確率bを包含する。図2は、本発明の一実施形態による文書-パッセージ-HMM-構築システムを示す図を提示している。文書-パッセージHMM構築システム200は、文書選択機構202と、パッセージ抽出機構204と、フィンガープリンティング機構206と、状態確率設定機構208と、遷移確率設定機構210と、文書受信機構212と、パッセージ類似性計算器214と、放出確率設定機構216とを含む。動作の間、文書選択機構202は、HMMを構築するための文書コレクションを選択する。文書コレクションは、ユーザによって手動で選択されることが可能であり、または文書コレクションは、システムによりユーザが規定する基準を用いて自動的に選択されることも可能である。例えば、文書コレクションは、指定されたフォルダ内の全ファイルを含むことができ、またはこれは、ハードドライブからの全てのMicrosoft登録商標WordまたはPowerPoint登録商標ワシントン州レドモンド所在のMicrosoft社の登録商標ファイルを含むことができる。さらに、本システムは、同じ著者を有するファイル、類似の名前を有するファイルまたは所定の時間期間中にタイムスタンプを付されているファイルを選択することができる。文書タイプは、テキスト、記号、図面及び/またはこれらの任意の組合せを含む任意のタイプであることが可能である。コレクション内の選択される文書も、プレーンテキスト、Microsoft登録商標Wordワシントン州レドモンド所在のMicrosoft社の登録商標、ハイパーテキストマークアップ言語HTML、ポータブルドキュメントフォーマットPDF、他等の任意タイプのファイルフォーマットを有することが可能である。文書コレクションは、文書のより小さい単位である文書パッセージを抽出するように構成されるパッセージ抽出機構204へ送られる。ある実施形態では、文書パッセージは、PowerPoint登録商標ワシントン州レドモンド所在のMicrosoft社の登録商標プレゼンテーションの個々のスライド、Microsoft登録商標Wordワシントン州レドモンド所在のMicrosoft社の登録商標ファイルの個々の段落及び/またはオブジェクト指向コンピュータプログラムの個々の機能を含むことが可能である。抽出された文書パッセージは、次に、パッセージのフィンガープリントを生成するように構成されるフィンガープリンティング機構206へ送られる。ある実施形態では、各パッセージについてテキストベースのフィンガープリントが生成される。また、視覚的な2次元2Dフィンガープリントもパッセージ毎に生成されることが可能である。視覚的な2Dフィンガープリントを生成するために、システムは、所定の文書の視覚的な2Dパターンを同定する。各文書パッセージのフィンガープリントは、構築されたHMMの1つの状態に対応する。大規模な文書コレクションを表現するHMMのスケールを制御するために、文書のフィンガープリントはより小さい表現集合を形成するためにクラスタ化されることが可能であり、各クラスタは1つの状態に対応する。文書フィンガープリントのクラスタ化には、機械学習等の教師なしクラスタリング方法を使用することができる。構築されたHMMに関する状態の初期確率は、状態確率設定機構208によって設定される。状態の初期確率は、状態アピアランスの尤度を規定する。文書パッセージの完全な、順序づけされたマッチングが必要とされるかどうかに依存して、状態確率設定機構208は、状態の初期確率状態アピアランスの尤度を適宜設定することができる。ある実施形態では、状態の初期確率は、文書パッセージの文書における出現順序を基礎として、減少する釣鐘曲線に従って設定されることが可能である。このような場合、システムは、コレクション内の各文書の第1のパッセージはどれも同じ初期確率を有することを想定している。さらなる実施形態では、システムは文書パッセージの順序を無視し、よって状態確率設定機構208は全ての状態パッセージに渡って一様の初期確率を設定する。HMMの状態間の遷移確率aij図1に示すa12等は、遷移確率設定機構210によって設定される。ある実施形態では、遷移確率は釣鐘曲線になるように設定される。所定のパッセージ状態の場合、曲線のピークは、遷移が、パッセージからその直後の文書パッセージへの遷移に一致するときに発生する。あるパッセージから次の他のパッセージへの遷移確率は、パッセージ間距離が増大するにつれて指数関数的に減少する。例えば、文書の第1のパッセージからその直後のパッセージ即ち、文書の第2のパッセージへの遷移確率は、0.8等の比較的大きい値に設定される可能性があるが、同じ第1のパッセージから文書の第3のパッセージへの遷移確率は、0.2等の遙かに低い数字に設定される可能性がある。曲線は、それが減少している限り、他の形状も可能である。ある実施形態では、遷移確率は、2パッセージ間の距離が増大するにつれて線形的に減少する。状態間の遷移確率の設定に際して、遷移確率設定機構210はパッセージの文書関連性も考慮する。同じ文書関連性を共有する同じ文書内に出現することを意味するパッセージについて、遷移確率設定機構210は、これらの間の遷移確率を、異なる文書関連性を有するパッセージを包含する全ての遷移の確率より僅かに高くなるように設定する。パッセージ距離及び文書関連性を基礎として遷移確率を非一様に設定することにより、システムは文書パッセージの連続性、及び1つの文書からの幾つかのパッセージを再使用する尤度は比較的高い可能性があるという事実を明らかにする。遷移確率がゼロに設定されれば発生する可能性がある所定の状態遷移の除外を防止するために、システムは、ラプラススムージング等の平滑化技術を用いてゼロ確率の発生を回避する。ある実施形態では、遷移確率設定機構210は、予め決められたしきい値より低い全ての遷移確率をしきい値に設定する。その一方で、可能性の高い状態遷移の確率は、全ての遷移確率の合計がなお1に等しいことを保証するために僅かに削ぎ落とされる。さらなる実施形態では、平滑化アルゴリズムによって使用されるしきい値はユーザ設定が可能である。遷移確率の設定に際しては、全ての状態に渡る遷移確率の合計は1に等しい、という制約が充足されなければならないことに留意されたい。文書受信機構212は、考慮する新しい文書を受信し、かつこの新しい文書を文書パッセージ抽出のためにパッセージ抽出機構204へ送る。新しい文書からの抽出されたパッセージはフィンガープリンティング機構206へ送られ、パッセージのフィンガープリントが生成される。新しい文書の文書パッセージフィンガープリントは、構築されたHMMによって生成された観測シーケンスと見なすことができる。文書パッセージは、新しい文書において再使用される前に修正を施される場合があることから、システムは、放出確率を決定するために、新しい文書からのパッセージを既知のパッセージと比較する必要がある。このようなタスクは、パッセージ類似性計算器214によって達成されることが可能である。パッセージ類似性計算器214は、新しい文書からのパッセージと既知のHMM状態に対応するパッセージとの間の類似性を計算する。ある実施形態では、類似性は、視覚的またはテキストベースのフィンガープリントの比較を基礎として計算される。新しい文書内のパッセージと既知の文書コレクション内の任意パッセージとの間の類似性が予め規定されたしきい値より少なければ、このようなパッセージは新しいパッセージと見なされる。即ち、新しい文書からのパッセージが前述の文書コレクションにおける任意のパッセージにほとんど似ていなければ、システムはこのパッセージを新たに生成されたパッセージとして扱うことができる。計算された類似性は、次に、HMM状態の放出確率図1に示すbを設定する放出確率設定機構216へ送られる。状態jの放出確率は、bjkとして定義されることが可能である。但し、kは観測である。ある実施形態では、放出確率設定機構216は放出確率を、文書フィンガープリント比較プロセスによって取得される正規化された類似性スコアパッセージ類似性計算器214の正規化された出力として設定する。故に、各状態の放出確率分布は、状態を表す文書パッセージ状態jと新しい文書の全文書パッセージ観測kとの間の正規化された類似性スコア分布に一致する。新しい文書パッセージに対応する新しい状態rの放出確率は、brk=1-[bjk]に設定できることに留意されたい。即ち、新しい状態rの放出確率は、HMMの状態の何れによっても状態rを除く観測が生成されていない残りの確率に設定される。遷移確率の場合と同様に、放出確率の設定に際しても、観測された全ての状態に渡る放出確率の合計は1に等しい、という制約が充足されなければならないことに留意されたい。図3は、本発明の一実施形態による、文書コレクションの文書パッセージを基礎としてHMMを構築するプロセスを示すフローチャートを提示している。動作の間、システムは文書コレクションを選択するオペレーション302。このようなコレクション内の文書は、レポート、プレゼンテーション及びコンピュータプログラム等の任意のタイプであることが可能である。システムは次に、コレクションから文書パッセージを抽出するオペレーション304。文書パッセージは、文書のサブユニットである。文書がレポートであれば、パッセージは個々の段落である可能性があり、文書がプレゼンテーションであれば、パッセージは個々のスライドである可能性がある。システムは、抽出された文書パッセージのフィンガープリントを生成しオペレーション306、かつこのフィンガープリントまたはフィンガープリントのクラスタを構築されたHMMの状態として設定するオペレーション308。システムは次に、個々の状態の初期確率を設定しオペレーション310、かつ状態間の遷移確率を設定するオペレーション312。続いて、システムは新しい文書を受信しオペレーション314、かつ新しい文書からパッセージを抽出するオペレーション316。システムは、新しい文書からの抽出されたパッセージにフィンガープリントを付しオペレーション318、かつ新しい文書のこのフィンガープリントを構築されたHMMにより出力されている観測シーケンスとして設定するオペレーション320。新しい文書のフィンガープリントは先行する文書コレクションのフィンガープリントと比較され、パッセージの類似性が計算されるオペレーション322。ある実施形態では、パッセージの類似性は、文書コンテンツ内で視覚的な2Dパターンを同定する単純な1対1の視覚的/テキストベースのフィンガープリント比較を基礎として計算される。HMMの構築を完了するために、システムは、計算された類似性を基礎として放出確率を設定するオペレーション324。文書コレクション内の任意のパッセージに対する新しい文書内のパッセージの類似性がしきい値より少なければ、このパッセージは新しい状態と見なされる。新しい文書に対応する放出確率は、HMMの状態の何れによっても新しい状態を除く観測が生成されていない残りの確率として設定される。図4は、本発明の一実施形態による、プレゼンテーションの個々のスライドを基礎とする例示的なHMMを示す図を提示している。HMM400は、プレゼンテーションコレクション402と、新しいプレゼンテーション404とを含む。プレゼンテーションコレクション402は、各々が1つのHMM状態に対応するスライド406-412等の幾つかのスライドを含む。新しいプレゼンテーション404も、観測シーケンスに対応するスライド414-418等の幾つかのスライドを含む。さらに、HMM400は、プレゼンテーションコレクション402に包含されない追加の状態に対応する新しいパッセージ状態420も含む。単純化を期して、プレゼンテーションコレクション402内の全スライドの初期確率は一様に設定される。HMM400の遷移確率は、スライド間の距離を基礎として釣鐘曲線に設定される。例えば、スライド406からその直後のスライド408への遷移の確率は0.8等の比較的高い数字に設定されるが、スライド406から、スライド406の直近ではないスライド410及び412への遷移の確率は、各々0.1及び0.05等の遙かに低い数字に設定される。同様に、スライド408からスライド410及び412への遷移確率は各々0.8及び0.1に設定される。他の全ての状態から新しいパッセージ状態420への遷移確率は、同じ低い数字に設定されることが可能である。視覚的/テキストベースの2Dフィンガープリント比較の結果を基礎として、新しいプレゼンテーション404内のスライド414はスライド406に80類似し、かつ新しいプレゼンテーション404内のスライド416はスライド410に80類似する。新しいプレゼンテーション404内の残りのスライドであるスライド418は、類似性の計算を基礎としてスコアが極めて低く、よって新しいスライドと見なされる。従って、スライド406からスライド414、及びスライド410からスライド416への放出確率は、正規化された類似性スコアとして設定される。スライド414への最大類似性スコア放出確率は0.8であることから、新しいパッセージ状態420から新しい文書404内のスライド414への放出確率は1-0.8=0.2として設定される。合計制約が充足される限り、正規化された類似性スコアを基礎として他の放出確率図示されていないも設定されることが可能である。HMMの基本的な問題点は、所定の観測シーケンスを生成する最適な状態シーケンスを決定することを含む。HMM状態が文書パッセージを表すコンテキストでは、このような問題点は、所定の新しい文書観測シーケンスに関して、システムが、既知の文書コレクションからその新しい文書を生成するためにユーザが実行した挿入、削除及び再配列等の最も可能性の高い動作シーケンスを決定できることを意味する。このような情報は、文書がどのようにして生成され、かつ大規模な文書コレクションにおいて経時的にどのように展開してきたかに関する仮説を提供する。ある実施形態では、システムは、ビタビアルゴリズム等の動的なプログラミングアルゴリズムを用いて最も可能性の高い状態シーケンスを決定する。ビタビアルゴリズムは、HMMの所定の観測シーケンスの唯一最良の状態シーケンスを発見するために使用されることが可能である。動作の間、本アルゴリズムは観察される状態への全ての可能経路を調査し、最も可能性の高いものだけを保持する。図4に示す例では、ビタビアルゴリズムの実行後、システムは、観測されるシーケンス新しい文書404の状態シーケンスとして可能性の高いものが状態406、状態410及び新しいパッセージ状態420であると決定する。従って、プレゼンテーションコレクション402から新しいプレゼンテーション404を生成するために、ユーザはスライド406を再使用し、スライド408を削除し、スライド410を再使用し、スライド412を削除しかつ新しいスライドを追加する可能性が最も高い。ビタビアルゴリズムに加えて、フォワードバックワードアルゴリズム等の、状態シーケンスを決定するための他のアルゴリズムも使用されることが可能である。フォワードバックワードアルゴリズムは、文書組換えの直接的比較のみが要求される例えば、2文書のどちらが文書コレクションから生成されている可能性が高いかを決定する場合に特に有益であるが、その理由は、フォワードバックワードアルゴリズムが可能性のある全ての組換え経路を考慮することにある。新しい文書について最も可能性の高い状態シーケンスが決定されると、システムは、新しい文書がどのように生成されるかを基礎として新しい文書と文書コレクション内の文書との間の類似性も決定することができる。例えば、図4に示す例では、新しい文書404は文書コレクション402からの2つのスライドを再使用している。このような情報は、新しい文書404と文書コレクション402内の文書との間の類似性を決定するために使用されることが可能である。文書A及び文書B間の1対1の類似性は、定義によって非対称であることに留意されたい。例えば、文書Bから文書Aを生成するためにユーザによって実行される動作または生成コストは、文書Aから文書Bを生成するために実行される動作とは異なる。文書A及びB間の1対1の類似性に関して対称測度を取得するために、システムは、BからAがどのようにして生成されるか、及びAからBがどのように生成されるかに基づいて計算される類似性を平均することによって生成コストを平均化することができる。図5は、本発明の一実施形態による、2文書A及びB間の類似性を計算するプロセスを示すフローチャートを提示している。動作の間、システムは、文書Aからのパッセージを状態として使用しかつ文書Bからのパッセージを観測シーケンスとして使用してHMMを構築するオペレーション502。HMMを構築するために使用されるシステム及びプロセスは、図2及び図3に示すものに類似している。システムは次に、ビタビアルゴリズムを用いて、文書Aから文書Bを生成するための最も可能性の高いシーケンスを決定しオペレーション504、かつ適宜B対A類似性を計算するオペレーション506。続いて、システムは、文書Bからのパッセージを状態として、かつ文書Aからのパッセージを観測シーケンスとして使用して異なるHMMを構築するオペレーション508。システムは、新しいHMMに対してビタビアルゴリズムを実行し、文書Bから文書Aを生成するための最も可能性の高いシーケンスを決定しオペレーション510、かつ適宜A対B類似性を計算するオペレーション512。この後、システムはA対B、及びB対A類似性を平均して、文書A及び文書B間の最終的な類似性を求めるオペレーション514。文書類似性の決定に加えて、文書の最も可能性の高い状態シーケンスを発見するこの能力は、文書コレクションにおける文書の系図を推測するためにも使用されることが可能である。このような情報は、データ系統システムへ入力として提供されることが可能であり、これは、文書により使用されるソースマテリアルを基礎として文書の完全性を評価するために使用されることが可能である。図6は、本発明の一実施形態による、文書類似性を推定するための例示的なコンピュータシステムを示す。ある実施形態では、コンピュータ及び通信システム600は、プロセッサ602と、メモリ604と、記憶装置606とを含む。記憶装置606は、文書類似性推定アプリケーション608、並びにアプリケーション610及び612等の他のアプリケーションを格納する。動作の間、文書類似性推定アプリケーション608は記憶装置606からメモリ604へロードされ、次いでプロセッサ602によって実行される。このプログラムを実行する一方で、プロセッサ602は前述の機能を実行する。コンピュータ及び通信システム600は、任意選択のディスプレイ614、キーボード616及びポインティングデバイス618へ結合される。"