目次判別目的類似度リンク計算の高速化
【課題】文書内目次認識に際するテキスト断片比較の回数を抑え処理時間を短縮する。
【解決手段】索引テキスト断片序列体３１４中葉のテキスト断片を起点ｉ（０）とし、それより冒頭寄り及び末尾寄りから選んだテキスト断片をそれぞれ冒頭側処理対象Ｌ（０）及び末尾側処理対象Ｈ（０）とする。本文テキスト断片序列体内からリンク先候補を選んで起点リンク先候補集合を形成しそれらにおける最小順序及び最大順序を求める。起点ｉ（０）には起点リンク先候補集合を、冒頭側処理対象Ｌ（０）には最小順序より冒頭寄りのリンク先候補本文テキスト断片の集合を、末尾側処理対象Ｈ（０）には最大順序より末尾寄りのリンク先候補本文テキスト断片の集合を関連付ける。以後の各巡では、それまでの処理対象Ｌ（０）及びＨ（０）を冒頭側起点ｉL（１）及び末尾側起点ｉH（１）として同様の処理を繰り返す。
【解決手段】索引テキスト断片序列体３１４中葉のテキスト断片を起点ｉ（０）とし、それより冒頭寄り及び末尾寄りから選んだテキスト断片をそれぞれ冒頭側処理対象Ｌ（０）及び末尾側処理対象Ｈ（０）とする。本文テキスト断片序列体内からリンク先候補を選んで起点リンク先候補集合を形成しそれらにおける最小順序及び最大順序を求める。起点ｉ（０）には起点リンク先候補集合を、冒頭側処理対象Ｌ（０）には最小順序より冒頭寄りのリンク先候補本文テキスト断片の集合を、末尾側処理対象Ｈ（０）には最大順序より末尾寄りのリンク先候補本文テキスト断片の集合を関連付ける。以後の各巡では、それまでの処理対象Ｌ（０）及びＨ（０）を冒頭側起点ｉL（１）及び末尾側起点ｉH（１）として同様の処理を繰り返す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報格納技術及び情報処理技術、特にレガシー文書（在来文書）の目録、索引乃至目次となる文書をＸＭＬ(extensible markup language)、ＳＧＭＬ(standard generalized markup language)、ＨＴＭＬ(hyper text markup language)等のマークアップ言語フォーマットで自動生成する技術等、種々の分野に関する。
【背景技術】
【０００２】
文書からその目次を抽出する処理においては、通常、テキスト断片(text fragment)同士を比較する手法が用いられている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、この手法には、文書内における目次(table of contents;TOC)の位置が判明していない場合、テキスト断片同士の比較をＮ×（Ｎ−１）／２回行わねばならないという問題がある（Ｎ：文書に含まれるテキスト断片の個数）。このようにＮ2回オーダの比較計算が必要になる手法は、とりわけ文書規模が大きい場合に厄介で能力を消費するものとなる。例えば、テキスト断片を２００００〜６００００個含む文書についてこの手法を適用するとしたら、約２×１０8〜１．８×１０9回の比較が必要になる。
【０００４】
文書内における目次の位置が判明しているのであれば、比較の回数はＮ×Ｔ回まで減る。Ｎは本文テキスト断片の個数（〜文書内テキスト断片個数）、Ｔは目次内の索引テキスト断片の個数である。例えば文書内テキスト断片個数が２００００〜６００００個、目次内の索引テキスト断片の個数が１００〜３００個であれば、比較の回数は２×１０6〜１８×１０6回ですむ。ただ、これはＮ2回オーダの比較計算回数に比べれば少数であるが、それでもまだ多すぎる。
【課題を解決するための手段】
【０００５】
ここに、本発明の一実施形態に係る文書内目次認識方法においては、索引テキスト断片序列体中葉に位置する起点索引テキスト断片に、本文テキスト断片序列体内から選んだ１個又は複数個のリンク先候補本文テキスト断片からなる起点リンク先候補集合を関連付け、起点索引テキスト断片より冒頭寄りにある冒頭側処理対象索引テキスト断片に、起点リンク先候補集合内最末尾本文テキスト断片より冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付け、起点索引テキスト断片より末尾寄りにある末尾側処理対象索引テキスト断片に、起点リンク先候補集合内最冒頭本文テキスト断片より末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付ける。
【０００６】
また、本発明の一実施形態に係る文書内目次認識方法においては、（ａ）索引テキスト断片序列体中葉に位置する起点索引テキスト断片に、本文テキスト断片序列体内から選んだ１個又は複数個のリンク先候補本文テキスト断片からなる起点リンク先候補集合を関連付け、（ｂ）索引テキスト断片序列体内索引テキスト断片のうち起点索引テキスト断片より冒頭寄りの索引テキスト断片の集合である冒頭寄り部分集合の中葉に位置することとなるよう、冒頭側処理対象索引テキスト断片を選択し、（ｃ）索引テキスト断片序列体内索引テキスト断片のうち起点索引テキスト断片より末尾寄りの索引テキスト断片の集合である末尾寄り部分集合の中葉に位置することとなるよう、末尾側処理対象索引テキスト断片を選択し、（ｄ）冒頭側処理対象索引テキスト断片に、起点リンク先候補集合内最末尾本文テキスト断片より冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付け、（ｅ）末尾側処理対象索引テキスト断片に、起点リンク先候補集合内最冒頭本文テキスト断片より末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付け、（ｆ）それまでの冒頭側処理対象索引テキスト断片を起点索引テキスト断片として、冒頭寄り部分集合についてステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）における選択動作及び関連付け動作と同様の動作を実行し、（ｇ）それまでの末尾側処理対象索引テキスト断片を起点索引テキスト断片として、末尾寄り部分集合についてステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）における選択動作及び関連付け動作と同様の動作を実行する。
【０００７】
本発明の一実施形態に係り、索引テキスト断片序列体及び本文テキスト断片序列体を含む文書中の目次を認識する方法においては、索引テキスト断片序列体内で冒頭側処理対象索引テキスト断片の末尾側にＮ個蝟集して連接している索引テキスト断片に係る最末尾リンク先候補本文テキスト断片に比べ、冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片を、その冒頭側処理対象索引テキスト断片に関連付け、索引テキスト断片序列体内で末尾側処理対象索引テキスト断片の冒頭側にＭ個蝟集して連接している索引テキスト断片に係る最冒頭リンク先候補本文テキスト断片に比べ、末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片を、その末尾側処理対象索引テキスト断片に関連付け、それまでの冒頭側処理対象索引テキスト断片より冒頭寄りの索引テキスト断片を新たな冒頭側処理対象索引テキスト断片とし、それまでの末尾側処理対象索引テキスト断片より末尾寄りの索引テキスト断片を新たな末尾側処理対象索引テキスト断片とし、これら、冒頭側処理対象索引テキスト断片へのリンク先候補の関連付け、末尾側処理対象索引テキスト断片へのリンク先候補の関連付け、冒頭側処理対象索引テキスト断片の更新、並びに末尾側処理対象索引テキスト断片の更新を繰り返すことによって、索引テキスト断片に係る１個又は複数個のリンク先候補本文テキスト断片の集合を生成する。
【発明を実施するための最良の形態】
【０００８】
テキスト断片同士の比較により目次を抽出する際には、通常、目次内項目であるかもしれない一組の索引テキスト断片（目次内項目候補）と、そのリンク先となるテキスト断片即ち章見出しやセクション見出し等の見出しであるかもしれない一組の本文テキスト断片（見出し候補）と、の対応関係を当該比較により求め両者を関連付ける。この関連付け乃至対応関係のことをリンクと呼ぶ。また、目次内項目候補及び見出し候補の文書内位置については、例えば文書内ポインタによって指し示すことができる。関連付けの要否については、フォントサイズ、フォントタイプ、フォントスタイル、大文字の有無、下線の有無等の様々な条件に従い決定することができる。
【０００９】
以下の説明では、テキスト断片同士がテキスト的にどの程度似通っているかを示す指標であるテキスト類似度(textual similarity)に基づき、テキスト断片同士を比較し、それによって文書から目次を抽出する実施形態を採り上げる。ご理解頂けるように、本発明の実施形態はそうした実施形態に限られるわけではなく、本発明の実施に当たり採用できるテキスト断片比較手法は様々である。例えば、テキスト類似度、フォントサイズ、フォントタイプ、フォントスタイル、大文字の有無、下線の有無等の条件や、それらの任意の組合せによる条件に従い、テキスト断片同士を比較する手法を採ることができる。
【００１０】
図１中の処理対象文書８は非構造化文書(unstructured document)である。例えば、ワードプロセッサやスプレッドシート等のアプリケーションソフトウェアを使用して作成した文書や、紙等の原稿を光学スキャンして得た文書等、様々な手段によって得た文書を処理対象文書８とすることができる。また、同図中の目次領域１０は、ユーザインタフェース９を介しユーザが指定する、同図の装置が自動的に認識する等のやり方によって定められた文書８内の領域である。領域１０の自動認識に使用できるやり方としては、例えば、何個かのエリプシス（“…”）が連なった後にページ番号が付されているテキスト断片をサーチする、文字の羅列の冒頭又は末尾に数字が付されている行を探す、文書８の作成に使用したワードプロセッサ等のアプリケーションソフトウェアによって文書８内の領域１０を自動認識させる、等々がある。テキストフラグメンタ(text fragmenter)１２は、文書８を索引テキスト断片序列体１４と本文テキスト断片序列体１６とに分解する。テキスト断片序列体とは複数個のテキスト断片をその順序通りに並べたものをいい、なかでも（ｉ）序列体１４は索引テキスト断片を並べたもの、（ｉｉ）序列体１６は本文テキスト断片を並べたものである。索引テキスト断片とは文書８内の領域１０から抽出したテキスト断片を、また本文テキスト断片とは文書８内の１個又は複数個の領域（但し領域１０以外或いは序列体１４以外）から抽出したテキスト断片を、それぞれ指している。通常、文書８は文字列リストとしてロードされる。文書８たる文字列リストは、例えばＡｄｏｂｅ（登録商標）ＰＤＦ、Ｗｏｒｄ（商標）、ＦｒａｍｅＭａｋｅｒ（登録商標）等のフォーマットで入力された文書を、市販の文書コンバータを用いテキスト、ＸＭＬ等のフォーマットに変換することによって得たものである。また、紙文書を光学スキャナによりスキャンし、更にＯＣＲ(optical character recognition)により処理することによっても、文書８たる文字列リストを好適にロードすることができる。文書８がテキスト文書なら、例えばそのテキスト文書を構成している行を単位としてテキスト断片が抽出され、行の順序と同じ順序で並べられることとなろう。また、文書８がＸＭＬ文書やＨＴＭＬ文書なら、例えばＰＣＤＡＴＡを単位としてテキスト断片が抽出されることとなろう。
【００１１】
テキスト断片を順序通りに並べる方法は種々あるが、文書内順序乃至ページ内テキスト断片位置を利用するのがよいであろう。例えば文字が横書きで各行が左から始まる文書なら、下の行より上の行を優先し同じ行内ではより左寄りにある語を優先する上下方向優先左端開始法(depth-first left-to-right traversal)を用いるとよい。また、ＸＭＬノードとテキスト断片との関係を示す情報を保持しておき、目次内項目であることが判明したテキスト断片からそれに対応するＸＭＬノードへの後方参照関係を、処理終了時にマッピングすることができるようにしてもよい。更に、テキストフラグメンタ１２による断片化の単位は、行、ブロック、同一行内連接語群等、様々に設定することができる。場合によっては、単一の語が複数個のテキスト断片に分かれることもある。例えば、タイトルの冒頭語の冒頭文字の体裁が後続文字の体裁と異なる場合である。
【００１２】
テキストフラグメンタ１２から得られる索引テキスト断片序列体１４及び本文テキスト断片序列体１６は、テキスト類似度性リンクアイデンティファイア(textual similarity link identifier)２０によって処理され、それによりリンク候補２２が認識される。各候補２２は、テキスト的に類似している一対のテキスト断片、即ち索引テキスト断片序列体１４を構成する索引テキスト断片のうち一つと本文テキスト断片序列体１６を構成する本文テキスト断片のうち一つとの対によって、形成される。そのテキスト断片対が候補２２を形成する対であるかどうかを判別する手法は幾つかあるが、概ねどの手法でも、索引テキスト断片の個数がＴ個で本文テキスト断片の個数がＮ個ならＴ×Ｎ回のテキスト断片比較が必要になる。これに対して、本実施形態においては、後述の通り、序列体１６のうちどの部分列をサーチ対象とすべきかをサーチ範囲セレクタ２４によって認識し、その結果に基づきアイデンティファイア２０によるサーチ対象を制限しているため、テキスト断片比較回数がＴ×Ｎ回よりかなり少なくなることが多い。
【００１３】
テキスト断片比較に当たっては、しばしばテキスト中に混入するノイズの影響を考慮して処理を行うことも求められる。ノイズ発生原因としては、文書変換や目次構成上の問題等、様々な原因を挙げることができる。例えば、ＰＤＦからテキストへのフォーマット変換時に変換誤りが生じると、その変換誤りはノイズとなる。また、目次構成上の問題に起因するノイズとしては、例えば、目次内に登場するが本文には登場しないページ番号によって発生するノイズや、目次内でセクションタイトルとページ番号とをつなぐのに使用されている記号（例えばエリプシス“………”）により発生するノイズがある。また、リンク候補２２をなす対かどうかを判断するため本実施形態ではテキスト類似度を求めているが、その際には、例えば、テキスト断片間をセパレータで区切って複数個のトークンの集合に変換する。例えば各テキスト断片が英文字からなる文字列である場合、セパレータとしては英文字でないもの、例えばタブ、スペース、句読点等を用いればよい。更に、テキスト類似度を測ることができる指標としては、Ｊａｃｃａｒｄ係数や編集距離(edit distance)等、種々の指標がある。Ｊａｃｃａｒｄ係数は、索引テキスト断片から導出したトークン集合と、本文テキスト断片から導出したトークン集合とに基づき、それら二種類のトークン集合の積集合即ち交わり部分の基数(cardinal)と、当該二種類のトークン集合の和集合即ち合併集合の基数とを求め、積集合の基数を和集合の基数により除することによって、求めることができる。求めたＪａｃｃａｒｄ係数が所定のマッチングしきい値を上回っているなら、それらテキスト断片同士をリンクさせる。また、編集距離を用いる場合は、編集距離の上限を以て編集距離しきい値とする。ある２個のテキスト断片間の編集距離が編集距離しきい値より小さければ、テキスト的に類似していると判断してそれらテキスト断片同士をリンクさせる。これらの他にも、テキスト類似度を測るのに適しリンク選択条件を定めるのに使用できる条件は幾つかある。
【００１４】
テキスト断片同士の組合せは例えば（ｉ，ｊ）と表すことができる。ｉは索引テキスト断片序列体１４に含まれる索引テキスト断片の番号、ｊは本文テキスト断片序列体１６に含まれる本文テキスト断片の番号である。本実施形態では、あるテキスト断片対（ｉ，ｊ）がしきい値条件等のリンク選択条件を満足しているなら、そのテキスト断片対（ｉ，ｊ）について、リンク候補２２を形成する対の一つであるとの判断を下す。また、リンク選択条件を満たした（例えばそのＪａｃｃａｒｄ係数がしきい値を上回っている）テキスト断片対（ｉ，ｊ）即ち候補２２には、テキスト類似度で表したリンク強度を示す指標値、例えばＪａｃｃａｒｄ係数の値を関連付ける。なお、本実施形態ではＪａｃｃａｒｄ係数等のテキスト類似度を用いて候補２２を認識するようにしているが、フォントサイズ、フォントスタイル、フォント特性、大文字の有無、下線の有無等を用いて候補２２を認識する手法や、それらの任意の組合せにより候補２２を認識する手法や、更にはそれらとテキスト類似度との任意の組合せにより候補２２を認識する手法等によって、本発明を実施することもできる。
【００１５】
図２に、目次領域１０における目次１１０の位置関係の例を示す。この図に示す目次１１０は、領域１０の一部分だけを占めるに過ぎず、領域１０の全体に亘っているわけではない。但し、目次が目次領域全体に拡がるケースもある。目次内項目と、そのリンク先本文テキスト断片例えばセクション見出し、章見出し等と、の間のリンクを弁別、認識するに当たっては、概略、次に述べる四種類の一般的条件を使用する。そのうち第１の条件は蝟集性条件(contiguity)である。蝟集性条件は、目次内テキスト断片は領域１０内で蝟集し序列体を形成しているはずであり、従って領域１０内テキスト断片蝟集序列体又はその部分列が目次になるはずである、という事実を利用した判断基準である。蝟集序列体とは蝟集体であって序列体でもあるもののことをいい、蝟集体とは蝟集している複数個のテキスト断片の集合のことをいい、序列体とはその順序通りに並んでいる複数個のテキスト断片の集合のことをいい、部分列（部分序列体）とは序列体に含まれる一連なりのテキスト断片のことをいい、蝟集とは複数個のテキスト断片が１箇所に寄り集まることをいう。蝟集性条件を満たす蝟集序列体又はその部分序列体内のテキスト断片は、大抵は目次内項目１１２である。また、項目１１２ならばその文書８内で目次１１０より後に位置する別のテキスト断片に何れかのリンクによってリンクしているはずである。図中の矢印付曲線１１４は目次１１０内に発するリンクを表している。目次１１０内の項目１１２に発し対応するリンク先テキスト断片に至っているリンク１１４の集合は、テキスト類似度性リンクアイデンティファイア２０によって算出された候補２２の集合の部分集合となる。候補２２の集合の中にリンク１１４でないものが多数含まれることも多い。
【００１６】
更に、目次１１０内テキスト断片の多くは目次内項目１１２であるが、なかには袋小路(hole)になっているものもある。袋小路とは、図中の１１６のように、文書８中の他の部分にリンク１１４を介してリンクしていないテキスト断片のことである。袋小路１１６になるテキスト断片は比較的少数であり、通常は、項目１１２に対する袋小路１１６の個数比率は０．２未満である。こうした袋小路１１６については、その許容最大個数をユーザがパラメータとして設定できるようにしてもよい。
【００１７】
第２の目次認識条件はテキスト類似度条件(textual similarity)である。テキスト類似度条件とは、各目次内項目１１２を他のテキスト断片例えば見出しにリンクさせるには、その項目１１２とその項目１１２にリンクさせたいテキスト断片とが、テキスト的に十分類似していなければならない、という条件である。前述のＪａｃｃａｒｄ係数等は、テキスト類似度性リンクアイデンティファイア２０により好適に計測できテキスト類似度指標値として至便に使用できるものである。また、項目１１２のリンク先本文テキスト断片の性質は、その目次１１０の性質乃至構成によって変わる。例えば目次１１０が通常の構成ならセクション見出しが、また文書内の図のリスト（図一覧表）なら図に付された表題等が、或いは表のリスト（表一覧表）なら表に付された表題等が、それぞれリンク先になる。なお、通常、表題は対応する図や表の下側等に付されている。
【００１８】
第３の目次認識条件は順序条件(ordering)である。順序条件とは、目次内項目１１２の順序と、それら項目１１２のリンク先本文テキスト断片の順序とが、同順でなければならない、という条件である。例えば、一組の目次内項目｛ｉ１，ｉ２，ｉ３，…｝を一組のリンク｛（ｉ１，ｊ１），（ｉ２，ｊ２），（ｉ３，ｊ３），…｝を介し一組の本文テキスト断片｛ｊ１，ｊ２，ｊ３，…｝にリンクさせる場合、テキスト断片蝟集体における項目登場順序ｉ１，ｉ２，ｉ３，…と同じ順序ｊ１，ｊ２，ｊ３，…でリンク先本文テキスト断片が登場する、という関係が成り立っていなければならない。
【００１９】
第４の目次認識条件は自己参照忌避条件(lack of self-reference)である。自己参照忌避条件とは、各リンク１１４のリンク元テキスト断片とリンク先テキスト断片とが同じ目次１１０内のテキスト断片であってはならない、という条件である。自己参照忌避条件を満たすには、目次領域１０から抽出された索引テキスト断片序列体１４から選択する目次内項目１１２の集合｛ｉ１，ｉ２，ｉ３，…｝と、同じ文書８内にあり領域１０とは別の１個又は複数個の領域から抽出された本文テキスト断片序列体１６から選択する対応するリンク先本文テキスト断片の集合｛ｊ１，ｊ２，ｊ３，…｝との間に、交わり部分が生じないようにすると共に、リンク先本文テキスト断片集合｛ｊ１，ｊ２，ｊ３，…｝に目次１１０内袋小路１１６に対応するテキスト断片が含まれないようにすればよい。
【００２０】
また、図１に示されている目次領域１０は、例えばユーザ入力によって、或いは処理対象文書８を生成したアプリケーションプログラムによる目次領域自動認識処理の結果として、アプリオリに与えられるものである。目次が領域１０全体に拡がっており領域１０全体が目次で埋め尽くされていると見なしてよい場合は、アプリオリに与えられる領域１０によって目次位置が厳密に決まる。これに対して、アプリオリに与えられる領域１０に比べて目次の拡がりが狭い場合は、領域１０内目次位置を精密に判別する必要がある。例えば、文書８をスキャンによって取り込み、目次記載ページ（群）をユーザが指定し、ユーザ指定ページ（群）を領域１０として扱う使用形態では、ユーザ指定ページ（群）全体が目次であることは少なく、実際にはその一部だけが目次であるのが普通である。
【００２１】
目次領域１０内目次を認識する際には、例えば、蝟集性条件、テキスト類似度条件、順序条件及び自己参照忌避条件に従い目次選択を行う。目次選択に当たってはまずは目次候補選択を行う。目次候補選択を行うのは目次候補セレクタ３０であり、これによって領域１０から１個又は複数個の目次候補が選択される。目次候補選択に当たっては、例えば、索引テキスト断片序列体１４内索引テキスト断片個数をＴ、期待目次長最小値をΔとし、ある種の命題をＴ−Δ回検証する。即ち、索引テキスト断片のうちＴ−Δ個を目次筆頭項目候補とし、各目次筆頭項目候補について、命題「この索引テキスト断片から目次が始まっている可能性があるか？」の成否を検証し、成り立つ場合はその目次筆頭項目候補に続くテキスト断片を可能な限りその目次候補に入れることでその目次候補の規模を拡張していく。目次候補規模拡張は、新たなテキスト断片を追加すると順序条件が成り立たなくなるようになるまで続ける。例えば、最近その目次候補に追加した索引テキスト断片のリンク先候補がｊ＝１５の本文テキスト断片及びｊ＝３３の本文テキスト断片であるとする。また、その次の索引テキスト断片のリンク先候補がｊ＝２０の本文テキスト断片だけであるとする。この場合、いま調べている索引テキスト断片のリンク先候補（ｊ＝２０）は先に追加した索引テキスト断片のリンク先（ｊ＝１５）より後であるので、いま調べている索引テキスト断片をその目次候補に追加する。これに対して、いま調べている索引テキスト断片のリンク先候補がｊ＝１２の本文テキスト断片だけなら、いま調べている索引テキスト断片をその目次候補に追加すると順序条件が成り立たなくなるので、その索引テキスト断片をその目次候補に追加しない。但し、順序条件を若干緩和し、目次候補内に数個の袋小路１１６が残りうるようにした方が、有益でもある。そうするには、例えば、どのリンク候補２２にも関連付けられていないテキスト断片を所定個数まで許容し、またリンク交差(link-crossing)のあるテキスト断片（関連する候補２２全部がその目次候補内で順序条件を満たしていないテキスト断片）を所定個数まで許容するようにすればよい。そうした若干のリンク交差を許容することが有益に働くのは、例えば、現在選定中の目次候補内でそのテキスト断片より前に登場しているテキスト断片が、その文書内でかなり前方に位置しているテキスト断片だけにリンクしている場合等である。
【００２２】
各目次候補を調べるこの処理は、Ｔ−Δ個の目次筆頭項目候補それぞれについて、従ってＴ−Δ回繰り返して実行する。その結果として得られるのは、それぞれ索引テキスト断片序列体１４の部分序列体となっている１個又は複数個の目次候補の集合である。それらの目次候補は、確実に順序条件に従うように（或いは更に袋小路１１６を所定個数まで許容しつつ）構築されているので、当然、各目次候補内の目次内項目候補それぞれに対応する何個かのリンク候補２２の中から、順序条件を満足する候補２２を目次内項目候補毎に１個は、選択することができる。また、目次候補セレクタ３０にて篩い落とし条件(filtering)を適用し、明らかに目次でない目次候補を除外するようにしてもよい。例えば、ある目次候補内のテキスト断片個数が期待目次長最小値Δを下回っている場合、その目次候補は無視するのが適当であろう。
【００２３】
目次セレクタ３４は、こうして選定された目次候補にランク付けし、最高ランクの目次候補を選択する。リンクオプティマイザ３８は、その最高ランク目次候補に係るリンク候補２２を最適化することによって、最終的な目次１１０を生成する。この場合、セレクタ３４が目次候補にランク付けするため実行する処理の計算量は比較的少なく、選択された目次候補に対しオプティマイザ３８が施す処理はより徹底した計算を伴う。本願出願人の知見によれば、このやり方は、目次１１０を正確に抽出できるという点でも上首尾な手法である。また、各目次候補にリンク最適化を施し、リンク最適化後の一群の目次候補をランク付けする、というやり方も、計算量が多くなるが採用に値するやり方である。
【００２４】
図１に基づき更に説明すると、目次セレクタ３４では、スコアリング関数を使用して各目次候補にランク付けし、その中で最高ランクの目次候補を目次１１０として選択して、後の処理に供する。セレクタ３４にてスコアリング関数として使用できる量としては、項目荷重総和、項目総数、文書内見出し分布拡がり率等、種々の量がある。それらのうち項目荷重総和は、各目次内項目候補に関連付けられているリンク候補２２の個数に反比例するよう項目荷重を定め、定めた項目荷重をその目次候補内で総和することによって得られる。一般に、ある索引テキスト断片に発する候補２２がその目次候補における“真正な”リンク１１４である確率は、同じ索引テキスト断片に発する候補２２の個数が多ければ多い程低くなるので、項目荷重によって各候補２２の確からしさを評価することができる。また、スコアリング関数として使用でき熟考に値する量としては、更にその目次候補内の項目総数がある。順序条件及び自己参照忌避条件を満足するテキスト断片が数多く蝟集していることが判明している“長大な”目次候補は、それより“短小な”目次候補に比べより“真正な”可能性が高いものであるといえる。もう一つ、スコアリング関数として熟考に値する量としては、処理対象文書８全体に対する見出し分布範囲の割合、即ち文書内見出し分布拡がり率がある。例えば、ある同じ目次候補内からのリンク先本文テキスト断片の文書８内分布が比較的狭い場合、その目次候補がその文書８の“真正な”目次１１０である確率は低い。なお、以上の量はスコアリング関数の例に過ぎず、従ってこれら以外のスコアリング関数を使用することも、また何種類かのスコアリング関数を組み合わせて使用することも可能である。
【００２５】
最高ランクが付された目次候補に対しては、最終的な目次１１０を得るべく、リンクオプティマイザ３８が適用される。オプティマイザ３８は、その最高ランク目次候補に係るリンク候補２２について大局的に最適な解を導出することによって、その目次に係る候補２２の中で最良の候補２２を目次内項目１１２毎に選択し、それによって最終的な目次１１０を構築する。最良リンク候補選択に当たっては、目次認識に使用した蝟集性条件、テキスト類似度条件、順序条件及び自己参照忌避条件の四条件が引き続き満足されるようにする。更に、最良リンク候補選択の手法としては、例えばマッチングの度合いに比例する荷重を各候補２２に割り当てそれを利用して最適な候補２２を選択する、Ｖｉｔｅｒｂｉの最短パスアルゴリズム(Viterbi shortest path algorithm)を用いて最適な候補２２を選択する等、種々のアルゴリズムを使用できる。
【００２６】
目次が目次領域１０の（ほぼ）全体に拡がっていると見なしてよい場合は、目次候補セレクタ３０及び目次セレクタ３４の適用を省略し、領域１０から抽出された索引テキスト断片序列体１４の全体を目次と見なしてリンクオプティマイザ３８を適用することができる。領域１０の拡がりと実際の目次の拡がりとの間に僅かに食い違いが生じることもありうるが、そうした食い違いは目次内袋小路として問題なく吸収することができる。例えば、目次であることを示す見出しが領域１０の先頭に付されているために生じる食い違いや、ページ番号又はページ見出しを表すテキスト断片が領域１０に含まれているため生じる食い違いである。
【００２７】
こうして認識した目次１１０は種々の処理に使用できる。例えば、各目次内項目１１２のリンク先セクション見出し毎に処理対象文書８が分割され、それによってその文書８が構造化文書(structured document)に変換されるように、文書オーガナイザ１２０による構造化に目次１１０を利用することができる。また、目次１１０を用いて文書８を自動的に構造化する場合は、通常、順序条件を厳密に適用した方が有利である。これは、構造化文書フォーマット時に交差リンクがエラーを引き起こすからである。また、ここに述べた例はとりわけテキストセクションの索引となる目次１１０を認識する例であるが、順に図、表、式等の索引である図一覧表、表一覧表、式一覧表等を生成して目次１１０とする際にも、同様の処理を適用して類似した効果を得ることができる。
【００２８】
また、Ｔ個の索引テキスト断片及びＮ個の本文テキスト断片全てを対象としてテキスト類似度性リンクアイデンティファイア２０にテキスト断片比較を行わせると、所要比較回数がほぼＴ×Ｎ回にもなってしまう。これは、例えば数万個の本文テキスト断片を含む文書８の目次領域１０に十数個〜数千個のテキスト断片が含まれていると、テキスト断片比較所要回数Ｔ×Ｎが当然の如くに数百万、数千万或いはそれ以上にもなってしまう、ということである。しかも、テキスト断片比較に際して行う必要がある計算、例えばＪａｃｃａｒｄ係数等の比較指標の計算は、かなり計算能力を要する計算となるのが普通である。本実施形態でサーチ範囲セレクタ２４を用いる目的は、本文テキスト断片序列体１６のうちのある部分序列体へとサーチ対象を絞り込むことによって、テキスト断片比較所要回数をＴ×Ｎ回より少ない回数に抑えることにある。これによって、通常、当該回数をＴ×Ｎ回よりもかなり少ない回数にすることができる。
【００２９】
図３に、図１に示した装置にて処理される文書８の例２０８を示す。この図の文書２０８は索引テキスト断片序列体２１４及び本文テキスト断片序列体２１６から構成されており、序列体２１４は順に７個の索引テキスト断片｛Ｆtoc,1｝，…，｛Ｆtoc,7｝を、また序列体２１６は順に本文テキスト断片｛Ｆb,1｝，｛Ｆb,2｝，｛Ｆb,3｝，…を、それぞれ含んでいる。サーチ範囲セレクタ２４及びテキスト類似度性リンクアイデンティファイア２０は、協働乃至分業して、前者のリンク先候補を後者から選択するリンク先候補認識処理を実行する。その際には、まず、序列体２１４中葉に位置する索引テキスト断片｛Ｆtoc,4｝を起点として選択し、アイデンティファイア２０が起点｛Ｆtoc,4｝のリンク先候補として見つけ出した本文テキスト断片｛Ｆb,8｝，｛Ｆb,10｝，｛Ｆb,13｝を起点｛Ｆtoc,4｝に関連付ける。起点｛Ｆtoc,4｝についてリンク先候補認識処理を実行する際には、序列体２１６全体をサーチ範囲とするのが望ましい。結果として得られるリンク先候補本文テキスト断片｛Ｆb,8｝，｛Ｆb,10｝，｛Ｆb,13｝の集合中、最冒頭の即ち最も順序が早い本文テキスト断片は｛Ｆb,8｝、最末尾の即ち最も順序が遅い本文テキスト断片は｛Ｆb,13｝である。従って、起点｛Ｆtoc,4｝に対するリンク先候補最小順序ｄminは８、リンク先候補最大順序ｄmaxは１３となる。セレクタ２４は、起点｛Ｆtoc,4｝のリンク先候補の最小順序ｄmin及び最大順序ｄmaxに基づきサーチ範囲を制限した上で、別の索引テキスト断片のリンク先候補本文テキスト断片をサーチし見つかったリンク先候補をその索引テキスト断片に関連付ける処理を、実行させる。
【００３０】
図４中、索引テキスト断片｛Ｆtoc,2｝は起点索引テキスト断片｛Ｆtoc,4｝より冒頭寄りにある。次はこの冒頭側処理対象索引テキスト断片｛Ｆtoc,2｝のリンク先候補本文テキスト断片をサーチし、見つけ出した何個かのリンク先候補本文テキスト断片の集合を冒頭側処理対象｛Ｆtoc,2｝に関連付ける。このサーチに当たっては、サーチ範囲セレクタ２４が、起点｛Ｆtoc,4｝のリンク先候補の最大順序ｄmax及び順序条件に基づき、冒頭側処理対象｛Ｆtoc,2｝についてのリンク先候補サーチ範囲を制限する。例えば、序列体２１６内で最冒頭に位置する第１本文テキスト断片｛Ｆb,1｝から第ｄmax−１＝第１２本文テキスト断片｛Ｆb,12｝に至る範囲｛Ｆb,1｝，…，｛Ｆb,12｝に制限する。ここで第ｄmax−１までをリンク先候補サーチ範囲とするのは、起点｛Ｆtoc,4｝との関係で冒頭側処理対象｛Ｆtoc,2｝が順序条件を満たすようにするためである。即ち、冒頭側処理対象｛Ｆtoc,2｝は目次内で起点｛Ｆtoc,4｝より冒頭寄りにあるのであるから、仮にｄmax番目又はそれより末尾寄りの本文テキスト断片に冒頭側処理対象｛Ｆtoc,2｝がリンクしていると、順序条件違背となってしまう。サーチ範囲制限は、比較回数抑制だけでなく冒頭側の順序条件違背を回避する役にも立つ。
【００３１】
同様に、図５中、索引テキスト断片｛Ｆtoc,6｝は起点索引テキスト断片｛Ｆtoc,4｝より末尾寄りにある。次は、冒頭側処理対象索引テキスト断片｛Ｆtoc,2｝についてのリンク先候補サーチと並行して又は相前後して、この末尾側処理対象索引テキスト断片｛Ｆtoc,6｝のリンク先候補本文テキスト断片をサーチし、見つけ出した何個かのリンク先候補本文テキスト断片の集合を末尾側処理対象｛Ｆtoc,6｝に関連付ける。このサーチに当たっては、サーチ範囲セレクタ２４が、起点｛Ｆtoc,4｝のリンク先候補の最小順序ｄmin及び順序条件に基づき、末尾側処理対象｛Ｆtoc,6｝についてのリンク先候補サーチ範囲を制限する。例えば、第ｄmin＋１本文テキスト断片｛Ｆb,9｝から最末尾本文テキスト断片に至る範囲｛Ｆb,9｝，…に制限する。ここで第ｄmin＋１からをリンク先候補サーチ範囲とするのは、起点｛Ｆtoc,4｝との関係で末尾側処理対象｛Ｆtoc,6｝が順序条件を満たすようにするためである。即ち、末尾側処理対象｛Ｆtoc,6｝は目次内で起点｛Ｆtoc,4｝よりも末尾寄りにあるのであるから、仮に第ｄmin又はそれより冒頭寄りの本文テキスト断片に末尾側処理対象｛Ｆtoc,6｝がリンクしていると、順序条件違背となってしまう。サーチ範囲制限は、比較回数抑制だけでなく末尾側の順序条件違背を回避する役にも立つ。
【００３２】
図６に示すように、索引テキスト断片序列体が図３〜図５に示したものより多数の索引テキスト断片を含む大きな序列体である場合は、以上の処理を複数回繰り返して行うとよい。この図に示した索引テキスト断片序列体３１４は１７個の索引テキスト断片｛Ｆtoc,1｝，…，｛Ｆtoc,17｝を含んでおり、０巡目及び１巡目を含む複数巡のリンク先候補認識処理の対象とされる。そのうち０巡目処理においては、まず、序列体３１４中葉にある索引テキスト断片例えば｛Ｆtoc,9｝を０巡目起点索引テキスト断片ｉ（０）として選択し（ｉ（０）等の（）内の数字は何巡目かを示す；以下同様）、起点ｉ（０）のリンク先候補本文テキスト断片をサーチし、見つかった何個かのリンク先候補（図示せず）を起点ｉ（０）に関連付け、それらリンク先候補における最小順序ｄmin及び最大順序ｄmaxを求める。次いで、最冒頭索引テキスト断片｛Ｆtoc,1｝と起点ｉ（０）の中間にある索引テキスト断片例えば｛Ｆtoc,4｝を０巡目冒頭側処理対象索引テキスト断片Ｌ（０）として選択し、最冒頭本文テキスト断片｛Ｆb,1｝から第ｄmax−１本文テキスト断片に至る部分序列体をサーチ範囲として冒頭側処理対象Ｌ（０）のリンク先候補本文テキスト断片をサーチし、見つかった何個かのリンク先候補（図示せず）を冒頭側処理対象Ｌ（０）に関連付ける。サーチ範囲を制限するのは、仮に冒頭側処理対象Ｌ（０）が起点ｉ（０）のリンク先候補より末尾寄りの本文テキスト断片とリンクしていると、順序条件に違背してしまうからである。同様に、冒頭側処理対象Ｌ（０）についての処理と並行して又は相前後して、起点ｉ（０）と最末尾索引テキスト断片｛Ｆtoc,17｝の中間にある索引テキスト断片例えば｛Ｆtoc,14｝を０巡目末尾側処理対象索引テキスト断片Ｈ（０）として選択し、第ｄmin＋１本文テキスト断片から最末尾本文テキスト断片に至る部分序列体をサーチ範囲として末尾側処理対象Ｈ（０）のリンク先候補本文テキスト断片をサーチし、見つかった何個かのリンク先候補（図示せず）を末尾側処理対象Ｈ（０）に関連付ける。サーチ範囲を制限するのは、仮に末尾側処理対象Ｈ（０）が起点ｉ（０）のリンク先候補より冒頭寄りの本文テキスト断片とリンクしていると、順序条件に違背してしまうからである。
【００３３】
図６に示す例では、続いて、索引テキスト断片序列体３１４内索引テキスト断片のうち０巡目起点索引テキスト断片ｉ（０）より順序が早い索引テキスト断片の集合即ち冒頭寄り部分集合と、同じ起点ｉ（０）より順序が遅い索引テキスト断片の集合即ち末尾寄り部分集合とを定めて、同様の処理を繰り返す。即ち、１巡目においては、冒頭寄り部分集合と末尾寄り部分集合とを別個に処理する。その際、冒頭寄り部分集合については、最冒頭索引テキスト断片｛Ｆtoc,1｝と０巡目起点ｉ（０）のほぼ中間に位置しており従って冒頭寄り部分集合の中葉にある索引テキスト断片例えば｛Ｆtoc,4｝を、１巡目起点索引テキスト断片ｉL（１）として選択し、また、末尾寄り部分集合については、０巡目起点ｉ（０）と最末尾索引テキスト断片｛Ｆtoc,17｝のほぼ中間に位置しており従って末尾寄り部分集合の中葉にある索引テキスト断片例えば｛Ｆtoc,14｝を、１巡目起点索引テキスト断片ｉH（１）として選択する。
【００３４】
冒頭寄り部分集合について１巡目処理を実行する際には、冒頭寄り部分集合冒頭索引テキスト断片｛Ｆtoc,1｝と、冒頭寄り部分集合についての１巡目起点索引テキスト断片ｉL（１）と、の中間に位置する索引テキスト断片例えば｛Ｆtoc,2｝を１巡目冒頭側処理対象索引テキスト断片ＬL（１）とし、また、同じ起点ｉL（１）と、冒頭寄り部分集合末尾索引テキスト断片｛Ｆtoc,8｝と、の中間に位置する索引テキスト断片例えば｛Ｆtoc,6｝を１巡目末尾側処理対象索引テキスト断片ＨL（１）とする。更に、１巡目起点ｉL（１）についてリンク先候補最小順序ｄmin及び最大順序ｄmaxを求め、それらを用いリンク先候補サーチ範囲を定める。そして、こうして制限されたサーチ範囲内で冒頭側処理対象ＬL（１）及び末尾側処理対象ＨL（１）のリンク先候補本文テキスト断片をサーチし、見つけたリンク先候補を対応する処理対象に関連付ける。
【００３５】
同様に、末尾寄り部分集合について１巡目処理を実行する際には、末尾寄り部分集合冒頭索引テキスト断片｛Ｆtoc,10｝と、末尾寄り部分集合についての１巡目起点索引テキスト断片ｉH（１）と、の中間に位置する索引テキスト断片例えば｛Ｆtoc,12｝を１巡目冒頭側処理対象索引テキスト断片ＬH（１）とし、また、同じ起点ｉH（１）と、末尾寄り部分集合末尾索引テキスト断片｛Ｆtoc,17｝と、の中間に位置する索引テキスト断片例えば｛Ｆtoc,16｝を、１巡目末尾側処理対象索引テキスト断片ＨH（１）とする。更に、１巡目起点ｉH（１）についてリンク先候補最小順序ｄmin及び最大順序ｄmaxを求め、それらを用いリンク先候補サーチ範囲を定める。そして、こうして制限されたサーチ範囲内で冒頭側処理対象ＬH（１）及び末尾側処理対象ＨH（１）のリンク先候補本文テキスト断片をサーチし、見つけたリンク先候補を対応する処理対象に関連付ける。なお、一般に、以上述べた処理と同様の処理（２巡目等々の処理）を繰り返す場合もある。即ち図６に示す例であれば、図示しないが、冒頭寄り部分集合を更に冒頭寄り部分集合と末尾寄り部分集合とに分割し、末尾寄り部分集合も更に冒頭寄り部分集合と末尾寄り部分集合とに分割して、それら部分集合について同様の処理を繰り返すようにするとよい。
【００３６】
また、図３〜図６においては、それぞれ単一の索引テキスト断片を以て起点索引テキスト断片、冒頭側処理対象索引テキスト断片及び末尾側処理対象索引テキスト断片としているが、目次中に袋小路が含まれている場合、その袋小路が起点、冒頭側処理対象又は末尾側処理対象として選択されてしまう可能性があり、選択されてしまうとそれに対応するリンク先候補本文テキスト断片は見つけられなくなる。こうした状況にうまく対処するには、例えば索引テキスト断片序列体中葉に蝟集している複数個の索引テキスト断片を以て起点索引テキスト断片とし、各起点のリンク先候補本文テキスト断片を本文テキスト断片序列体から見つけ出し、見つけ出した何個かのリンク先候補をその起点に関連付けると共に、同じく索引テキスト断片序列体中で蝟集している複数個の索引テキスト断片を以て冒頭側処理対象索引テキスト断片とし、索引テキスト断片序列体中で蝟集している複数個の索引テキスト断片を以て末尾側処理対象索引テキスト断片とするとよい。起点個数、冒頭側処理対象個数及び末尾側処理対象個数が袋小路最大許容蝟集個数より多ければ、リンク先候補最小順序ｄmin及び最大順序ｄmaxを必ず定めることができるので、図３〜図６に示した複数巡構成のリンク先候補認識処理は目次内袋小路に対してロバストになる。
【００３７】
図３〜図６に示した手法によれば、テキスト断片比較回数を減らし処理時間を短縮することができる。例えば、２６１個の目次内索引テキスト断片及び５５２３８個の本文テキスト断片を含む１３００ページの文書８を、サーチ範囲セレクタ２４を用いずに処理してみたところ、テキスト断片比較回数がＮ×Ｔ＝２６１×５５２３８＝１４４１７１１８回にもなり、テキスト類似度性リンクアイデンティファイア２０にてこれを実行するのに１７０秒もの処理時間が必要であった。これに対し、同じ文書８をセレクタ２４を用いて処理してみたところ、テキスト断片比較回数が８４１４２８８回まで減り、アイデンティファイア２０にてこれを実行するのに１１０秒で足りた。これは処理速度にして４０％の上昇である。また、他の処理も含めた総処理時間も２６０秒から１５５秒へと減り、処理速度にして４０％上昇していることからすれば、目次候補セレクタ３０、目次セレクタ３４及びリンクオプティマイザ３８による処理も、リンク候補総数低減の恩恵を受けているといえよう。
【００３８】
また、場合によっては、目次が目次領域１０に比べかなり小さいことがある。即ち、領域１０のうちの目次前部分、目次後部分又はその双方に、多数の非目次テキスト断片が存在していることがある。この状況に対しては、目次セレクタ３０にて領域１０内目次を認識することで少なくとも部分的に対処できるが、領域１０内の目次前部分や目次後部分に含まれるテキスト断片に係るリンクが順序条件に従うとは限らないので、そうしたテキスト断片の存在はまた別の問題を生む原因となりかねない。従って、領域１０内目次前部分及び目次後部分にかなりの個数の非目次テキスト断片が存在している場合には、リンク先候補認識処理の深さを例えば最大３巡に制限することによって、対処する方がよい。０巡目から２巡目までの３巡に制限する場合、領域１０は、０巡目ではひとまとまりで、１巡目では２個の部分に分けて、２巡目では４個の部分に分けて、それぞれ処理されるので、処理時における領域１０の分割数は最大４個になる。最大四分割に留まるので、領域１０内最冒頭部分である第１略四半部や領域１０内最末尾部分である第４略四半部、更にはその構成部分に属するテキスト断片について、そのリンク先候補の最小順序ｄminや最大順序ｄmaxが計算されることがない。そのため、こうしたやり方を採れば、領域１０内目次外部分が領域１０全体の約１／４又はそれ未満に留まる場合に、ロバスト性が向上する。但し、リンク先候補認識処理の深さを制限するとその分処理速度向上効果が損なわれる。例えば、先に例示した１３００ページの文書であれば、処理の深さを３巡に制限すると速度向上幅が４０％から２０％に狭まる。
【００３９】
図７に、目次領域１０のうち本物の目次外に位置する目次外部分に余分なテキスト断片が存在しているとき、それに抗してロバスト性を向上させる手法について、また別の例を示す。この図に示した索引テキスト断片序列体３１４は図６に示したものと同じもの、即ち１７個の索引テキスト断片｛Ｆtoc,1｝，…，｛Ｆtoc,17｝を含むものである。この図の序列体３１４に対し本例に係るロバスト性向上手法を適用する際には、図６に示した例と同様、まずは領域１０中葉に位置する索引テキスト断片を０巡目起点索引テキスト断片ｉ（０）として選択し、０巡目起点ｉ（０）に対し何個かの本文テキスト断片をリンク先候補として関連付け、そしてそれらリンク先候補における最小順序ｄmin及び最大順序ｄmaxを導出する。なお、この例においても、袋小路最大許容蝟集個数より多くの索引テキスト断片を含む索引テキスト断片蝟集体を以て起点とすることによって、目次内袋小路に対するロバスト性を向上できる（後の巡でも同様）。
【００４０】
但し、この図に示すやり方では、０巡目冒頭側処理対象索引テキスト断片Ｌ（０）及び末尾側処理対象索引テキスト断片Ｈ（０）の選び方が図６に示した例とは異なっている。即ち、この図の例では、索引テキスト断片序列体３１４内で０巡目起点索引テキスト断片ｉ（０）に連接するように索引テキスト断片を選択して０巡目冒頭側処理対象Ｌ（０）及び末尾側処理対象Ｈ（０）とする。こうして選択した０巡目冒頭側処理対象Ｌ（０）及び末尾側処理対象Ｈ（０）については、先の例と同様にしてリンク先候補認識処理を実施する。即ち、０巡目起点ｉ（０）のリンク先候補の最大順序ｄmaxに従いサーチ範囲を制限して０巡目冒頭側処理対象Ｌ（０）のリンク先候補本文テキスト断片をサーチし認識する一方、０巡目起点ｉ（０）のリンク先候補の最小順序ｄminに従いサーチ範囲を制限して０巡目末尾側処理対象Ｈ（０）のリンク先候補本文テキスト断片をサーチし認識する。
【００４１】
次の１巡目においては、０巡目起点索引テキスト断片ｉ（０）並びにそれに連接する０巡目冒頭側処理対象索引テキスト断片Ｌ（０）及び末尾側処理対象索引テキスト断片Ｈ（０）の集合、即ち目次領域１０中葉にあり索引テキスト断片蝟集体を構成している複数個の索引テキスト断片の集合｛Ｌ（０），ｉ（０），Ｈ（０）｝を以て、１巡目起点索引テキスト断片ｉ（１）として選択し、それら１巡目起点ｉ（１）のリンク先候補本文テキスト断片をサーチして関連付け、それらリンク先候補における最小順序ｄmin及び最大順序ｄmaxを導出する。このとき１巡目リンク先候補最小順序ｄminとされるのは、複数個の１巡目起点ｉ（１）のうち何れかについてのリンク先候補本文テキスト断片の中で最冒頭の本文テキスト断片であり、１巡目リンク先候補最大順序ｄmaxとされるのは、複数個の１巡目起点ｉ（１）のうち何れかについてのリンク先候補本文テキスト断片の中で最末尾の本文テキスト断片である。更に、１巡目起点ｉ（１）に連接するよう１巡目冒頭側処理対象索引テキスト断片Ｌ（１）及び末尾側処理対象索引テキスト断片Ｈ（１）を選択し、１巡目リンク先候補最小順序ｄmin及び最大順序dmaxをサーチ範囲制限手段として用いて、それら処理対象Ｌ（１）及びＨ（１）についてリンク先候補認識処理を行う。
【００４２】
そして２巡目においては、索引テキスト断片蝟集体｛Ｌ（１），ｉ（１），Ｈ（１）｝を構成する複数個の索引テキスト断片を以て２巡目起点索引テキスト断片ｉ（２）とし、それに連接する索引テキスト断片を以て２巡目冒頭側処理対象索引テキスト断片Ｌ（２）及び末尾側処理対象索引テキスト断片Ｈ（２）とし、それら処理対象Ｌ（２）及びＨ（２）についてリンク先候補認識処理を行う。最後に３巡目においては、索引テキスト断片蝟集体｛Ｌ（２），ｉ（２），Ｈ（２）｝を構成する複数個の索引テキスト断片を以て３巡目起点索引テキスト断片ｉ（３）とし、それに連接する索引テキスト断片を以て３巡目冒頭側処理対象索引テキスト断片Ｌ（３）及び末尾側処理対象索引テキスト断片Ｈ（３）とし、それら処理対象Ｌ（３）及びＨ（３）についてリンク先候補認識処理を行う。このように、先の巡目での冒頭側及び末尾側処理対象索引テキスト断片を先の巡目での起点索引テキスト断片に連ねた索引テキスト断片蝟集体を以て起点索引テキスト断片とし、その冒頭側及び末尾側に連接する索引テキスト断片を処理対象索引テキスト断片として選択し、そのリンク先候補本文テキスト断片をサーチして対応する処理対象に関連付ける処理を、必要な巡数分繰り返すようにすればよい。
【００４３】
なお、図７に示した例では、０巡目起点索引テキスト断片ｉ（０）並びに各巡目冒頭側及び末尾側処理対象索引テキスト断片が何れも１個であったが、目次には袋小路が含まれていることもある。目次に袋小路、即ち最終的な目次内で本文テキスト断片にリンクすることのない索引テキスト断片が含まれていると、その袋小路が、０巡目起点ｉ（０）又は各巡目冒頭側若しくは末尾側処理対象として選ばれてしまうかもしれない。こうした状況に対処するには、例えば、索引テキスト断片序列体中葉にある複数個の索引テキスト断片の蝟集体を以て、０巡目起点ｉ（０）とするのが望ましい。その場合、複数個の０巡目起点ｉ（０）に対しては、それぞれ、本文テキスト断片序列体からリンク先候補本文テキスト断片を選択し、選択した何個かのリンク先候補を関連付ける。更に、リンク先候補最小順序ｄmin及び最大順序ｄmaxについては、蝟集体を構成している複数個の０巡目起点ｉ（０）のうち何れかについてのリンク候補本文テキスト断片の中で最冒頭のものの順序を最小順序ｄmin、最末尾のものの順序を最大順序ｄmaxとすることによって定める。０巡目起点ｉ（０）の個数Ｎを袋小路最大許容蝟集個数より多くすれば最小順序ｄmin及び最大順序ｄmaxを必ず求めることができる。その後の処理は、例えば図７に示した例と同じやり方でもよいが、別のやり方を採ることもできる。
【００４４】
例えば、各巡目（但し０巡目より後）のリンク先候補認識処理毎に、それぞれ複数個の起点索引テキスト断片から構成される複数個の固定長摺動窓を使用し、それら摺動窓を互いに逆の方向に摺動させる、というやり方がある。即ち、索引テキスト断片序列体１４内で現在の冒頭側処理対象の末尾側に連接及び蝟集しているＮ個の索引テキスト断片を以て上摺動窓とし、また同じ序列体１４内で現在の末尾側処理対象の冒頭側に連接及び蝟集しているＮ個の索引テキスト断片を以て下摺動窓とする。各巡目（但し０巡目より後）のリンク先候補認識処理においては、リンク先候補サーチに当たり、上摺動窓内のＮ個の索引テキスト断片についての最大順序ｄmaxにより冒頭側処理対象のリンク先候補サーチ範囲を制限し、下摺動窓内のＮ個の索引テキスト断片についての最小順序ｄminにより末尾側処理対象のリンク先候補サーチ範囲を制限する。これによってその巡目に係るリンク先候補認識処理を終えたら、それまでの冒頭側処理対象より順序が１個早い索引テキスト断片を新たな冒頭側処理対象とすることにより、Ｎ個の索引テキスト断片からなる上摺動窓を“上向き”に索引テキスト断片１個分摺動させ、また、それまでの末尾側処理対象より順序が１個遅い索引テキスト断片を新たな末尾側処理対象とすることにより、Ｎ個の索引テキスト断片からなる下摺動窓を“下向き”に索引テキスト断片１個分摺動させた上で、次の巡目の処理を実行する。なお、このやり方においても、単独の索引テキスト断片を以て冒頭側又は末尾側処理対象とするだけでなく、ひとまとまりに連接している複数個のテキスト断片を以て冒頭側又は末尾側処理対象とすることも可能である。後者、即ち一連なりになっている複数個のテキスト断片を以て処理対象とする場合には、各巡目における冒頭側処理対象索引テキスト断片蝟集個数分だけ上摺動窓を動かすことができ、同様に各巡目における末尾側処理対象索引テキスト断片蝟集個数分だけ下摺動窓を動かすことができる。更に、例えば上摺動窓内索引テキスト断片蝟集個数をＮ個とし、下摺動窓内索引テキスト断片蝟集個数をＭ個とする、というように、２個の摺動窓の大きさを違えることも熟慮に値する。
【００４５】
図７に示したやり方は、目次領域１０内にあり目次の先頭、末尾又はその双方に位置している余分な即ちノイズになるテキスト断片に対してロバストになる、という点で有益である。即ち、起点索引テキスト断片蝟集体が、各巡目の処理を終える毎に領域１０中葉から見て上下方向に拡張されていくので、領域１０内外寄り部分に位置しておりノイズが多い可能性がある領域に、処理当初からぶつかることを避けることができる。
【図面の簡単な説明】
【００４６】
【図１】文書内目次認識装置の一例構成を示す図である。
【図２】目次認識結果の一例を示す図である。
【図３】１巡構成のリンク先候補認識処理における起点索引テキスト断片、その処理によって判明したリンク先候補並びにその最小順序及び最大順序を示す図である。
【図４】図３の起点索引テキスト断片より冒頭寄りの領域から選んだ処理対象索引テキスト断片のリンク先候補をサーチする際使用され、起点索引テキスト断片のリンク先候補最大順序に基づき制限されているサーチ範囲を示す図である。
【図５】図３の起点索引テキスト断片より末尾寄りの領域から選んだ処理対象索引テキスト断片のリンク先候補をサーチする際使用され、起点索引テキスト断片のリンク先候補最小順序に基づき制限されているサーチ範囲を示す図である。
【図６】図３〜図５に示した例より長い目次について実施される２巡構成のリンク先候補認識処理を示す図である。
【図７】図６に示した例と同じ目次について実施される４巡構成のリンク先候補認識処理を示す図である。
【符号の説明】
【００４７】
８，２０８ 処理対象文書（非構造化文書）、９ ユーザインタフェース、１０ 目次領域、１２ テキストフラグメンタ、１４，２１４，３１４ 索引テキスト断片序列体、１６，２１６ 本文テキスト断片序列体、２０ テキスト類似度性リンクアイデンティファイア、２２ リンク候補、２４ サーチ範囲セレクタ、３０ 目次候補セレクタ、３４ 目次セレクタ、３８ リンクオプティマイザ、１１０ 目次、１１２ 目次内項目、１１４ リンク、１１６ 袋小路、１２０ 文書オーガナイザ、ｄmin リンク先候補最小順序、ｄmax リンク先候補最大順序、Ｆb,n 本文テキスト断片、Ｆtoc,n，Ｈ（ｎ），ＨL（ｎ），ｉ（ｎ），ｉL（ｎ），ｉＨ（ｎ），Ｌ（ｎ），ＬL（ｎ） 索引テキスト断片。
【技術分野】
【０００１】
本発明は、情報格納技術及び情報処理技術、特にレガシー文書（在来文書）の目録、索引乃至目次となる文書をＸＭＬ(extensible markup language)、ＳＧＭＬ(standard generalized markup language)、ＨＴＭＬ(hyper text markup language)等のマークアップ言語フォーマットで自動生成する技術等、種々の分野に関する。
【背景技術】
【０００２】
文書からその目次を抽出する処理においては、通常、テキスト断片(text fragment)同士を比較する手法が用いられている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、この手法には、文書内における目次(table of contents;TOC)の位置が判明していない場合、テキスト断片同士の比較をＮ×（Ｎ−１）／２回行わねばならないという問題がある（Ｎ：文書に含まれるテキスト断片の個数）。このようにＮ2回オーダの比較計算が必要になる手法は、とりわけ文書規模が大きい場合に厄介で能力を消費するものとなる。例えば、テキスト断片を２００００〜６００００個含む文書についてこの手法を適用するとしたら、約２×１０8〜１．８×１０9回の比較が必要になる。
【０００４】
文書内における目次の位置が判明しているのであれば、比較の回数はＮ×Ｔ回まで減る。Ｎは本文テキスト断片の個数（〜文書内テキスト断片個数）、Ｔは目次内の索引テキスト断片の個数である。例えば文書内テキスト断片個数が２００００〜６００００個、目次内の索引テキスト断片の個数が１００〜３００個であれば、比較の回数は２×１０6〜１８×１０6回ですむ。ただ、これはＮ2回オーダの比較計算回数に比べれば少数であるが、それでもまだ多すぎる。
【課題を解決するための手段】
【０００５】
ここに、本発明の一実施形態に係る文書内目次認識方法においては、索引テキスト断片序列体中葉に位置する起点索引テキスト断片に、本文テキスト断片序列体内から選んだ１個又は複数個のリンク先候補本文テキスト断片からなる起点リンク先候補集合を関連付け、起点索引テキスト断片より冒頭寄りにある冒頭側処理対象索引テキスト断片に、起点リンク先候補集合内最末尾本文テキスト断片より冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付け、起点索引テキスト断片より末尾寄りにある末尾側処理対象索引テキスト断片に、起点リンク先候補集合内最冒頭本文テキスト断片より末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付ける。
【０００６】
また、本発明の一実施形態に係る文書内目次認識方法においては、（ａ）索引テキスト断片序列体中葉に位置する起点索引テキスト断片に、本文テキスト断片序列体内から選んだ１個又は複数個のリンク先候補本文テキスト断片からなる起点リンク先候補集合を関連付け、（ｂ）索引テキスト断片序列体内索引テキスト断片のうち起点索引テキスト断片より冒頭寄りの索引テキスト断片の集合である冒頭寄り部分集合の中葉に位置することとなるよう、冒頭側処理対象索引テキスト断片を選択し、（ｃ）索引テキスト断片序列体内索引テキスト断片のうち起点索引テキスト断片より末尾寄りの索引テキスト断片の集合である末尾寄り部分集合の中葉に位置することとなるよう、末尾側処理対象索引テキスト断片を選択し、（ｄ）冒頭側処理対象索引テキスト断片に、起点リンク先候補集合内最末尾本文テキスト断片より冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付け、（ｅ）末尾側処理対象索引テキスト断片に、起点リンク先候補集合内最冒頭本文テキスト断片より末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付け、（ｆ）それまでの冒頭側処理対象索引テキスト断片を起点索引テキスト断片として、冒頭寄り部分集合についてステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）における選択動作及び関連付け動作と同様の動作を実行し、（ｇ）それまでの末尾側処理対象索引テキスト断片を起点索引テキスト断片として、末尾寄り部分集合についてステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）における選択動作及び関連付け動作と同様の動作を実行する。
【０００７】
本発明の一実施形態に係り、索引テキスト断片序列体及び本文テキスト断片序列体を含む文書中の目次を認識する方法においては、索引テキスト断片序列体内で冒頭側処理対象索引テキスト断片の末尾側にＮ個蝟集して連接している索引テキスト断片に係る最末尾リンク先候補本文テキスト断片に比べ、冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片を、その冒頭側処理対象索引テキスト断片に関連付け、索引テキスト断片序列体内で末尾側処理対象索引テキスト断片の冒頭側にＭ個蝟集して連接している索引テキスト断片に係る最冒頭リンク先候補本文テキスト断片に比べ、末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片を、その末尾側処理対象索引テキスト断片に関連付け、それまでの冒頭側処理対象索引テキスト断片より冒頭寄りの索引テキスト断片を新たな冒頭側処理対象索引テキスト断片とし、それまでの末尾側処理対象索引テキスト断片より末尾寄りの索引テキスト断片を新たな末尾側処理対象索引テキスト断片とし、これら、冒頭側処理対象索引テキスト断片へのリンク先候補の関連付け、末尾側処理対象索引テキスト断片へのリンク先候補の関連付け、冒頭側処理対象索引テキスト断片の更新、並びに末尾側処理対象索引テキスト断片の更新を繰り返すことによって、索引テキスト断片に係る１個又は複数個のリンク先候補本文テキスト断片の集合を生成する。
【発明を実施するための最良の形態】
【０００８】
テキスト断片同士の比較により目次を抽出する際には、通常、目次内項目であるかもしれない一組の索引テキスト断片（目次内項目候補）と、そのリンク先となるテキスト断片即ち章見出しやセクション見出し等の見出しであるかもしれない一組の本文テキスト断片（見出し候補）と、の対応関係を当該比較により求め両者を関連付ける。この関連付け乃至対応関係のことをリンクと呼ぶ。また、目次内項目候補及び見出し候補の文書内位置については、例えば文書内ポインタによって指し示すことができる。関連付けの要否については、フォントサイズ、フォントタイプ、フォントスタイル、大文字の有無、下線の有無等の様々な条件に従い決定することができる。
【０００９】
以下の説明では、テキスト断片同士がテキスト的にどの程度似通っているかを示す指標であるテキスト類似度(textual similarity)に基づき、テキスト断片同士を比較し、それによって文書から目次を抽出する実施形態を採り上げる。ご理解頂けるように、本発明の実施形態はそうした実施形態に限られるわけではなく、本発明の実施に当たり採用できるテキスト断片比較手法は様々である。例えば、テキスト類似度、フォントサイズ、フォントタイプ、フォントスタイル、大文字の有無、下線の有無等の条件や、それらの任意の組合せによる条件に従い、テキスト断片同士を比較する手法を採ることができる。
【００１０】
図１中の処理対象文書８は非構造化文書(unstructured document)である。例えば、ワードプロセッサやスプレッドシート等のアプリケーションソフトウェアを使用して作成した文書や、紙等の原稿を光学スキャンして得た文書等、様々な手段によって得た文書を処理対象文書８とすることができる。また、同図中の目次領域１０は、ユーザインタフェース９を介しユーザが指定する、同図の装置が自動的に認識する等のやり方によって定められた文書８内の領域である。領域１０の自動認識に使用できるやり方としては、例えば、何個かのエリプシス（“…”）が連なった後にページ番号が付されているテキスト断片をサーチする、文字の羅列の冒頭又は末尾に数字が付されている行を探す、文書８の作成に使用したワードプロセッサ等のアプリケーションソフトウェアによって文書８内の領域１０を自動認識させる、等々がある。テキストフラグメンタ(text fragmenter)１２は、文書８を索引テキスト断片序列体１４と本文テキスト断片序列体１６とに分解する。テキスト断片序列体とは複数個のテキスト断片をその順序通りに並べたものをいい、なかでも（ｉ）序列体１４は索引テキスト断片を並べたもの、（ｉｉ）序列体１６は本文テキスト断片を並べたものである。索引テキスト断片とは文書８内の領域１０から抽出したテキスト断片を、また本文テキスト断片とは文書８内の１個又は複数個の領域（但し領域１０以外或いは序列体１４以外）から抽出したテキスト断片を、それぞれ指している。通常、文書８は文字列リストとしてロードされる。文書８たる文字列リストは、例えばＡｄｏｂｅ（登録商標）ＰＤＦ、Ｗｏｒｄ（商標）、ＦｒａｍｅＭａｋｅｒ（登録商標）等のフォーマットで入力された文書を、市販の文書コンバータを用いテキスト、ＸＭＬ等のフォーマットに変換することによって得たものである。また、紙文書を光学スキャナによりスキャンし、更にＯＣＲ(optical character recognition)により処理することによっても、文書８たる文字列リストを好適にロードすることができる。文書８がテキスト文書なら、例えばそのテキスト文書を構成している行を単位としてテキスト断片が抽出され、行の順序と同じ順序で並べられることとなろう。また、文書８がＸＭＬ文書やＨＴＭＬ文書なら、例えばＰＣＤＡＴＡを単位としてテキスト断片が抽出されることとなろう。
【００１１】
テキスト断片を順序通りに並べる方法は種々あるが、文書内順序乃至ページ内テキスト断片位置を利用するのがよいであろう。例えば文字が横書きで各行が左から始まる文書なら、下の行より上の行を優先し同じ行内ではより左寄りにある語を優先する上下方向優先左端開始法(depth-first left-to-right traversal)を用いるとよい。また、ＸＭＬノードとテキスト断片との関係を示す情報を保持しておき、目次内項目であることが判明したテキスト断片からそれに対応するＸＭＬノードへの後方参照関係を、処理終了時にマッピングすることができるようにしてもよい。更に、テキストフラグメンタ１２による断片化の単位は、行、ブロック、同一行内連接語群等、様々に設定することができる。場合によっては、単一の語が複数個のテキスト断片に分かれることもある。例えば、タイトルの冒頭語の冒頭文字の体裁が後続文字の体裁と異なる場合である。
【００１２】
テキストフラグメンタ１２から得られる索引テキスト断片序列体１４及び本文テキスト断片序列体１６は、テキスト類似度性リンクアイデンティファイア(textual similarity link identifier)２０によって処理され、それによりリンク候補２２が認識される。各候補２２は、テキスト的に類似している一対のテキスト断片、即ち索引テキスト断片序列体１４を構成する索引テキスト断片のうち一つと本文テキスト断片序列体１６を構成する本文テキスト断片のうち一つとの対によって、形成される。そのテキスト断片対が候補２２を形成する対であるかどうかを判別する手法は幾つかあるが、概ねどの手法でも、索引テキスト断片の個数がＴ個で本文テキスト断片の個数がＮ個ならＴ×Ｎ回のテキスト断片比較が必要になる。これに対して、本実施形態においては、後述の通り、序列体１６のうちどの部分列をサーチ対象とすべきかをサーチ範囲セレクタ２４によって認識し、その結果に基づきアイデンティファイア２０によるサーチ対象を制限しているため、テキスト断片比較回数がＴ×Ｎ回よりかなり少なくなることが多い。
【００１３】
テキスト断片比較に当たっては、しばしばテキスト中に混入するノイズの影響を考慮して処理を行うことも求められる。ノイズ発生原因としては、文書変換や目次構成上の問題等、様々な原因を挙げることができる。例えば、ＰＤＦからテキストへのフォーマット変換時に変換誤りが生じると、その変換誤りはノイズとなる。また、目次構成上の問題に起因するノイズとしては、例えば、目次内に登場するが本文には登場しないページ番号によって発生するノイズや、目次内でセクションタイトルとページ番号とをつなぐのに使用されている記号（例えばエリプシス“………”）により発生するノイズがある。また、リンク候補２２をなす対かどうかを判断するため本実施形態ではテキスト類似度を求めているが、その際には、例えば、テキスト断片間をセパレータで区切って複数個のトークンの集合に変換する。例えば各テキスト断片が英文字からなる文字列である場合、セパレータとしては英文字でないもの、例えばタブ、スペース、句読点等を用いればよい。更に、テキスト類似度を測ることができる指標としては、Ｊａｃｃａｒｄ係数や編集距離(edit distance)等、種々の指標がある。Ｊａｃｃａｒｄ係数は、索引テキスト断片から導出したトークン集合と、本文テキスト断片から導出したトークン集合とに基づき、それら二種類のトークン集合の積集合即ち交わり部分の基数(cardinal)と、当該二種類のトークン集合の和集合即ち合併集合の基数とを求め、積集合の基数を和集合の基数により除することによって、求めることができる。求めたＪａｃｃａｒｄ係数が所定のマッチングしきい値を上回っているなら、それらテキスト断片同士をリンクさせる。また、編集距離を用いる場合は、編集距離の上限を以て編集距離しきい値とする。ある２個のテキスト断片間の編集距離が編集距離しきい値より小さければ、テキスト的に類似していると判断してそれらテキスト断片同士をリンクさせる。これらの他にも、テキスト類似度を測るのに適しリンク選択条件を定めるのに使用できる条件は幾つかある。
【００１４】
テキスト断片同士の組合せは例えば（ｉ，ｊ）と表すことができる。ｉは索引テキスト断片序列体１４に含まれる索引テキスト断片の番号、ｊは本文テキスト断片序列体１６に含まれる本文テキスト断片の番号である。本実施形態では、あるテキスト断片対（ｉ，ｊ）がしきい値条件等のリンク選択条件を満足しているなら、そのテキスト断片対（ｉ，ｊ）について、リンク候補２２を形成する対の一つであるとの判断を下す。また、リンク選択条件を満たした（例えばそのＪａｃｃａｒｄ係数がしきい値を上回っている）テキスト断片対（ｉ，ｊ）即ち候補２２には、テキスト類似度で表したリンク強度を示す指標値、例えばＪａｃｃａｒｄ係数の値を関連付ける。なお、本実施形態ではＪａｃｃａｒｄ係数等のテキスト類似度を用いて候補２２を認識するようにしているが、フォントサイズ、フォントスタイル、フォント特性、大文字の有無、下線の有無等を用いて候補２２を認識する手法や、それらの任意の組合せにより候補２２を認識する手法や、更にはそれらとテキスト類似度との任意の組合せにより候補２２を認識する手法等によって、本発明を実施することもできる。
【００１５】
図２に、目次領域１０における目次１１０の位置関係の例を示す。この図に示す目次１１０は、領域１０の一部分だけを占めるに過ぎず、領域１０の全体に亘っているわけではない。但し、目次が目次領域全体に拡がるケースもある。目次内項目と、そのリンク先本文テキスト断片例えばセクション見出し、章見出し等と、の間のリンクを弁別、認識するに当たっては、概略、次に述べる四種類の一般的条件を使用する。そのうち第１の条件は蝟集性条件(contiguity)である。蝟集性条件は、目次内テキスト断片は領域１０内で蝟集し序列体を形成しているはずであり、従って領域１０内テキスト断片蝟集序列体又はその部分列が目次になるはずである、という事実を利用した判断基準である。蝟集序列体とは蝟集体であって序列体でもあるもののことをいい、蝟集体とは蝟集している複数個のテキスト断片の集合のことをいい、序列体とはその順序通りに並んでいる複数個のテキスト断片の集合のことをいい、部分列（部分序列体）とは序列体に含まれる一連なりのテキスト断片のことをいい、蝟集とは複数個のテキスト断片が１箇所に寄り集まることをいう。蝟集性条件を満たす蝟集序列体又はその部分序列体内のテキスト断片は、大抵は目次内項目１１２である。また、項目１１２ならばその文書８内で目次１１０より後に位置する別のテキスト断片に何れかのリンクによってリンクしているはずである。図中の矢印付曲線１１４は目次１１０内に発するリンクを表している。目次１１０内の項目１１２に発し対応するリンク先テキスト断片に至っているリンク１１４の集合は、テキスト類似度性リンクアイデンティファイア２０によって算出された候補２２の集合の部分集合となる。候補２２の集合の中にリンク１１４でないものが多数含まれることも多い。
【００１６】
更に、目次１１０内テキスト断片の多くは目次内項目１１２であるが、なかには袋小路(hole)になっているものもある。袋小路とは、図中の１１６のように、文書８中の他の部分にリンク１１４を介してリンクしていないテキスト断片のことである。袋小路１１６になるテキスト断片は比較的少数であり、通常は、項目１１２に対する袋小路１１６の個数比率は０．２未満である。こうした袋小路１１６については、その許容最大個数をユーザがパラメータとして設定できるようにしてもよい。
【００１７】
第２の目次認識条件はテキスト類似度条件(textual similarity)である。テキスト類似度条件とは、各目次内項目１１２を他のテキスト断片例えば見出しにリンクさせるには、その項目１１２とその項目１１２にリンクさせたいテキスト断片とが、テキスト的に十分類似していなければならない、という条件である。前述のＪａｃｃａｒｄ係数等は、テキスト類似度性リンクアイデンティファイア２０により好適に計測できテキスト類似度指標値として至便に使用できるものである。また、項目１１２のリンク先本文テキスト断片の性質は、その目次１１０の性質乃至構成によって変わる。例えば目次１１０が通常の構成ならセクション見出しが、また文書内の図のリスト（図一覧表）なら図に付された表題等が、或いは表のリスト（表一覧表）なら表に付された表題等が、それぞれリンク先になる。なお、通常、表題は対応する図や表の下側等に付されている。
【００１８】
第３の目次認識条件は順序条件(ordering)である。順序条件とは、目次内項目１１２の順序と、それら項目１１２のリンク先本文テキスト断片の順序とが、同順でなければならない、という条件である。例えば、一組の目次内項目｛ｉ１，ｉ２，ｉ３，…｝を一組のリンク｛（ｉ１，ｊ１），（ｉ２，ｊ２），（ｉ３，ｊ３），…｝を介し一組の本文テキスト断片｛ｊ１，ｊ２，ｊ３，…｝にリンクさせる場合、テキスト断片蝟集体における項目登場順序ｉ１，ｉ２，ｉ３，…と同じ順序ｊ１，ｊ２，ｊ３，…でリンク先本文テキスト断片が登場する、という関係が成り立っていなければならない。
【００１９】
第４の目次認識条件は自己参照忌避条件(lack of self-reference)である。自己参照忌避条件とは、各リンク１１４のリンク元テキスト断片とリンク先テキスト断片とが同じ目次１１０内のテキスト断片であってはならない、という条件である。自己参照忌避条件を満たすには、目次領域１０から抽出された索引テキスト断片序列体１４から選択する目次内項目１１２の集合｛ｉ１，ｉ２，ｉ３，…｝と、同じ文書８内にあり領域１０とは別の１個又は複数個の領域から抽出された本文テキスト断片序列体１６から選択する対応するリンク先本文テキスト断片の集合｛ｊ１，ｊ２，ｊ３，…｝との間に、交わり部分が生じないようにすると共に、リンク先本文テキスト断片集合｛ｊ１，ｊ２，ｊ３，…｝に目次１１０内袋小路１１６に対応するテキスト断片が含まれないようにすればよい。
【００２０】
また、図１に示されている目次領域１０は、例えばユーザ入力によって、或いは処理対象文書８を生成したアプリケーションプログラムによる目次領域自動認識処理の結果として、アプリオリに与えられるものである。目次が領域１０全体に拡がっており領域１０全体が目次で埋め尽くされていると見なしてよい場合は、アプリオリに与えられる領域１０によって目次位置が厳密に決まる。これに対して、アプリオリに与えられる領域１０に比べて目次の拡がりが狭い場合は、領域１０内目次位置を精密に判別する必要がある。例えば、文書８をスキャンによって取り込み、目次記載ページ（群）をユーザが指定し、ユーザ指定ページ（群）を領域１０として扱う使用形態では、ユーザ指定ページ（群）全体が目次であることは少なく、実際にはその一部だけが目次であるのが普通である。
【００２１】
目次領域１０内目次を認識する際には、例えば、蝟集性条件、テキスト類似度条件、順序条件及び自己参照忌避条件に従い目次選択を行う。目次選択に当たってはまずは目次候補選択を行う。目次候補選択を行うのは目次候補セレクタ３０であり、これによって領域１０から１個又は複数個の目次候補が選択される。目次候補選択に当たっては、例えば、索引テキスト断片序列体１４内索引テキスト断片個数をＴ、期待目次長最小値をΔとし、ある種の命題をＴ−Δ回検証する。即ち、索引テキスト断片のうちＴ−Δ個を目次筆頭項目候補とし、各目次筆頭項目候補について、命題「この索引テキスト断片から目次が始まっている可能性があるか？」の成否を検証し、成り立つ場合はその目次筆頭項目候補に続くテキスト断片を可能な限りその目次候補に入れることでその目次候補の規模を拡張していく。目次候補規模拡張は、新たなテキスト断片を追加すると順序条件が成り立たなくなるようになるまで続ける。例えば、最近その目次候補に追加した索引テキスト断片のリンク先候補がｊ＝１５の本文テキスト断片及びｊ＝３３の本文テキスト断片であるとする。また、その次の索引テキスト断片のリンク先候補がｊ＝２０の本文テキスト断片だけであるとする。この場合、いま調べている索引テキスト断片のリンク先候補（ｊ＝２０）は先に追加した索引テキスト断片のリンク先（ｊ＝１５）より後であるので、いま調べている索引テキスト断片をその目次候補に追加する。これに対して、いま調べている索引テキスト断片のリンク先候補がｊ＝１２の本文テキスト断片だけなら、いま調べている索引テキスト断片をその目次候補に追加すると順序条件が成り立たなくなるので、その索引テキスト断片をその目次候補に追加しない。但し、順序条件を若干緩和し、目次候補内に数個の袋小路１１６が残りうるようにした方が、有益でもある。そうするには、例えば、どのリンク候補２２にも関連付けられていないテキスト断片を所定個数まで許容し、またリンク交差(link-crossing)のあるテキスト断片（関連する候補２２全部がその目次候補内で順序条件を満たしていないテキスト断片）を所定個数まで許容するようにすればよい。そうした若干のリンク交差を許容することが有益に働くのは、例えば、現在選定中の目次候補内でそのテキスト断片より前に登場しているテキスト断片が、その文書内でかなり前方に位置しているテキスト断片だけにリンクしている場合等である。
【００２２】
各目次候補を調べるこの処理は、Ｔ−Δ個の目次筆頭項目候補それぞれについて、従ってＴ−Δ回繰り返して実行する。その結果として得られるのは、それぞれ索引テキスト断片序列体１４の部分序列体となっている１個又は複数個の目次候補の集合である。それらの目次候補は、確実に順序条件に従うように（或いは更に袋小路１１６を所定個数まで許容しつつ）構築されているので、当然、各目次候補内の目次内項目候補それぞれに対応する何個かのリンク候補２２の中から、順序条件を満足する候補２２を目次内項目候補毎に１個は、選択することができる。また、目次候補セレクタ３０にて篩い落とし条件(filtering)を適用し、明らかに目次でない目次候補を除外するようにしてもよい。例えば、ある目次候補内のテキスト断片個数が期待目次長最小値Δを下回っている場合、その目次候補は無視するのが適当であろう。
【００２３】
目次セレクタ３４は、こうして選定された目次候補にランク付けし、最高ランクの目次候補を選択する。リンクオプティマイザ３８は、その最高ランク目次候補に係るリンク候補２２を最適化することによって、最終的な目次１１０を生成する。この場合、セレクタ３４が目次候補にランク付けするため実行する処理の計算量は比較的少なく、選択された目次候補に対しオプティマイザ３８が施す処理はより徹底した計算を伴う。本願出願人の知見によれば、このやり方は、目次１１０を正確に抽出できるという点でも上首尾な手法である。また、各目次候補にリンク最適化を施し、リンク最適化後の一群の目次候補をランク付けする、というやり方も、計算量が多くなるが採用に値するやり方である。
【００２４】
図１に基づき更に説明すると、目次セレクタ３４では、スコアリング関数を使用して各目次候補にランク付けし、その中で最高ランクの目次候補を目次１１０として選択して、後の処理に供する。セレクタ３４にてスコアリング関数として使用できる量としては、項目荷重総和、項目総数、文書内見出し分布拡がり率等、種々の量がある。それらのうち項目荷重総和は、各目次内項目候補に関連付けられているリンク候補２２の個数に反比例するよう項目荷重を定め、定めた項目荷重をその目次候補内で総和することによって得られる。一般に、ある索引テキスト断片に発する候補２２がその目次候補における“真正な”リンク１１４である確率は、同じ索引テキスト断片に発する候補２２の個数が多ければ多い程低くなるので、項目荷重によって各候補２２の確からしさを評価することができる。また、スコアリング関数として使用でき熟考に値する量としては、更にその目次候補内の項目総数がある。順序条件及び自己参照忌避条件を満足するテキスト断片が数多く蝟集していることが判明している“長大な”目次候補は、それより“短小な”目次候補に比べより“真正な”可能性が高いものであるといえる。もう一つ、スコアリング関数として熟考に値する量としては、処理対象文書８全体に対する見出し分布範囲の割合、即ち文書内見出し分布拡がり率がある。例えば、ある同じ目次候補内からのリンク先本文テキスト断片の文書８内分布が比較的狭い場合、その目次候補がその文書８の“真正な”目次１１０である確率は低い。なお、以上の量はスコアリング関数の例に過ぎず、従ってこれら以外のスコアリング関数を使用することも、また何種類かのスコアリング関数を組み合わせて使用することも可能である。
【００２５】
最高ランクが付された目次候補に対しては、最終的な目次１１０を得るべく、リンクオプティマイザ３８が適用される。オプティマイザ３８は、その最高ランク目次候補に係るリンク候補２２について大局的に最適な解を導出することによって、その目次に係る候補２２の中で最良の候補２２を目次内項目１１２毎に選択し、それによって最終的な目次１１０を構築する。最良リンク候補選択に当たっては、目次認識に使用した蝟集性条件、テキスト類似度条件、順序条件及び自己参照忌避条件の四条件が引き続き満足されるようにする。更に、最良リンク候補選択の手法としては、例えばマッチングの度合いに比例する荷重を各候補２２に割り当てそれを利用して最適な候補２２を選択する、Ｖｉｔｅｒｂｉの最短パスアルゴリズム(Viterbi shortest path algorithm)を用いて最適な候補２２を選択する等、種々のアルゴリズムを使用できる。
【００２６】
目次が目次領域１０の（ほぼ）全体に拡がっていると見なしてよい場合は、目次候補セレクタ３０及び目次セレクタ３４の適用を省略し、領域１０から抽出された索引テキスト断片序列体１４の全体を目次と見なしてリンクオプティマイザ３８を適用することができる。領域１０の拡がりと実際の目次の拡がりとの間に僅かに食い違いが生じることもありうるが、そうした食い違いは目次内袋小路として問題なく吸収することができる。例えば、目次であることを示す見出しが領域１０の先頭に付されているために生じる食い違いや、ページ番号又はページ見出しを表すテキスト断片が領域１０に含まれているため生じる食い違いである。
【００２７】
こうして認識した目次１１０は種々の処理に使用できる。例えば、各目次内項目１１２のリンク先セクション見出し毎に処理対象文書８が分割され、それによってその文書８が構造化文書(structured document)に変換されるように、文書オーガナイザ１２０による構造化に目次１１０を利用することができる。また、目次１１０を用いて文書８を自動的に構造化する場合は、通常、順序条件を厳密に適用した方が有利である。これは、構造化文書フォーマット時に交差リンクがエラーを引き起こすからである。また、ここに述べた例はとりわけテキストセクションの索引となる目次１１０を認識する例であるが、順に図、表、式等の索引である図一覧表、表一覧表、式一覧表等を生成して目次１１０とする際にも、同様の処理を適用して類似した効果を得ることができる。
【００２８】
また、Ｔ個の索引テキスト断片及びＮ個の本文テキスト断片全てを対象としてテキスト類似度性リンクアイデンティファイア２０にテキスト断片比較を行わせると、所要比較回数がほぼＴ×Ｎ回にもなってしまう。これは、例えば数万個の本文テキスト断片を含む文書８の目次領域１０に十数個〜数千個のテキスト断片が含まれていると、テキスト断片比較所要回数Ｔ×Ｎが当然の如くに数百万、数千万或いはそれ以上にもなってしまう、ということである。しかも、テキスト断片比較に際して行う必要がある計算、例えばＪａｃｃａｒｄ係数等の比較指標の計算は、かなり計算能力を要する計算となるのが普通である。本実施形態でサーチ範囲セレクタ２４を用いる目的は、本文テキスト断片序列体１６のうちのある部分序列体へとサーチ対象を絞り込むことによって、テキスト断片比較所要回数をＴ×Ｎ回より少ない回数に抑えることにある。これによって、通常、当該回数をＴ×Ｎ回よりもかなり少ない回数にすることができる。
【００２９】
図３に、図１に示した装置にて処理される文書８の例２０８を示す。この図の文書２０８は索引テキスト断片序列体２１４及び本文テキスト断片序列体２１６から構成されており、序列体２１４は順に７個の索引テキスト断片｛Ｆtoc,1｝，…，｛Ｆtoc,7｝を、また序列体２１６は順に本文テキスト断片｛Ｆb,1｝，｛Ｆb,2｝，｛Ｆb,3｝，…を、それぞれ含んでいる。サーチ範囲セレクタ２４及びテキスト類似度性リンクアイデンティファイア２０は、協働乃至分業して、前者のリンク先候補を後者から選択するリンク先候補認識処理を実行する。その際には、まず、序列体２１４中葉に位置する索引テキスト断片｛Ｆtoc,4｝を起点として選択し、アイデンティファイア２０が起点｛Ｆtoc,4｝のリンク先候補として見つけ出した本文テキスト断片｛Ｆb,8｝，｛Ｆb,10｝，｛Ｆb,13｝を起点｛Ｆtoc,4｝に関連付ける。起点｛Ｆtoc,4｝についてリンク先候補認識処理を実行する際には、序列体２１６全体をサーチ範囲とするのが望ましい。結果として得られるリンク先候補本文テキスト断片｛Ｆb,8｝，｛Ｆb,10｝，｛Ｆb,13｝の集合中、最冒頭の即ち最も順序が早い本文テキスト断片は｛Ｆb,8｝、最末尾の即ち最も順序が遅い本文テキスト断片は｛Ｆb,13｝である。従って、起点｛Ｆtoc,4｝に対するリンク先候補最小順序ｄminは８、リンク先候補最大順序ｄmaxは１３となる。セレクタ２４は、起点｛Ｆtoc,4｝のリンク先候補の最小順序ｄmin及び最大順序ｄmaxに基づきサーチ範囲を制限した上で、別の索引テキスト断片のリンク先候補本文テキスト断片をサーチし見つかったリンク先候補をその索引テキスト断片に関連付ける処理を、実行させる。
【００３０】
図４中、索引テキスト断片｛Ｆtoc,2｝は起点索引テキスト断片｛Ｆtoc,4｝より冒頭寄りにある。次はこの冒頭側処理対象索引テキスト断片｛Ｆtoc,2｝のリンク先候補本文テキスト断片をサーチし、見つけ出した何個かのリンク先候補本文テキスト断片の集合を冒頭側処理対象｛Ｆtoc,2｝に関連付ける。このサーチに当たっては、サーチ範囲セレクタ２４が、起点｛Ｆtoc,4｝のリンク先候補の最大順序ｄmax及び順序条件に基づき、冒頭側処理対象｛Ｆtoc,2｝についてのリンク先候補サーチ範囲を制限する。例えば、序列体２１６内で最冒頭に位置する第１本文テキスト断片｛Ｆb,1｝から第ｄmax−１＝第１２本文テキスト断片｛Ｆb,12｝に至る範囲｛Ｆb,1｝，…，｛Ｆb,12｝に制限する。ここで第ｄmax−１までをリンク先候補サーチ範囲とするのは、起点｛Ｆtoc,4｝との関係で冒頭側処理対象｛Ｆtoc,2｝が順序条件を満たすようにするためである。即ち、冒頭側処理対象｛Ｆtoc,2｝は目次内で起点｛Ｆtoc,4｝より冒頭寄りにあるのであるから、仮にｄmax番目又はそれより末尾寄りの本文テキスト断片に冒頭側処理対象｛Ｆtoc,2｝がリンクしていると、順序条件違背となってしまう。サーチ範囲制限は、比較回数抑制だけでなく冒頭側の順序条件違背を回避する役にも立つ。
【００３１】
同様に、図５中、索引テキスト断片｛Ｆtoc,6｝は起点索引テキスト断片｛Ｆtoc,4｝より末尾寄りにある。次は、冒頭側処理対象索引テキスト断片｛Ｆtoc,2｝についてのリンク先候補サーチと並行して又は相前後して、この末尾側処理対象索引テキスト断片｛Ｆtoc,6｝のリンク先候補本文テキスト断片をサーチし、見つけ出した何個かのリンク先候補本文テキスト断片の集合を末尾側処理対象｛Ｆtoc,6｝に関連付ける。このサーチに当たっては、サーチ範囲セレクタ２４が、起点｛Ｆtoc,4｝のリンク先候補の最小順序ｄmin及び順序条件に基づき、末尾側処理対象｛Ｆtoc,6｝についてのリンク先候補サーチ範囲を制限する。例えば、第ｄmin＋１本文テキスト断片｛Ｆb,9｝から最末尾本文テキスト断片に至る範囲｛Ｆb,9｝，…に制限する。ここで第ｄmin＋１からをリンク先候補サーチ範囲とするのは、起点｛Ｆtoc,4｝との関係で末尾側処理対象｛Ｆtoc,6｝が順序条件を満たすようにするためである。即ち、末尾側処理対象｛Ｆtoc,6｝は目次内で起点｛Ｆtoc,4｝よりも末尾寄りにあるのであるから、仮に第ｄmin又はそれより冒頭寄りの本文テキスト断片に末尾側処理対象｛Ｆtoc,6｝がリンクしていると、順序条件違背となってしまう。サーチ範囲制限は、比較回数抑制だけでなく末尾側の順序条件違背を回避する役にも立つ。
【００３２】
図６に示すように、索引テキスト断片序列体が図３〜図５に示したものより多数の索引テキスト断片を含む大きな序列体である場合は、以上の処理を複数回繰り返して行うとよい。この図に示した索引テキスト断片序列体３１４は１７個の索引テキスト断片｛Ｆtoc,1｝，…，｛Ｆtoc,17｝を含んでおり、０巡目及び１巡目を含む複数巡のリンク先候補認識処理の対象とされる。そのうち０巡目処理においては、まず、序列体３１４中葉にある索引テキスト断片例えば｛Ｆtoc,9｝を０巡目起点索引テキスト断片ｉ（０）として選択し（ｉ（０）等の（）内の数字は何巡目かを示す；以下同様）、起点ｉ（０）のリンク先候補本文テキスト断片をサーチし、見つかった何個かのリンク先候補（図示せず）を起点ｉ（０）に関連付け、それらリンク先候補における最小順序ｄmin及び最大順序ｄmaxを求める。次いで、最冒頭索引テキスト断片｛Ｆtoc,1｝と起点ｉ（０）の中間にある索引テキスト断片例えば｛Ｆtoc,4｝を０巡目冒頭側処理対象索引テキスト断片Ｌ（０）として選択し、最冒頭本文テキスト断片｛Ｆb,1｝から第ｄmax−１本文テキスト断片に至る部分序列体をサーチ範囲として冒頭側処理対象Ｌ（０）のリンク先候補本文テキスト断片をサーチし、見つかった何個かのリンク先候補（図示せず）を冒頭側処理対象Ｌ（０）に関連付ける。サーチ範囲を制限するのは、仮に冒頭側処理対象Ｌ（０）が起点ｉ（０）のリンク先候補より末尾寄りの本文テキスト断片とリンクしていると、順序条件に違背してしまうからである。同様に、冒頭側処理対象Ｌ（０）についての処理と並行して又は相前後して、起点ｉ（０）と最末尾索引テキスト断片｛Ｆtoc,17｝の中間にある索引テキスト断片例えば｛Ｆtoc,14｝を０巡目末尾側処理対象索引テキスト断片Ｈ（０）として選択し、第ｄmin＋１本文テキスト断片から最末尾本文テキスト断片に至る部分序列体をサーチ範囲として末尾側処理対象Ｈ（０）のリンク先候補本文テキスト断片をサーチし、見つかった何個かのリンク先候補（図示せず）を末尾側処理対象Ｈ（０）に関連付ける。サーチ範囲を制限するのは、仮に末尾側処理対象Ｈ（０）が起点ｉ（０）のリンク先候補より冒頭寄りの本文テキスト断片とリンクしていると、順序条件に違背してしまうからである。
【００３３】
図６に示す例では、続いて、索引テキスト断片序列体３１４内索引テキスト断片のうち０巡目起点索引テキスト断片ｉ（０）より順序が早い索引テキスト断片の集合即ち冒頭寄り部分集合と、同じ起点ｉ（０）より順序が遅い索引テキスト断片の集合即ち末尾寄り部分集合とを定めて、同様の処理を繰り返す。即ち、１巡目においては、冒頭寄り部分集合と末尾寄り部分集合とを別個に処理する。その際、冒頭寄り部分集合については、最冒頭索引テキスト断片｛Ｆtoc,1｝と０巡目起点ｉ（０）のほぼ中間に位置しており従って冒頭寄り部分集合の中葉にある索引テキスト断片例えば｛Ｆtoc,4｝を、１巡目起点索引テキスト断片ｉL（１）として選択し、また、末尾寄り部分集合については、０巡目起点ｉ（０）と最末尾索引テキスト断片｛Ｆtoc,17｝のほぼ中間に位置しており従って末尾寄り部分集合の中葉にある索引テキスト断片例えば｛Ｆtoc,14｝を、１巡目起点索引テキスト断片ｉH（１）として選択する。
【００３４】
冒頭寄り部分集合について１巡目処理を実行する際には、冒頭寄り部分集合冒頭索引テキスト断片｛Ｆtoc,1｝と、冒頭寄り部分集合についての１巡目起点索引テキスト断片ｉL（１）と、の中間に位置する索引テキスト断片例えば｛Ｆtoc,2｝を１巡目冒頭側処理対象索引テキスト断片ＬL（１）とし、また、同じ起点ｉL（１）と、冒頭寄り部分集合末尾索引テキスト断片｛Ｆtoc,8｝と、の中間に位置する索引テキスト断片例えば｛Ｆtoc,6｝を１巡目末尾側処理対象索引テキスト断片ＨL（１）とする。更に、１巡目起点ｉL（１）についてリンク先候補最小順序ｄmin及び最大順序ｄmaxを求め、それらを用いリンク先候補サーチ範囲を定める。そして、こうして制限されたサーチ範囲内で冒頭側処理対象ＬL（１）及び末尾側処理対象ＨL（１）のリンク先候補本文テキスト断片をサーチし、見つけたリンク先候補を対応する処理対象に関連付ける。
【００３５】
同様に、末尾寄り部分集合について１巡目処理を実行する際には、末尾寄り部分集合冒頭索引テキスト断片｛Ｆtoc,10｝と、末尾寄り部分集合についての１巡目起点索引テキスト断片ｉH（１）と、の中間に位置する索引テキスト断片例えば｛Ｆtoc,12｝を１巡目冒頭側処理対象索引テキスト断片ＬH（１）とし、また、同じ起点ｉH（１）と、末尾寄り部分集合末尾索引テキスト断片｛Ｆtoc,17｝と、の中間に位置する索引テキスト断片例えば｛Ｆtoc,16｝を、１巡目末尾側処理対象索引テキスト断片ＨH（１）とする。更に、１巡目起点ｉH（１）についてリンク先候補最小順序ｄmin及び最大順序ｄmaxを求め、それらを用いリンク先候補サーチ範囲を定める。そして、こうして制限されたサーチ範囲内で冒頭側処理対象ＬH（１）及び末尾側処理対象ＨH（１）のリンク先候補本文テキスト断片をサーチし、見つけたリンク先候補を対応する処理対象に関連付ける。なお、一般に、以上述べた処理と同様の処理（２巡目等々の処理）を繰り返す場合もある。即ち図６に示す例であれば、図示しないが、冒頭寄り部分集合を更に冒頭寄り部分集合と末尾寄り部分集合とに分割し、末尾寄り部分集合も更に冒頭寄り部分集合と末尾寄り部分集合とに分割して、それら部分集合について同様の処理を繰り返すようにするとよい。
【００３６】
また、図３〜図６においては、それぞれ単一の索引テキスト断片を以て起点索引テキスト断片、冒頭側処理対象索引テキスト断片及び末尾側処理対象索引テキスト断片としているが、目次中に袋小路が含まれている場合、その袋小路が起点、冒頭側処理対象又は末尾側処理対象として選択されてしまう可能性があり、選択されてしまうとそれに対応するリンク先候補本文テキスト断片は見つけられなくなる。こうした状況にうまく対処するには、例えば索引テキスト断片序列体中葉に蝟集している複数個の索引テキスト断片を以て起点索引テキスト断片とし、各起点のリンク先候補本文テキスト断片を本文テキスト断片序列体から見つけ出し、見つけ出した何個かのリンク先候補をその起点に関連付けると共に、同じく索引テキスト断片序列体中で蝟集している複数個の索引テキスト断片を以て冒頭側処理対象索引テキスト断片とし、索引テキスト断片序列体中で蝟集している複数個の索引テキスト断片を以て末尾側処理対象索引テキスト断片とするとよい。起点個数、冒頭側処理対象個数及び末尾側処理対象個数が袋小路最大許容蝟集個数より多ければ、リンク先候補最小順序ｄmin及び最大順序ｄmaxを必ず定めることができるので、図３〜図６に示した複数巡構成のリンク先候補認識処理は目次内袋小路に対してロバストになる。
【００３７】
図３〜図６に示した手法によれば、テキスト断片比較回数を減らし処理時間を短縮することができる。例えば、２６１個の目次内索引テキスト断片及び５５２３８個の本文テキスト断片を含む１３００ページの文書８を、サーチ範囲セレクタ２４を用いずに処理してみたところ、テキスト断片比較回数がＮ×Ｔ＝２６１×５５２３８＝１４４１７１１８回にもなり、テキスト類似度性リンクアイデンティファイア２０にてこれを実行するのに１７０秒もの処理時間が必要であった。これに対し、同じ文書８をセレクタ２４を用いて処理してみたところ、テキスト断片比較回数が８４１４２８８回まで減り、アイデンティファイア２０にてこれを実行するのに１１０秒で足りた。これは処理速度にして４０％の上昇である。また、他の処理も含めた総処理時間も２６０秒から１５５秒へと減り、処理速度にして４０％上昇していることからすれば、目次候補セレクタ３０、目次セレクタ３４及びリンクオプティマイザ３８による処理も、リンク候補総数低減の恩恵を受けているといえよう。
【００３８】
また、場合によっては、目次が目次領域１０に比べかなり小さいことがある。即ち、領域１０のうちの目次前部分、目次後部分又はその双方に、多数の非目次テキスト断片が存在していることがある。この状況に対しては、目次セレクタ３０にて領域１０内目次を認識することで少なくとも部分的に対処できるが、領域１０内の目次前部分や目次後部分に含まれるテキスト断片に係るリンクが順序条件に従うとは限らないので、そうしたテキスト断片の存在はまた別の問題を生む原因となりかねない。従って、領域１０内目次前部分及び目次後部分にかなりの個数の非目次テキスト断片が存在している場合には、リンク先候補認識処理の深さを例えば最大３巡に制限することによって、対処する方がよい。０巡目から２巡目までの３巡に制限する場合、領域１０は、０巡目ではひとまとまりで、１巡目では２個の部分に分けて、２巡目では４個の部分に分けて、それぞれ処理されるので、処理時における領域１０の分割数は最大４個になる。最大四分割に留まるので、領域１０内最冒頭部分である第１略四半部や領域１０内最末尾部分である第４略四半部、更にはその構成部分に属するテキスト断片について、そのリンク先候補の最小順序ｄminや最大順序ｄmaxが計算されることがない。そのため、こうしたやり方を採れば、領域１０内目次外部分が領域１０全体の約１／４又はそれ未満に留まる場合に、ロバスト性が向上する。但し、リンク先候補認識処理の深さを制限するとその分処理速度向上効果が損なわれる。例えば、先に例示した１３００ページの文書であれば、処理の深さを３巡に制限すると速度向上幅が４０％から２０％に狭まる。
【００３９】
図７に、目次領域１０のうち本物の目次外に位置する目次外部分に余分なテキスト断片が存在しているとき、それに抗してロバスト性を向上させる手法について、また別の例を示す。この図に示した索引テキスト断片序列体３１４は図６に示したものと同じもの、即ち１７個の索引テキスト断片｛Ｆtoc,1｝，…，｛Ｆtoc,17｝を含むものである。この図の序列体３１４に対し本例に係るロバスト性向上手法を適用する際には、図６に示した例と同様、まずは領域１０中葉に位置する索引テキスト断片を０巡目起点索引テキスト断片ｉ（０）として選択し、０巡目起点ｉ（０）に対し何個かの本文テキスト断片をリンク先候補として関連付け、そしてそれらリンク先候補における最小順序ｄmin及び最大順序ｄmaxを導出する。なお、この例においても、袋小路最大許容蝟集個数より多くの索引テキスト断片を含む索引テキスト断片蝟集体を以て起点とすることによって、目次内袋小路に対するロバスト性を向上できる（後の巡でも同様）。
【００４０】
但し、この図に示すやり方では、０巡目冒頭側処理対象索引テキスト断片Ｌ（０）及び末尾側処理対象索引テキスト断片Ｈ（０）の選び方が図６に示した例とは異なっている。即ち、この図の例では、索引テキスト断片序列体３１４内で０巡目起点索引テキスト断片ｉ（０）に連接するように索引テキスト断片を選択して０巡目冒頭側処理対象Ｌ（０）及び末尾側処理対象Ｈ（０）とする。こうして選択した０巡目冒頭側処理対象Ｌ（０）及び末尾側処理対象Ｈ（０）については、先の例と同様にしてリンク先候補認識処理を実施する。即ち、０巡目起点ｉ（０）のリンク先候補の最大順序ｄmaxに従いサーチ範囲を制限して０巡目冒頭側処理対象Ｌ（０）のリンク先候補本文テキスト断片をサーチし認識する一方、０巡目起点ｉ（０）のリンク先候補の最小順序ｄminに従いサーチ範囲を制限して０巡目末尾側処理対象Ｈ（０）のリンク先候補本文テキスト断片をサーチし認識する。
【００４１】
次の１巡目においては、０巡目起点索引テキスト断片ｉ（０）並びにそれに連接する０巡目冒頭側処理対象索引テキスト断片Ｌ（０）及び末尾側処理対象索引テキスト断片Ｈ（０）の集合、即ち目次領域１０中葉にあり索引テキスト断片蝟集体を構成している複数個の索引テキスト断片の集合｛Ｌ（０），ｉ（０），Ｈ（０）｝を以て、１巡目起点索引テキスト断片ｉ（１）として選択し、それら１巡目起点ｉ（１）のリンク先候補本文テキスト断片をサーチして関連付け、それらリンク先候補における最小順序ｄmin及び最大順序ｄmaxを導出する。このとき１巡目リンク先候補最小順序ｄminとされるのは、複数個の１巡目起点ｉ（１）のうち何れかについてのリンク先候補本文テキスト断片の中で最冒頭の本文テキスト断片であり、１巡目リンク先候補最大順序ｄmaxとされるのは、複数個の１巡目起点ｉ（１）のうち何れかについてのリンク先候補本文テキスト断片の中で最末尾の本文テキスト断片である。更に、１巡目起点ｉ（１）に連接するよう１巡目冒頭側処理対象索引テキスト断片Ｌ（１）及び末尾側処理対象索引テキスト断片Ｈ（１）を選択し、１巡目リンク先候補最小順序ｄmin及び最大順序dmaxをサーチ範囲制限手段として用いて、それら処理対象Ｌ（１）及びＨ（１）についてリンク先候補認識処理を行う。
【００４２】
そして２巡目においては、索引テキスト断片蝟集体｛Ｌ（１），ｉ（１），Ｈ（１）｝を構成する複数個の索引テキスト断片を以て２巡目起点索引テキスト断片ｉ（２）とし、それに連接する索引テキスト断片を以て２巡目冒頭側処理対象索引テキスト断片Ｌ（２）及び末尾側処理対象索引テキスト断片Ｈ（２）とし、それら処理対象Ｌ（２）及びＨ（２）についてリンク先候補認識処理を行う。最後に３巡目においては、索引テキスト断片蝟集体｛Ｌ（２），ｉ（２），Ｈ（２）｝を構成する複数個の索引テキスト断片を以て３巡目起点索引テキスト断片ｉ（３）とし、それに連接する索引テキスト断片を以て３巡目冒頭側処理対象索引テキスト断片Ｌ（３）及び末尾側処理対象索引テキスト断片Ｈ（３）とし、それら処理対象Ｌ（３）及びＨ（３）についてリンク先候補認識処理を行う。このように、先の巡目での冒頭側及び末尾側処理対象索引テキスト断片を先の巡目での起点索引テキスト断片に連ねた索引テキスト断片蝟集体を以て起点索引テキスト断片とし、その冒頭側及び末尾側に連接する索引テキスト断片を処理対象索引テキスト断片として選択し、そのリンク先候補本文テキスト断片をサーチして対応する処理対象に関連付ける処理を、必要な巡数分繰り返すようにすればよい。
【００４３】
なお、図７に示した例では、０巡目起点索引テキスト断片ｉ（０）並びに各巡目冒頭側及び末尾側処理対象索引テキスト断片が何れも１個であったが、目次には袋小路が含まれていることもある。目次に袋小路、即ち最終的な目次内で本文テキスト断片にリンクすることのない索引テキスト断片が含まれていると、その袋小路が、０巡目起点ｉ（０）又は各巡目冒頭側若しくは末尾側処理対象として選ばれてしまうかもしれない。こうした状況に対処するには、例えば、索引テキスト断片序列体中葉にある複数個の索引テキスト断片の蝟集体を以て、０巡目起点ｉ（０）とするのが望ましい。その場合、複数個の０巡目起点ｉ（０）に対しては、それぞれ、本文テキスト断片序列体からリンク先候補本文テキスト断片を選択し、選択した何個かのリンク先候補を関連付ける。更に、リンク先候補最小順序ｄmin及び最大順序ｄmaxについては、蝟集体を構成している複数個の０巡目起点ｉ（０）のうち何れかについてのリンク候補本文テキスト断片の中で最冒頭のものの順序を最小順序ｄmin、最末尾のものの順序を最大順序ｄmaxとすることによって定める。０巡目起点ｉ（０）の個数Ｎを袋小路最大許容蝟集個数より多くすれば最小順序ｄmin及び最大順序ｄmaxを必ず求めることができる。その後の処理は、例えば図７に示した例と同じやり方でもよいが、別のやり方を採ることもできる。
【００４４】
例えば、各巡目（但し０巡目より後）のリンク先候補認識処理毎に、それぞれ複数個の起点索引テキスト断片から構成される複数個の固定長摺動窓を使用し、それら摺動窓を互いに逆の方向に摺動させる、というやり方がある。即ち、索引テキスト断片序列体１４内で現在の冒頭側処理対象の末尾側に連接及び蝟集しているＮ個の索引テキスト断片を以て上摺動窓とし、また同じ序列体１４内で現在の末尾側処理対象の冒頭側に連接及び蝟集しているＮ個の索引テキスト断片を以て下摺動窓とする。各巡目（但し０巡目より後）のリンク先候補認識処理においては、リンク先候補サーチに当たり、上摺動窓内のＮ個の索引テキスト断片についての最大順序ｄmaxにより冒頭側処理対象のリンク先候補サーチ範囲を制限し、下摺動窓内のＮ個の索引テキスト断片についての最小順序ｄminにより末尾側処理対象のリンク先候補サーチ範囲を制限する。これによってその巡目に係るリンク先候補認識処理を終えたら、それまでの冒頭側処理対象より順序が１個早い索引テキスト断片を新たな冒頭側処理対象とすることにより、Ｎ個の索引テキスト断片からなる上摺動窓を“上向き”に索引テキスト断片１個分摺動させ、また、それまでの末尾側処理対象より順序が１個遅い索引テキスト断片を新たな末尾側処理対象とすることにより、Ｎ個の索引テキスト断片からなる下摺動窓を“下向き”に索引テキスト断片１個分摺動させた上で、次の巡目の処理を実行する。なお、このやり方においても、単独の索引テキスト断片を以て冒頭側又は末尾側処理対象とするだけでなく、ひとまとまりに連接している複数個のテキスト断片を以て冒頭側又は末尾側処理対象とすることも可能である。後者、即ち一連なりになっている複数個のテキスト断片を以て処理対象とする場合には、各巡目における冒頭側処理対象索引テキスト断片蝟集個数分だけ上摺動窓を動かすことができ、同様に各巡目における末尾側処理対象索引テキスト断片蝟集個数分だけ下摺動窓を動かすことができる。更に、例えば上摺動窓内索引テキスト断片蝟集個数をＮ個とし、下摺動窓内索引テキスト断片蝟集個数をＭ個とする、というように、２個の摺動窓の大きさを違えることも熟慮に値する。
【００４５】
図７に示したやり方は、目次領域１０内にあり目次の先頭、末尾又はその双方に位置している余分な即ちノイズになるテキスト断片に対してロバストになる、という点で有益である。即ち、起点索引テキスト断片蝟集体が、各巡目の処理を終える毎に領域１０中葉から見て上下方向に拡張されていくので、領域１０内外寄り部分に位置しておりノイズが多い可能性がある領域に、処理当初からぶつかることを避けることができる。
【図面の簡単な説明】
【００４６】
【図１】文書内目次認識装置の一例構成を示す図である。
【図２】目次認識結果の一例を示す図である。
【図３】１巡構成のリンク先候補認識処理における起点索引テキスト断片、その処理によって判明したリンク先候補並びにその最小順序及び最大順序を示す図である。
【図４】図３の起点索引テキスト断片より冒頭寄りの領域から選んだ処理対象索引テキスト断片のリンク先候補をサーチする際使用され、起点索引テキスト断片のリンク先候補最大順序に基づき制限されているサーチ範囲を示す図である。
【図５】図３の起点索引テキスト断片より末尾寄りの領域から選んだ処理対象索引テキスト断片のリンク先候補をサーチする際使用され、起点索引テキスト断片のリンク先候補最小順序に基づき制限されているサーチ範囲を示す図である。
【図６】図３〜図５に示した例より長い目次について実施される２巡構成のリンク先候補認識処理を示す図である。
【図７】図６に示した例と同じ目次について実施される４巡構成のリンク先候補認識処理を示す図である。
【符号の説明】
【００４７】
８，２０８ 処理対象文書（非構造化文書）、９ ユーザインタフェース、１０ 目次領域、１２ テキストフラグメンタ、１４，２１４，３１４ 索引テキスト断片序列体、１６，２１６ 本文テキスト断片序列体、２０ テキスト類似度性リンクアイデンティファイア、２２ リンク候補、２４ サーチ範囲セレクタ、３０ 目次候補セレクタ、３４ 目次セレクタ、３８ リンクオプティマイザ、１１０ 目次、１１２ 目次内項目、１１４ リンク、１１６ 袋小路、１２０ 文書オーガナイザ、ｄmin リンク先候補最小順序、ｄmax リンク先候補最大順序、Ｆb,n 本文テキスト断片、Ｆtoc,n，Ｈ（ｎ），ＨL（ｎ），ｉ（ｎ），ｉL（ｎ），ｉＨ（ｎ），Ｌ（ｎ），ＬL（ｎ） 索引テキスト断片。
【特許請求の範囲】
【請求項１】
（ａ）索引テキスト断片序列体中葉に位置する起点索引テキスト断片に、本文テキスト断片序列体内から選んだ１個又は複数個のリンク先候補本文テキスト断片からなる起点リンク先候補集合を関連付けるステップと、
（ｂ）索引テキスト断片序列体内索引テキスト断片のうち起点索引テキスト断片より冒頭寄りの索引テキスト断片の集合である冒頭寄り部分集合の中葉に位置することとなるよう、冒頭側処理対象索引テキスト断片を選択するステップと、
（ｃ）索引テキスト断片序列体内索引テキスト断片のうち起点索引テキスト断片より末尾寄りの索引テキスト断片の集合である末尾寄り部分集合の中葉に位置することとなるよう、末尾側処理対象索引テキスト断片を選択するステップと、
（ｄ）冒頭側処理対象索引テキスト断片に、起点リンク先候補集合内最末尾本文テキスト断片より冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付けるステップと、
（ｅ）末尾側処理対象索引テキスト断片に、起点リンク先候補集合内最冒頭本文テキスト断片より末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付けるステップと、
（ｆ）それまでの冒頭側処理対象索引テキスト断片を起点索引テキスト断片として、冒頭寄り部分集合についてステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）における選択動作及び関連付け動作と同様の動作を実行するステップと、
（ｇ）それまでの末尾側処理対象索引テキスト断片を起点索引テキスト断片として、末尾寄り部分集合についてステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）における選択動作及び関連付け動作と同様の動作を実行するステップと、
を有する文書内目次認識方法。
【請求項２】
請求項１記載の文書内目次認識方法であって、起点索引テキスト断片、冒頭側処理対象索引テキスト断片及び末尾側処理対象索引テキスト断片のうち少なくとも何れかが、索引テキスト断片序列体の一部を構成する複数個の索引テキスト断片の蝟集部分を含む文書内目次認識方法。
【請求項３】
請求項１記載の文書内目次認識方法であって、ステップ（ａ）、（ｄ）及び（ｅ）における関連付け動作が、索引テキスト断片に対するテキスト類似度に基づき索引テキスト断片に対応するリンク先候補本文テキスト断片を選択する動作を含む文書内目次認識方法。
【請求項４】
索引テキスト断片序列体及び本文テキスト断片序列体を含む文書中の目次を認識する方法であって、
索引テキスト断片序列体内で冒頭側処理対象索引テキスト断片の末尾側にＮ個蝟集して連接している索引テキスト断片に係る最末尾リンク先候補本文テキスト断片に比べ、冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片を、その冒頭側処理対象索引テキスト断片に関連付けるステップと、
索引テキスト断片序列体内で末尾側処理対象索引テキスト断片の冒頭側にＭ個蝟集して連接している索引テキスト断片に係る最冒頭リンク先候補本文テキスト断片に比べ、末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片を、その末尾側処理対象索引テキスト断片に関連付けるステップと、
それまでの冒頭側処理対象索引テキスト断片より冒頭寄りの索引テキスト断片を新たな冒頭側処理対象索引テキスト断片とするステップと、
それまでの末尾側処理対象索引テキスト断片より末尾寄りの索引テキスト断片を新たな末尾側処理対象索引テキスト断片とするステップと、
これら、冒頭側処理対象索引テキスト断片へのリンク先候補の関連付け、末尾側処理対象索引テキスト断片へのリンク先候補の関連付け、冒頭側処理対象索引テキスト断片の更新、並びに末尾側処理対象索引テキスト断片の更新を繰り返すことによって、索引テキスト断片に係る１個又は複数個のリンク先候補本文テキスト断片の集合を生成するステップと、
を有する方法。
【請求項１】
（ａ）索引テキスト断片序列体中葉に位置する起点索引テキスト断片に、本文テキスト断片序列体内から選んだ１個又は複数個のリンク先候補本文テキスト断片からなる起点リンク先候補集合を関連付けるステップと、
（ｂ）索引テキスト断片序列体内索引テキスト断片のうち起点索引テキスト断片より冒頭寄りの索引テキスト断片の集合である冒頭寄り部分集合の中葉に位置することとなるよう、冒頭側処理対象索引テキスト断片を選択するステップと、
（ｃ）索引テキスト断片序列体内索引テキスト断片のうち起点索引テキスト断片より末尾寄りの索引テキスト断片の集合である末尾寄り部分集合の中葉に位置することとなるよう、末尾側処理対象索引テキスト断片を選択するステップと、
（ｄ）冒頭側処理対象索引テキスト断片に、起点リンク先候補集合内最末尾本文テキスト断片より冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付けるステップと、
（ｅ）末尾側処理対象索引テキスト断片に、起点リンク先候補集合内最冒頭本文テキスト断片より末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片の集合を関連付けるステップと、
（ｆ）それまでの冒頭側処理対象索引テキスト断片を起点索引テキスト断片として、冒頭寄り部分集合についてステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）における選択動作及び関連付け動作と同様の動作を実行するステップと、
（ｇ）それまでの末尾側処理対象索引テキスト断片を起点索引テキスト断片として、末尾寄り部分集合についてステップ（ｂ）、（ｃ）、（ｄ）及び（ｅ）における選択動作及び関連付け動作と同様の動作を実行するステップと、
を有する文書内目次認識方法。
【請求項２】
請求項１記載の文書内目次認識方法であって、起点索引テキスト断片、冒頭側処理対象索引テキスト断片及び末尾側処理対象索引テキスト断片のうち少なくとも何れかが、索引テキスト断片序列体の一部を構成する複数個の索引テキスト断片の蝟集部分を含む文書内目次認識方法。
【請求項３】
請求項１記載の文書内目次認識方法であって、ステップ（ａ）、（ｄ）及び（ｅ）における関連付け動作が、索引テキスト断片に対するテキスト類似度に基づき索引テキスト断片に対応するリンク先候補本文テキスト断片を選択する動作を含む文書内目次認識方法。
【請求項４】
索引テキスト断片序列体及び本文テキスト断片序列体を含む文書中の目次を認識する方法であって、
索引テキスト断片序列体内で冒頭側処理対象索引テキスト断片の末尾側にＮ個蝟集して連接している索引テキスト断片に係る最末尾リンク先候補本文テキスト断片に比べ、冒頭寄りにある１個又は複数個のリンク先候補本文テキスト断片を、その冒頭側処理対象索引テキスト断片に関連付けるステップと、
索引テキスト断片序列体内で末尾側処理対象索引テキスト断片の冒頭側にＭ個蝟集して連接している索引テキスト断片に係る最冒頭リンク先候補本文テキスト断片に比べ、末尾寄りにある１個又は複数個のリンク先候補本文テキスト断片を、その末尾側処理対象索引テキスト断片に関連付けるステップと、
それまでの冒頭側処理対象索引テキスト断片より冒頭寄りの索引テキスト断片を新たな冒頭側処理対象索引テキスト断片とするステップと、
それまでの末尾側処理対象索引テキスト断片より末尾寄りの索引テキスト断片を新たな末尾側処理対象索引テキスト断片とするステップと、
これら、冒頭側処理対象索引テキスト断片へのリンク先候補の関連付け、末尾側処理対象索引テキスト断片へのリンク先候補の関連付け、冒頭側処理対象索引テキスト断片の更新、並びに末尾側処理対象索引テキスト断片の更新を繰り返すことによって、索引テキスト断片に係る１個又は複数個のリンク先候補本文テキスト断片の集合を生成するステップと、
を有する方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００７−２２６７９７（Ｐ２００７−２２６７９７Ａ）
【公開日】平成１９年９月６日（２００７．９．６）
【国際特許分類】
【出願番号】特願２００７−４０１３２（Ｐ２００７−４０１３２）
【出願日】平成１９年２月２１日（２００７．２．２１）
【出願人】（５９６１７０１７０）ゼロックス コーポレイション (1,961)
【氏名又は名称原語表記】ＸＥＲＯＸ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成１９年９月６日（２００７．９．６）
【国際特許分類】
【出願日】平成１９年２月２１日（２００７．２．２１）
【出願人】（５９６１７０１７０）ゼロックス コーポレイション (1,961)
【氏名又は名称原語表記】ＸＥＲＯＸ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]