(57)【特許請求の範囲】
【請求項１】
プロセッサ、入力装置、及び記憶装置を有するコンピュータを備え、
前記プロセッサが、
前記記憶装置に記憶された文書から複数個のテキスト断片を抽出するテキスト断片化手段と、
前記入力装置から入力される前記文書の目次所在ページの情報に基づき、前記目次所在ページから抽出されたテキスト断片を目次内テキスト断片の蝟集体と認識する目次領域認識手段と、
（ｉ）前記目次内テキスト断片と前記蝟集体以外のテキスト断片との間の類似度に基づいて、前記蝟集体以外のテキスト断片の中から前記目次内テキスト断片のリンク先となるテキスト断片を認識し、
（ｉｉ）前記目次内テキスト断片それぞれについて、そのテキスト断片から目次が始まっているか否かを検証し、そのテキスト断片から目次が始まっていると判断された場合にそのテキスト断片を目次筆頭項目候補とし、前記目次筆頭項目候補を目次内項目の実質蝟集体の１つとし、前記目次筆頭項目候補に後続する前記蝟集体内のそれぞれのテキスト断片について、そのテキスト断片のリンク先が、直前に前記実質蝟集体に加えられたテキスト断片のリンク先よりも後ろである場合に、前記そのテキスト断片を前記実質蝟集体に加える目次抽出手段と、
を実行することを特徴とする文書内目次認識装置。
【請求項２】
請求項１記載の文書内目次認識装置であって、目次抽出手段が、基準書式との照合によってテキスト断片を選択的に候補から除外した上で、目次内項目らしきテキスト断片、そのリンク先らしきテキスト断片又はその双方を認識する文書内目次認識装置。
【請求項３】
請求項１記載の文書内目次認識装置であって、テキスト断片化手段が、テキスト断片をそのページ内位置と関連付けて抽出し、目次抽出手段が、各テキスト断片に関連付けられているページ内位置に基づき候補を絞った上で、目次内項目のリンク先らしきテキスト断片を認識する文書内目次認識装置。
【請求項４】
請求項１記載の文書内目次認識装置であって、更に、前記プロセッサが、目次内項目又はそのリンク先として認識されたテキスト断片が有効なテキスト断片であるか否かを、前記目次内テキスト断片それぞれのリンク先の拡がり率が所定値以上である場合は有効なテキスト断片であり、前記拡がり率が所定値より小さい場合は有効なテキスト断片ではないとする有効性確認手段を実行することを特徴とする文書内目次認識装置。
【請求項５】
請求項１記載の文書内目次認識装置であって、更に、前記プロセッサが、目次内項目又はそのリンク先として認識されたテキスト断片が有効なテキスト断片であるか否かを、前記蝟集体以外のテキスト断片の中から前記実質蝟集体のコピーを検索し、前記コピー内に前記目次内項目のリンク先が存在しない場合は有効なテキスト断片であり、前記コピー内に前記目次内項目のリンク先が存在する場合は有効なテキスト断片ではないとする有効性確認手段を実行することを特徴とする文書内目次認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報格納技術及び情報処理技術に関する。本発明の典型的な利用分野は、レガシー文書（在来文書）の目録、索引乃至目次となる文書をマークアップ言語フォーマットで自動生成する処理である。そこで、以下の説明ではその種の分野における本発明の利用例について説明を行う。但し、本発明は他の分野でも利用可能である。また、マークアップ言語とは、ＸＭＬ(extensible markup language)、ＳＧＭＬ(standard generalized markup language)、ＨＴＭＬ(hyper text markup language)等のことである。
【背景技術】
【０００２】
非構造化文書(unstructured document)には、しばしば、目次(table of contents;TOC)が付されている。目次はその文書におけるコンテンツの配置順序、例えば章立て、セクション分け等の文書構成を表すものである。そのため、非構造化文書を構造化して構造化文書(structured document)を生成する処理の分野では、非構造化文書から目次を抽出してフレームワークとし、そのフレームワークに基づき文書を構造化することができる手法及び装置の開発に、期待が抱かれている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
非構造化文書から抽出した目次に基づき文書を構造化する処理においては、しばしば、そのフォントサイズや修飾（強調等）内容が他の箇所と異なる部分を文書から検知し、その部分を見出しと見なして目次内項目に関連付ける（リンクを形成する）、という手法が採られる。また、その中身がページ単位で区切られており、各セクションがページを改めて始まり、更に各セクション名が目次内に項目として挙がっている体裁の非構造化文書であれば、その体裁を利用することで上述の処理をより好適に行うことができる。しかしながら、各ページの冒頭に見出し情報が記されていることもあるので、こうした手法が常に万全に働くわけではない。
【０００４】
また、目次を抽出する処理や、その目次内の項目を見出し（章見出しやセクション見出し）とリンクさせる処理で使用されている既存のアルゴリズムは、かなり信頼性が高いとはいえ完全なものではなく、リンク誤りや目次見逃しをしばしば引き起こす。例えば、章見出し又はセクション見出しと同じ文章が本文に含まれている場合、目次内項目にリンクさせるべき見出しがそれらの文章のうちどれなのかが判然としないので、そうした問題が発生する。また、複雑な構成の文書には目次が複数個あることがある。例えば複数巻からなる文書では、ある巻の目次と全く又は部分的に同じ目次が、別の巻に付されることがある。そうした文書に対して既存のアルゴリズムを適用すると、目次内項目と見出しとの関係が誤認され、ある巻に付された目次内の項目から別の巻に付された目次内の項目に至るリンクが生成されることがある。更に、光学スキャンで読み取った原稿をＯＣＲ(optical character recognition)処理して得た電子化文書にはテキスト認識誤りが含まれていることがあり、そうしたテキスト認識誤りによるリンク抽出誤りも発生する可能性がある。
【課題を解決するための手段】
【０００５】
ここに、本発明の一実施形態に係る文書内目次認識方法においては、入力装置から入力される文書から複数個のテキスト断片を抽出して認識処理に供する。認識処理では、（ｉ）目次内テキスト断片と蝟集体以外のテキスト断片との間の類似度に基づいて、蝟集体以外のテキスト断片の中から目次内テキスト断片のリンク先となるテキスト断片を認識し（ｉｉ）目次内テキスト断片それぞれについて、そのテキスト断片から目次が始まっているか否かを検証し、そのテキスト断片から目次が始まっていると判断された場合にそのテキスト断片を目次筆頭項目候補とし、目次筆頭項目候補を目次内項目の実質蝟集体の１つとし、目次筆頭項目候補に後続する蝟集体内のそれぞれのテキスト断片について、そのテキスト断片のリンク先が、直前に実質蝟集体に加えられたテキスト断片のリンク先よりも後ろである場合に、前記そのテキスト断片を実質蝟集体に加える。更に、リンク先らしきテキスト断片の認識は、少なくとも一通りの個数削減条件に従い候補を絞った上で行う。
【０００６】
また、本発明の一実施形態に係る文書内目次認識方法においては、入力装置から入力される文書から複数個のテキスト断片を抽出して認識処理に供する。認識処理では、（ｉ）目次内テキスト断片と蝟集体以外のテキスト断片との間の類似度に基づいて、蝟集体以外のテキスト断片の中から目次内テキスト断片のリンク先となるテキスト断片を認識し（ｉｉ）目次内テキスト断片それぞれについて、そのテキスト断片から目次が始まっているか否かを検証し、そのテキスト断片から目次が始まっていると判断された場合にそのテキスト断片を目次筆頭項目候補とし、目次筆頭項目候補を目次内項目の実質蝟集体の１つとし、目次筆頭項目候補に後続する蝟集体内のそれぞれのテキスト断片について、そのテキスト断片のリンク先が、直前に実質蝟集体に加えられたテキスト断片のリンク先よりも後ろである場合に、前記そのテキスト断片を実質蝟集体に加える。そして、目次内項目又はそのリンク先らしきテキスト断片として認識したテキスト断片が果たしてその種のテキスト断片であるか否かを、前記目次内テキスト断片それぞれのリンク先の拡がり率が所定値以上である場合は有効なテキスト断片であり、前記拡がり率が所定値より小さい場合は有効なテキスト断片ではないとする有効性確認手段に従い確認する。
【０００７】
そして、本発明の一実施形態に係る文書内目次認識装置は、入力装置から入力される文書から複数個のテキスト断片を抽出するテキスト断片化手段と、入力装置から入力される文書の目次所在ページの情報に基づき、目次所在ページから抽出されたテキスト断片を目次内テキスト断片の蝟集体と認識する目次領域認識手段と、（ｉ）目次内テキスト断片と蝟集体以外のテキスト断片との間の類似度に基づいて、蝟集体以外のテキスト断片の中から目次内テキスト断片のリンク先となるテキスト断片を認識し（ｉｉ）目次内テキスト断片それぞれについて、そのテキスト断片から目次が始まっているか否かを検証し、そのテキスト断片から目次が始まっていると判断された場合にそのテキスト断片を目次筆頭項目候補とし、目次筆頭項目候補を目次内項目の実質蝟集体の１つとし、目次筆頭項目候補に後続する蝟集体内のそれぞれのテキスト断片について、そのテキスト断片のリンク先が、直前に実質蝟集体に加えられたテキスト断片のリンク先よりも後ろである場合に、前記そのテキスト断片を実質蝟集体に加える目次抽出手段と、を備える。
【発明を実施するための最良の形態】
【０００８】
文書から目次を抽出するのに使用できる手法は幾つかあるが、通常は、目次抽出手段である目次エクストラクタを用いて一群のテキスト断片(text fragment)を出力する手法が採られる。目次はそれぞれその目次を構成する項目（目次内項目）を表す複数個のテキスト断片から成り立っており、目次エクストラクタからは、通常、目次内項目に相当するテキスト断片が複数個、出力される。目次内項目は、見出し例えば章見出しやセクション見出しを表すテキスト断片と対をなすべきものである。適当な条件を使用しさえすれば、こうした対応関係即ち目次内項目から見出しへのリンクを認識することができる。条件としては、テキスト断片にて使用されるフォントサイズ、フォントサイズ等のフォント特性の違いに関する条件や、ページ内位置関係に関する条件等が、用いられている。なお、目次内項目の位置やその目次内項目に対応する見出しの位置は、文書内ポインタによって指し示されることが多い。
【０００９】
これに対して、本発明の実施形態に係る目次エクストラクタ及び目次抽出アルゴリズムでは、主に、テキスト断片同士がどの程度似通っているかを表す指標、即ちテキスト類似度(textual similarity)に基づいて、目次内項目、見出し及びリンクの抽出、認識を実行する。フォント特性、ページ内位置関係等を利用してもよいがそれらは高々副次的な役割を担うに留まる。フォント特性、ページ内位置関係等の特性は文書変換プロセス実行時や文書保存時（例えばプレーンテキスト等の文書フォーマットでの保存時）に変化、消失することがあるので、本発明の実施形態に係るテキスト類似度利用型目次エクストラクタ及び目次抽出アルゴリズムによれば、従来に比べロバスト性を向上させることができる。以下、このようなテキスト類似度利用型目次抽出アルゴリズムに基づき目次エクストラクタを構築し、ロバスト性を向上させる手法及びそのための装置に関し説明する。但し、本発明に係る文書内目次認識装置及び方法は、テキスト類似度利用型目次抽出アルゴリズム乃至目次エクストラクタとしてだけでなく、それと種々の目次抽出アルゴリズム例えばフォント特性差利用型アルゴリズムやページ内位置関係利用型アルゴリズムを併用する形態等でも、実施することができる。
【００１０】
図１に文書内目次認識装置の一例構成を示す。この図の装置は非構造化文書である処理対象文書１０中の目次を認識するための装置である。そのため、テキスト断片化手段たるテキストフラグメンタ(text fragmenter)１２は、文書１０を一群のテキスト断片に分解して順序通りに並べることにより、テキスト断片蝟集序列体１４を生成する。フラグメンタ１２に文書１０としてロードされるのは、通常は文字列リストである。この文字列リストは、例えば、Ａｄｏｂｅ（登録商標）ＰＤＦ、Ｗｏｒｄ（商標）、ＦｒａｍｅＭａｋｅｒ（登録商標）等のフォーマットで入力された文書を、市販の文書コンバータによってテキスト、ＸＭＬ等のフォーマットに変換することによって、得られる。また、紙文書を光学スキャナによりスキャンし、更にＯＣＲにより処理することによって得た文書も、文書１０たる文字列リストとして好適にロードすることができる。文書１０がテキスト文書なら、例えばそのテキスト文書を構成する行を単位としてテキスト断片が抽出され、行の順序と同じ順序で並べられることとなろう。また、文書１０がＸＭＬ文書やＨＴＭＬ文書なら、ＰＣＤＡＴＡを単位としてテキスト断片が抽出されることとなろう。
【００１１】
テキスト断片を順序通りに並べる方法は種々あるが、文書内順序乃至ページ内テキスト断片位置を利用するのがよいであろう。例えば文字が横書きで各行が左から始まる文書なら、下の行より上の行を優先し同じ行内ならより左にある語を優先する上下方向優先左端開始法(depth-first left-to-right traversal)を用いるとよい。また、ＸＭＬノードとテキスト断片との関係を示す情報を保持しておき、目次内項目であることが判明したテキスト断片からそれに対応するＸＭＬノードへの後方参照関係を、処理終了時にマッピングすることができるようにしてもよい。更に、テキストフラグメンタ１２による断片化の単位は、行、ブロック、同一行内連接語群等とすることができる。場合によっては、単一の語が複数個のテキスト断片に分かれることもある。例えば、タイトルの冒頭にある語の先頭の文字を後続の文字とは異なる体裁の文字にしてある場合、当該冒頭語は、単一の語であるにもかかわらず２個のテキスト断片に分割される可能性がある。何れにせよ、フラグメンタ１２によって得られるテキスト断片蝟集序列体１４は、目次抽出手段の一部たるテキスト類似度性リンクアイデンティファイア(textual similarity link identifier)２０によって処理され、それによりリンク２２が認識される。リンク２２とは、任意のテキスト断片と、そのテキスト断片とテキスト的に類似している別のテキスト断片との対応関係、或いはそれらテキスト断片の対のことをいう。また、対をなしてリンク２２を形成するテキスト断片のうち一方はリンク元、他方はリンク先であり、リンク元のテキスト断片は、目次内項目である可能性があるため目次内項目候補とされ、リンク先のテキスト断片は、目次内項目に対応する見出しである可能性があるため見出し候補とされる。
【００１２】
リンク２２を形成するテキスト断片対を判別する手法は幾つかあるが、概ねどの手法でも、Ｎ個のテキスト断片についてリンク２２を求めるにはＮ2回オーダの計算が必要となり、またテキスト中に混入するノイズの影響を考慮した処理を実行することが求められる。ノイズ発生原因としては、文書変換や目次構成上の問題等、様々な原因を挙げることができる。例えば、ＰＤＦからテキストへのフォーマット変換時に変換誤りが生じると、その変換誤りはノイズとなる。また、目次構成上の問題に起因するノイズとしては、例えば、本文に登場しないページ番号が目次に存在するため発生するノイズや、目次内である種の記号（例えば一続きのエリプシス“………”）によりセクションタイトルとページ番号とをつないでいるため発生するノイズがある。また、リンク２２をなす対かどうかを判断するため本実施形態ではテキスト類似度を求めているが、その際には、例えば、テキスト断片間をセパレータで区切って複数個のトークンに変換する。例えば各テキスト断片が英文字からなる文字列である場合、セパレータとしては英文字でないもの、例えばタブ、スペース、句読点等を用いればよい。更に、テキスト類似度を測る指標としてはＪａｃｃａｒｄ係数や編集距離(edit distance)等がある。Ｊａｃｃａｒｄ係数は、リンク元としうるかどうかを調べたいテキスト断片から導出したトークン集合と、リンク先としうるかどうかを調べたいテキスト断片から導出したトークン集合とに基づき、それら二種類のトークン集合の積集合（交わり部分）及び和集合（合併集合）それぞれの基数(cardinal)を求め、積集合の基数を和集合の基数により除することによって、求めることができる。求めたＪａｃｃａｒｄ係数が所定のマッチングしきい値を上回っているなら、それらテキスト断片同士をリンクさせる。また、編集距離を用いる場合は、編集距離の上限を以て編集距離しきい値とする。ある２個のテキスト断片間の編集距離が編集距離しきい値より小さければ、それらはテキスト的に類似しているので、それらテキスト断片同士をリンクさせる。これらの他にも、テキスト類似度を測るのに適しリンク選択条件を定めるのに使用できる条件は幾つかある。
【００１３】
図２に類似度マトリクスの例１００を示す。このマトリクス１００は、テキスト類似度に基づくリンク２２の認識結果を視覚的に表したものである。テキスト断片間の類似関係は相互的な関係であるので、しきい値条件等のリンク選択条件に基づく処理でリンク（ｉ，ｊ）が形成されるのであれば、同じリンク選択条件に基づく処理でリンク（ｊ，ｉ）も形成される。なお、リンク（ｉ，ｊ）とはｉ番目のテキスト断片をリンク元としｊ番目のテキスト断片をリンク先とするリンク２２のことであり、リンク（ｊ，ｉ）とはｊ番目のテキスト断片をリンク元としｉ番目のテキスト断片をリンク先とするリンク２２のことである。従って、マトリクス１００の構成要素のうち計算する必要があるのは右上半分だけ（或いは逆に左下半分だけ）である。図中、リンク選択条件が成り立っている（例えばＪａｃｃａｒｄ係数が所定のマッチングしきい値を上回っている）テキスト断片対を表す升目には、その断片対がリンク２２を形成することを示す記号“Ｘ”を記してある。更に、図上は省略されているが、リンク選択条件が成り立っている（例えばＪａｃｃａｒｄ係数が所定のマッチングしきい値を上回っている）断片対には、テキスト類似度で表したリンク強度を示す指標値例えばＪａｃｃａｒｄ係数の値が関連付けられている。
【００１４】
図３に、目次認識結果の例１１０を示す。この図に示すように、本実施形態では、テキスト断片蝟集序列体１４に含まれるテキスト断片蝟集体を取り出し、取り出した蝟集体がある条件を満たす場合に、取り出した蝟集体を以て目次１１０として認識する。また、蝟集体１４に含まれる目次１１０を認識するための条件としては、大略、四種類の条件を使用している。そのうち第１の条件は蝟集性条件(contiguity)である。蝟集性条件とは、目次１１０内の項目１１２ならば蝟集体１４の中で互いに蝟集して存在しているはずである、という判断基準である。蝟集性条件を満たしていれば、そのテキスト断片は大概目次内項目１１２に該当する。また、目次内項目１１２なら、その文書１０内で目次１１０より後に位置する別のテキスト断片へと何れかのリンク２２によりリンクしているはずである。図中の矢印付曲線１１４は目次１１０内に発するリンク２２を表している。目次１１０内の項目１１２に発し対応するリンク先のテキスト断片に至るリンク１１４の集合は、テキスト類似度性リンクアイデンティファイア２０によって算出されたリンク２２の集合の部分集合となる。リンク１１４でないリンク２２が数多く存在することも多い。
【００１５】
更に、目次１１０たるテキスト断片蝟集体に含まれるテキスト断片は、大部分が目次内項目１１２であるものの、なかには袋小路(hole)になっているものもある。袋小路とは、図中の１１６のように、対応するリンク１１４がなく従って文書１０中の他の部分にリンクしていないテキスト断片のことである。袋小路１１６になるテキスト断片は比較的少数であり、通常、目次内項目１１２に対する袋小路１１６の個数比率は０．２未満である。こうした袋小路１１６については、その許容最大個数をユーザがパラメータとして設定できるようにしてもよい。このように、目次内項目１１２は、目次１１０たる蝟集体の中で（完全とはいわず）実質的に蝟集している必要がある。
【００１６】
第２の目次認識条件はテキスト類似度条件(textual similarity)である。テキスト類似度条件とは、各目次内項目１１２と、何れかのリンク１１４によってその項目１１２に結び付けられリンクしている他のテキスト断片例えば見出しとが、テキスト内容的に同様のものでなければならない、という条件である。前述のＪａｃｃａｒｄ係数等は、テキスト類似度性リンクアイデンティファイア２０により好適に計測できテキスト類似度指標値として至便に使用できるものである。また、目次内項目１１２のリンク先になりうるテキスト断片がどのようなテキスト断片であるかは、その目次１１０の性質乃至構成によって変わる。例えば目次１１０が通常の構成ならセクション見出しが、また文書内の図のリスト（図一覧表）なら図に付された表題等が、或いは表のリスト（表一覧表）なら表に付された表題等が、それぞれリンク先になる。なお、表題とは、図や表の下側等に付された文字列等のことをいう。
【００１７】
第３の目次認識条件は順序条件(ordering)である。順序条件とは、目次内項目１１２の順序と、リンク１１４を介しそれら目次内項目１１２からリンクされるテキスト断片の順序とが、同順でなければならない、という条件である。例えば、一組の目次内項目｛ｉ１，ｉ２，ｉ３，…｝が一組のリンク｛（ｉ１，ｊ１），（ｉ２，ｊ２），（ｉ３，ｊ３），…｝を介し一組のテキスト断片｛ｊ１，ｊ２，ｊ３，…｝にリンクしているとする。この場合、テキスト断片蝟集体における項目１１２の登場順序がｉ１，ｉ２，ｉ３，…の順であるなら、そのリンク先もｊ１，ｊ２，ｊ３，…の順、即ち項目１１２と同順で現れていなければならない。
【００１８】
第４の目次認識条件は自己参照忌避条件(lack of self-reference)である。自己参照忌避条件とは、各リンク１１４のリンク元のテキスト断片とリンク先のテキスト断片とが同じ目次１１０内のテキスト断片であってはならない、という条件である。即ち、目次内項目１１２の集合｛ｉ１，ｉ２，ｉ３，…｝とそのリンク先のテキスト断片の集合｛ｊ１，ｊ２，ｊ３，…｝は交わっていてはならず、更にリンク先の断片｛ｊ１，ｊ２，ｊ３，…｝の中に目次１１０内の袋小路１１６に対応するものがあってはならない。
【００１９】
図４に示すように、自己参照忌避条件と、目次は文書冒頭（又は末尾）付近にあるのが普通だという経験則とを併用すれば、類似度マトリクス１００におけるサーチエリアを更に狭めることができる。例えば、目次内項目１１２である可能性があるのが文書冒頭からｋ個のテキスト断片及び文書末尾からｋ個のテキスト断片だけであると見なしてよいなら、マトリクス１００の中央にある暗灰色正方形１２０の部分を除外領域とし、目次１１０を認識する処理を行うとよい。なお、この図の例ではｋ＝５としてある。
【００２０】
次に、再び図１を参照し、蝟集性条件、テキスト類似度条件、順序条件及び自己参照忌避条件に従いテキスト断片蝟集序列体１４の中から目次１１０たるテキスト断片蝟集体を検出する手法の例を説明する。この例では、まず目次抽出手段の一部である目次候補セレクタ３０にて、目次候補を１個又は複数個選択する。目次候補を選択する際には、例えば、蝟集体１４の中から目次筆頭項目であるかもしれないテキスト断片（目次筆頭項目候補）をＮ個選び、選んだ目次筆頭項目候補それぞれについて、従って合計ではＮ回、ある種の命題の検証に始まる処理を実行する。例えば、その目次筆頭項目候補について命題「この断片から目次が始まっている可能性があるか？」の成否を検証し、成り立つ場合はその目次筆頭項目候補に続くテキスト断片を可能な限りその目次候補に入れていく。即ち、蝟集体１４内で目次筆頭項目候補に続いているテキスト断片を次から次へと目次候補に追加して、目次候補の規模を拡張していく。但し、新たなテキスト断片を追加すると順序条件が満たされなくなる状態になったら、拡張をやめる。例えば、最近リンク元として目次候補に追加したテキスト断片のリンク先がｊ＝１５のテキスト断片及びｊ＝３３のテキスト断片であるとする。また、その次のテキスト断片のリンク先がｊ＝２０のテキスト断片だけであるとする。この場合、いま調べているテキスト断片のリンク先（ｊ＝２０）は先に追加したテキスト断片のリンク先（ｊ＝１５）より後であるので、目次候補に追加してもかまわない。これに対して、いま調べているテキスト断片のリンク先がｊ＝１２のテキスト断片だけなら、それを目次候補に追加すると順序条件が成り立たなくなるので、そのテキスト断片をその目次候補に追加することはできない。但し、順序条件を若干緩和し、目次候補内に数個の袋小路１１６が残りうるようにした方が、有益でもある。そうするには、例えば、どのリンク２２にも関連付けられていないテキスト断片を所定個数まで許容し、またリンク交差(link-crossing)のあるテキスト断片即ち関連するリンク２２が全てその目次候補内で順序条件を満たしていないテキスト断片を所定個数まで許容するようにすればよい。そうした若干のリンク交差を許容することが有益に働くのは、例えば、現在選定中の目次候補内でそのテキスト断片より前に登場しているテキスト断片が、その文書内でかなり前方に位置しているテキスト断片だけにリンクしている場合等である。
【００２１】
順序条件に基づく検証により目次候補の拡がりを調べたら、続いて自己参照忌避条件に基づく二巡目処理を実施するのが望ましい。目次候補の末尾項目がどこにあるのか見当が付かないまま目次筆頭項目候補から目次候補を拡張していく一巡目処理と異なり、二巡目処理開始段階では目次末尾項目候補がとりあえず決まっているので、自己参照忌避条件に基づく検証を行うことができる。二巡目処理では、その目次候補の先頭に位置するテキスト断片即ち一巡目処理で目次筆頭項目候補としたテキスト断片から開始して、その後に続く一連のテキスト断片を順に検証していく。同じ目次候補内のテキスト断片にしかリンクしていないテキスト断片が検証によって見つかったならば、そのテキスト断片にて自己参照忌避条件違背が生じているということであるので、その時点でその目次候補についての二巡目処理を打ち切り、自己参照忌避条件違背を引き起こしたテキスト断片の直前にある別のテキスト断片をその目次候補の目次末尾項目とする。また、二巡目処理においても、目次候補内に袋小路１１６が何個か残りうるようにした方がよい。そうするには、例えば、その目次候補内の幾つかのテキスト断片が自己参照を引き起こしていても、１個又は数個程度ならそれを許容するように、二巡目処理を実行すればよい。それら、自己参照忌避条件違背を引き起こしたテキスト断片は、その目次候補中では目次内項目１１２の候補ではなく袋小路１１６と見なされる。
【００２２】
二巡目処理は、Ｎ個の目次筆頭項目候補それぞれについて、従ってＮ回繰り返して実行される。その結果として得られるのは、それぞれテキスト断片のリストとなっており何れも蝟集性条件を満たす１個又は複数個の目次候補の集合である。それらの目次候補は、確実に順序条件及び自己参照忌避条件に従うように（或いは更に袋小路１１６を所定個数まで許容しつつ）構築されているので、当然、各目次候補内の目次内項目候補それぞれに対応する何個かのリンク２２の中から、順序条件及び自己参照忌避条件を満足するリンク２２を目次内項目候補毎に１個は、選択することができる。また、目次候補セレクタ３０にて篩い落とし条件(filtering)を適用し、明らかに目次でない目次候補を除外するようにしてもよい。例えば、ある目次候補を構成するテキスト断片の個数が３個未満である場合、その目次候補は無視するのが適当であろう。
【００２３】
目次抽出手段の一部である目次セレクタ３４は、こうして選定された目次候補にランク付けし、最高ランクの目次候補を選択する。リンクオプティマイザ３８は、その最高ランク目次候補に係るリンク２２を最適化することによって、最終的な目次１１０を生成する。この場合、セレクタ３４が目次候補にランク付けするため実行する処理の計算量は比較的少なく、選択された目次候補に対してオプティマイザ３８が施す処理はより徹底した計算を伴う。本願出願人の知見によれば、このやり方は、目次１１０を正確に抽出できるという点でも上首尾な手法である。また、各目次候補にリンク最適化を施し、リンク最適化後の一群の目次候補をランク付けする、というやり方も、計算量が多くなるが採用に値するやり方である。
【００２４】
図１に基づき更に説明すると、目次セレクタ３４では、スコアリング関数を使用して各目次候補にランク付けし、その中で最高ランクの目次候補を目次１１０として選択して、後の処理に供する。目次セレクタ３４にてスコアリング関数として使用できる量としては、項目荷重総和、項目総数、文書内見出し分布拡がり率等、種々の量がある。それらのうち項目荷重総和は、各目次内項目候補に関連付けられているリンク２２の個数に反比例するように項目荷重を定め、項目荷重をその目次候補内で総和することによって得られる。一般に、あるテキスト断片に発するリンク２２がその目次候補における“真正な”リンク１１４である確率は、同じテキスト断片に発するリンク２２の個数が多ければ多い程低くなるので、項目荷重によって各リンク２２の確からしさを評価することができる。また、スコアリング関数として使用でき熟考に値する量としては、更にその目次候補内の項目総数がある。順序条件及び自己参照忌避条件を満足するテキスト断片が数多く蝟集していることが判明している“長大な”目次候補は、それより“短小な”目次候補に比べより“真正な”可能性が高いものであるといえる。もう一つ、スコアリング関数として熟考に値する量としては、処理対象文書１０の全体に対する見出し分布範囲の割合、即ち文書内見出し分布拡がり率がある。例えば、ある同じ目次候補内の種々のテキスト断片からのリンク先が、その文書１０内の比較的狭い部分内に蝟集している場合、その目次候補がその文書１０の“真正な”目次１１０である確率は低い。なお、以上の量はスコアリング関数の例に過ぎず、従ってこれら以外のスコアリング関数を使用することも、また何種類かのスコアリング関数を組み合わせて使用することも可能である。
【００２５】
最高ランクが付された目次候補に対しては、最終的な目次１１０を得るべく、リンクオプティマイザ３８が適用される。リンクオプティマイザ３８は、その最高ランク目次候補に係るリンク２２について大局的に最適な解を導出することによって、その目次に係るリンク２２の中で最良のリンク２２を目次内項目１１２毎に選択し、それによって最終的な目次１１０を構築する。最良リンク選択に当たっては、目次認識に使用した蝟集性条件、テキスト類似度条件、順序条件及び自己参照忌避条件の四条件が引き続き満足されるようにする。更に、最良リンク選択の手法としては、例えばマッチングの度合いに比例する荷重を各リンクに割り当てそれを利用して最適リンクを選択する、Ｖｉｔｅｒｂｉの最短パスアルゴリズム(Viterbi shortest path algorithm)を用いて最適リンクを選択する等、種々のアルゴリズムを使用できる。
【００２６】
こうして認識した目次１１０は種々の処理に使用できる。例えば、各セクションの見出しが互いに別々の目次内項目１１２からリンクされるように、目次１１０に基づき処理対象文書１０をセクション分割することによって、その文書１０を構造化することができる。また、目次１１０を用いて文書１０を自動的に構造化する場合は、通常、順序条件を厳密に適用した方が有利である。これは、構造化文書のフォーマット時に交差リンクがエラーを引き起こすからである。また、ここに述べた例はとりわけテキスト部分の索引となる目次１１０を認識する例であるが、順に図、表、式等の索引である図一覧表、表一覧表、式一覧表等を目次１０として生成する例でも、同様の処理を適用でき類似した効果を得ることができる。
【００２７】
次に、目次抽出におけるロバスト性改善手法及びその用途例について、テキスト類似度利用型目次抽出アルゴリズム及びそれを用いた目次エクストラクタを念頭に置いて説明する。但し、他の目次抽出アルゴリズムに対しても、同様の手法を広く適用することができる。
【００２８】
本発明の実施形態に係る手法においては、大まかには、候補テキスト断片個数削減、認識結果有効性確認又はその組合せを実施して、目次抽出におけるロバスト性を改善している。それらのうち、候補テキスト断片個数削減とは、目次内項目候補たるテキスト断片、そのリンク先として認識されうるテキスト断片、又はその双方の個数を、一通り又は複数通りの個数削減条件に従い削減する、という処理である。また、これの代わりに又はこれと共に実行される認識結果有効性確認は、認識した目次内項目１１２及びそのリンク先の有効性を、リンク先分布に関連する一通り又は複数通りの有効性確認条件に従い確認し、それによってロバスト性を向上させる、という処理である。
【００２９】
図１に示す実施形態においては、テキスト類似度性リンクアイデンティファイア２０によって一通り又は複数通りの個数削減条件１３０が適用され、それによって見出し候補の個数が削減される。ここで使用される条件１３０は様々な手段で定義できる。例えば、一種類又は複数種類の基準書式によって条件１３０を定義しておき、それらの基準書式とマッチするもの（又はマッチしないもの）を見出し候補から除外する。具体的には、索引数字、索引英文字、索引ローマ数字等のようにテキスト断片の先頭に付される索引部分について基準書式を設定しておき、基準書式として定められている索引部分書式に合致しないテキスト断片を見出し候補から除外する。各目次内項目１１２に章番号（章１、章２等々）や英字によるセクション索引（Ａ．はじめに、Ｂ．問題点の説明等々）等の索引部分がある場合、こうしたやり方が有益である。
【００３０】
基準書式の具体例としては、第２に、一般に章見出しやセクション見出しを表すキーワード、例えば「編」「巻」「章」「部」「セクション」やそれらの任意の組合せが含まれているテキスト断片に、候補を絞る書式がある。見出しであることを表すキーワードを何も含んでいないテキスト断片は、この基準書式を満足しないテキスト断片であるので、見出し候補から除外される。更に、この種の基準書式にてキーワード位置を指定することも可能である。例えば、“Ｃｈａｐｔｅｒ  ＊”といった表現によって、大文字のＣで始まる“Ｃｈａｐｔｅｒ”即ち「章」を意味する語が先頭にあり、その後に１文字分のスペースが続き、更にその後に任意のテキスト部分（“＊”）が続く、という位置関係を、指定することができる。また、基準書式で指定したキーワードが現れていさえすれば基準書式を満足していると見なされ、そのキーワードの位置が問われないように、基準書式を定めることもできる。
【００３１】
基準書式の具体例としては、第３に、含まれる英文字が全て大文字であるテキスト断片だけを候補にするための書式がある。この種の書式を基準書式として使用すれば、テキスト類似度性リンクアイデンティファイア２０にて、小文字の英文字を含むテキスト断片を以後の処理対象から除外することができる。また、これと類似する書式として、小文字の英文字が２個又はそれ以上含まれるテキスト断片を候補から除外する書式等がある。そうした類似書式も基準書式として使用できる。以上、基準書式の具体例を示したが、基準書式として使用できる書式はこれらの具体例以外にも数多くある。また、それらの書式は単独でも、或いは任意に組み合わせた形態でも、基準書式として使用できる。更に、本願における「基準書式」とは、その基準書式とテキスト断片との比較、照合を計算機ベースで実行できる書式のことをいう。当該比較、照合を計算機ベースで実行する方法は種々あり、例えばキーワードを含むテキスト断片をある種のテキストサーチアルゴリズムによって見つけ出す手法や、有限状態ネットワークベースオートマトンを用いて単純な若しくは複雑な文字列パターンと比較する手法等を、使用することができる。
【００３２】
また、個数削減条件１３０のうち何個かを、テキスト断片のページ内位置に基づく条件又はその組合せとすることもできる。そうするには、例えば、テキスト断片の抽出元である処理対象文書１０がページ内位置情報を含むフォーマットの文書例えばページ内レイアウト情報を伴うＰＤＦ文書であり、且つ、テキストフラグメンタ１２がテキスト断片蝟集体における各テキスト断片のページ内位置を検知でき且つそれをそのテキスト断片に関連付けることができねばならない。ページ内位置情報は、例えばページ内縦方向位置、ページ内横方向位置等、そのページ内における断片抽出位置をテキスト断片毎に特定する情報である。ページ内縦方向位置は、例えばそのページの上端からの距離によって表せる他、複数行を有する横書き文書であれば行番号等によっても表せる。ページ内横方向位置は、ページ内縦方向位置と同様に（但しページの左端や右端を基準に）表せる他、ページ内が複数個の縦長のブロック（いわゆるカラム）に分割されている横書き文書であれば、カラム番号によって表すこともできる。
【００３３】
ページ内位置に基づく個数削減条件１３０としては、例えば（ｉ）そのページの先頭から所定距離内にあるテキスト断片だけを見出し候補にするという条件、（ｉｉ）そのページの最左端カラムを表すカラム番号に関連付けられているテキスト断片だけを見出し候補にするという条件、条件（ｉ）と条件（ｉｉ）の組合せ条件等がある。条件（ｉ）は、章やセクションはページの先頭（例えば上端や左端や右端）から始まるものである、というアプリオリな知識に基づくものであり、条件（ｉｉ）は、複数カラム文書の章やセクションはページの最左端カラムから始まるものである、というアプリオリな知識に基づくものである。但し、これらはページ内位置関係に基づく条件１３０の例に過ぎず、文書ページ内レイアウトに関する種々のアプリオリな知識を利用すれば、ページ内位置関係に基づく条件１３０を種々に設定できる。それらの条件１３０は任意に利用できる。
【００３４】
これら、ページ内位置関係乃至ページ内レイアウトに基づく個数削減条件１３０を適用できるのは、専ら見出し候補の個数削減に対してであり、目次内項目候補の個数削減のために同種の条件を適用するのは難しい。それは、章見出しやセクション見出しは文書構成上ページ先頭に置かれることが多く、従ってページ内位置関係に基づく条件１３０を適用することで見出しらしきテキスト断片を選定できるのに対して、目次１１０は目次内項目１１２の羅列であり、従って目次内項目候補はページの大部分に亘って或いは複数のページに跨って分布することが多いので、ページ内位置関係に基づく条件では目次内項目１１２らしきテキスト断片を選定できないためである。このように、見出し候補の個数削減には割合に適しているが目次内項目候補の個数削減にはさほど適していない等、条件によって適不適はあるものの、基準書式を利用して条件を記述することで、見出し候補の個数削減に適する条件１３０、目次内項目候補の個数削減に適する条件１３０、その双方に適する条件１３０等を、任意にまた好適に設定することができる。
【００３５】
また、テキスト断片蝟集序列体１４中の然るべきテキスト断片蝟集体を目次１１０として認識するには、例えば然るべく構成されているユーザインタフェース１３６によってユーザから与えられた情報に基づき、目次領域１３４即ち目次１１０を含む領域を認識するようにすればよい。具体的には、目次抽出元たる処理対象文書１０全体をユーザが調べ、ユーザがその結果に基づき目次１１０の所在ページ（群）を指定し、テキストフラグメンタ１２にて文書１０を断片化して一群のテキスト断片を生成し、ユーザが指示した目次所在ページ（群）から抽出されたテキスト断片だけを、領域１３４内の項目と見なすようにする。また、目次１１０があるのは大抵は文書冒頭であろうという期待的知識からすれば、テキスト断片のうち文書１０の冒頭から５％、１０％等々までの範囲内にあるテキスト断片、即ち文書１０の冒頭部分を以て領域１３４とするのがよいであろう。この手法なら、目次内項目候補の個数だけでなく見出し候補の個数も削減できる。即ち、領域１３４による目次内項目候補個数制限と、個数削減条件１３０の適用による見出し候補個数削減の併用によって、目次抽出速度をかなり改善することができる。
【００３６】
しかしながら、これらの手法、即ち目次領域１３４による目次内項目候補個数制限や何種類かの個数削減条件１３０の適用による見出し候補個数削減だけでは、単一の処理対象文書１０内に複数個の目次がありそれらの目次の内容に重複があることによって生じる問題に、対処することができない。こうした問題が生じるのは、例えば、文書１０が複数巻から構成されており、その文書１０のある巻に付された目次のコピーが同じ文書１０の別の巻に目次として付されている場合や、ある巻に付された目次の部分コピーが他の巻に目次として付されている場合等である。後者の例としては、その文書１０を構成する全ての巻の全ての章若しくはセクションの名称を羅列した総目次の他に、巻毎に、その巻に含まれる章若しくはセクションの名称を羅列した巻別目次が設けられる場合がある。
【００３７】
図５に、総目次１４０の他にコピー版目次１４２を有しており、そのコピー版目次１４２が例えば第２巻冒頭に付されている処理対象文書１０の例を示す。コピー版目次１４２内のテキスト断片は総目次１４０内のテキスト断片とよく似通っている（或いは全く同じである）ので、こうした文書１０を対象として目次認識プロセスを実施すると、総目次１４０内のテキスト断片のうち何個か（或いはその大多数）のリンク先が誤認され、コピー版目次１４２内のテキスト断片にリンクされてしまうこととなりかねない。図５に示した例はなかでも最悪のケース、即ち総目次１４０内の全項目がコピー版目次１４２内のテキスト断片にリンクしてしまっているケースである。
【００３８】
図６に、図５の例程極端ではないがなお問題のある例を示す。この図に示す処理対象文書１０には、目次１５０、第１巻中のセクションＡに付されたセクション見出し１５２、第１巻中のセクションＢに付されたセクション見出し１５４、第２巻冒頭の目次１５６、第２巻中のセクションＣに付されたセクション見出し１５８等が含まれており、また目次１５６は目次１５０のコピー版となっている。この例では、目次１５０内の項目のうちセクションＡ及びＢに対応する項目に対し、対応する見出し１５２及び１５４（同順）が正しく関連付けられ、正しいリンクが形成されている。しかしながら、目次１５０内の項目のうちセクションＣ、Ｄ及びＥに対応する項目に対しては、誤って目次１５６内のテキスト断片が関連付けられ、誤ったリンクが形成されている。更に、セクションＣに付されたセクション見出し１５８についてもリンク誤りがあり、この見出し１５８はどの目次内項目からもリンクされていない。なお、その巻に含まれる章やセクションだけを羅列した巻別目次が各巻に付されておりそれら巻別目次が別の目次（例えば総目次）の部分コピーとなっている場合等においても、これと類似した状況が発生しうる。
【００３９】
図５に示した状況や図６に例示した状況に対しては、図１に示すように、一群のテキスト断片のうち目次１１０を構成するものとして抽出されたテキスト断片の有効性を、リンク先テキスト断片たる見出しの分布に関連する一通り又は複数通りの有効性確認条件１６２に従い、有効性確認手段たる目次バリデータ１６０が確認することによって、好適に対処することができる。条件１６２とするに相応しい条件としては、例えば、処理対象文書１０における見出し分布拡がり（スパン）率による条件がある。コピー版目次１４２の拡がりは見出し分布程広くないので、この条件は、図５に示した状況又はそれに類似した状況にて大きな効果を発揮する。具体的には、抽出した目次１１０を構成するテキスト断片のリンク先となっているテキスト断片の分布の拡がりが、例えば約１０％〜２０％に設定されている拡がり率しきい値を上回っている場合、少なくともその条件についてはそれら目次１１０を構成するテキスト断片は有効である、と判断する。但し、注意すべきことであるが、この拡がり率条件だけでは、図６に示した種類の誤り等を認識できない場合がある。即ち、目次１５０内の項目からのリンクの一部だけがコピー版目次１５６内のテキスト断片に達しているというリンクの誤りを、全て認識できるとは限らない。それは、正しいリンク先である見出し並びに誤ったリンク先であるテキスト断片を含むリンク先断片の分布の拡がり率が、拡がり率しきい値を上回ることがあるためである。
【００４０】
また、図５の例のように総目次１４０とコピー版目次１４２との間に１対１の対応関係がある状況やそれに類する状況に対しては、別の手法で対処することもできる。例えば、一群の目次内項目１１２がある場所に蝟集しており、それら目次内項目１１２と１対１に対応するリンク先のテキスト断片が所定個数以上蝟集している場合に、後者即ち互いに蝟集している一群のリンク先テキスト断片に係るリンクを無効リンクとすればよい。この処理は例えば目次バリデータ１６０にて行う。目次内項目１１２と１対１に対応するリンク先テキスト断片が所定個数以上蝟集していることが判明したとき、無効リンクリムーバ１６４は、それら無効リンクに係る一群のリンク先テキスト断片を、見出しとして認識済のテキスト断片の集合から除外し、目次セレクタ３４及びリンクオプティマイザ３８は、それら一群のリンク先テキスト断片を見出し候補から除外して目次１１０を再認識する。このやり方を適用できるのは、図５に示した例即ちコピー版目次１４２が総目次１４０の厳密なコピーである状況だけではない。例えば、コピー版目次が総目次の部分コピーであり、他の目次内の項目との間に１対１の対応関係があり、その項目からリンクされているテキスト断片がその部分コピー内で所定個数以上蝟集している状況にも、適用することができる。但し、蝟集体同士の１対１対応関係が厳密には成立していない“実質的な”部分コピーに関しては、この手法では認識できないことがある。
【００４１】
更に、図６に示した例のように目次１５０内の項目がコピー版目次１５６内のテキスト断片のうち一部に誤ってリンクしている状況に対処するには、例えば次のような条件を有効性確認条件１６２として使用すればよい。即ち、目次内項目１１２として認識されたテキスト断片が蝟集している目次部分と、その目次部分のコピー部分とがあるが、両部分が実質的な蝟集体であってテキスト断片が必ずしも厳密に蝟集しているわけではなく、しかもコピー部分が目次部分の実質的なコピーであって厳密なコピーであるとは限らない状況下でも、コピー部分内テキスト断片以外のテキスト断片にリンクしている目次部分内テキスト断片を有効と判別できる条件を使用するとよい。この条件を条件１６２として使用する際には、目次内項目１１２として認識されているテキスト断片の実質蝟集体の実質コピー部分を適当なサーチ手法でサーチすることが必要となる。また、そのサーチ手法は、例えば文書の欠陥やリンク誤りや目次内の袋小路のような原因で生じたノイズによる若干の違いを許容し、目次内項目１１２に対するその“実質的な”コピーを発見することができるものでなければならない。更に、その手法は、目次内項目１１２の集まりとして認識されている断片実質蝟集体の実質コピーである部分コピーを認識できる手法でなければならない。
【００４２】
好適に使用できるサーチ手法としては、例えば、その目次１１０内の項目１１２と、その目次１１０のコピーかもしれないテキスト断片の集まり（コピー候補）とを、ある種の文字列評価指標(figure of merit)により対照する手法を用いるとよい。文字列評価指標として使用できるものには、少なくとも、（ｉ）目次内項目１１２とコピー候補内テキスト断片との間のテキスト類似度を表すテキスト類似度指標、並びに（ｉｉ）目次内項目１１２とコピー候補内テキスト断片とに共通に含まれる最長の文字列即ち最長共有文字列等がある。目次エクストラクタにおける処理アルゴリズムとして例えば先に例示したテキスト類似度利用型処理アルゴリズムを使用するのであれば、テキスト類似度指標はリンク２２から直ちに得ることができる。また、テキスト類似度利用型以外の処理アルゴリズム例えばフォント利用型処理アルゴリズムを使用する場合でも、類似度に関する前述のＪａｃｃａｒｄ係数等をテキスト類似度指標として使用することができる。
【００４３】
また、ある２個のテキスト断片についてその最長共有文字列を求めるには、それらのテキスト断片をシーケンシャルに相互対比すればよい。ある２個のテキスト断片から通常の手法によって最長共有文字列を求める際には、それら２個のテキスト断片が一致していなければ二通りの選択肢即ち第１のテキスト断片を無視する選択肢及び第２のテキスト断片を無視する選択肢の何れを採るかを検討するのであるが、本実施形態の場合そうした検討は行わず、ページ内の文字を順繰りに読むとき先に読まれる方のテキスト断片を無視するようにする。この手法は、線形複雑度法(linear complexity)によってまた記憶無しで、しかも１ページ内の相違箇所数が許容最大個数に至るまではそれらの相違を許容しつつ、目次１１０のコピーを発見できる手法である。具体的には、所与の目次候補中の最初の目次内項目候補と、処理対象文書１０の本文に含まれておりその目次内項目候補に対応するテキスト断片であるかもしれないＮ個のテキスト断片とにより、Ｎ個のテキスト断片対を形成し、それら断片対を調べるようにするとよい。最初の目次内項目候補と対をなすＮ個のテキスト断片は、何れも、その目次に対応するコピー版目次の始まりである可能性がある。この手法は、その始まりに関するある種の命題を満足するものだけを目次候補とすることができ、目次候補であれば同じ項目から始まるという仮定に基づくものである（これに類する重要な手法としては、目次内項目候補のうち冒頭からＭ個（Ｍ：相違の最大許容個数）の目次内項目候補それぞれについてＮ個のテキスト断片それぞれとの対を形成し、それらの対を全て調べるという手法があり、その手法によれば更にロバスト性を高めることができる）。また、Ｎ個の断片対毎に繰り返し実行される処理の内容は、
【数１】
0005144940.tif 000002
で表される通りである。この繰り返し処理においては、１ページ内の相違を最大許容個数まで許容しつつ、対をなすテキスト断片同士をシーケンシャルに対比していく。上述の処理中のイズアフタ述語（is-after predicate)は文書内順序に従って２個のテキスト断片の位置を比較する述語であり、この述語ではまずページ順を、次いでカラム順を、そして縦方向位置を比較する。また、目次１１０の部分コピーを見つける際にも、その目次１１０の始まりにあるテキスト断片と同じテキスト断片からその部分コピーが始まっているのであれば、同様のやり方でそのテキスト断片を探すことによりその部分コピーを発見することができる。仮に、その目次１１０の始まりにあるテキスト断片と同じテキスト断片がその部分コピーに含まれていなくても、新たなページの冒頭にあるテキスト断片から順に全てのテキスト断片について同様の手法を適用し、そのテキスト断片と同じテキスト断片を探していくことにより、その部分コピーを発見することができる。
【００４４】
更に、上述の通り最長共有文字列型の文字列評価指標を使用する手法では、カラムやページへの分割の仕方やページ上での配置の仕方が目次でもそのコピーでも同じである、という前提乃至制約条件をおいているが、この制約条件をより緩くすることもできる。即ち、より一般化された（応用の利く）最長共有文字列型文字列評価指標を使用することもできる。但し、実施の仕方によっては、より込み入った処理が必要になる可能性がある。
【００４５】
ある目次についてその実質コピーが見つかったら、目次バリデータ１６０は、リンク元たる目次内項目１１２に発しその実質コピー内のテキスト断片に達するリンク２２があるかどうかをチェックする。バリデータ１６０は、実質コピー内に達するリンク２２があればそれを無効リンクと認定し、無効リンクリムーバ１６４は、見出しとして認識済のテキスト断片の集合から当該実質コピー内のリンク先テキスト断片を除外し、目次セレクタ３４及びリンクオプティマイザ３８は、見出し候補から当該実質コピー内のテキスト断片を除外して見出し１１０を再認識する。この処理手順は、自分自身のコピーに至るリンク２２を有していない目次１１０が選定されるに至るまで繰り返し実行される。
【００４６】
有効性確認が終われば最終的な目次１１０が得られる。この目次１１０は、好適なことに、種々の目的に使用することができる。即ち、抽出された目次１１０は、実質的に蝟集しておりそれぞれ目次内項目１１２となる一群のテキスト断片と、それぞれ対応する目次内項目１１２にリンクしている別の一群のテキスト断片とを含んでいるので、これを利用することにより、例えば文書オーガナイザ１７０が文書を組織化してＸＭＬやＨＴＭＬによる構造化文書等を生成することができる。
【図面の簡単な説明】
【００４７】
【図１】文書内目次認識装置の一例構成を示す図である。
【図２】１５個のテキスト断片を含む文書についての類似度マトリクスの例を示す図である。
【図３】目次認識結果の例を示す図である。
【図４】目次内項目となりえないテキスト断片に係る部分を目次内項目候補から除外する処理の一例を、図２に示した類似度マトリクスに基づき示す図である。
【図５】テキスト断片実質蝟集体を形成する各目次内項目が、目次抽出手段によって誤って関連付けられコピー版目次内のテキスト断片にリンクしてしまっている状況を示す図である。
【図６】テキスト断片実質蝟集体を形成する各目次内項目が、目次抽出手段によって一部は正しく関連付けられセクション見出したるテキスト断片にリンクしているものの、同じ目次抽出手段によって他の一部が誤って関連付けられコピー版目次内のテキスト断片にリンクしてしまっている状況を示す図である。
【符号の説明】
【００４８】
１０  処理対象文書（非構造化文書）、１２  テキストフラグメンタ、１４  テキスト断片蝟集序列体、２０  テキスト類似度性リンクアイデンティファイア、２２，１１４  リンク、３０  目次候補セレクタ、３４  目次セレクタ、３８  リンクオプティマイザ、１００  類似度マトリクス、１１０，１４０，１４２，１５０，１５６  目次、１１２  目次内項目、１１６  袋小路、１２０  除外領域、１３０  個数削減条件、１３４  目次領域、１３６  ユーザインタフェース、１４４  リンク先テキスト断片、１５２，１５４，１５８  セクション見出し、１６０  目次バリデータ、１６２  有効性確認条件、１６４  無効リンクリムーバ、Ａ〜Ｅ  セクション。
【図１】
0005144940.tif 000003
【図２】
0005144940.tif 000004
【図３】
0005144940.tif 000005
【図４】
0005144940.tif 000006
【図５】
0005144940.tif 000007
【図６】
0005144940.tif 000008