(57)【要約】      （修正有）【課題】パッセージシーケンスの再使用を介して文書の展開を推測することによる文書類似性の測定ができる方法を提供する。【解決手段】動作の間、パッセージの第１の集合を含む文書コレクションを選択し、パッセージの第１の集合を基礎としてパッセージシーケンスモデルを構築し、パッセージの第２の集合を含む新しい文書を受信し、かつ構築されたパッセージシーケンスモデルを基礎として文書のコレクションに対して新しい文書に関連づけられる動作シーケンスを決定する。【選択図】図３
2011238221.tif 000002
【特許請求の範囲】
【請求項１】
パッセージの第１の集合を含む文書のコレクションを選択することと、
前記パッセージの第１の集合を基礎としてパッセージシーケンスモデルを構築することと、
パッセージの第２の集合を含む新しい文書を受信することと、
前記構築されたパッセージシーケンスモデルを基礎として、前記文書のコレクションに対して前記新しい文書に関連づけられる動作シーケンスを決定することを含む方法。
【請求項２】
前記決定される動作シーケンスを基礎として、前記新しい文書と前記コレクション内の少なくとも１つの文書との間の類似性を推定することをさらに含む、請求項１に記載の方法。
【請求項３】
前記パッセージシーケンスモデルは隠れマルコフモデル（ＨＭＭ）であり、かつ前記方法は、前記パッセージの第１の集合のフィンガープリントを生成することをさらに含み、少なくとも１つのフィンガープリントはＨＭＭの１つの状態に対応する、請求項１に記載の方法。
【請求項４】
前記ＨＭＭの状態間の遷移確率を決定することをさらに含む、請求項３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して文書類似性の分析に関する。より具体的には、本開示は、パッセージシーケンスの再使用を介して文書の展開を推測することによる文書類似性の測定に関する。
【発明の概要】
【課題を解決するための手段】
【０００２】
本発明の一実施形態は、文書類似性を推定するためのシステムを提供する。動作の間、本システムは、パッセージの第１の集合を含む文書コレクションを選択し、パッセージの第１の集合を基礎としてパッセージシーケンスモデルを構築し、パッセージの第２の集合を含む新しい文書を受信し、かつ構築されたパッセージシーケンスモデルを基礎として文書のコレクションに対して新しい文書に関連づけられる動作シーケンスを決定する。
【０００３】
この実施形態の一変形例では、本システムはさらに、決定される動作シーケンスを基礎として、新しい文書と文書コレクション内の少なくとも１つの文書との間の類似性を推定する。
【０００４】
この実施形態の一変形例では、パッセージシーケンスモデルは隠れマルコフモデル（ＨＭＭ）である。さらに、本システムはパッセージの第１の集合のフィンガープリントを生成し、少なくとも１つのフィンガープリントはＨＭＭの１つの状態に対応する。
【０００５】
さらなる変形例では、本システムは、ＨＭＭの状態間の遷移確率を決定する。
【０００６】
さらなる変形例では、遷移確率は、パッセージの第１の集合に関連づけられる連続的関係を基礎として決定される。
【０００７】
さらなる変形例では、本システムはパッセージの第２の集合のフィンガープリントを生成し、パッセージの第２の集合のこのフィンガープリントはＨＭＭの観測シーケンスに対応する。
【０００８】
さらなる変形例では、本システムは、パッセージの第２の集合のフィンガープリントをパッセージの第１の集合のフィンガープリントと比較することによってパッセージの類似性を計算する。
【０００９】
さらなる変形例では、本システムは、計算されたパッセージの類似性を基礎として、ＨＭＭの放出確率を決定する。
【００１０】
さらなる変形例では、本システムは、ＨＭＭに属する他の状態の最大放出確率を基礎として、新しいパッセージの生成に対応する追加的状態の放出確率を設定する。
【００１１】
さらなる変形例では、パッセージの第１の集合のフィンガープリントは視覚的な２次元フィンガープリントを含む。
【００１２】
この実施形態の一変形例において、動作シーケンスを決定することは、ＨＭＭにビタビアルゴリズムを適用することを含む。
【図面の簡単な説明】
【００１３】
【図１Ａ】例示的な隠れマルコフモデル（ＨＭＭ）の全体構造を示す図である（先行技術）。
【図１Ｂ】３つの隠れ状態と４つの観測とを有する定常ＨＭＭの例示的事例の確率的パラメータを示す図である（先行技術）。
【図２】本発明の一実施形態による文書−パッセージＨＭＭ構築システムを示す図である。
【図３】本発明の一実施形態による、文書コレクションの文書パッセージを基礎としてＨＭＭを構築するプロセスを示すフローチャートである。
【図４】本発明の一実施形態による、プレゼンテーションの個々のスライドを基礎とする例示的なＨＭＭを示す図である。
【図５】本発明の一実施形態による、２文書（Ａ及びＢ）間の類似性を計算するプロセスを示すフローチャートである。
【図６】本発明の一実施形態による、文書類似性を推定するための例示的なコンピュータシステムを示す。
【発明を実施するための形態】
【００１４】
諸図を通じて、類似の参照数字は同じ図エレメントを指す。
【００１５】
本発明の実施形態は、所定の文書が生成されると実行される動作シーケンスを検出することによって文書類似性を推定するためのシステムを提供する。動作の間、本システムは、幾つかのパッセージを含む文書コレクションを選択し、かつパッセージの発生を基礎として文書コレクションの隠れマルコフモデル（ＨＭＭ）を構築する。新しい文書は、ＨＭＭの観測可能な出力シーケンスとして見られることが可能である。システムは次に、ビタビアルゴリズムを用いて、新しい文書を生成するための最も可能性の高い動作シーケンスを計算する。システムはさらに、この動作シーケンスを基礎として、古い文書のうちの１つまたはそれ以上に対する新しい文書の類似性を推定する。
【００１６】
本発明の実施形態では、文書は文書パッセージのシーケンスとして見られる。文書パッセージはより小さい文書単位であり、これらのより小さい文書単位のシーケンスが文書を構成する。例えば、テキストレポートの場合、文書パッセージは個々の段落である可能性があり、かつレポートは段落のシーケンスと見なされる可能性がある。または、スライドを含むプレゼンテーションの場合、文書パッセージは個々のスライドである可能性があり、よってプレゼンテーションはスライドのシーケンスと見なされる可能性がある。既存の文書からの個々のパッセージまたはパッセージシーケンスは、新しい文書を生成する際にユーザによって再使用されてもよい。例えば、ユーザは、既存の文書からのパッセージまたはパッセージの修正版をコピーして新しい文書へ貼り付けてもよく、ユーザは既存の文書から１つまたは複数のパッセージを削除し及び／または既存の文書へ新しいパッセージを挿入してもよく、またはユーザは複数の既存文書からのパッセージを結合して新しい文書を生成してもよい。新しい文書を生成するためにユーザにより実行される可能性のある動作を調べることにより、本システムは、この文書と大規模な文書コレクション内の複数の文書との比較を可能にし、かつ大規模なコレクションにおいて文書がどのように生成されて経時的に展開してきたかについて仮説を提供する。
【００１７】
次に、各文書パッセージまたはそのフィンガープリントは状態として見られることが可能であり、かつ文書コレクションに関して隠れマルコフモデル（ＨＭＭ）を構築することができる。ＨＭＭは、モデリングされているシステムが、状態が観測されていないマルコフ過程であると想定される統計的モデルである。通常のマルコフモデルでは、観測者は状態を直に目にすることができ、よって、状態遷移確率が唯一のパラメータである。ＨＭＭでは、状態を直に目にすることはできないが、状態に依存する出力は見える。各状態は、可能な出力トークンに渡る確率分布を有する。従って、ＨＭＭによって生成されるトークンのシーケンスは、状態のシーケンスに関する何らかの情報を与える。ＨＭＭのパラメータ、及び特定の出力シーケンスを所与とすれば、その出力シーケンスを生成した可能性が最も高い状態シーケンスを発見することができる。「隠れ」とは、モデルのパラメータではなく、モデルが通過する状態シーケンスを指すことに留意されたい。
【００１８】
図１Ａは、例示的な隠れマルコフモデル（ＨＭＭ）の全体構造を示す図を提示している（先行技術）。楕円１０２等の各楕円形は、幾つかの値のうちの任意のものをとることができる確率変数を表す。確率変数ｘ（ｔ）は、時間ｔにおける隠れ状態である。確率変数ｙ（ｔ）は、時間ｔにおける観測である。矢印１０４等の図内の矢印は、条件付き依存を示す。図１Ｂは、３つの隠れ状態と４つの観測とを有する定常ＨＭＭの例示的事例の確率的パラメータを示す図を提示している（先行技術）。図１Ｂにおいて、Ｘ１、Ｘ２及びＸ３は隠れ状態（図１Ａにおけるｘ（ｔ））の確率変数ｘの可能な値であり、Ｙ１、Ｙ２、Ｙ３及びＹ４は観測確率変数ｙ（図１Ａにおけるｙ（ｔ））の可能な値を表し、ａ１１，．．．，ａ３３は隠れ状態間の状態遷移確率であり、かつｂ１１，．．．，ｂ３４は出力（または放出）確率である。より一般的には、非定常ＨＭＭは、時間ｔに依存する状態遷移確率ａ及び放出確率ｂを包含する。
【００１９】
図２は、本発明の一実施形態による文書−パッセージ−ＨＭＭ−構築システムを示す図を提示している。文書−パッセージＨＭＭ構築システム２００は、文書選択機構２０２と、パッセージ抽出機構２０４と、フィンガープリンティング機構２０６と、状態確率設定機構２０８と、遷移確率設定機構２１０と、文書受信機構２１２と、パッセージ類似性計算器２１４と、放出確率設定機構２１６とを含む。
【００２０】
動作の間、文書選択機構２０２は、ＨＭＭを構築するための文書コレクションを選択する。文書コレクションは、ユーザによって手動で選択されることが可能であり、または文書コレクションは、システムによりユーザが規定する基準を用いて自動的に選択されることも可能である。例えば、文書コレクションは、指定されたフォルダ内の全ファイルを含むことができ、またはこれは、ハードドライブからの全てのＭｉｃｒｏｓｏｆｔ（登録商標）ＷｏｒｄまたはＰｏｗｅｒＰｏｉｎｔ（登録商標）（ワシントン州レドモンド所在のＭｉｃｒｏｓｏｆｔ社の登録商標）ファイルを含むことができる。さらに、本システムは、同じ著者を有するファイル、類似の名前を有するファイルまたは所定の時間期間中にタイムスタンプを付されているファイルを選択することができる。文書タイプは、テキスト、記号、図面及び／またはこれらの任意の組合せを含む任意のタイプであることが可能である。コレクション内の選択される文書も、プレーンテキスト、Ｍｉｃｒｏｓｏｆｔ（登録商標）Ｗｏｒｄ（ワシントン州レドモンド所在のＭｉｃｒｏｓｏｆｔ社の登録商標）、ハイパーテキストマークアップ言語（ＨＴＭＬ）、ポータブルドキュメントフォーマット（ＰＤＦ）、他等の任意タイプのファイルフォーマットを有することが可能である。
【００２１】
文書コレクションは、文書のより小さい単位である文書パッセージを抽出するように構成されるパッセージ抽出機構２０４へ送られる。ある実施形態では、文書パッセージは、ＰｏｗｅｒＰｏｉｎｔ（登録商標）（ワシントン州レドモンド所在のＭｉｃｒｏｓｏｆｔ社の登録商標）プレゼンテーションの個々のスライド、Ｍｉｃｒｏｓｏｆｔ（登録商標）Ｗｏｒｄ（ワシントン州レドモンド所在のＭｉｃｒｏｓｏｆｔ社の登録商標）ファイルの個々の段落及び／またはオブジェクト指向コンピュータプログラムの個々の機能を含むことが可能である。
【００２２】
抽出された文書パッセージは、次に、パッセージのフィンガープリントを生成するように構成されるフィンガープリンティング機構２０６へ送られる。ある実施形態では、各パッセージについてテキストベースのフィンガープリントが生成される。また、視覚的な２次元（２Ｄ）フィンガープリントもパッセージ毎に生成されることが可能である。視覚的な２Ｄフィンガープリントを生成するために、システムは、所定の文書の視覚的な２Ｄパターンを同定する。各文書パッセージのフィンガープリントは、構築されたＨＭＭの１つの状態に対応する。大規模な文書コレクションを表現するＨＭＭのスケールを制御するために、文書のフィンガープリントはより小さい表現集合を形成するためにクラスタ化されることが可能であり、各クラスタは１つの状態に対応する。文書フィンガープリントのクラスタ化には、機械学習等の教師なしクラスタリング方法を使用することができる。
【００２３】
構築されたＨＭＭに関する状態の初期確率は、状態確率設定機構２０８によって設定される。状態の初期確率は、状態アピアランスの尤度を規定する。文書パッセージの完全な、順序づけされたマッチングが必要とされるかどうかに依存して、状態確率設定機構２０８は、状態の初期確率（状態アピアランスの尤度）を適宜設定することができる。ある実施形態では、状態の初期確率は、文書パッセージの文書における出現順序を基礎として、減少する釣鐘曲線に従って設定されることが可能である。このような場合、システムは、コレクション内の各文書の第１のパッセージはどれも同じ初期確率を有することを想定している。さらなる実施形態では、システムは文書パッセージの順序を無視し、よって状態確率設定機構２０８は全ての状態（パッセージ）に渡って一様の初期確率を設定する。
【００２４】
ＨＭＭの状態間の遷移確率ａｉｊ（図１に示すａ１２等）は、遷移確率設定機構２１０によって設定される。ある実施形態では、遷移確率は釣鐘曲線になるように設定される。所定のパッセージ状態の場合、曲線のピークは、遷移が、パッセージからその直後の文書パッセージへの遷移に一致するときに発生する。あるパッセージから次の他のパッセージへの遷移確率は、パッセージ間距離が増大するにつれて指数関数的に減少する。例えば、文書の第１のパッセージからその直後のパッセージ（即ち、文書の第２のパッセージ）への遷移確率は、０．８等の比較的大きい値に設定される可能性があるが、同じ第１のパッセージから文書の第３のパッセージへの遷移確率は、０．２等の遙かに低い数字に設定される可能性がある。曲線は、それが減少している限り、他の形状も可能である。ある実施形態では、遷移確率は、２パッセージ間の距離が増大するにつれて線形的に減少する。
【００２５】
状態間の遷移確率の設定に際して、遷移確率設定機構２１０はパッセージの文書関連性も考慮する。同じ文書関連性を共有する（同じ文書内に出現することを意味する）パッセージについて、遷移確率設定機構２１０は、これらの間の遷移確率を、異なる文書関連性を有するパッセージを包含する全ての遷移の確率より僅かに高くなるように設定する。
【００２６】
（パッセージ距離及び文書関連性を基礎として）遷移確率を非一様に設定することにより、システムは文書パッセージの連続性、及び１つの文書からの幾つかのパッセージを再使用する尤度は比較的高い可能性があるという事実を明らかにする。遷移確率がゼロに設定されれば発生する可能性がある所定の状態遷移の除外を防止するために、システムは、ラプラススムージング等の平滑化技術を用いてゼロ確率の発生を回避する。ある実施形態では、遷移確率設定機構２１０は、予め決められたしきい値より低い全ての遷移確率をしきい値に設定する。その一方で、可能性の高い状態遷移の確率は、全ての遷移確率の合計がなお１に等しいことを保証するために僅かに削ぎ落とされる。さらなる実施形態では、平滑化アルゴリズムによって使用されるしきい値はユーザ設定が可能である。遷移確率の設定に際しては、全ての状態に渡る遷移確率の合計は１に等しい、という制約が充足されなければならないことに留意されたい。
【００２７】
文書受信機構２１２は、考慮する新しい文書を受信し、かつこの新しい文書を文書パッセージ抽出のためにパッセージ抽出機構２０４へ送る。新しい文書からの抽出されたパッセージはフィンガープリンティング機構２０６へ送られ、パッセージのフィンガープリントが生成される。新しい文書の文書パッセージフィンガープリントは、構築されたＨＭＭによって生成された観測シーケンスと見なすことができる。
【００２８】
文書パッセージは、新しい文書において再使用される前に修正を施される場合があることから、システムは、放出確率を決定するために、新しい文書からのパッセージを既知のパッセージと比較する必要がある。このようなタスクは、パッセージ類似性計算器２１４によって達成されることが可能である。パッセージ類似性計算器２１４は、新しい文書からのパッセージと既知のＨＭＭ状態に対応するパッセージとの間の類似性を計算する。ある実施形態では、類似性は、視覚的またはテキストベースのフィンガープリントの比較を基礎として計算される。新しい文書内のパッセージと既知の文書コレクション内の任意パッセージとの間の類似性が予め規定されたしきい値より少なければ、このようなパッセージは新しいパッセージと見なされる。即ち、新しい文書からのパッセージが前述の文書コレクションにおける任意のパッセージにほとんど似ていなければ、システムはこのパッセージを新たに生成されたパッセージとして扱うことができる。
【００２９】
計算された類似性は、次に、ＨＭＭ状態の放出確率（図１に示すｂ）を設定する放出確率設定機構２１６へ送られる。状態ｊの放出確率は、ｂｊ（ｋ）として定義されることが可能である。但し、ｋは観測である。ある実施形態では、放出確率設定機構２１６は放出確率を、文書フィンガープリント比較プロセスによって取得される正規化された類似性スコア（パッセージ類似性計算器２１４の正規化された出力）として設定する。故に、各状態の放出確率分布は、状態を表す文書パッセージ（状態ｊ）と新しい文書の全文書パッセージ（観測ｋ）との間の正規化された類似性スコア分布に一致する。新しい文書パッセージに対応する新しい状態ｒの放出確率は、ｂｒ（ｋ）＝１−
【数１】
2011238221.tif 000003
［ｂｊ（ｋ）］に設定できることに留意されたい。即ち、新しい状態ｒの放出確率は、ＨＭＭの状態の何れによっても（状態ｒを除く）観測が生成されていない残りの確率に設定される。遷移確率の場合と同様に、放出確率の設定に際しても、観測された全ての状態に渡る放出確率の合計は１に等しい、という制約が充足されなければならないことに留意されたい。
【００３０】
図３は、本発明の一実施形態による、文書コレクションの文書パッセージを基礎としてＨＭＭを構築するプロセスを示すフローチャートを提示している。動作の間、システムは文書コレクションを選択する（オペレーション３０２）。このようなコレクション内の文書は、レポート、プレゼンテーション及びコンピュータプログラム等の任意のタイプであることが可能である。システムは次に、コレクションから文書パッセージを抽出する（オペレーション３０４）。文書パッセージは、文書のサブユニットである。文書がレポートであれば、パッセージは個々の段落である可能性があり、文書がプレゼンテーションであれば、パッセージは個々のスライドである可能性がある。システムは、抽出された文書パッセージのフィンガープリントを生成し（オペレーション３０６）、かつこのフィンガープリントまたはフィンガープリントのクラスタを構築されたＨＭＭの状態として設定する（オペレーション３０８）。システムは次に、個々の状態の初期確率を設定し（オペレーション３１０）、かつ状態間の遷移確率を設定する（オペレーション３１２）。
【００３１】
続いて、システムは新しい文書を受信し（オペレーション３１４）、かつ新しい文書からパッセージを抽出する（オペレーション３１６）。システムは、新しい文書からの抽出されたパッセージにフィンガープリントを付し（オペレーション３１８）、かつ新しい文書のこのフィンガープリントを構築されたＨＭＭにより出力されている観測シーケンスとして設定する（オペレーション３２０）。新しい文書のフィンガープリントは先行する文書コレクションのフィンガープリントと比較され、パッセージの類似性が計算される（オペレーション３２２）。ある実施形態では、パッセージの類似性は、文書コンテンツ内で視覚的な２Ｄパターンを同定する単純な１対１の視覚的／テキストベースのフィンガープリント比較を基礎として計算される。ＨＭＭの構築を完了するために、システムは、計算された類似性を基礎として放出確率を設定する（オペレーション３２４）。文書コレクション内の任意のパッセージに対する新しい文書内のパッセージの類似性がしきい値より少なければ、このパッセージは新しい状態と見なされる。新しい文書に対応する放出確率は、ＨＭＭの状態の何れによっても（新しい状態を除く）観測が生成されていない残りの確率として設定される。
【００３２】
図４は、本発明の一実施形態による、プレゼンテーションの個々のスライドを基礎とする例示的なＨＭＭを示す図を提示している。ＨＭＭ４００は、プレゼンテーションコレクション４０２と、新しいプレゼンテーション４０４とを含む。プレゼンテーションコレクション４０２は、各々が１つのＨＭＭ状態に対応するスライド４０６−４１２等の幾つかのスライドを含む。新しいプレゼンテーション４０４も、観測シーケンスに対応するスライド４１４−４１８等の幾つかのスライドを含む。さらに、ＨＭＭ４００は、プレゼンテーションコレクション４０２に包含されない追加の状態に対応する新しいパッセージ状態４２０も含む。
【００３３】
単純化を期して、プレゼンテーションコレクション４０２内の全スライドの初期確率は一様に設定される。ＨＭＭ４００の遷移確率は、スライド間の距離を基礎として釣鐘曲線に設定される。例えば、スライド４０６からその直後のスライド４０８への遷移の確率は０．８等の比較的高い数字に設定されるが、スライド４０６から、スライド４０６の直近ではないスライド４１０及び４１２への遷移の確率は、各々０．１及び０．０５等の遙かに低い数字に設定される。同様に、スライド４０８からスライド４１０及び４１２への遷移確率は各々０．８及び０．１に設定される。他の全ての状態から新しいパッセージ状態４２０への遷移確率は、同じ低い数字に設定されることが可能である。
【００３４】
視覚的／テキストベースの２Ｄフィンガープリント比較の結果を基礎として、新しいプレゼンテーション４０４内のスライド４１４はスライド４０６に８０％類似し、かつ新しいプレゼンテーション４０４内のスライド４１６はスライド４１０に８０％類似する。新しいプレゼンテーション４０４内の残りのスライドであるスライド４１８は、類似性の計算を基礎としてスコアが極めて低く、よって新しいスライドと見なされる。従って、スライド４０６からスライド４１４、及びスライド４１０からスライド４１６への放出確率は、正規化された類似性スコアとして設定される。スライド４１４への最大類似性スコア（放出確率）は０．８であることから、新しいパッセージ状態４２０から新しい文書４０４内のスライド４１４への放出確率は１−０．８＝０．２として設定される。合計制約が充足される限り、正規化された類似性スコアを基礎として他の放出確率（図示されていない）も設定されることが可能である。
【００３５】
ＨＭＭの基本的な問題点は、所定の観測シーケンスを生成する最適な状態シーケンスを決定することを含む。ＨＭＭ状態が文書パッセージを表すコンテキストでは、このような問題点は、所定の新しい文書（観測シーケンス）に関して、システムが、既知の文書コレクションからその新しい文書を生成するためにユーザが実行した挿入、削除及び再配列等の最も可能性の高い動作シーケンスを決定できることを意味する。このような情報は、文書がどのようにして生成され、かつ大規模な文書コレクションにおいて経時的にどのように展開してきたかに関する仮説を提供する。
【００３６】
ある実施形態では、システムは、ビタビアルゴリズム等の動的なプログラミングアルゴリズムを用いて最も可能性の高い状態シーケンスを決定する。ビタビアルゴリズムは、ＨＭＭの所定の観測シーケンスの唯一最良の状態シーケンスを発見するために使用されることが可能である。動作の間、本アルゴリズムは観察される状態への全ての可能経路を調査し、最も可能性の高いものだけを保持する。
【００３７】
図４に示す例では、ビタビアルゴリズムの実行後、システムは、観測されるシーケンス（新しい文書４０４）の状態シーケンスとして可能性の高いものが状態４０６、状態４１０及び新しいパッセージ状態４２０であると決定する。従って、プレゼンテーションコレクション４０２から新しいプレゼンテーション４０４を生成するために、ユーザはスライド４０６を再使用し、スライド４０８を削除し、スライド４１０を再使用し、スライド４１２を削除しかつ新しいスライドを追加する可能性が最も高い。
【００３８】
ビタビアルゴリズムに加えて、フォワードバックワードアルゴリズム等の、状態シーケンスを決定するための他のアルゴリズムも使用されることが可能である。フォワードバックワードアルゴリズムは、文書組換えの直接的比較のみが要求される（例えば、２文書のどちらが文書コレクションから生成されている可能性が高いかを決定する）場合に特に有益であるが、その理由は、フォワードバックワードアルゴリズムが可能性のある全ての組換え経路を考慮することにある。
【００３９】
新しい文書について最も可能性の高い状態シーケンスが決定されると、システムは、新しい文書がどのように生成されるかを基礎として新しい文書と文書コレクション内の文書との間の類似性も決定することができる。例えば、図４に示す例では、新しい文書４０４は文書コレクション４０２からの２つのスライドを再使用している。このような情報は、新しい文書４０４と文書コレクション４０２内の文書との間の類似性を決定するために使用されることが可能である。文書Ａ及び文書Ｂ間の１対１の類似性は、定義によって非対称であることに留意されたい。例えば、文書Ｂから文書Ａを生成するためにユーザによって実行される動作（または生成コスト）は、文書Ａから文書Ｂを生成するために実行される動作とは異なる。文書Ａ及びＢ間の１対１の類似性に関して対称測度を取得するために、システムは、ＢからＡがどのようにして生成されるか、及びＡからＢがどのように生成されるかに基づいて計算される類似性を平均することによって生成コストを平均化することができる。
【００４０】
図５は、本発明の一実施形態による、２文書（Ａ及びＢ）間の類似性を計算するプロセスを示すフローチャートを提示している。動作の間、システムは、文書Ａからのパッセージを状態として使用しかつ文書Ｂからのパッセージを観測シーケンスとして使用してＨＭＭを構築する（オペレーション５０２）。ＨＭＭを構築するために使用されるシステム及びプロセスは、図２及び図３に示すものに類似している。システムは次に、ビタビアルゴリズムを用いて、文書Ａから文書Ｂを生成するための最も可能性の高いシーケンスを決定し（オペレーション５０４）、かつ適宜Ｂ対Ａ類似性を計算する（オペレーション５０６）。続いて、システムは、文書Ｂからのパッセージを状態として、かつ文書Ａからのパッセージを観測シーケンスとして使用して異なるＨＭＭを構築する（オペレーション５０８）。システムは、新しいＨＭＭに対してビタビアルゴリズムを実行し、文書Ｂから文書Ａを生成するための最も可能性の高いシーケンスを決定し（オペレーション５１０）、かつ適宜Ａ対Ｂ類似性を計算する（オペレーション５１２）。この後、システムはＡ対Ｂ、及びＢ対Ａ類似性を平均して、文書Ａ及び文書Ｂ間の最終的な類似性を求める（オペレーション５１４）。
【００４１】
文書類似性の決定に加えて、文書の最も可能性の高い状態シーケンスを発見するこの能力は、文書コレクションにおける文書の系図を推測するためにも使用されることが可能である。このような情報は、データ系統システムへ入力として提供されることが可能であり、これは、文書により使用されるソースマテリアルを基礎として文書の完全性を評価するために使用されることが可能である。
【００４２】
図６は、本発明の一実施形態による、文書類似性を推定するための例示的なコンピュータシステムを示す。ある実施形態では、コンピュータ及び通信システム６００は、プロセッサ６０２と、メモリ６０４と、記憶装置６０６とを含む。記憶装置６０６は、文書類似性推定アプリケーション６０８、並びにアプリケーション６１０及び６１２等の他のアプリケーションを格納する。動作の間、文書類似性推定アプリケーション６０８は記憶装置６０６からメモリ６０４へロードされ、次いでプロセッサ６０２によって実行される。このプログラムを実行する一方で、プロセッサ６０２は前述の機能を実行する。コンピュータ及び通信システム６００は、任意選択のディスプレイ６１４、キーボード６１６及びポインティングデバイス６１８へ結合される。
【図１】
2011238221.tif 000004
【図２】
2011238221.tif 000005
【図３】
2011238221.tif 000006
【図４】
2011238221.tif 000007
【図５】
2011238221.tif 000008
【図６】
2011238221.tif 000009