目次と見出しの対応付け方法、対応付け装置、及び対応付けプログラム
【課題】目次と本文中の見出し間の対応付けをコンピュータの演算処理により行う技術を提供する。
【解決手段】目次と見出しの対応付け装置３００は、文書の目次項目単位の目次データCと、行単位の本文データDとを入力する入力部３０２と、目次と見出しの対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索する探索部３０４と、スコア関数Sを最大にする対応付けMを出力する出力部３０６とを含む。上記スコア関数Sは、各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアuを全目次項目について足し合わせた第１の和と、目次項目ペアの見出し候補行への対応付けの尤もらしさを目次項目ペアのそれぞれの対応付けの共通度に基づき評価するバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求められる。
【解決手段】目次と見出しの対応付け装置３００は、文書の目次項目単位の目次データCと、行単位の本文データDとを入力する入力部３０２と、目次と見出しの対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索する探索部３０４と、スコア関数Sを最大にする対応付けMを出力する出力部３０６とを含む。上記スコア関数Sは、各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアuを全目次項目について足し合わせた第１の和と、目次項目ペアの見出し候補行への対応付けの尤もらしさを目次項目ペアのそれぞれの対応付けの共通度に基づき評価するバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求められる。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、電子化された書籍において、目次と本文中の見出し間の対応付けをコンピュータの演算処理により行う技術に関する。
【背景技術】
【０００２】
近年、国内外で書籍の電子化の勢いが増してきており、多くの書籍が電子化されつつある。書籍等の文書の電子化においては、光学式文字読取装置（Optical Character Reader :ＯＣＲ)によってテキスト・データを取得した後にこれに適切な構造情報を付与し、電子化のメリットを最大限に享受することが望まれる。電子化文書の価値を増加させる構造情報の１つとして、目次と本文中の見出し間の対応関係がある。目次と見出し間の対応関係の情報の付与によって、例えば、目次から本文中の対応する見出しへのリンクを貼ったり、本文中の文章の読み上げ順序を決定したり、また、検索時において本文よりも見出しを重視した重み付けを行うことが可能となる。
【０００３】
目次と本文中の見出し間の対応関係の情報は人手により付与することは不可能ではない。しかし、図書館等多くの書籍を所有する機関における電子化を考えると、人手による付与は現実的ではなく、コンピュータを利用した構造情報の自動付与が望まれる。
【０００４】
目次と本文中の見出しを自動で対応付ける従来技術として、特許文献１が存在する。特許文献１は、目次を認識するための条件として、各目次内項目と、その項目に結び付けられリンクしている他のテキスト断片例えば見出しとが、テキスト内容的に同様のものでなければならない、というテキスト類似度条件を開示する。しかしながら、テキスト類似度条件だけでは、例えば、章見出し又はセクション見出しと同じ文章が本文に含まれている場合、目次内項目にリンクさせるべき見出しがそれらの文章のうちどれなのかが判然としないという問題がある。
【０００５】
そこで特許文献１は、基準書式との照合によってテキスト断片を選択的に候補から除外した上で、目次内項目らしきテキスト断片、そのリンク先らしきテキスト断片又はその双方を認識する技術を開示する。より具体的には、特許文献１は、索引部分書式に合致しないテキスト断片や、見出しであることを示すキーワードを含んでいないテキスト断片、小文字の英文字を含むテキスト断片を見出し候補から除外する技法を開示する。
【０００６】
また、特許文献１は、各テキスト断片に関連付けられているページ内位置に基づき候補を絞った上で、目次内項目のリンク先らしきテキスト断片を認識する技術を開示する。ページ内位置に基づく個数削減条件としては、そのページの先頭から所定距離内にあるテキスト断片だけを見出し候補にするという条件、そのページの最左端カラムを表すカラム番号に関連付けられているテキスト断片だけを見出し候補にするという条件が開示されている。
【０００７】
また、特許文献２〜６は、タイトルを抽出することを目的とし、タイトル固有の特徴をポイントとして用いることにより、ポイント数の多い文字列領域をタイトルとして自動抽出する技術を開示する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００７−２２６７９２号公報
【特許文献２】特開２０００−１４８７８８号公報
【特許文献３】特開平１０−２６０９９３号公報
【特許文献４】特開２００１−３４７６３号公報
【特許文献５】特開２００３−１６０７６号公報
【特許文献６】特開２００３−５８５５６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１の技術によって、基準書式との照合によってテキスト断片を選択的に候補から除外するとしても、処理対象の文書が用いると予測される基準書式を事前に全て網羅して設定することは不可能である。処理対象の文書ごと人手で基準書式を設定すればこのような問題は解決できるが、それでは手間がかかりすぎる。
【００１０】
ページ内位置に基づく個数削減条件についても同様である。即ち、文書が採用するレイアウトに一定の傾向がみられるとしても具体的な位置条件は文書ごとに異なる。そのため位置条件を事前に設定しようとすると、全ての文書に適用可能な緩い条件を設定せざるをえなくなり、候補の絞込みを十分に行うことができなくなる。
【００１１】
また、位置情報に関しては、目次に含まれるページ情報を利用して見出し候補を当該ページ内に含まれるものに限定することも考えられる。しかしながら、前書き等の本文以外のページの存在のために、目次におけるページ番号と実際のページ番号、即ち通し番号とにずれが生じることも多い。そのためページ情報を利用する場合でも事前に人手により差分情報を付与することが必要となる。
【００１２】
なお、特許文献２〜６は、タイトル抽出のために利用可能なタイトル固有の特徴を開示する背景技術として挙げたものであり、目次と見出しの対応付けに関する技術を開示するものではない。
【００１３】
この発明は、上記の問題点を解決するためになされたものであって、見出し候補の絞り込み条件を事前に網羅的に設定したり文書ごとに人手により設定したりする必要なしに、電子化された書籍において、目次と本文中の見出し間の適切な対応付けをコンピュータの演算処理により行うことのできる技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成する本願発明は、次のような、文書の目次内の目次項目を前記文書の本文中の見出し行に対応付ける、コンピュータの演算処理による目次と見出しの対応付け方法によって実現される。そのような目次と見出しの対応付け方法は、前記コンピュータが、前記文書の目次項目単位の目次データCを受け取るステップと、前記コンピュータが、前記文書の行単位の本文データDを受け取るステップと、前記コンピュータが、前記目次データC内の全目次項目の前記本文データD内の見出し候補としての行である見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索するステップと、前記コンピュータが、前記スコア関数Sを最大にする前記対応付けMを出力するステップとを含む。ここで、前記スコア関数Sは、各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアuを全目次項目について足し合わせた第１の和と、一の目次項目と他の目次項目のペアである目次項目ペアの見出し候補行への対応付けの尤もらしさを前記目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価するバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求められる。
【００１５】
好ましくは、前記目次はフラット構造を有し、前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列との類似度に基づき求められる。また、前記バイグラムスコアbは、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度に基づき求められる。
【００１６】
より好ましくは、前記バイグラムスコアbは更に、前記目次項目ペアのそれぞれの対応付けにおける、目次項目に含まれるページ番号と該目次項目に対応付ける見出し候補行が含まれるページの通し番号との差の共通度に基づいて求められる。
【００１７】
また好ましくは、前記一の目次項目と前記他の目次項目とは隣接関係にある。
【００１８】
より好ましくは、前記目次は木構造を有し、前記一の目次項目と隣接関係にある前記他の目次項目を、前記目次の木構造において前記一の目次項目と同一階層において隣り合う兄弟関係にある目次項目に限定する。
【００１９】
更に好ましくは、前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列との類似度に基づき求められ、前記バイグラムスコアbは、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度に基づき求められる。
【００２０】
更により好ましくは、前記フォーマットの共通度は、前記目次項目ペアにそれぞれ対応付ける見出し候補行のフォントサイズの共通度と、前記目次項目ペアにそれぞれ対応付ける見出し候補行の最初の文字又は最初の文字と最後の文字との共通度と、前記目次項目ペアにそれぞれ対応付ける見出し候補行の文字列のうち、対応付ける目次項目の文字列に類似する部分である類似文字列の前後の所定数の文字の共通度のうちの少なくとも１つの共通度である。
【００２１】
また、更に好ましくは、前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列の類似度に基づき求められ、前記バイグラムスコアbは、前記目次項目ペアのそれぞれの対応付けにおける、目次項目に含まれるページ番号と該目次項目に対応付ける見出し候補行が含まれるページの通し番号との差の共通度に基づいて求められる。
【００２２】
更により好ましくは、前記バイグラムスコアbは、前記一の目次項目に対応付ける一の見出し候補行と、前記他の目次項目に対応付ける他の見出し候補行とが隣接している場合に値を減じられる。
【００２３】
また、より好ましくは、前記一の目次項目に隣接する目次項目に、前記一の目次項目に所定の数以下の目次項目を挟んで隣接する目次項目を含める。
【００２４】
また、より好ましくは、前記スコア関数Sの最大値は、Viterbiアルゴリズム又はダイクストラ法に従い探索される。
【００２５】
また、より好ましくは、前記スコア関数Sの最大値の探索において、前記目次データCに含まれる各目次項目にそれぞれ対応付ける前記見出し候補行を、本文データD内の全行のうち、前記目次項目の文字列と一定以上の類似度を有する文字列の行に限定する。
【００２６】
また、好ましくは、前記目次は木構造を有し、前記木構造において同一階層において隣り合う兄弟関係にある前記目次項目ペアに対しては、前記バイグラムスコアbとして、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度が高いほど高いスコア値を返す兄弟バイグラムスコアb1を採用し、前記木構造において親子関係にある前記目次項目ペアに対しては、前記バイグラムスコアbとして、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度が低いほど高いスコア値を返す親子バイグラムスコアb2を採用する。
【００２７】
より好ましくは、前記親子バイグラムスコアb2は、親である目次項目に対応付ける見出し候補行のフォントサイズがと子である目次項目に対応付ける見出し候補行のフォントサイズの間に大小関係がある場合に高いスコア値を返す。
【００２８】
また、より好ましくは、前記親子バイグラムスコアb2は、親である目次項目に対応付ける見出し候補行の索引部分と子である目次項目に対応付ける見出し候補行の索引部分のフォーマットが異なる場合に高いスコア値を返す。
【００２９】
また、より好ましくは、前記スコア関数Sの最大値は、2nd order Eisnerを応用したアルゴリズムに従い探索される。
【００３０】
また、より好ましくは、前記スコア関数Sの最大値の探索において、前記目次データCに含まれる各目次項目にそれぞれ対応付ける前記見出し候補行を、本文データD内の全行のうち、前記目次項目の文字列と一定以上の類似度を有する文字列を含む行に限定する。
【００３１】
以上、目次と見出しの対応付け方法として本願発明を説明した。しかし、本願発明は、そのような目次と見出しの対応付け方法を実行する目次と見出しの対応付け装置、及びそのような目次と見出しの自動対応付け方法をコンピュータに実行させる目次と見出しの対応付けプログラムとして把握することもできる。
【発明の効果】
【００３２】
本願発明では、目次項目の見出し候補行への対応付けの尤もらしさを、当該対応付け単独で評価するだけでなく、当該目次項目の見出し候補行への対応付けと他の目次項目の見出し候補行への対応付けとの共通度をも考慮して評価する。従って、本願発明によれば、見出しに共通する属性情報や目次におけるページ番号と通し番号との差分情報を、事前に網羅的に設定したり文書ごとに人手により設定したりする必要なしに、電子化された書籍において、目次と本文中の見出し間の適切な対応付けをコンピュータの演算処理により行うことができる。本願発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００３３】
【図１】目次と見出しの対応付けの一例を示す図である。
【図２】目次と見出しの対応付けの他の一例を示す図である。
【図３】本願発明の実施の形態に係る自動対応付け装置３００の機能構成の一例を示す図である。
【図４】スコア関数Sの最大値の探索するための探索対象のグラフの一例を示す図である。
【図５】第１のフィルタリング及び第２のフィルタリングを施した探索対象のグラフの一例を示す図である。
【図６】ページ抜けを示すエッジを追加した探索対象のグラフの一例を示す図である。
【図７】ページ抜けを示すノードを追加した探索対象のグラフの一例を示す図である。
【図８】自動対応付け装置３００による処理の全体の流れの一例（実施例１）を示すフローチャートである。
【図９】DAGのノード作成処理の流れの一例を示すフローチャートである。
【図１０】DAGのエッジ作成処理の流れの一例を示すフローチャートである。
【図１１】スコア関数Sの最大値探索処理の流れの一例を示すフローチャートである。
【図１２】スコア関数Sの最大値を与える対応付けMの出力処理の流れの一例を示すフローチャートである。
【図１３】図１３（ａ）は、木構造を有する目次の一例を示す図である。図１３（ｂ）は、対応付けMの配列の復元順序の一例を示す図である。
【図１４】自動対応付け装置３００による処理の全体の流れの一例（実施例２）を示すフローチャートである。
【図１５】見出し候補行の決定処理の流れの一例を示すフローチャートである。
【図１６】再帰関数comp(c, l, r)の計算処理の流れの一例を示すフローチャートである。
【図１７】再帰関数incomp(c, l, r)の計算処理の流れの一例を示すフローチャートである。
【図１８】再帰関数getcomp(c, l, r)処理の流れの一例を示すフローチャートである。
【図１９】再帰関数getincomp(c, l, r)処理の流れの一例を示すフローチャートである。
【図２０】本願発明の実施の形態に係る自動対応付け装置３００を実現するのに好適な情報処理装置のハードウェア構成の一例を示した図である。
【発明を実施するための形態】
【００３４】
以下、本願発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００３５】
図１は、目次と見出しの対応付けの一例を示す図である。図１において左側は目次ページ１００を示し、右側は本文ページ１０２を示す。目次ページ１００には目次項目が並び、各目次項目は、索引部分を有する文字列（目次項目１０４の例では「第六十九回」から始まる文字列１０６）とページ番号（目次項目１０４の例では「６」の数字１０８）とからなる。また、本文ページ１０２は、目次項目に対応する見出し１１０を含み、ページ左下に「６」のページ番号１１２を含む。
【００３６】
本願発明は、図１に示す矢印のように、目次ページ１００内の各目次項目を、本文ページ内の対応する見出し行に、コンピュータの演算処理により自動で適切に対応付けることを目的とする。目次項目の見出し行への対応付けの尤もらしさを評価するのに有効な基準の１つは、目次項目と見出し行の文字列の類似度である。
【００３７】
しかしながら、ＯＣＲ処理によって得られた目次データや本文データにはノイズ（誤字、脱字、ゴミ文字）が含まれることが予想される。また、図１に示す例では目次項目の文字列は索引部分が含んでいるが、このような索引部分は見出し行にのみ付与されることも少なくない。このような場合に目次項目の文字列と同じ文字列が本文中に複数含まれていると、文字列の類似度だけで対応付けの尤もらしさを正しく評価することはできない。
【００３８】
上述のケースの一例を図２に示す。図１と同様、左側は目次ページ２００を示し、右側は本文ページ２０２を示す。本文ページ２０２では全見出し行２１６、２１８、２２４に章番号が付与されているのに対し、目次ページ２００では、大章番号のみが該当する目次項目２０４、２１２に付与されている。そのため文字列の類似度だけでは「隠れマルコフモデル」の目次項目２０６を、本文ページ２０２内の「第４章 隠れマルコフモデル」の行２１６と、「4.1隠れマルコフモデル」の行２１８と、「隠れマルコフモデル」の行２２０のいずれに対応付けるべきか判断できない。
【００３９】
上記問題に対し、特許文献１の従来技術は、見出しには索引部分がある場合が多いことに注目し、基準書式との照合によって見出しの候補を絞り込む。また、上記従来技術は、見出しに関する文書ページ内レイアウトに関する種々のアプリオリな知識を利用し、ページ内位置関係に基づく条件によって見出しの候補を絞り込む。しかしながらそのためには、照合すべき基準書式やページ内位置関係に基づく条件を事前に設定しておく必要がある。事前設定にない基準書式が利用される場合、また、事前設定の条件が広すぎる場合には当該方法は有効に機能しない。
【００４０】
そこで本願発明では、見出しには共通して見られる見出しとしての特徴があることを、一の目次項目の見出し候補としての行（以下、「見出し候補行」という）への対応付けと、他の目次項目の見出し候補行への対応付けとの共通度を評価することで利用する。これを先の図２のケースを例に説明する。
【００４１】
上述したように、「隠れマルコフモデル」の目次項目２０６については、目次項目と見出し候補行の文字列の類似度から、本文ページ２０２内の「第４章 隠れマルコフモデル」の行２１６と、「4.1隠れマルコフモデル」の行２１８と、「隠れマルコフモデル」の行２２０の３つの行が見出し候補行として抽出される。ここで、目次項目２０６の見出し候補行への対応付けを、隣接する「マルコフ過程」の目次項目２０８の見出し候補行である「4.2マルコフ過程」の行２２４への対応づけとの共通度に基づき更に検討する。すると、対応付ける見出し候補行の索引部分の共通度の高さから、「4.1隠れマルコフモデル」の行２１８を正しく選択できる。
【００４２】
なお、対応付けの共通度を評価するにあたり選択すべき他の目次項目は、目次が木構造を有するか否かによって異なる。目次が木構造を有さずフラット構造を有する場合、各目次項目に対応付けられる見出しのフォーマットは同一と考えられる。従って、全ての目次項目が同一レベルにある場合、他の目次項目は一の目次項目と異なる任意の目次項目でよく、共通度の評価では共通度が高いほど高い評価となる。但し、他の目次項目は目次項目ごと異なることが好ましいことから、以下に説明する実施例では、他の目次項目は一の目次項目に隣接する目次項目とする。
【００４３】
一方、目次が木構造を有する場合、兄弟関係にある目次項目のペアにそれぞれ対応付けられる見出しのフォーマットは同一と考えられが、親子関係にある目次項目のペアにそれぞれ対応付けられる見出しのフォーマットは同一ではなく、例えばフォントサイズや章番号等、大小関係があると考えられる。従って目次が木構造を有する場合、選択すべき他の目次項目は、一の目次項目と兄弟関係にある目次項目であり、共通度の評価では共通度が高いほど高い評価となる。但し、共通度の評価を、共通度が低いほど高い評価を行うようにすれば、他の目次項目として、一の目次項目と親子関係にある目次項目を選択することも可能である。
【００４４】
また、一の目次項目の見出し候補行への対応付けと、他の目次項目の見出し候補行への対応付けとの共通度を評価することによって、目次におけるページ情報の利用が可能となる。なぜならば、目次項目に含まれる目次のページ番号と実際のページ番号、即ち、文書の最初のページからの通し番号とにずれがあったとしても、ずれの程度は全ての対応付けにおいて同一であるからである。なお、通し番号から目次項目のページ番号を差し引いた差分の共通性に基づく対応付けの評価は、目次が木構造を有するか否かによらず、任意の目次項目ペアに対して適用可能であることに留意されたい。
【００４５】
以下、目次項目と見出し候補行との対応付けの問題を定式化し、定式化した問題に対して本願発明を説明する。
【００４６】
まず、本願発明の一実施形態に係る目次と見出しの自動対応付け装置への入力として、目次データCと、本文データDを次のように定義する。
C = {(s1,p1), …, (s|C|,p|C|)} ― （定義１）
ここで、|C|は目次に含まれる全目次項目数、siはi番目の目次項目の文字列、piはi番目の目次項目のページ番号を示す。
D = {L1, …, L|D|} ― （定義２）
ここで、|D|は本文に含まれる全行数、Lkは本文に含まれるk番目の行を示す。
【００４７】
このような目次データCは、文書のスキャンデータから目次ページを推定して、各行を目次データとすることにより取得してよい。その際、各行の最後にある数字をページ番号piとし、両端の空白文字を除く残りを目次項目の文字列siとしてよい。かかる処理の詳細は、例えば以下の文献を参照されたい。
S. Mandal, S. P. Chowdhury, A. K. Das, B. Chanda, “AutomatedDetection and Segmentation of Table of Contents Page from Document Images.”, In proc. of ICDAR 2003.
なお、目次データCは書籍の所有者である出版社が所有していることも多く、その場合出版社から取得できる。
【００４８】
一方、本文に含まれる各行Lkは、文字列と通し番号やフォントサイズ等の付加情報からなるものとする。一般的にＯＣＲは認識した文字の情報だけでなく、該文字が占める矩形情報をも出力する。具体的には、ページ隅を原点としたページ内での矩形の位置座標(x,y)、矩形の幅width及び高さheightである。また、一般的なＯＣＲは、閾値以下で隣接する文字を同じ行としてつなぎ合わせる等の処理をして行を認識し、行単位で文字単位のスキャン結果を出力することができる。そこで本実施例では、ＯＣＲの当該機能を利用し、同一行と認識された文字単位の認識結果の集合から、各行Lkの文字列（空白文字は含まない）を取得し、また、高さheightの中央値を求めてこれを各行Lkのフォントサイズとする。更にＯＣＲは、横書きの場合ページごとに上から下へ順次スキャンを行うことから通し番号やページ内行番号を取得可能であり（縦書きの場合は通し番号とページ内の列番号）、本実施例では当該通し番号とページ内行番号を各行Lkに付与するものとする。
【００４９】
次に、目次と見出しの自動対応付け装置からの出力として、出力データMを次のように定義する。
M = {m1, …, m|C|} ― （定義３）
ここで、|C|は目次に含まれる全目次項目数を示す。
出力データMは、各目次項目が何行目に対応しているかを表す正の整数の列であり、要素miは、i番目の目次項目がmi（正の整数値）行目に対応することを示す。そのため以下では出力データMを対応付けMともいう。
【００５０】
ここで、目次データC内の全目次項目の本文データD内の見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sを考える。すると、目次項目の見出し候補行への対応付けの問題は、スコア関数Sを最大にする対応付けMを求める問題として定式化できる。
【００５１】
本願発明では、上述したように、目次項目の見出し候補行への対応付けの尤もらしさを、当該対応付け単独で評価するだけでなく、他の目次項目の見出し候補行への対応付けとの共通度をも考慮して評価する。そこで、本願発明では、上記スコア関数Sを以下のように定義する。
S(C,D,M) = Σi u(i,mi,C,D)+ Σib(i, mi, mj, C,D) ― （定義４）
ここで、uは各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアを示し、出力データMの要素miごとのスコアを示す。
また、bは一の目次項目と他の目次項目のペアである目次項目ペアの見出し候補行への対応付けの尤もらしさを目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価するバイグラムスコアを示し、出力データMの要素のペアmi, mjごとのスコアを示す。
【００５２】
対応付けMの候補は入力長に対して指数個存在するため、全ての対応付けMを列挙してスコア関数Sの最大値を求めることは一般に、計算量的に困難である。しかし、スコア関数Sを上記のようにユニグラムスコアuを全目次項目について足し合わせた第１の和と、バイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として表すことで、多項式時間で計算することが可能である。例えば、Viterbiアルゴリズムを適用すれば、上記スコア関数Sを最大にする対応付けMの系列は、目次項目数|C|、本文行数|D｜に対して、時間計算量O(|C||D|2)で求められることが知られている。なお、本文データDの要素、即ち見出し候補行をフィルタリングすることによって、時間計算量は更に少なくすることが可能である。
【００５３】
以上のように定式化した問題に対し、本願発明の一実施形態に係る目次と見出しの自動対応付け装置３００を説明する。図３は、本願発明の一実施形態に係る目次と見出しの自動対応付け装置３００の機能構成を示す図である。目次と見出しの自動対応付け装置３００は、入力部３０２と、探索部３０４と、出力部３０６とを備える。
【００５４】
入力部３０２は、文書の目次項目単位の目次データCと、文書の行単位の本文データDとを、記憶装置から読み出して、またはネットワークを介して他のコンピュータから、入力する。探索部３０４は、目次データC内の全目次項目の本文データD内の見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索する。出力部３０６は、スコア関数Sを最大にする前記対応付けMを出力する。
【００５５】
ここで探索部３０４は、スコア関数Sを、定義４に関して説明したユニグラムスコアuを全目次項目について足し合わせた第１の和と、同じく定義４に関して説明したバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求める。
【００５６】
ところでバイグラムスコアbは上述したように、目次が木構造を有するか否かによってその値を求めるべき目次項目のペアの組み方が異なる。そこで以下では、目次がフラット構造を有する場合を実施例１、目次が木構造を有する場合を実施例２としてそれぞれ順に説明する。
【実施例１】
【００５７】
実施例１では、目次はフラット構造を有し、全ての目次項目が同一レベルにあるとする。この場合、バイグラムスコアbを求めるべき目次項目のペアは、任意の目次項目のペアであってよく、共通度の評価では共通度が高いほど高い評価となる。しかし、一の目次項目のペアとすべき他の目次項目は目次項目ごと異なることが好ましい。そこで本実施例では、目次項目のペアは隣接関係にある目次項目のペアとし、定義４を次のように書き直す。
S(C,D,M) =Σi u(i,mi,C,D) + Σib(i, mi,mi+1, C,D) ―（定義５）
以下ではまず定義５におけるユニグラムスコアuとバイグラムスコアbの設計方法を説明する。その後に、定義５で示されるスコア関数Sの最大値の探索方法を図４から図７を参照して説明する。
【００５８】
既に説明したとおり、ユニグラムスコアu(i,mi,C,D)は、i番目の目次項目 (C[i]）を文書のmi行目（D[mi]）に対応付ける対応付けの尤もらしさを該対応付け単独で評価したスコアである。以下ではユニグラムスコアu (i,mi,C,D)を、簡略してu(i, mi)とも記載する。単独評価の第１の例は、文字列の類似度に基づく評価である。即ち、C[i]の文字列とD[mi]の文字列が互いに類似しているならば高いスコアを返すようにユニグラムスコアuを設計する。
【００５９】
類似か否かの判断は、一例としてC[i]の文字列とD[mi]の文字列の編集距離や、C[i]の文字列とD[mi]の文字列に共通に含まれる隣接２文字対の数を利用してよい。前者の編集距離は、２つの文字列がどの程度異なっているかを示す数値であるため、編集距離が所定の閾値以下であれば類似と判断してよい。後者は、各文字列について隣接２文字対の集合をそれぞれ求め、２つの集合の積集合のサイズが所定の閾値以上であれば類似と判断してよい。便宜上、以下では類似であるか否かを判断する際の所定の閾値をMINSIMという。編集距離の詳細については、例えば以下の文献を参照されたい。
Gonzalo Navarro, Mathieu Raffinot, “FlexiblePattern Matching in Strings: Practical On-Line Search Algorithms for Texts andBiological Sequences”, Cambridge UniversityPress, 2007.
【００６０】
単独評価の第２の例は、行の種類に基づく評価である。即ち、フォントサイズや位置等の情報から、D[mi]が見出しにみられる特徴を有すると判断できる場合、高いスコアを返すユニグラムスコアuを設計する。逆に、フォントサイズや位置等の情報から、D[mi]が柱や注釈、本文に見られる特徴を有すると判断される場合、低いスコアを返すユニグラムスコアuを設計する。なお、行の種類に基づく評価は複数考えられるため、例えば、見出しの可能性が高いと判断すればスコアを１増やし、見出しでない可能性が高いと判断すればスコアを１減らし、というように複数の判断を組み合わせて最終的なスコアを出力するよう設計してもよい。
【００６１】
ここでフォントサイズの大小は、見出しや注釈以外の本文との比較によって判断されうるものである。そこで、本文のフォントサイズを文書内の全行のフォントサイズの中央値で代替し、D[mi]が該中央値より大きいフォントサイズを有する場合に見出しと判断し、D[mi]が上記中央値より小さいフォントサイズを有する場合に見出しでないと判断してよい。また、位置情報に関しては、例えば、見出しはページの最初につきやすいことから、D[mi]がページの最初の行である場合に見出しと判断してもよい。逆に、D[mi]がページの最後の行である場合には注釈である可能性が高いことから、見出しではないと判断してもよい。また、見出し行は中央寄せであったり、本文よりも左に飛び出すなど、本文と異なる傾向にあることから、例えば横書きの場合、全行の文字の始まり位置の中央値からD[mi]の文字の始まり位置を差し引いた値の絶対値が所定の閾値以上であれば見出しと判断し、そうでない場合見出しでないと判断してもよい。なおこれらは位置情報に基づく判断の一例として説明したものであり、他の位置情報に関する見出しの特徴の知識の利用を制限するものではないことに留意されたい。
【００６２】
ユニグラムスコアuは、上述した文字列の類似度にのみ基づいて評価するものでもよく、または文字列の類似度に基づく評価（スコア）と行の種類に基づく評価（スコア）とを適宜重み付けをしつつ足し合わせて総合評価するのでもよい。このような総合評価を採用する場合、対応付けのいくつかについてフォントサイズや位置情報を取得できないため全部の評価(スコア）を取得できないとしても、いずれか１つの評価（スコア）を求めることができれば問題はない。また、重み付けは正解データから各スコアの重みを自動学習してもよい。
【００６３】
次に、バイグラムスコアb(i, mi, mi+1, C,D)の設計方法について説明する。既に説明したとおり、バイグラムスコアb(i, mi, mi+1, C,D)は、一の目次項目（i番目の目次項目 (C[i]））と該一の目次項目に隣接する他の目次項目（i+1番目の目次項目 (C[i+1]））のペアである目次項目ペアの見出し候補行（mi行目（D[mi]）とmi+1行目（D[mi+1]））への対応付けの尤もらしさを、当該隣接する目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価したスコアである。なお上述したように、実施例１における共通度の評価は、共通度が高いほど高い評価を行う評価である。また、以下ではバイグラムスコア b(i, mi, mi+1, C,D)を、単にb(i, i+1, mi,mi+1,)とも記載する。
【００６４】
共通度に基づく評価の第１の例は、フォーマットの共通度に基づく評価である。即ち、C[i]を対応付けるD[mi]と、C[i+1]を対応付けるD[mi+1]のフォーマットの共通度が高い場合に高いスコアを返すようにバイグラムスコアbを設計してよい。より具体的には、フォーマットの共通度は、D[mi]とD[mi+1]のフォントサイズの共通度であってよく、D[mi]とD[mi+1]のフォントサイズが同一とみなせる場合にフォーマットの共通度が高いと判断してよい。これは、目次がフラット構造であれば見出しのフォントサイズは同じであるという知識に基づくものである。
【００６５】
また、フォーマットの共通度は、D[mi]の文字列とD[mi+1]の文字列の最初の文字又は最初の文字と最後の文字の共通度であってよい。即ち、D[mi]の文字列とD[mi+1] の文字列が、共通の文字で始まる又は共通の文字で始まりかつ共通の文字で終わる場合にフォーマットの共通度が高いと判断してもよい。これは、見出しには、索引部分（例えば、“第Ｘ章”や“第Ｘ部”等）や見出しであることを示す記号（例えば、“§”や“○”等）が先頭において含まれることが多いこと、また、見出しであることを示す記号については、例えば“■リストの実現■”のように、見出しの最初と最後に含まれていることがあること、そして目次がフラット構造であればそのような書式は全見出しに共通であるという知識に基づくものである。
【００６６】
また、C[i]の文字列と類似するD[mi]の文字列部分（以下、D[mi]の類似文字列という）と、C[i+1]の文字列と類似するD[mi+1]の文字列部分（以下、D[mi+1]の類似文字列という）の前後の所定数の文字の類似度が高い場合にフォーマットの共通度が高いと判断してもよい。かかる判断は、１つには、目次項目の文字列に索引部分や記号部分が含まれない場合に効果的である。なぜならばこの場合、D[mi]やD[mi+1]の類似文字列の前後の所定数の文字は、索引部分（例えば、“第Ｘ章”や“第Ｘ部”等）や記号部分（例えば、“§”や“■リストの実現■”の“■”等）を指すことになり、当該部分の類似度が高い場合にフォーマットの共通度が高いと判断することになるからである。またかかる判断は、スキャンデータ以外のデータであって位置情報を持たないデータを利用する場合に有効である。この場合、見出し候補行の文字列はフォーマット調整のための空白文字を含み、従ってD[mi]やD[mi+1]の類似文字列の前後の所定数の文字は、フォーマットに利用された空白文字を指すことになり、当該部分の類似度が高い場合にフォーマットの共通度が高いと判断することになるからである。
【００６７】
共通度に基づく評価の第２の例は、目次におけるページ番号と実際のページ番号、即ち、最初のページからの通し番号との差分の共通度に基づく評価である。即ち、C[i]に含まれるページ番号とC[i]に対応付けるD[mi]を含むページの通し番号との差分と、C[i+1]に含まれるページ番号とC[i+1]を対応付けるD[mi+1] を含むページの通し番号との差分との共通度が高い場合に高いスコアを返すようにバイグラムスコアbを設計してよい。なお、差分の共通度の高さは、一例として差分が同一である場合に共通度が高いとしてよい。
【００６８】
当該評価は、前書き等の本文以外のページの存在のため、目次におけるページ番号と通し番号にはずれが生じることが多いが、その差分は一定であるという知識にもとづくものである。例えば、目次に含まれる各目次項目のページ番号がそれぞれ、１、４、１１、７（誤）、２２、２６であったとする。但し７のページ番号は読み取り誤りがあったため、間違ったページ番号であるとする。これに対し、対応する見出し候補行の通し番号がそれぞれ、２、５、１２、１８、２３、２７であったとする。するとその差分はそれぞれ、１、１、１、１１、１、１であり、５つの隣接目次項目のペアのうち３つは差分の値が同一となる。このようにページ番号を差分で評価することにより、ページ番号のわずかな読み取り誤りによって評価が大きく影響を受けることはなくなる。
【００６９】
上記差分の共通度に基づく評価に加えて、非隣接行制約に従うようバイグラムスコアbを設計してもよい。ここで非隣接行制約とは、隣接する目次項目ペアC[i] 、C[i+1]にそれぞれ対応付けられる見出し候補行D[mi] 、D[mi+1]は、隣接する行であってはいけないという制約である。この制約は、連続する見出しの間には必ず本文があるという知識に基づくものである。そこで、C[i] 、C[i+1]が隣接する行である場合、バイグラムスコアbの値を減じるように設計してもよい。
【００７０】
バイグラムスコアbは、上述した３つのフォーマットの共通度に基づく評価（スコア）と、ページの差分の共通度に基づく評価（スコア）と、非隣接行制約に基づく評価（スコア）とのうち任意の数の評価（スコア）を、重み付けをしつつ組み合わせて評価するものであってもよい。複数の評価（スコア）を足し合わせて評価する場合、対応付けのいくつかについてフォントサイズやページ情報を取得できないため全部の評価(スコア）を取得できないとしても、いずれか１つの評価（スコア）を求めることができれば問題はない。また、重み付けは正解データから各スコアの重みを自動学習してもよい。
【００７１】
次に定義５により表されるスコア関数Sの最大値の探索方法を説明する。図４は、スコア関数Sの最大値の探索するための探索対象のグラフ４００を示す。グラフ４００は、（目次項目数（|C|）４０２×本文の全行数（|D|）４０４）個の丸で示されるノードと、探索開始地点を示す仮想ノードであるBOS４０６と、探索終了地点を示す仮想ノードであるEOS４１０と、隣接するノード間を結ぶエッジとから構成される。なお、図４では一部のエッジのみ表示し、残りのエッジは省略していることに留意されたい。
【００７２】
グラフ４００の各ノードは、該ノードが属する列の列番号とノードに付けられた番号によって、何番目の目次項目を何行目に対応付けるかその対応付けを示す。例えばノード４１２は、１番目の列に属しノードに番号４が付けられていることから、１番目の目次項目を４行目に対応付ける対応付けを示す。従って、i番目の列に属するノードの集合は、対応付けMの要素miが示しうる全対応付けの集合とみることができる。なお、図４では、一部のノードのみ丸の中に対応付けた行番号を表示し、残りのノードについてはそのような行番号を表示していないことに留意されたい。
【００７３】
また、グラフ４００の各エッジは、エッジ両端のノードが示す対応付けのペア、即ち、隣接関係にある目次項目のペアの対応付けを示す。例えばエッジ４１４は、１番目の目次項目を３行目に対応付ける対応付けと、１番目の目次項目に隣接する２番目の目次項目を４行目に対応付ける対応付けのペアを示す。
【００７４】
各ノードには該ノードが示す対応付けについてのユニグラムスコアuが付与されている。また、各エッジには該エッジが示す隣接する目次項目のペアの対応付けについてのバイグラムスコアbが付与されている。このようなグラフ４００が与えられた場合に、スコア関数Sの最大値の探索は、BOS４０６を始点としEOS４１０を終点とするあらゆる経路の中で（経路４０８は一例）、その経路に含まれるノード及びエッジに付与されたスコアの合計を最大にする経路を選択する問題として捉えることができる。
【００７５】
グラフ４００は無閉路有向グラフ(DirectedAcyclic Graph: DAG)であることから、この経路探索の問題はViterbiアルゴリズムやダイクストラ法によりノード数に対して多項式時間で解くことができる。具体的には、目次項目数|C|、本文行数|D｜に対して、時間計算量O(|C||D|2)で求めることができる。従って実際の計算時間は、本文データDの要素、即ち見出し候補行をフィルタリングすることによって、更に少なくすることができる。
【００７６】
そこで、次に見出し候補行のフィルタリングについて説明する。第１のフィルタリングはページ番号の制約に基づくフィルタリングである。目次は見出しを順序立てて書いたものである。従って、目次項目C[i]に対応付ける見出し行の行番号miは、iが大きくなるにつれて大きくならなければならない。従って、図４に示すグラフ４００においてmi > mi+1となるエッジは削除してよい。エッジの削除によって孤立するノードもまた削除してよい。
【００７７】
第２のフィルタリングは、目次項目と該目次項目に対応付ける見出し候補行の文字列の類似度に基づくフィルタリングである。即ち、目次項目C[i]に対応付ける見出し候補行D[mi]を、本文データD内の全行のうち、C[i]の文字列と一定以上の類似度を有する文字列の行に限定してよい。ここで類似度の判断は、上述したユニグラムスコアuにおける類似度の判断と同様の方法を使用してよい。
【００７８】
図５は、図４に示すグラフ４００において、第１のフィルタリング及び第２のフィルタリングによりエッジとノードを削除した結果のグラフ５００を示す。但し図５では、m1 とm２の列以外は、ノードの行番号とエッジとを省略していることに留意されたい。m1の列５０８をみてみると、各ノードに付けられた行番号は、１、８、１３、２８、…と飛び飛びの値をとっている。これは、第２のフィルタリングにより１番目の目次項目C[１]に対応付ける見出し候補行が絞り込まれた結果である。また、例えばノード５１０をみると、当該ノードには、該ノードの行番号８よりも大きい行番号１５、２３をそれぞれ持つノード５１２、５１４へのエッジのみが引かれている。これは、第１のフィルタリングによりmi > mi+1となるエッジが削除された結果である。このようにフィルタリングによりエッジやノードを削除することにより、計算時間を少なくすることができる。
【００７９】
ところで、本文データDはＯＣＲ処理により取得されるので、ページ抜けの可能性がある。そこで本実施例では図６および図７を参照して以下に説明する２つの方法によりページ抜けに対応する。
【００８０】
ページ抜けに対応する第１の方法は、ページ抜けを示すエッジを追加する方法である。エッジによって隣接関係にある目次項目のペアの対応付けを示すためには、エッジは隣接するノード間でのみ引かなければならない。しかし、間に一定数（便宜上、以下ではこの数値をMAXSKIPという）以下のノードを挟んでエッジを引くことを許容することにより、ページ抜けに対応することが可能となる。これを図６に示すグラフを参照して説明する。
【００８１】
図６は、図５に示すフィルタリング後のグラフ５００において、間に１つのノードを挟んでエッジを引くことを許容してエッジを追加したものである。但し図６では、m1 の列６０８からm3の列６１０までの列を除いて、ノードの行番号とエッジとを省略していることに留意されたい。図６では、m1の列６０８のノードとm3の列６１０のノードとを結合するエッジが複数追加されている。この新たに追加された各エッジは、２番目の目次項目に対応付けるべき見出し候補行がないことを示す。従って、スコアの合計を最大とする経路がこの新たに追加したエッジを含む場合、２番目の目次項目に対応付けるべき見出し候補行を含むページが抜けていたということが示される。なお、新たに追加するエッジに対しても、第１のフィルタリングを適用可能であること、また、バイグラムスコアbを付与することに留意されたい。
【００８２】
ページ抜けに対応する第２の方法は、ページ抜けを示すノードを追加する方法である。このページ抜けを示すノードは、抜けたページの行数を区別するために、全ノードの各々に対し１つ追加する。そして追加したノードには、直後のノードの行番号-0.5を付与する。これは、直後の行と直前の行の間に存在したはずだが、認識できなかった、あるいはページ抜けのために存在しなかったということを示すことになる。また、各ノードのユニグラムスコアとして、ページ抜けに対するペナルティーとして低い、あるいは負のスコアを与える。これは、ページ抜けと判断しづらくするためである。隣接見出し間のフォーマットの類似度は測ることができないので、バイグラムスコアbは0とする。
【００８３】
図７は、図５に示すフィルタリング後のグラフ５００において、全ノードの各々に対してノードを１つ追加したものである。なお、図７のグラフ７００では、追加したノードは黒丸で示している。但し図７では、m1 とm2の列を除いて、ノードの行番号やエッジ、また追加ノードを省略していることに留意されたい。ここで例えばノード７０８は、１２行目と１３行目の間に対応する行があったがそのような行を見つけられなかったことを示す。従って、スコアの合計を最大とする経路がこの新たに追加したノード７０８を含む場合、１番目の目次項目に対応付けるべき見出し候補行を含むページが抜けていたということが示される。なお、新たに追加するノードを結合するエッジに対しても、第１のフィルタリングは適用可能である。
【００８４】
次に図８から図１２を参照して、実施例１に係る目次と見出しの自動対応付け装置３００による処理の流れを説明する。なお、スコア関数Sの最大値の探索は、Viterbiアルゴリズムを利用するものとする。
【００８５】
図８は、自動対応付け装置３００による処理の全体の流れの一例を示すフローチャートである。図９は、図８に示すフローチャートのステップ８０４のDAGのノード作成処理の流れの一例を示すフローチャートである。図１０は、図８に示すフローチャートのステップ８０６のDAGのエッジ作成処理の流れの一例を示すフローチャートである。図１１は、図８に示すフローチャートのステップ８０８のスコア関数Sの最大値探索処理の流れの一例を示すフローチャートである。図１２は、図８に示すフローチャートのステップ８１０のスコア関数Sの最大値を与える対応付けMの出力処理の流れの一例を示すフローチャートである。
【００８６】
まず、図８を参照して目次と見出しの自動対応付けの全体処理の流れを説明する。図８に示す自動対応付けの全体処理はステップ８００から開始し、自動対応付け装置３００は、記憶装置またはネットワークを介して他のコンピュータから、目次項目単位の目次データCと行単位の本文データDを入力する（ステップ８００、ステップ８０２）。続いて自動対応付け装置３００は、入力した目次データCと本文データDとを使用して、図４、図５を参照して説明した、定義５により表されるスコア関数S(C,D,M)の最大値を探索するためのグラフ（以下、DAGという）のノードを作成する（ステップ８０４）。ノード作成処理の詳細は、図９を参照して後述する。
【００８７】
続いて自動対応付け装置３００は、前のステップで作成したDAGのノード情報に基づいてDAGのエッジを作成する（ステップ８０６）。エッジ作成処理の詳細は、図１０を参照して後述する。続いて自動対応付け装置３００は、作成したDAGを使用して、スコア関数S(C,D,M)の最大値を探索する（ステップ８０８）。探索処理の詳細は、図１１を参照して後述する。最後に自動対応付け装置３００は、ステップ８０８で求めたスコア関数S(C,D,M)の最大値を与える対応付けMを出力する。対応付けMの出力処理の詳細は、図１２を参照して後述する。そして処理は終了する。
【００８８】
次に図９を参照して、DAGのノード作成処理の詳細を説明する。ここでは上述した文字列の類似度に基づく第２フィルタリングを採用する。図９に示すDAGのノード作成処理はステップ９００から開始し、自動対応付け装置３００はまずDAGのノード情報を表す２次元配列dagを用意する。２次元配列dagの各要素への値の設定は続く処理において行うが、２次元配列dagの要素rはノードを表す抽象データ型とし、toc(r)番目の目次項目を行番号line(r)の見出し候補行に対応付ける対応付けを示すものとする。但し、関数tocと関数lineは、要素rに対しそれぞれ対応付けの目次項目の番号と見出し候補行の行番号を返す関数とする。また、目次項目のc番目に対し、dag[c]はc番目の目次項目に対応するノードの配列を表すものとする。
【００８９】
２次元配列dagを用意すると続いて自動対応付け装置３００は、２次元配列dag[0]に探索開始地点を示す仮想ノードBOSを追加する（ステップ９０２）。なお、関数tocと関数lineは仮想ノードBOSに対し共に0を返すものとする。続いて自動対応付け装置３００は、ステップ９０４及び該当する場合はステップ９０６の処理を、第１のループ及び第２のループにより繰り返す。第１のループは、変数cを1から目次項目数|C|まで１つずつ増やし繰り返すループである。第２のループは、変数cの値に対し変数dを1から本文の全行数|D|まで１つずつ増やしながら繰り返すループである。
【００９０】
ステップ９０４において、自動対応付け装置３００は、c番目の目次項目C[c]の文字列とd番目の行D[d]の文字列との類似度が許容できる最小の類似度MINSIMより大きいか否かを判定する。類似度の判定は、既に説明した通り編集距離等の既存技術を利用してよい。類似度がMINSIMより大きい場合（ステップ９０４：ＹＥＳ）、自動対応付け装置３００は、dag[c]にc番目の目次項目をd行目に対応付ける対応付け(c,d)を示すノードを追加する（ステップ９０６）。類似度がMINSIM以下の場合（ステップ９０４：ＮＯ）、またはステップ９０６の処理の後、自動対応付け装置３００は、第１及び第２の全てのループを抜け出すまで一連の処理を繰り返す。
【００９１】
上記繰り返し処理が終了すると、自動対応付け装置３００は、２次元配列dag[|D|+1]に、探索終了地点を示す仮想ノードEOSを追加する（ステップ９０８）。なお、関数tocと関数lineは仮想ノードEOSに対し、それぞれ|C|+1、|D|+1を返す。そして処理は終了する。
【００９２】
続いて図１０を参照して、DAGのエッジ作成処理の詳細を説明する。ここでは上述したページ番号の制約に基づく第１フィルタリングを採用する。また、ページ抜けに対応すべく上述した第１の方法、即ち、ページ抜けを示すエッジを追加する方法を採用する。図１０に示すDAGのエッジ作成処理はステップ１０００から開始し、自動対応付け装置３００は、DAGのエッジ情報を表す２次元配列leftを用意する。２次元配列leftの各要素への値の設定は続く処理において行うが、２次元配列dagの各要素nに対し、２次元配列left[n]は、要素nが示すノード（以下、単にノードnという）の列の左隣（仮想ノードBOS側）の列にあるノードであって、ノードnとの間にエッジを引くべきノードの配列を表すものとする。
【００９３】
２次元配列leftを用意すると自動対応付け装置３００は、ステップ１００４及び該当する場合はステップ１００６の処理を、入れ子になった４つのループにより繰り返す。第１のループは、変数cを1から目次項目数|C|まで１つずつ増やし繰り返すループである。第２のループは、各変数cの値に対してdag[c]が示すノードの配列から順に１のノードrを取り出して繰り返すループである。第３のループは、各ノードrに対して変数sを0から許容できる最大のページ抜け数MAXSKIPまで１つずつ増やし繰り返すループである。第４のループは、変数c、変数sのそれぞれの値に対してdag[c-s-1]が示すノードの配列から順に１のノードlを取り出して繰り返すループである。
【００９４】
ステップ１００２において自動対応付け装置３００は、ノードrの行番号line(r)の値がノードlの行番号line(l)の値より大きいか否かを判定する。line(r)＞line(l)の場合（ステップ１００２：ＹＥＳ）、自動対応付け装置３００は、left[r]にノードlを追加する（ステップ１００４）。line(r)≦line(l)の場合（ステップ１００２：ＮＯ）、またはステップ１００６の処理の後、自動対応付け装置３００は、４つのループ全てを抜け出すまで一連の処理を繰り返す。そして処理は終了する。
【００９５】
続いて図１１を参照して、スコア関数Sの最大値探索処理の詳細を説明する。図１１に示すスコア関数Sの最大値探索処理はステップ１１００から開始し、自動対応付け装置３００は、生成したDAGのノード数に等しい要素をそれぞれ有する配列Sと配列Bを用意する。配列Sと配列Bのそれぞれの要素への値の設定は続く処理において行うが、S[n]は、仮想ノードBOSを始点としノードnを終点とする経路のスコアのうち最大のスコアを格納するものとする。ここで、経路のスコアとは該経路に含まれるノード及びエッジにそれぞれ付与されるユニグラムスコアu、バイグラムスコアbの合計をいう。また、B[n]は、S[n]に設定される最大のスコアを与える経路に含まれる最後のエッジの情報（ノードnに至る１つ前のノード情報）を格納するものとする。なお、配列Sの0番目の要素S[0]はnullで初期化しておく。
【００９６】
既に説明したとおり、ノードrに付与されるユニグラムスコアuとは、該ノードrが示す対応付けについてのユニグラムスコアu(toc(r), line(r)) である。また、ノードrとノードlを結合するエッジに付与されるバイグラムスコアbとは、該エッジが示す隣接する目次項目のペアの対応付けについてのバイグラムスコアb（toc(r), toc(l), line(r), line(l))である。各ノード、各エッジにそれぞれ付与されるユニグラムスコアuとバイグラムスコアbは、スコア関数Sの最大値探索処理の前に予め求めておいてもよく、或いは以下のステップ１１０４、１１１０において必要に応じて求めてもよい。
【００９７】
上記のように配列Sを定義すると、求めるべきスコア関数Sの最大値はS[EOS]として求められる。ところで仮想ノードBOSを始点としノードrを終点とする経路の最大スコアS[r]は、ノードrに至る１つ前のノードlについての配列Sの値S[l]と、ノードlとノードrを結合するエッジのバイグラムスコアbとを足した値の最大値（以下では、部分最大値という）に、ノードrのユニグラムスコアuを足したものとして求めることができる。従って、S[EOS]の値を求めるには、仮想ノードBOSから仮想ノードEOSへ向う順序で、DAGのノード各々について配列S及び配列Bの値を求める必要がある。なお配列Bは、詳細は図１２を参照して後述するが、スコア関数Sの最大値を与える経路を特定する際に利用される。
【００９８】
そこで自動対応付け装置３００は、仮想ノードBOSから仮想ノードEOSへ向う順序で、DAGのノード各々について配列Sと配列Bの値を求めるべく、ステップ１１０２からステップ１１１０の処理（但しステップ１００８は該当する場合のみ）を第１ループと第２ループにより繰り返す。第１のループは、変数cを1から目次項目数に1加えた（|C|+1）まで１つずつ増やし繰り返すループである。第２のループは、各変数cの値に対してdag[c]が示すノードの配列から順に１のノードrを取り出して繰り返すループである。
【００９９】
ステップ１１０２において、自動対応付け装置３００は、ノードrについて上記部分最大値を求めるための変数maxを用意しこれを−∞で初期化する。自動対応付け装置３００はまた、変数maxに部分最大値の値が設定される際の最後のエッジ情報を保持しておくための変数bestを用意し、これをnullで初期化する。そして自動対応付け装置は、ノードrについて上記部分最大値を求めるために、続くステップ１１０４からステップ１１０８の処理（但しステップ１１０８の処理は該当する場合のみ）を第３ループにより繰り返す。第３のループは、各ノードrに対してleft[r]が示すノードの配列から順に１のノードlを取り出して繰り返すループである。
【０１００】
ステップ１１０４において、自動対応付け装置３００は、一時変数sにノードlとノードrを結合するエッジに付与されたバイグラムスコアb(toc(l),c,line(l),line(r))とS[l]とを足し合わせた値を設定する。続いて自動対応付け装置３００は、一時変数sが変数maxより大きいか否かを判定する（ステップ１１０６）。s＞maxの場合（ステップ１１０６：ＹＥＳ）、自動対応付け装置３００は、変数maxに一時変数sの値を、変数bestにノードlを設定する（ステップ１１０８）。s≦maxの場合（ステップ１１０６：ＮＯ）、またはステップ１１０８の処理の後、自動対応付け装置３００は、第３のループを抜け出すまで一連の処理を繰り返す。
【０１０１】
第３のループを抜け出すと、続いて自動対応付け装置３００は、S[r]に変数maxとユニグラムスコアu(c, line(r))とを足し合わせた値を設定し、またB[r]に変数bestの値を設定する（ステップ１１１０）。続いて自動対応付け装置３００は、第１のループを抜け出すまで上記一連の処理を繰り返す。そして処理は終了する。
【０１０２】
続いて図１２を参照して、スコア関数Sの最大値を与える対応付けMの出力処理の詳細を説明する。図１１に示すスコア関数Sの最大値探索処理において求められた配列Bの各要素B[n]には、上述したように、配列S[n]に設定される最大のスコアを与える経路に含まれる最後のエッジの情報（ノードnに至る１つ前のノード情報）が格納されている。また、スコア関数Sの最大値はS[EOS]により与えられる。従って、スコア関数Sの最大値を与える対応付けMは、B[EOS] を出発点としてB[BOS]までエッジ情報を順次繋ぎ合わせることにより求められる。そこで処理の開始において、自動対応付け装置３００はまず、定義３として説明した対応付けMの配列を用意する（ステップ１２００）。
【０１０３】
続いて自動対応付け装置３００は、ノードを表す変数nに、探索終点を示す仮想ノードEOSを設定する（ステップ１２０２）。続いて自動対応付け装置３００はnにB[n]を設定する（ステップ１２０４）。続いて自動対応付け装置３００は、現在の変数nの値がBOSに等しいか否かを判定する（ステップ１２０６）。変数nの値がBOSに等しくない場合（ステップ１２０６：ＮＯ）、自動対応付け装置３００はステップ１２０８の処理へ進み、M[toc(n)]にline(n)の値を設定する。その後自動対応付け装置３００はステップ１２０４の処理に戻る。
【０１０４】
一方、変数nの値がBOSに等しい場合（ステップ１２０６：ＹＥＳ）、自動対応付け装置３００はステップ１２１０の処理へ進み、配列Mを出力する。そして処理は終了する。
【実施例２】
【０１０５】
実施例２では、目次は木構造を有するものとする。図１３（ａ）に、木構造を有する目次の例を示す。図１３（ａ）において、目次は矩形内の数字によりその索引部分のみが示されている。また、図中矢印は目次項目の親子関係を示し、矩形下に表示された１段目の数字は目次項目番号を、２段目の数字はルートの階層レベルを０とした階層のレベルを示している。矢印の先が同一の兄弟関係にある目次項目の任意のペア（例えば、「1.1」と「1.2」）は、階層のレベルが同一でありフォーマットも共通している。一方、矢印元と矢印先という親子関係にある目次項目の任意ペア（例えば、「1」と「1.1」）は、階層のレベルが一段階異なりフォーマットも異なっている。
【０１０６】
このように目次の木構造において兄弟関係にある目次項目のペアにそれぞれ対応付けられる見出しのフォーマットは同一と考えられる。一方、目次の木構造において親子関係にある目次項目のペアにそれぞれ対応付けられる見出しのフォーマットは同一ではなく、例えばフォントサイズや章番号等、大小関係があると考えられる。従って目次が木構造を有する場合、バイグラムスコアbを求めるべき目次項目のペアは、目次の木構造において同一階層で隣り合う兄弟関係にある目次項目のペア（以下、兄弟関係にある隣接目次項目ペアという）であり、共通度の評価では共通度が高いほど高い評価となる。但し、共通度の評価を、共通度が低いほど高い評価を行うようにすれば、親子関係にある目次項目のペアを選択することも可能である。なお、目次の木構造のデータは、一例としてその階層レベルを示す数値を目次項目順に並べたリストとして記憶して利用してよい。
【０１０７】
そこで実施例２においては、兄弟関係にある隣接目次項目ペアに対しては、バイグラムスコアbとして、目次項目ペアのそれぞれの見出し候補行への対応付けの共通度が高いほど高いスコア値を返す兄弟バイグラムスコアb1を採用する。また、親子関係にある目次項目ペアに対しては、バイグラムスコアbとして、目次項目ペアのそれぞれの見出し候補行への対応付けの共通度が低いほど高いスコア値を返す親子バイグラムスコアb2を採用する。なお、バイグラムスコアbとして兄弟バイグラムスコアb1または親子バイグラムスコアb2いずれか一方のみを採用することも可能であることはいうまでもない。
【０１０８】
従って、実施例２において定義４は次のように書き直される。
S(C,D,M) =Σi u(i,mi,C,D)+ Σib1(i, mi, msib(i), C,D) + Σib2(i, mi, mpar(i), C,D)―（定義６）
ここで、sib(i)は、i番目の目次項目に同一階層において隣接する１つ前の兄ノードの目次項目番号を返す関数である。図１３（ａ）の目次の例では、例えばsib (4)=3、sib (11)=5である。また、par(i)は、i番目の目次項目の親ノードの目次項目番号を返す関数である。図１３（ａ）の目次の例では、例えばpar (4)=1、cpar (5)=0である。上記２つの関数に加えて、i番目の目次項目の最後の子ノードの目次項目番号を返す関数chd(i)を導入する。図１３（ａ）の目次の例では、例えばchd(0)=11、chd(1)=4である。新たに導入した３つの関数の擬似コードを以下に記載しておく。
【０１０９】
par(n): // nより前で、階層がnより小さい最初の項目
for i in {n-1, n-2, ..., 0}:
ifL[i] < L[n]:
returni
return-1
sib(n): // nより前、par(n)よりあとで、階層がnと同じ最初の項目
for i in {n-1, n-2, ..., par(n) + 1}:
ifL[i] == L[n]:
returni
return-1
chd(n):// nより後ろ、nと同じ階層の項目より前で、階層がnより1つ大きい最後の項目
c =-1
for i in {n+1, ..., |L|}:
ifL[i] == L[n]:
returnc
elseif L[i] == L[n]+1:
c = i
return c
【０１１０】
また、定義６の右辺において、第１項のユニグラムスコアuについての和は、全目次項目についての和である。第２項の兄弟バイグラムスコアb1についての和は、兄弟関係にある隣接目次項目のペア全てについての和である。第３項の親子バイグラムスコアb2についての和は、親子関係にある目次項目のペア全てについての和である。各スコアの設計方法は、ユニグラムスコアuと兄弟バイグラムスコアb1については、それぞれ実施例１に関して説明したユニグラムスコアu、バイグラムスコアbと同じであるためここでは説明を省略する。そこで以下では、親子バイグラムスコアb2についてその設計方法を説明する。その後で、定義６で示されるスコア関数Sの最大値の探索方法を説明する。
【０１１１】
親子バイグラムスコアb2(i, mi, mpar(i), C,D)は、一の目次項目（i番目の目次項目 (C[i]））と該一の目次項目の親となる目次項目（par(i)番目の目次項目 (C[par(i)]））のペア、即ち親子関係にある目次項目ペアの見出し候補行（mi行目（D[mi]）とmpar(i)行目（D[mpar(i)]））への対応付けの尤もらしさを、親子関係にある目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価したスコアである。なお上述したように、親子バイグラムスコアb2の共通度の評価は、共通度が低いほど高い評価となる。
【０１１２】
共通度に基づく評価の第１の例は、フォーマットの共通度に基づく評価である。即ち、子の目次項目C[i]を対応付けるD[mi]と、親の目次項目C[par(i)]を対応付けるD[mpar(i)]のフォーマットの共通度が低い場合に高いスコアを返すように親子バイグラムスコアb2を設計する。より具体的には、子の目次項目C[i]に対応するD[mi]のフォントサイズと、親の目次項目C[par(i)]に対応するD[mpar(i)]のフォントサイズとの間に大小関係がある場合に高いスコアを返すように親子バイグラムスコアb2を設計する。これは一般に親見出しの方が子見出しよりもフォントサイズが大きいとの知識に基づくものである。
【０１１３】
上記フォントサイズに代えてまたは加えて、子の目次項目C[i]に対応するD[mi]の索引部分が、親の目次項目C[par(i)]に対応するD[mpar(i)]の索引部分とフォーマットが異なる場合に高いスコアを返すように親子バイグラムスコアb2を設計してもよい。索引部分のフォーマットが異なる例を以下に挙げる。親の索引部分―子の索引部分とすると、第１部―第１章、第１章―１．１、１．１―１．１．１、１―（１）、（１）−（ａ）等があるがこれに限定されない。索引部分のフォーマットの判定は、一例として事前に索引部分のフォーマットの正規表現を用意してこれとマッチングさせ、一致したフォーマットが異なれば互いに異なるフォーマットであると判定してよい。例えば「第１章」や「１．１」に対してはそれぞれ次のような正規表現を用意できる。
/第([0-9]+)章/
/([0-9+])\.([0-9]+)/
バリエーションとして、「第二章」のように漢数字であるならば、
/第([一二三四五六七八九]+)章/
また、「１−１」のように「．」でなく「−」であるならば
/([0-9+])−([0-9]+)/
となる。他のフォーマットについても同様にして正規表現を用意できる。
【０１１４】
共通度に基づく評価の第２の例は、目次におけるページ番号と実際のページ番号、即ち、最初のページからの通し番号との差分の共通度に基づく評価である。但し第２の例については、共通度が高いほど高いスコアを返すように親子バイグラムスコアb2を設計する。即ち、C[i]に含まれるページ番号とC[i]に対応付けるD[mi]を含むページの通し番号との差分と、C[par(i)]に含まれるページ番号とC[par(i)]を対応付けるD[mpar(i)]を含むページの通し番号との差分との共通度が高い場合に高いスコアを返すように親子バイグラムスコアb2を設計する。なお、差分の共通度の高さは、一例として差分が同一である場合に共通度が高いとしてよい。
【０１１５】
親子バイグラムスコアb2は、上述した３つの共通度に基づく評価（スコア）のうち任意の数の評価（スコア）を、重み付けをしつつ組み合わせて評価するものであってもよい。複数の評価（スコア）を足し合わせて評価する場合、対応付けのいくつかについてフォントサイズやページ情報を取得できないため全部の評価(スコア）を取得できないとしても、いずれか１つの評価（スコア）を求めることができれば問題はない。また、重み付けは正解データから各スコアの重みを自動学習してもよい。
【０１１６】
次に定義６により表されるスコア関数Sの最大値の算出方法を説明する。定義６により表されるスコア関数Sを最大にする対応付けMの系列は、2nd order Eisnerアルゴリズムを応用して、時間計算量O(|C||D|3)で求めることができる。従って、本文データDの要素、即ち見出し候補行をフィルタリングすることによって、実際の計算時間は更に少なくすることが可能である。フィルタリングは、一例として、実施例１に関して説明した目次項目と該目次項目に対応付ける見出し候補行の文字列の類似度に基づくフィルタリングを適用可能である。以下、2nd order Eisnerアルゴリズムを応用したスコア関数Sの最大値の探索方法を説明する。
【０１１７】
まず、説明を容易にするため、ユニグラムスコアuとバイグラムスコアbの表記を次のように単純化する。なお、以下ではi、l、rはそれぞれ文書中の位置、即ち行番号を示す整数とする。ユニグラムスコアu(c,i)は、c番目の目次項目をi行目の見出し候補行に対応付けたときのユニグラムスコアuを表す。兄弟バググラムスコアb1(c, sib(c), i, l) は、c番目の目次項目をi行目の見出し候補行に、かつ、兄弟関係にあるsib(c)番目の目次項目をl行目の見出し候補行に対応付けたときの兄弟バググラムスコアb1を表す。親子バググラムスコアb2(c,par(c), i, l) は、c番目の目次項目をi行目の見出し候補行に、かつ、親子関係にあるpar(c)番目の目次項目をl行目の見出し候補行に対応付けたときの親子バググラムスコアb2を表す。
【０１１８】
次に新たに２種類の再帰関数を導入する。再帰関数comp(c, l, r)は、c番目の目次項目をルートとする目次のサブツリーが、行番号が{l,…, r-1}の文書中の範囲に対応付けられるときの最大のスコアを返す関数とする。但し、c番目の目次項目はl行目に対応するものとする。また、再帰関数incomp(c, l, r)は、c番目の目次項目の兄に該当する目次項目をルートとする目次のサブツリーを全兄の目次項目について集めた集合が、行番号が{l+1,…, r-1}の文書中の範囲に対応付けられるときの最大のスコアを返す関数とする。但し、c番目の目次項目はr行目に、また、par(c)番目の目次項目はl行目に対応するものとする。
【０１１９】
すると再帰関数comp(c, l, r)とincomp(c, l, r)は、次の２つの再帰式により計算できる。但し、記号maxi{G}は、Gの値がiに依存する場合において最大のGの値を示すものとする。
再帰式１：
comp(c, l, r) = maxi{ incomp(chd(c), l, i) + comp(chd(c), i, r) + u(chd(c), i) + b2(c, chd(c), l, i)}
再帰式２：
incomp(c, l, r) = maxi{incomp(sib(c), l, i) + comp(sib(c),i, r) + u(sib(c), i) + b2(par(c),sib(c), l, i) + b1(sib(c), c, i,r) } ―（再帰式２）
【０１２０】
再帰式１は、chd(c)番目の目次項目がi行目に対応づけられると仮定して、記号maxiを利用してcomp(c, l, r)を書き換えたものである。即ち、上記仮定において、chd(c)番目の目次項目の兄に該当する目次項目をルートとする目次のサブツリーを全兄の目次項目について集めた集合は、行番号が{l+1,…, i-1}の範囲に対応付けられる。また、chd(c)番目の目次項目をルートとする目次のサブツリーは、行番号が{i,…, r-1}の範囲に対応付けられる。なお、comp(c, l, r)の定義から、c番目の目次項目はl行目に対応付けられることに留意されたい。
【０１２１】
また、再帰式２は、sib(c) 番目の目次項目がi行目に対応づけられると仮定して、記号maxiを利用してincomp(c, l, r)を書き換えたものである。即ち、上記仮定において、sib(c)番目の目次項目の兄に該当する目次項目をルートとする目次のサブツリーを全兄の目次項目について集めた集合は、行番号が{l+1,…, i-1}の範囲に対応付けられる。また、sib(c)番目の目次項目をルートとする目次のサブツリーは、行番号が{i,…, r-1}の範囲に対応付けられる。なお、incomp(c,l, r)の定義から、c番目の目次項目はr行目に、また、par(c)番目の目次項目はl行目に対応対応付けられることに留意されたい。
【０１２２】
スコア関数Sの最大値の探索は、再帰関数comp(c, l, r)において目次のツリー全体の最大スコアを求めることに等しい。即ち、スコア関数Sの最大値は、上記再帰関数を利用して、comp(0, 0, |D|+1)として求められる。そして、スコア関数Sを最大とする目次と本文見出しの対応付けMは、comp(0, 0, |D|+1)を求める際に再帰的に呼び出されるcomp(c,l, r)の各々の計算において最大値を与えるchd(c)番目の目次項目についての対応付けと、同じく再帰的に呼び出されるincomp(c,l, r)の各々の計算において最大値を与えるsib(c) 番目の目次項目についての対応付けの集合として求められる。
【０１２３】
なお、本実施例では、上記対応付けの集合を対応付けMとして出力するために更に２つの再帰関数を用意する。第１の再帰関数getcomp(c,l, r)は、comp(c, l, r)の計算において最大値を与えるchd(c)番目の目次項目の対応付けをM[chd(c)]に設定した後、後述する第２の再帰関数と自分自身とを呼び出す再帰関数である。第２の再帰関数getincomp(c,l, r)は、incomp(c,l, r)の計算において最大値を与えるsib(c)番目の目次項目の対応付けをM[sib (c)]に設定した後、自分自身と第１の再帰関数とを呼び出す再帰関数である。これら２つの再帰関数を計算方法の詳細は、図１８及び図１９に示すフローチャートを参照して後述する。
【０１２４】
次に図１４から１９を参照して、実施例２に係る目次と見出しの自動対応付け装置３００による処理の流れを説明する。図１４は、自動対応付け装置３００による処理の全体の流れの一例を示すフローチャートである。図１５は、図１４に示すフローチャートのステップ１４０４の見出し候補行の決定処理の流れの一例を示すフローチャートである。図１６は、再帰関数comp(c, l, r)の計算処理の流れの一例を示すフローチャートである。図１７は、再帰関数incomp(c, l, r)の計算処理の流れの一例を示すフローチャートである。図１８は、再帰関数getcomp(c, l, r)処理の流れの一例を示すフローチャートである。図１９は、再帰関数getincomp(c, l, r)処理の流れの一例を示すフローチャートである。
【０１２５】
まず、図１４を参照して目次と見出しの自動対応付けの全体処理の流れを説明する。図１４に示す自動対応付けの全体処理はステップ１４００から開始し、自動対応付け装置３００は、記憶装置からまたはネットワークを介して他のコンピュータから、目次項目単位の目次データCと行単位の本文データDを入力する（ステップ１４００、ステップ１４０２）。続いて自動対応付け装置３００は、入力した目次データCと本文データDとを使用して、目次項目ごと、対応付けを検討すべき見出し候補行を決定する（ステップ１４０４）。見出し候補行決定処理の詳細は、図１５を参照して後述する。
【０１２６】
続いて自動対応付け装置３００は、整数の３つ組みを取るハッシュテーブルcmax、imax、cbest、ibestを用意し、それぞれ−∞で初期化する（ステップ１４０６）。ここでcmaxは、(c, l, r)をキーとして再帰関数comp(c,l, r)の最大値を返すハッシュテーブルである。imaxは、(c, l, r)をキーとして再帰関数incomp(c, l, r)の最大値を返すハッシュテーブルである。cbestは、(c, l, r)をキーとして再帰関数comp(c,l, r)の計算において最大値を与えたchd(c)番目の目次項目の対応付け結果を返すハッシュテーブルである。ibestは、(c, l, r)をキーとして再帰関数incomp(c, l, r)の計算において最大値を与えたsib(c)番目の目次項目の対応付け結果を返すハッシュテーブルである。
【０１２７】
続いて自動対応付け装置３００は、comp(0, 0, | D|+1)を呼び出して、スコア関数Ｓの最大値を求める（ステップ１４０８）。comp(0, 0, | D|+1)の呼び出し処理の詳細は、再帰関数comp(c, l, r)の計算処理の詳細に代えて図１６を参照して後述する。続いて自動対応付け装置３００は、対応付けMの配列mを用意する（ステップ１４１０）。続いて自動対応付け装置３００は、getcomp(0,0,|D|+1)を呼び出してスコア関数Ｓを最大にする対応付けを配列mに設定する（ステップ１４１２）。getcomp(0,0,|D|+1)の呼び出し処理の詳細は、再帰関数getcomp (c, l, r)の計算処理の詳細に代えて図１８を参照して後述する。最後に自動対応付け装置３００は、配列mを求めるべき目次と見出しの対応付けとして出力する（ステップ１４１４）。そして処理は終了する。
【０１２８】
次に図１５を参照して、見出し候補行の決定処理の詳細を説明する。ここでは実施例１に関して説明した文字列の類似度に基づく第２フィルタリングを利用して見出し候補行の絞り込みを行う。図１５に示す見出し候補決定処理はステップ１５００から開始し、自動対応付け装置３００はまず２次元配列candsを用意する。２次元配列candsの各要素への値の設定は続く処理において行うが、目次項目のc番目に対しcands[c]は、c番目の目次項目との対応付けを検討すべき見出し候補行の配列を表すものとする。
【０１２９】
２次元配列candsを用意すると続いて自動対応付け装置３００は、２次元配列cands [0]に0を設定する（ステップ１５０２）。続いて自動対応付け装置３００は、ステップ１５０４及び該当する場合はステップ１５０６の処理を、第１のループ及び第２のループにより繰り返す。第１のループは、変数cを1から目次項目数|C|まで１つずつ増やし繰り返すループである。第２のループは、変数cの値に対し変数dを1から本文の全行数|D|まで１つずつ増やしながら繰り返すループである。
【０１３０】
ステップ１５０４において、自動対応付け装置３００は、c番目の目次項目C[c]の文字列とd番目の行D[d]の文字列との類似度が許容できる最小の類似度MINSIMより大きいか否かを判定する。類似度の判定は、既に説明した通り、編集距離等の既存技術を利用してよい。類似度がMINSIMより大きい場合（ステップ１５０４：ＹＥＳ）、自動対応付け装置３００は、cands[c]に見出し候補行としてd番目の行を追加する（ステップ１５０６）。類似度がMINSIM以下の場合（ステップ１５０４：ＮＯ）、またはステップ１５０６の処理の後、自動対応付け装置３００は、第１及び第２の全てのループを抜け出すまで上記一連の処理を繰り返す。そして処理は終了する。
【０１３１】
次に図１６を参照して、再帰関数comp(c, l, r)の計算処理の詳細を説明する。図１６に示す再帰関数comp(c, l, r)の計算処理はステップ１６００から開始し、自動対応付け装置３００は、cmax(c, l, r)が−∞に等しいか否かを判定する。これはcompが再帰関数であることから、同じ引数について対してcompが既に計算済みであるならばその結果を再利用するためである。cmax(c, l, r)≠-∞である場合（ステップ１６００：ＮＯ）、即ち、現在の引数に対しcompの値が既に算出されている場合、自動対応付け装置３００はステップ１６２４へ進み、変数maxにcmax[c, l, r]の値を設定する。一方、cmax(c, l, r)の値が-∞である場合（ステップ１６００：ＹＥＳ）、即ち、現在の引数に対して未だcompの値が算出されていない場合、自動対応付け装置３００はchd(c)の値を変数c’に設定する（ステップ１６０２）。
【０１３２】
続いて自動対応付け装置３００は変数c’の値がnullであるか否かを判定する（ステップ１６０４）。変数c’の値がnullの場合（ステップ１６０４：ＹＥＳ）、即ち、c番目の目次項目に対して子の関係にある目次項目が存在しない場合、自動対応付け装置３００はステップ１６２２へ進み、変数maxに0を設定する。一方、変数c’の値がnullでない場合（ステップ１６０４：ＮＯ）、自動対応付け装置３００は、上述した再帰式１の右辺の最大値を求めるための変数maxを用意し、これを−∞で初期化する（ステップ１６０６）。自動対応付け装置３００はまた、上記右辺の最大値を与えるchd(c)番目の目次項目の対応付けを保持しておくための変数bestを用意し、これを0で初期化する。
【０１３３】
続いて自動対応付け装置３００は、再帰式１の右辺の最大値を求めるために、続くステップ１６０８からステップ１６１４までの処理をループにより繰り返す。ここでループは、c’番目の目次項目についての見出し候補行の配列から順に１の見出し候補行（i番目の行）を取り出して繰り返すループである。ステップ１６０８において、自動対応付け装置３００は、l < i < r であるか否かを判定する。これは、c’番目の目次項目に対応する見出し候補行（i番目の行）が、行番号が{l+1, …, r-1}の範囲にあることを確認するためである。l < i < rである場合（ステップ１６０８：ＹＥＳ）、自動対応付け装置３００は変数sを用意して、これにincomp(c’, l, i) + comp(c’, i,r) + u(c’, i) + b2(c, c’, l, i)の値を設定する（ステップ１６１０）。なお、再帰関数incompの計算処理の詳細は図１７を参照して後述する。
【０１３４】
続いて自動対応付け装置３００は、max< sであるか否かを判定する（ステップ１６１２）。max< sである場合（ステップ１６１２：ＹＥＳ）、自動対応付け装置３００は、変数maxに変数sの値を、また、変数bestに変数iの値を設定する（ステップ１６１４）。ステップ１６０８においてl < i < r でない場合、また、ステップ１６１２においてmax < sでない場合、またはステップ１６１４の後、自動対応付け装置３００は上記ループを抜け出すまで一連の処理を繰り返す。
【０１３５】
ループを抜けると続いて自動対応付け装置３００は、変数maxの値をハッシュテーブルcmax[c,l, r]の値として、また、変数bestの値をハッシュテーブルcbest[c,l, r]の値として設定する（ステップ１６１６、ステップ１６１８）。ステップ１６２２、ステップ１６２４、またはステップ１６１８から、自動対応付け装置３００はステップ１６２０へ進み、変数maxの値を返す。そして処理は終了する。
【０１３６】
次に図１７を参照して、再帰関数incomp(c, l, r)の計算処理の詳細を説明する。図１７に示す再帰関数incomp(c, l, r)の計算処理はステップ１７００から開始し、自動対応付け装置３００は、imax(c, l, r)が−∞に等しいか否かを判定する。これはincompが再帰関数であることから、同じ引数に対してincompが既に計算済みであるならばその結果を再利用するためである。imax(c, l, r)≠-∞である場合（ステップ１７００：ＮＯ）、即ち、現在の引数に対しincompの値が既に算出されている場合、自動対応付け装置３００はステップ１７２４へ進み、変数maxにimax[c, l, r]の値を設定する。一方、imax(c, l, r)の値が-∞である場合（ステップ１６００：ＹＥＳ）、即ち、現在の引数に対して未だincompの値が算出されていない場合、自動対応付け装置３００はsib(c)の値を変数c’に設定する（ステップ１７０２）。
【０１３７】
続いて自動対応付け装置３００は変数c’の値がnullであるか否かを判定する（ステップ１７０４）。変数c’の値がnullの場合（ステップ１７０４：ＹＥＳ）、即ち、c番目の目次項目に対して兄の関係にある目次項目が存在しない場合、自動対応付け装置３００はステップ１７２２へ進み、変数maxに0を設定する。一方、変数c’の値がnullでない場合（ステップ１７０４：ＮＯ）、自動対応付け装置３００は、上述した再帰式２の右辺の最大値を求めるための変数maxを用意し、これを−∞で初期化する（ステップ１７０６）。自動対応付け装置３００はまた、上記右辺の最大値を与えるsib(c)番目の目次項目の対応付けを保持しておくための変数bestを用意し、これを0で初期化する。
【０１３８】
続いて自動対応付け装置３００は、再帰式２の右辺の最大値を求めるために、続くステップ１７０８からステップ１７１４までの処理をループにより繰り返す。ここでループは、c’番目の目次項目についての見出し候補行の配列から順に１の見出し候補行（i番目の行）を取り出して繰り返すループである。ステップ１７０８において、自動対応付け装置３００は、l < i < r であるか否かを判定する。これは、c’番目の目次項目に対応する見出し候補行（i番目の行）が、行番号が{l+1, …, r-1}の範囲にあることを確認するためである。l < i < rである場合（ステップ１７０８：ＹＥＳ）、自動対応付け装置３００は変数sを用意して、これにincomp(c’, l, i) + comp(c’, i,r) + u(c’, i) + b2(par(c’), c’, l, i) + b1(c’ c, i, r)の値を設定する（ステップ１７１０）。
【０１３９】
続いて自動対応付け装置３００は、max< sであるか否かを判定する（ステップ１７１２）。max< sである場合（ステップ１７１２：ＹＥＳ）、自動対応付け装置３００は、変数maxに変数sの値を、また、変数bestに変数iの値を設定する（ステップ１７１４）。ステップ１７０８においてl < i < r でない場合、また、ステップ１６１２においてmax < sでない場合、またはステップ１６１４の後、自動対応付け装置３００は上記ループを抜け出すまで一連の処理を繰り返す。
【０１４０】
ループを抜けると続いて自動対応付け装置３００は、変数maxの値をハッシュ関数imax[c, l, r]の値として、また、変数bestの値をハッシュ関数ibest[c, l, r]の値として設定する（ステップ１７１６、ステップ１７１８）。ステップ１７２２、ステップ１７２４、またはステップ１７１８から、自動対応付け装置３００はステップ１７２０へ進み、変数maxの値を返す。そして処理は終了する。
【０１４１】
次に、再帰関数getcomp、getincompの計算処理の流れを説明する前に、図１３（ｂ）を参照して対応付けMの配列の復元順序を説明する。なお、図１３（ｂ）に示す復元順序は、１３（ａ）に示す目次を例にしており、矩形で示す目次項目の下の数字は復元順序を示している。数字を見ると分かるように、復元順序は、階層レベルの低い順、同階層であるならば右優先である。
【０１４２】
次に図１８を参照して、再帰関数getcomp(c, l, r)の計算処理の詳細を説明する。図１８に示す再帰関数getcomp(c, l, r)の計算処理はステップ１８００から開始し、自動対応付け装置３００は、chd(c)の値を変数c’に設定し、変数c’の値がnullであるか否かを判定する（ステップ１８０２）。変数c’の値がnullの場合（ステップ１８０４：ＹＥＳ）、即ち、c番目の目次項目に対して子の関係にある目次項目が存在しない場合処理は終了する。
【０１４３】
一方、変数c’の値がnullでない場合（ステップ１８０２：ＮＯ）、自動対応付け装置３００は、ハッシュ関数cbest[c, l, r]の値を変数iに設定する（ステップ１８０４）。続いて自動対応付け装置３００は、変数iの値を対応付けMの配列要素m[c’]に設定する（ステップ１８０６）。続いて、自動対応付け装置３００は、再帰関数getincomp(c’, l, i)を呼び出す。再帰関数getincompの計算処理の詳細は図１９を参照して後述する。続いて自動対応付け装置３００は、getcomp(c’, i, r)を呼び出す。そして処理は終了する。
【０１４４】
次に図１９を参照して、再帰関数getincomp(c, l, r)の計算処理の詳細を説明する。図１８に示す再帰関数getincomp(c, l, r)の計算処理はステップ１９００から開始し、自動対応付け装置３００は、sib(c)の値を変数c’に設定し、変数c’の値がnullであるか否かを判定する（ステップ１９０２）。変数c’の値がnullの場合（ステップ１９０４：ＹＥＳ）、即ち、c番目の目次項目に対して兄の関係にある目次項目が存在しない場合処理は終了する。
【０１４５】
一方、変数c’の値がnullでない場合（ステップ１９０２：ＮＯ）、自動対応付け装置３００は、ハッシュ関数ibest[c, l, r]の値を変数iに設定する（ステップ１９０４）。続いて自動対応付け装置３００は、変数iの値を対応付けMの配列要素m[c’]に設定する（ステップ１９０６）。続いて、自動対応付け装置３００は、再帰関数getincomp(c’, l, i)を呼び出す。続いて自動対応付け装置３００は、getcomp(c’, i, r)を呼び出す。そして処理は終了する。
【０１４６】
図２０は、本実施形態に係るコンピュータ５０のハードウェア構成の一例を示した図である。コンピュータ５０は、バス２に接続されたメインＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、及びＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。
【０１４７】
フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ１に命令を与え、本願発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、上記説明した数々の記憶装置には、コンピュータ５０にインストールされ、コンピュータ５０を自動対応付け装置３００として機能させる目次および見出しの自動対応付けプログラムや目次データC、本文データD等のデータ、更には、自動対応付けの結果である出力データMを記録することができる。
【０１４８】
上記自動対応付けプログラムは、入力モジュールと、探索モジュールと、出力モジュールとを含む。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、入力部３０２、探索部３０４と、出力部３０６としてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。
【０１４９】
コンピュータ５０は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。コンピュータ５０は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。コンピュータ５０は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。コンピュータ５０は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【０１５０】
以上の説明により、本実施形態に係るコンピュータ５０は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本願発明の必須構成要素となるわけではない。
【０１５１】
以上、実施形態を用いて本願発明の説明をしたが、本願発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。従って、そのような変更又は改良を加えた形態も当然に本願発明の技術的範囲に含まれる。
【０１５２】
なお、特許請求の範囲、明細書、及び図面中において示した装置、システム、プログラム、及び方法における動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り任意の順序で実現しうることに留意すべきである。また、前の処理の出力を後の処理で用いる場合でも、前の処理と後の処理の間に他の処理が入ることは可能である場合があること、又は間に他の処理が入るように記載されていても前の処理を後の処理の直前に行うよう変更することも可能である場合があることも留意されたい。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」、「続いて、」等を用いて説明したとしても、この順で実施することが必須であることを必ずしも意味するとは限らない。
【技術分野】
【０００１】
本願発明は、電子化された書籍において、目次と本文中の見出し間の対応付けをコンピュータの演算処理により行う技術に関する。
【背景技術】
【０００２】
近年、国内外で書籍の電子化の勢いが増してきており、多くの書籍が電子化されつつある。書籍等の文書の電子化においては、光学式文字読取装置（Optical Character Reader :ＯＣＲ)によってテキスト・データを取得した後にこれに適切な構造情報を付与し、電子化のメリットを最大限に享受することが望まれる。電子化文書の価値を増加させる構造情報の１つとして、目次と本文中の見出し間の対応関係がある。目次と見出し間の対応関係の情報の付与によって、例えば、目次から本文中の対応する見出しへのリンクを貼ったり、本文中の文章の読み上げ順序を決定したり、また、検索時において本文よりも見出しを重視した重み付けを行うことが可能となる。
【０００３】
目次と本文中の見出し間の対応関係の情報は人手により付与することは不可能ではない。しかし、図書館等多くの書籍を所有する機関における電子化を考えると、人手による付与は現実的ではなく、コンピュータを利用した構造情報の自動付与が望まれる。
【０００４】
目次と本文中の見出しを自動で対応付ける従来技術として、特許文献１が存在する。特許文献１は、目次を認識するための条件として、各目次内項目と、その項目に結び付けられリンクしている他のテキスト断片例えば見出しとが、テキスト内容的に同様のものでなければならない、というテキスト類似度条件を開示する。しかしながら、テキスト類似度条件だけでは、例えば、章見出し又はセクション見出しと同じ文章が本文に含まれている場合、目次内項目にリンクさせるべき見出しがそれらの文章のうちどれなのかが判然としないという問題がある。
【０００５】
そこで特許文献１は、基準書式との照合によってテキスト断片を選択的に候補から除外した上で、目次内項目らしきテキスト断片、そのリンク先らしきテキスト断片又はその双方を認識する技術を開示する。より具体的には、特許文献１は、索引部分書式に合致しないテキスト断片や、見出しであることを示すキーワードを含んでいないテキスト断片、小文字の英文字を含むテキスト断片を見出し候補から除外する技法を開示する。
【０００６】
また、特許文献１は、各テキスト断片に関連付けられているページ内位置に基づき候補を絞った上で、目次内項目のリンク先らしきテキスト断片を認識する技術を開示する。ページ内位置に基づく個数削減条件としては、そのページの先頭から所定距離内にあるテキスト断片だけを見出し候補にするという条件、そのページの最左端カラムを表すカラム番号に関連付けられているテキスト断片だけを見出し候補にするという条件が開示されている。
【０００７】
また、特許文献２〜６は、タイトルを抽出することを目的とし、タイトル固有の特徴をポイントとして用いることにより、ポイント数の多い文字列領域をタイトルとして自動抽出する技術を開示する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００７−２２６７９２号公報
【特許文献２】特開２０００−１４８７８８号公報
【特許文献３】特開平１０−２６０９９３号公報
【特許文献４】特開２００１−３４７６３号公報
【特許文献５】特開２００３−１６０７６号公報
【特許文献６】特開２００３−５８５５６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１の技術によって、基準書式との照合によってテキスト断片を選択的に候補から除外するとしても、処理対象の文書が用いると予測される基準書式を事前に全て網羅して設定することは不可能である。処理対象の文書ごと人手で基準書式を設定すればこのような問題は解決できるが、それでは手間がかかりすぎる。
【００１０】
ページ内位置に基づく個数削減条件についても同様である。即ち、文書が採用するレイアウトに一定の傾向がみられるとしても具体的な位置条件は文書ごとに異なる。そのため位置条件を事前に設定しようとすると、全ての文書に適用可能な緩い条件を設定せざるをえなくなり、候補の絞込みを十分に行うことができなくなる。
【００１１】
また、位置情報に関しては、目次に含まれるページ情報を利用して見出し候補を当該ページ内に含まれるものに限定することも考えられる。しかしながら、前書き等の本文以外のページの存在のために、目次におけるページ番号と実際のページ番号、即ち通し番号とにずれが生じることも多い。そのためページ情報を利用する場合でも事前に人手により差分情報を付与することが必要となる。
【００１２】
なお、特許文献２〜６は、タイトル抽出のために利用可能なタイトル固有の特徴を開示する背景技術として挙げたものであり、目次と見出しの対応付けに関する技術を開示するものではない。
【００１３】
この発明は、上記の問題点を解決するためになされたものであって、見出し候補の絞り込み条件を事前に網羅的に設定したり文書ごとに人手により設定したりする必要なしに、電子化された書籍において、目次と本文中の見出し間の適切な対応付けをコンピュータの演算処理により行うことのできる技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成する本願発明は、次のような、文書の目次内の目次項目を前記文書の本文中の見出し行に対応付ける、コンピュータの演算処理による目次と見出しの対応付け方法によって実現される。そのような目次と見出しの対応付け方法は、前記コンピュータが、前記文書の目次項目単位の目次データCを受け取るステップと、前記コンピュータが、前記文書の行単位の本文データDを受け取るステップと、前記コンピュータが、前記目次データC内の全目次項目の前記本文データD内の見出し候補としての行である見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索するステップと、前記コンピュータが、前記スコア関数Sを最大にする前記対応付けMを出力するステップとを含む。ここで、前記スコア関数Sは、各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアuを全目次項目について足し合わせた第１の和と、一の目次項目と他の目次項目のペアである目次項目ペアの見出し候補行への対応付けの尤もらしさを前記目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価するバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求められる。
【００１５】
好ましくは、前記目次はフラット構造を有し、前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列との類似度に基づき求められる。また、前記バイグラムスコアbは、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度に基づき求められる。
【００１６】
より好ましくは、前記バイグラムスコアbは更に、前記目次項目ペアのそれぞれの対応付けにおける、目次項目に含まれるページ番号と該目次項目に対応付ける見出し候補行が含まれるページの通し番号との差の共通度に基づいて求められる。
【００１７】
また好ましくは、前記一の目次項目と前記他の目次項目とは隣接関係にある。
【００１８】
より好ましくは、前記目次は木構造を有し、前記一の目次項目と隣接関係にある前記他の目次項目を、前記目次の木構造において前記一の目次項目と同一階層において隣り合う兄弟関係にある目次項目に限定する。
【００１９】
更に好ましくは、前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列との類似度に基づき求められ、前記バイグラムスコアbは、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度に基づき求められる。
【００２０】
更により好ましくは、前記フォーマットの共通度は、前記目次項目ペアにそれぞれ対応付ける見出し候補行のフォントサイズの共通度と、前記目次項目ペアにそれぞれ対応付ける見出し候補行の最初の文字又は最初の文字と最後の文字との共通度と、前記目次項目ペアにそれぞれ対応付ける見出し候補行の文字列のうち、対応付ける目次項目の文字列に類似する部分である類似文字列の前後の所定数の文字の共通度のうちの少なくとも１つの共通度である。
【００２１】
また、更に好ましくは、前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列の類似度に基づき求められ、前記バイグラムスコアbは、前記目次項目ペアのそれぞれの対応付けにおける、目次項目に含まれるページ番号と該目次項目に対応付ける見出し候補行が含まれるページの通し番号との差の共通度に基づいて求められる。
【００２２】
更により好ましくは、前記バイグラムスコアbは、前記一の目次項目に対応付ける一の見出し候補行と、前記他の目次項目に対応付ける他の見出し候補行とが隣接している場合に値を減じられる。
【００２３】
また、より好ましくは、前記一の目次項目に隣接する目次項目に、前記一の目次項目に所定の数以下の目次項目を挟んで隣接する目次項目を含める。
【００２４】
また、より好ましくは、前記スコア関数Sの最大値は、Viterbiアルゴリズム又はダイクストラ法に従い探索される。
【００２５】
また、より好ましくは、前記スコア関数Sの最大値の探索において、前記目次データCに含まれる各目次項目にそれぞれ対応付ける前記見出し候補行を、本文データD内の全行のうち、前記目次項目の文字列と一定以上の類似度を有する文字列の行に限定する。
【００２６】
また、好ましくは、前記目次は木構造を有し、前記木構造において同一階層において隣り合う兄弟関係にある前記目次項目ペアに対しては、前記バイグラムスコアbとして、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度が高いほど高いスコア値を返す兄弟バイグラムスコアb1を採用し、前記木構造において親子関係にある前記目次項目ペアに対しては、前記バイグラムスコアbとして、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度が低いほど高いスコア値を返す親子バイグラムスコアb2を採用する。
【００２７】
より好ましくは、前記親子バイグラムスコアb2は、親である目次項目に対応付ける見出し候補行のフォントサイズがと子である目次項目に対応付ける見出し候補行のフォントサイズの間に大小関係がある場合に高いスコア値を返す。
【００２８】
また、より好ましくは、前記親子バイグラムスコアb2は、親である目次項目に対応付ける見出し候補行の索引部分と子である目次項目に対応付ける見出し候補行の索引部分のフォーマットが異なる場合に高いスコア値を返す。
【００２９】
また、より好ましくは、前記スコア関数Sの最大値は、2nd order Eisnerを応用したアルゴリズムに従い探索される。
【００３０】
また、より好ましくは、前記スコア関数Sの最大値の探索において、前記目次データCに含まれる各目次項目にそれぞれ対応付ける前記見出し候補行を、本文データD内の全行のうち、前記目次項目の文字列と一定以上の類似度を有する文字列を含む行に限定する。
【００３１】
以上、目次と見出しの対応付け方法として本願発明を説明した。しかし、本願発明は、そのような目次と見出しの対応付け方法を実行する目次と見出しの対応付け装置、及びそのような目次と見出しの自動対応付け方法をコンピュータに実行させる目次と見出しの対応付けプログラムとして把握することもできる。
【発明の効果】
【００３２】
本願発明では、目次項目の見出し候補行への対応付けの尤もらしさを、当該対応付け単独で評価するだけでなく、当該目次項目の見出し候補行への対応付けと他の目次項目の見出し候補行への対応付けとの共通度をも考慮して評価する。従って、本願発明によれば、見出しに共通する属性情報や目次におけるページ番号と通し番号との差分情報を、事前に網羅的に設定したり文書ごとに人手により設定したりする必要なしに、電子化された書籍において、目次と本文中の見出し間の適切な対応付けをコンピュータの演算処理により行うことができる。本願発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００３３】
【図１】目次と見出しの対応付けの一例を示す図である。
【図２】目次と見出しの対応付けの他の一例を示す図である。
【図３】本願発明の実施の形態に係る自動対応付け装置３００の機能構成の一例を示す図である。
【図４】スコア関数Sの最大値の探索するための探索対象のグラフの一例を示す図である。
【図５】第１のフィルタリング及び第２のフィルタリングを施した探索対象のグラフの一例を示す図である。
【図６】ページ抜けを示すエッジを追加した探索対象のグラフの一例を示す図である。
【図７】ページ抜けを示すノードを追加した探索対象のグラフの一例を示す図である。
【図８】自動対応付け装置３００による処理の全体の流れの一例（実施例１）を示すフローチャートである。
【図９】DAGのノード作成処理の流れの一例を示すフローチャートである。
【図１０】DAGのエッジ作成処理の流れの一例を示すフローチャートである。
【図１１】スコア関数Sの最大値探索処理の流れの一例を示すフローチャートである。
【図１２】スコア関数Sの最大値を与える対応付けMの出力処理の流れの一例を示すフローチャートである。
【図１３】図１３（ａ）は、木構造を有する目次の一例を示す図である。図１３（ｂ）は、対応付けMの配列の復元順序の一例を示す図である。
【図１４】自動対応付け装置３００による処理の全体の流れの一例（実施例２）を示すフローチャートである。
【図１５】見出し候補行の決定処理の流れの一例を示すフローチャートである。
【図１６】再帰関数comp(c, l, r)の計算処理の流れの一例を示すフローチャートである。
【図１７】再帰関数incomp(c, l, r)の計算処理の流れの一例を示すフローチャートである。
【図１８】再帰関数getcomp(c, l, r)処理の流れの一例を示すフローチャートである。
【図１９】再帰関数getincomp(c, l, r)処理の流れの一例を示すフローチャートである。
【図２０】本願発明の実施の形態に係る自動対応付け装置３００を実現するのに好適な情報処理装置のハードウェア構成の一例を示した図である。
【発明を実施するための形態】
【００３４】
以下、本願発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００３５】
図１は、目次と見出しの対応付けの一例を示す図である。図１において左側は目次ページ１００を示し、右側は本文ページ１０２を示す。目次ページ１００には目次項目が並び、各目次項目は、索引部分を有する文字列（目次項目１０４の例では「第六十九回」から始まる文字列１０６）とページ番号（目次項目１０４の例では「６」の数字１０８）とからなる。また、本文ページ１０２は、目次項目に対応する見出し１１０を含み、ページ左下に「６」のページ番号１１２を含む。
【００３６】
本願発明は、図１に示す矢印のように、目次ページ１００内の各目次項目を、本文ページ内の対応する見出し行に、コンピュータの演算処理により自動で適切に対応付けることを目的とする。目次項目の見出し行への対応付けの尤もらしさを評価するのに有効な基準の１つは、目次項目と見出し行の文字列の類似度である。
【００３７】
しかしながら、ＯＣＲ処理によって得られた目次データや本文データにはノイズ（誤字、脱字、ゴミ文字）が含まれることが予想される。また、図１に示す例では目次項目の文字列は索引部分が含んでいるが、このような索引部分は見出し行にのみ付与されることも少なくない。このような場合に目次項目の文字列と同じ文字列が本文中に複数含まれていると、文字列の類似度だけで対応付けの尤もらしさを正しく評価することはできない。
【００３８】
上述のケースの一例を図２に示す。図１と同様、左側は目次ページ２００を示し、右側は本文ページ２０２を示す。本文ページ２０２では全見出し行２１６、２１８、２２４に章番号が付与されているのに対し、目次ページ２００では、大章番号のみが該当する目次項目２０４、２１２に付与されている。そのため文字列の類似度だけでは「隠れマルコフモデル」の目次項目２０６を、本文ページ２０２内の「第４章 隠れマルコフモデル」の行２１６と、「4.1隠れマルコフモデル」の行２１８と、「隠れマルコフモデル」の行２２０のいずれに対応付けるべきか判断できない。
【００３９】
上記問題に対し、特許文献１の従来技術は、見出しには索引部分がある場合が多いことに注目し、基準書式との照合によって見出しの候補を絞り込む。また、上記従来技術は、見出しに関する文書ページ内レイアウトに関する種々のアプリオリな知識を利用し、ページ内位置関係に基づく条件によって見出しの候補を絞り込む。しかしながらそのためには、照合すべき基準書式やページ内位置関係に基づく条件を事前に設定しておく必要がある。事前設定にない基準書式が利用される場合、また、事前設定の条件が広すぎる場合には当該方法は有効に機能しない。
【００４０】
そこで本願発明では、見出しには共通して見られる見出しとしての特徴があることを、一の目次項目の見出し候補としての行（以下、「見出し候補行」という）への対応付けと、他の目次項目の見出し候補行への対応付けとの共通度を評価することで利用する。これを先の図２のケースを例に説明する。
【００４１】
上述したように、「隠れマルコフモデル」の目次項目２０６については、目次項目と見出し候補行の文字列の類似度から、本文ページ２０２内の「第４章 隠れマルコフモデル」の行２１６と、「4.1隠れマルコフモデル」の行２１８と、「隠れマルコフモデル」の行２２０の３つの行が見出し候補行として抽出される。ここで、目次項目２０６の見出し候補行への対応付けを、隣接する「マルコフ過程」の目次項目２０８の見出し候補行である「4.2マルコフ過程」の行２２４への対応づけとの共通度に基づき更に検討する。すると、対応付ける見出し候補行の索引部分の共通度の高さから、「4.1隠れマルコフモデル」の行２１８を正しく選択できる。
【００４２】
なお、対応付けの共通度を評価するにあたり選択すべき他の目次項目は、目次が木構造を有するか否かによって異なる。目次が木構造を有さずフラット構造を有する場合、各目次項目に対応付けられる見出しのフォーマットは同一と考えられる。従って、全ての目次項目が同一レベルにある場合、他の目次項目は一の目次項目と異なる任意の目次項目でよく、共通度の評価では共通度が高いほど高い評価となる。但し、他の目次項目は目次項目ごと異なることが好ましいことから、以下に説明する実施例では、他の目次項目は一の目次項目に隣接する目次項目とする。
【００４３】
一方、目次が木構造を有する場合、兄弟関係にある目次項目のペアにそれぞれ対応付けられる見出しのフォーマットは同一と考えられが、親子関係にある目次項目のペアにそれぞれ対応付けられる見出しのフォーマットは同一ではなく、例えばフォントサイズや章番号等、大小関係があると考えられる。従って目次が木構造を有する場合、選択すべき他の目次項目は、一の目次項目と兄弟関係にある目次項目であり、共通度の評価では共通度が高いほど高い評価となる。但し、共通度の評価を、共通度が低いほど高い評価を行うようにすれば、他の目次項目として、一の目次項目と親子関係にある目次項目を選択することも可能である。
【００４４】
また、一の目次項目の見出し候補行への対応付けと、他の目次項目の見出し候補行への対応付けとの共通度を評価することによって、目次におけるページ情報の利用が可能となる。なぜならば、目次項目に含まれる目次のページ番号と実際のページ番号、即ち、文書の最初のページからの通し番号とにずれがあったとしても、ずれの程度は全ての対応付けにおいて同一であるからである。なお、通し番号から目次項目のページ番号を差し引いた差分の共通性に基づく対応付けの評価は、目次が木構造を有するか否かによらず、任意の目次項目ペアに対して適用可能であることに留意されたい。
【００４５】
以下、目次項目と見出し候補行との対応付けの問題を定式化し、定式化した問題に対して本願発明を説明する。
【００４６】
まず、本願発明の一実施形態に係る目次と見出しの自動対応付け装置への入力として、目次データCと、本文データDを次のように定義する。
C = {(s1,p1), …, (s|C|,p|C|)} ― （定義１）
ここで、|C|は目次に含まれる全目次項目数、siはi番目の目次項目の文字列、piはi番目の目次項目のページ番号を示す。
D = {L1, …, L|D|} ― （定義２）
ここで、|D|は本文に含まれる全行数、Lkは本文に含まれるk番目の行を示す。
【００４７】
このような目次データCは、文書のスキャンデータから目次ページを推定して、各行を目次データとすることにより取得してよい。その際、各行の最後にある数字をページ番号piとし、両端の空白文字を除く残りを目次項目の文字列siとしてよい。かかる処理の詳細は、例えば以下の文献を参照されたい。
S. Mandal, S. P. Chowdhury, A. K. Das, B. Chanda, “AutomatedDetection and Segmentation of Table of Contents Page from Document Images.”, In proc. of ICDAR 2003.
なお、目次データCは書籍の所有者である出版社が所有していることも多く、その場合出版社から取得できる。
【００４８】
一方、本文に含まれる各行Lkは、文字列と通し番号やフォントサイズ等の付加情報からなるものとする。一般的にＯＣＲは認識した文字の情報だけでなく、該文字が占める矩形情報をも出力する。具体的には、ページ隅を原点としたページ内での矩形の位置座標(x,y)、矩形の幅width及び高さheightである。また、一般的なＯＣＲは、閾値以下で隣接する文字を同じ行としてつなぎ合わせる等の処理をして行を認識し、行単位で文字単位のスキャン結果を出力することができる。そこで本実施例では、ＯＣＲの当該機能を利用し、同一行と認識された文字単位の認識結果の集合から、各行Lkの文字列（空白文字は含まない）を取得し、また、高さheightの中央値を求めてこれを各行Lkのフォントサイズとする。更にＯＣＲは、横書きの場合ページごとに上から下へ順次スキャンを行うことから通し番号やページ内行番号を取得可能であり（縦書きの場合は通し番号とページ内の列番号）、本実施例では当該通し番号とページ内行番号を各行Lkに付与するものとする。
【００４９】
次に、目次と見出しの自動対応付け装置からの出力として、出力データMを次のように定義する。
M = {m1, …, m|C|} ― （定義３）
ここで、|C|は目次に含まれる全目次項目数を示す。
出力データMは、各目次項目が何行目に対応しているかを表す正の整数の列であり、要素miは、i番目の目次項目がmi（正の整数値）行目に対応することを示す。そのため以下では出力データMを対応付けMともいう。
【００５０】
ここで、目次データC内の全目次項目の本文データD内の見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sを考える。すると、目次項目の見出し候補行への対応付けの問題は、スコア関数Sを最大にする対応付けMを求める問題として定式化できる。
【００５１】
本願発明では、上述したように、目次項目の見出し候補行への対応付けの尤もらしさを、当該対応付け単独で評価するだけでなく、他の目次項目の見出し候補行への対応付けとの共通度をも考慮して評価する。そこで、本願発明では、上記スコア関数Sを以下のように定義する。
S(C,D,M) = Σi u(i,mi,C,D)+ Σib(i, mi, mj, C,D) ― （定義４）
ここで、uは各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアを示し、出力データMの要素miごとのスコアを示す。
また、bは一の目次項目と他の目次項目のペアである目次項目ペアの見出し候補行への対応付けの尤もらしさを目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価するバイグラムスコアを示し、出力データMの要素のペアmi, mjごとのスコアを示す。
【００５２】
対応付けMの候補は入力長に対して指数個存在するため、全ての対応付けMを列挙してスコア関数Sの最大値を求めることは一般に、計算量的に困難である。しかし、スコア関数Sを上記のようにユニグラムスコアuを全目次項目について足し合わせた第１の和と、バイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として表すことで、多項式時間で計算することが可能である。例えば、Viterbiアルゴリズムを適用すれば、上記スコア関数Sを最大にする対応付けMの系列は、目次項目数|C|、本文行数|D｜に対して、時間計算量O(|C||D|2)で求められることが知られている。なお、本文データDの要素、即ち見出し候補行をフィルタリングすることによって、時間計算量は更に少なくすることが可能である。
【００５３】
以上のように定式化した問題に対し、本願発明の一実施形態に係る目次と見出しの自動対応付け装置３００を説明する。図３は、本願発明の一実施形態に係る目次と見出しの自動対応付け装置３００の機能構成を示す図である。目次と見出しの自動対応付け装置３００は、入力部３０２と、探索部３０４と、出力部３０６とを備える。
【００５４】
入力部３０２は、文書の目次項目単位の目次データCと、文書の行単位の本文データDとを、記憶装置から読み出して、またはネットワークを介して他のコンピュータから、入力する。探索部３０４は、目次データC内の全目次項目の本文データD内の見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索する。出力部３０６は、スコア関数Sを最大にする前記対応付けMを出力する。
【００５５】
ここで探索部３０４は、スコア関数Sを、定義４に関して説明したユニグラムスコアuを全目次項目について足し合わせた第１の和と、同じく定義４に関して説明したバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求める。
【００５６】
ところでバイグラムスコアbは上述したように、目次が木構造を有するか否かによってその値を求めるべき目次項目のペアの組み方が異なる。そこで以下では、目次がフラット構造を有する場合を実施例１、目次が木構造を有する場合を実施例２としてそれぞれ順に説明する。
【実施例１】
【００５７】
実施例１では、目次はフラット構造を有し、全ての目次項目が同一レベルにあるとする。この場合、バイグラムスコアbを求めるべき目次項目のペアは、任意の目次項目のペアであってよく、共通度の評価では共通度が高いほど高い評価となる。しかし、一の目次項目のペアとすべき他の目次項目は目次項目ごと異なることが好ましい。そこで本実施例では、目次項目のペアは隣接関係にある目次項目のペアとし、定義４を次のように書き直す。
S(C,D,M) =Σi u(i,mi,C,D) + Σib(i, mi,mi+1, C,D) ―（定義５）
以下ではまず定義５におけるユニグラムスコアuとバイグラムスコアbの設計方法を説明する。その後に、定義５で示されるスコア関数Sの最大値の探索方法を図４から図７を参照して説明する。
【００５８】
既に説明したとおり、ユニグラムスコアu(i,mi,C,D)は、i番目の目次項目 (C[i]）を文書のmi行目（D[mi]）に対応付ける対応付けの尤もらしさを該対応付け単独で評価したスコアである。以下ではユニグラムスコアu (i,mi,C,D)を、簡略してu(i, mi)とも記載する。単独評価の第１の例は、文字列の類似度に基づく評価である。即ち、C[i]の文字列とD[mi]の文字列が互いに類似しているならば高いスコアを返すようにユニグラムスコアuを設計する。
【００５９】
類似か否かの判断は、一例としてC[i]の文字列とD[mi]の文字列の編集距離や、C[i]の文字列とD[mi]の文字列に共通に含まれる隣接２文字対の数を利用してよい。前者の編集距離は、２つの文字列がどの程度異なっているかを示す数値であるため、編集距離が所定の閾値以下であれば類似と判断してよい。後者は、各文字列について隣接２文字対の集合をそれぞれ求め、２つの集合の積集合のサイズが所定の閾値以上であれば類似と判断してよい。便宜上、以下では類似であるか否かを判断する際の所定の閾値をMINSIMという。編集距離の詳細については、例えば以下の文献を参照されたい。
Gonzalo Navarro, Mathieu Raffinot, “FlexiblePattern Matching in Strings: Practical On-Line Search Algorithms for Texts andBiological Sequences”, Cambridge UniversityPress, 2007.
【００６０】
単独評価の第２の例は、行の種類に基づく評価である。即ち、フォントサイズや位置等の情報から、D[mi]が見出しにみられる特徴を有すると判断できる場合、高いスコアを返すユニグラムスコアuを設計する。逆に、フォントサイズや位置等の情報から、D[mi]が柱や注釈、本文に見られる特徴を有すると判断される場合、低いスコアを返すユニグラムスコアuを設計する。なお、行の種類に基づく評価は複数考えられるため、例えば、見出しの可能性が高いと判断すればスコアを１増やし、見出しでない可能性が高いと判断すればスコアを１減らし、というように複数の判断を組み合わせて最終的なスコアを出力するよう設計してもよい。
【００６１】
ここでフォントサイズの大小は、見出しや注釈以外の本文との比較によって判断されうるものである。そこで、本文のフォントサイズを文書内の全行のフォントサイズの中央値で代替し、D[mi]が該中央値より大きいフォントサイズを有する場合に見出しと判断し、D[mi]が上記中央値より小さいフォントサイズを有する場合に見出しでないと判断してよい。また、位置情報に関しては、例えば、見出しはページの最初につきやすいことから、D[mi]がページの最初の行である場合に見出しと判断してもよい。逆に、D[mi]がページの最後の行である場合には注釈である可能性が高いことから、見出しではないと判断してもよい。また、見出し行は中央寄せであったり、本文よりも左に飛び出すなど、本文と異なる傾向にあることから、例えば横書きの場合、全行の文字の始まり位置の中央値からD[mi]の文字の始まり位置を差し引いた値の絶対値が所定の閾値以上であれば見出しと判断し、そうでない場合見出しでないと判断してもよい。なおこれらは位置情報に基づく判断の一例として説明したものであり、他の位置情報に関する見出しの特徴の知識の利用を制限するものではないことに留意されたい。
【００６２】
ユニグラムスコアuは、上述した文字列の類似度にのみ基づいて評価するものでもよく、または文字列の類似度に基づく評価（スコア）と行の種類に基づく評価（スコア）とを適宜重み付けをしつつ足し合わせて総合評価するのでもよい。このような総合評価を採用する場合、対応付けのいくつかについてフォントサイズや位置情報を取得できないため全部の評価(スコア）を取得できないとしても、いずれか１つの評価（スコア）を求めることができれば問題はない。また、重み付けは正解データから各スコアの重みを自動学習してもよい。
【００６３】
次に、バイグラムスコアb(i, mi, mi+1, C,D)の設計方法について説明する。既に説明したとおり、バイグラムスコアb(i, mi, mi+1, C,D)は、一の目次項目（i番目の目次項目 (C[i]））と該一の目次項目に隣接する他の目次項目（i+1番目の目次項目 (C[i+1]））のペアである目次項目ペアの見出し候補行（mi行目（D[mi]）とmi+1行目（D[mi+1]））への対応付けの尤もらしさを、当該隣接する目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価したスコアである。なお上述したように、実施例１における共通度の評価は、共通度が高いほど高い評価を行う評価である。また、以下ではバイグラムスコア b(i, mi, mi+1, C,D)を、単にb(i, i+1, mi,mi+1,)とも記載する。
【００６４】
共通度に基づく評価の第１の例は、フォーマットの共通度に基づく評価である。即ち、C[i]を対応付けるD[mi]と、C[i+1]を対応付けるD[mi+1]のフォーマットの共通度が高い場合に高いスコアを返すようにバイグラムスコアbを設計してよい。より具体的には、フォーマットの共通度は、D[mi]とD[mi+1]のフォントサイズの共通度であってよく、D[mi]とD[mi+1]のフォントサイズが同一とみなせる場合にフォーマットの共通度が高いと判断してよい。これは、目次がフラット構造であれば見出しのフォントサイズは同じであるという知識に基づくものである。
【００６５】
また、フォーマットの共通度は、D[mi]の文字列とD[mi+1]の文字列の最初の文字又は最初の文字と最後の文字の共通度であってよい。即ち、D[mi]の文字列とD[mi+1] の文字列が、共通の文字で始まる又は共通の文字で始まりかつ共通の文字で終わる場合にフォーマットの共通度が高いと判断してもよい。これは、見出しには、索引部分（例えば、“第Ｘ章”や“第Ｘ部”等）や見出しであることを示す記号（例えば、“§”や“○”等）が先頭において含まれることが多いこと、また、見出しであることを示す記号については、例えば“■リストの実現■”のように、見出しの最初と最後に含まれていることがあること、そして目次がフラット構造であればそのような書式は全見出しに共通であるという知識に基づくものである。
【００６６】
また、C[i]の文字列と類似するD[mi]の文字列部分（以下、D[mi]の類似文字列という）と、C[i+1]の文字列と類似するD[mi+1]の文字列部分（以下、D[mi+1]の類似文字列という）の前後の所定数の文字の類似度が高い場合にフォーマットの共通度が高いと判断してもよい。かかる判断は、１つには、目次項目の文字列に索引部分や記号部分が含まれない場合に効果的である。なぜならばこの場合、D[mi]やD[mi+1]の類似文字列の前後の所定数の文字は、索引部分（例えば、“第Ｘ章”や“第Ｘ部”等）や記号部分（例えば、“§”や“■リストの実現■”の“■”等）を指すことになり、当該部分の類似度が高い場合にフォーマットの共通度が高いと判断することになるからである。またかかる判断は、スキャンデータ以外のデータであって位置情報を持たないデータを利用する場合に有効である。この場合、見出し候補行の文字列はフォーマット調整のための空白文字を含み、従ってD[mi]やD[mi+1]の類似文字列の前後の所定数の文字は、フォーマットに利用された空白文字を指すことになり、当該部分の類似度が高い場合にフォーマットの共通度が高いと判断することになるからである。
【００６７】
共通度に基づく評価の第２の例は、目次におけるページ番号と実際のページ番号、即ち、最初のページからの通し番号との差分の共通度に基づく評価である。即ち、C[i]に含まれるページ番号とC[i]に対応付けるD[mi]を含むページの通し番号との差分と、C[i+1]に含まれるページ番号とC[i+1]を対応付けるD[mi+1] を含むページの通し番号との差分との共通度が高い場合に高いスコアを返すようにバイグラムスコアbを設計してよい。なお、差分の共通度の高さは、一例として差分が同一である場合に共通度が高いとしてよい。
【００６８】
当該評価は、前書き等の本文以外のページの存在のため、目次におけるページ番号と通し番号にはずれが生じることが多いが、その差分は一定であるという知識にもとづくものである。例えば、目次に含まれる各目次項目のページ番号がそれぞれ、１、４、１１、７（誤）、２２、２６であったとする。但し７のページ番号は読み取り誤りがあったため、間違ったページ番号であるとする。これに対し、対応する見出し候補行の通し番号がそれぞれ、２、５、１２、１８、２３、２７であったとする。するとその差分はそれぞれ、１、１、１、１１、１、１であり、５つの隣接目次項目のペアのうち３つは差分の値が同一となる。このようにページ番号を差分で評価することにより、ページ番号のわずかな読み取り誤りによって評価が大きく影響を受けることはなくなる。
【００６９】
上記差分の共通度に基づく評価に加えて、非隣接行制約に従うようバイグラムスコアbを設計してもよい。ここで非隣接行制約とは、隣接する目次項目ペアC[i] 、C[i+1]にそれぞれ対応付けられる見出し候補行D[mi] 、D[mi+1]は、隣接する行であってはいけないという制約である。この制約は、連続する見出しの間には必ず本文があるという知識に基づくものである。そこで、C[i] 、C[i+1]が隣接する行である場合、バイグラムスコアbの値を減じるように設計してもよい。
【００７０】
バイグラムスコアbは、上述した３つのフォーマットの共通度に基づく評価（スコア）と、ページの差分の共通度に基づく評価（スコア）と、非隣接行制約に基づく評価（スコア）とのうち任意の数の評価（スコア）を、重み付けをしつつ組み合わせて評価するものであってもよい。複数の評価（スコア）を足し合わせて評価する場合、対応付けのいくつかについてフォントサイズやページ情報を取得できないため全部の評価(スコア）を取得できないとしても、いずれか１つの評価（スコア）を求めることができれば問題はない。また、重み付けは正解データから各スコアの重みを自動学習してもよい。
【００７１】
次に定義５により表されるスコア関数Sの最大値の探索方法を説明する。図４は、スコア関数Sの最大値の探索するための探索対象のグラフ４００を示す。グラフ４００は、（目次項目数（|C|）４０２×本文の全行数（|D|）４０４）個の丸で示されるノードと、探索開始地点を示す仮想ノードであるBOS４０６と、探索終了地点を示す仮想ノードであるEOS４１０と、隣接するノード間を結ぶエッジとから構成される。なお、図４では一部のエッジのみ表示し、残りのエッジは省略していることに留意されたい。
【００７２】
グラフ４００の各ノードは、該ノードが属する列の列番号とノードに付けられた番号によって、何番目の目次項目を何行目に対応付けるかその対応付けを示す。例えばノード４１２は、１番目の列に属しノードに番号４が付けられていることから、１番目の目次項目を４行目に対応付ける対応付けを示す。従って、i番目の列に属するノードの集合は、対応付けMの要素miが示しうる全対応付けの集合とみることができる。なお、図４では、一部のノードのみ丸の中に対応付けた行番号を表示し、残りのノードについてはそのような行番号を表示していないことに留意されたい。
【００７３】
また、グラフ４００の各エッジは、エッジ両端のノードが示す対応付けのペア、即ち、隣接関係にある目次項目のペアの対応付けを示す。例えばエッジ４１４は、１番目の目次項目を３行目に対応付ける対応付けと、１番目の目次項目に隣接する２番目の目次項目を４行目に対応付ける対応付けのペアを示す。
【００７４】
各ノードには該ノードが示す対応付けについてのユニグラムスコアuが付与されている。また、各エッジには該エッジが示す隣接する目次項目のペアの対応付けについてのバイグラムスコアbが付与されている。このようなグラフ４００が与えられた場合に、スコア関数Sの最大値の探索は、BOS４０６を始点としEOS４１０を終点とするあらゆる経路の中で（経路４０８は一例）、その経路に含まれるノード及びエッジに付与されたスコアの合計を最大にする経路を選択する問題として捉えることができる。
【００７５】
グラフ４００は無閉路有向グラフ(DirectedAcyclic Graph: DAG)であることから、この経路探索の問題はViterbiアルゴリズムやダイクストラ法によりノード数に対して多項式時間で解くことができる。具体的には、目次項目数|C|、本文行数|D｜に対して、時間計算量O(|C||D|2)で求めることができる。従って実際の計算時間は、本文データDの要素、即ち見出し候補行をフィルタリングすることによって、更に少なくすることができる。
【００７６】
そこで、次に見出し候補行のフィルタリングについて説明する。第１のフィルタリングはページ番号の制約に基づくフィルタリングである。目次は見出しを順序立てて書いたものである。従って、目次項目C[i]に対応付ける見出し行の行番号miは、iが大きくなるにつれて大きくならなければならない。従って、図４に示すグラフ４００においてmi > mi+1となるエッジは削除してよい。エッジの削除によって孤立するノードもまた削除してよい。
【００７７】
第２のフィルタリングは、目次項目と該目次項目に対応付ける見出し候補行の文字列の類似度に基づくフィルタリングである。即ち、目次項目C[i]に対応付ける見出し候補行D[mi]を、本文データD内の全行のうち、C[i]の文字列と一定以上の類似度を有する文字列の行に限定してよい。ここで類似度の判断は、上述したユニグラムスコアuにおける類似度の判断と同様の方法を使用してよい。
【００７８】
図５は、図４に示すグラフ４００において、第１のフィルタリング及び第２のフィルタリングによりエッジとノードを削除した結果のグラフ５００を示す。但し図５では、m1 とm２の列以外は、ノードの行番号とエッジとを省略していることに留意されたい。m1の列５０８をみてみると、各ノードに付けられた行番号は、１、８、１３、２８、…と飛び飛びの値をとっている。これは、第２のフィルタリングにより１番目の目次項目C[１]に対応付ける見出し候補行が絞り込まれた結果である。また、例えばノード５１０をみると、当該ノードには、該ノードの行番号８よりも大きい行番号１５、２３をそれぞれ持つノード５１２、５１４へのエッジのみが引かれている。これは、第１のフィルタリングによりmi > mi+1となるエッジが削除された結果である。このようにフィルタリングによりエッジやノードを削除することにより、計算時間を少なくすることができる。
【００７９】
ところで、本文データDはＯＣＲ処理により取得されるので、ページ抜けの可能性がある。そこで本実施例では図６および図７を参照して以下に説明する２つの方法によりページ抜けに対応する。
【００８０】
ページ抜けに対応する第１の方法は、ページ抜けを示すエッジを追加する方法である。エッジによって隣接関係にある目次項目のペアの対応付けを示すためには、エッジは隣接するノード間でのみ引かなければならない。しかし、間に一定数（便宜上、以下ではこの数値をMAXSKIPという）以下のノードを挟んでエッジを引くことを許容することにより、ページ抜けに対応することが可能となる。これを図６に示すグラフを参照して説明する。
【００８１】
図６は、図５に示すフィルタリング後のグラフ５００において、間に１つのノードを挟んでエッジを引くことを許容してエッジを追加したものである。但し図６では、m1 の列６０８からm3の列６１０までの列を除いて、ノードの行番号とエッジとを省略していることに留意されたい。図６では、m1の列６０８のノードとm3の列６１０のノードとを結合するエッジが複数追加されている。この新たに追加された各エッジは、２番目の目次項目に対応付けるべき見出し候補行がないことを示す。従って、スコアの合計を最大とする経路がこの新たに追加したエッジを含む場合、２番目の目次項目に対応付けるべき見出し候補行を含むページが抜けていたということが示される。なお、新たに追加するエッジに対しても、第１のフィルタリングを適用可能であること、また、バイグラムスコアbを付与することに留意されたい。
【００８２】
ページ抜けに対応する第２の方法は、ページ抜けを示すノードを追加する方法である。このページ抜けを示すノードは、抜けたページの行数を区別するために、全ノードの各々に対し１つ追加する。そして追加したノードには、直後のノードの行番号-0.5を付与する。これは、直後の行と直前の行の間に存在したはずだが、認識できなかった、あるいはページ抜けのために存在しなかったということを示すことになる。また、各ノードのユニグラムスコアとして、ページ抜けに対するペナルティーとして低い、あるいは負のスコアを与える。これは、ページ抜けと判断しづらくするためである。隣接見出し間のフォーマットの類似度は測ることができないので、バイグラムスコアbは0とする。
【００８３】
図７は、図５に示すフィルタリング後のグラフ５００において、全ノードの各々に対してノードを１つ追加したものである。なお、図７のグラフ７００では、追加したノードは黒丸で示している。但し図７では、m1 とm2の列を除いて、ノードの行番号やエッジ、また追加ノードを省略していることに留意されたい。ここで例えばノード７０８は、１２行目と１３行目の間に対応する行があったがそのような行を見つけられなかったことを示す。従って、スコアの合計を最大とする経路がこの新たに追加したノード７０８を含む場合、１番目の目次項目に対応付けるべき見出し候補行を含むページが抜けていたということが示される。なお、新たに追加するノードを結合するエッジに対しても、第１のフィルタリングは適用可能である。
【００８４】
次に図８から図１２を参照して、実施例１に係る目次と見出しの自動対応付け装置３００による処理の流れを説明する。なお、スコア関数Sの最大値の探索は、Viterbiアルゴリズムを利用するものとする。
【００８５】
図８は、自動対応付け装置３００による処理の全体の流れの一例を示すフローチャートである。図９は、図８に示すフローチャートのステップ８０４のDAGのノード作成処理の流れの一例を示すフローチャートである。図１０は、図８に示すフローチャートのステップ８０６のDAGのエッジ作成処理の流れの一例を示すフローチャートである。図１１は、図８に示すフローチャートのステップ８０８のスコア関数Sの最大値探索処理の流れの一例を示すフローチャートである。図１２は、図８に示すフローチャートのステップ８１０のスコア関数Sの最大値を与える対応付けMの出力処理の流れの一例を示すフローチャートである。
【００８６】
まず、図８を参照して目次と見出しの自動対応付けの全体処理の流れを説明する。図８に示す自動対応付けの全体処理はステップ８００から開始し、自動対応付け装置３００は、記憶装置またはネットワークを介して他のコンピュータから、目次項目単位の目次データCと行単位の本文データDを入力する（ステップ８００、ステップ８０２）。続いて自動対応付け装置３００は、入力した目次データCと本文データDとを使用して、図４、図５を参照して説明した、定義５により表されるスコア関数S(C,D,M)の最大値を探索するためのグラフ（以下、DAGという）のノードを作成する（ステップ８０４）。ノード作成処理の詳細は、図９を参照して後述する。
【００８７】
続いて自動対応付け装置３００は、前のステップで作成したDAGのノード情報に基づいてDAGのエッジを作成する（ステップ８０６）。エッジ作成処理の詳細は、図１０を参照して後述する。続いて自動対応付け装置３００は、作成したDAGを使用して、スコア関数S(C,D,M)の最大値を探索する（ステップ８０８）。探索処理の詳細は、図１１を参照して後述する。最後に自動対応付け装置３００は、ステップ８０８で求めたスコア関数S(C,D,M)の最大値を与える対応付けMを出力する。対応付けMの出力処理の詳細は、図１２を参照して後述する。そして処理は終了する。
【００８８】
次に図９を参照して、DAGのノード作成処理の詳細を説明する。ここでは上述した文字列の類似度に基づく第２フィルタリングを採用する。図９に示すDAGのノード作成処理はステップ９００から開始し、自動対応付け装置３００はまずDAGのノード情報を表す２次元配列dagを用意する。２次元配列dagの各要素への値の設定は続く処理において行うが、２次元配列dagの要素rはノードを表す抽象データ型とし、toc(r)番目の目次項目を行番号line(r)の見出し候補行に対応付ける対応付けを示すものとする。但し、関数tocと関数lineは、要素rに対しそれぞれ対応付けの目次項目の番号と見出し候補行の行番号を返す関数とする。また、目次項目のc番目に対し、dag[c]はc番目の目次項目に対応するノードの配列を表すものとする。
【００８９】
２次元配列dagを用意すると続いて自動対応付け装置３００は、２次元配列dag[0]に探索開始地点を示す仮想ノードBOSを追加する（ステップ９０２）。なお、関数tocと関数lineは仮想ノードBOSに対し共に0を返すものとする。続いて自動対応付け装置３００は、ステップ９０４及び該当する場合はステップ９０６の処理を、第１のループ及び第２のループにより繰り返す。第１のループは、変数cを1から目次項目数|C|まで１つずつ増やし繰り返すループである。第２のループは、変数cの値に対し変数dを1から本文の全行数|D|まで１つずつ増やしながら繰り返すループである。
【００９０】
ステップ９０４において、自動対応付け装置３００は、c番目の目次項目C[c]の文字列とd番目の行D[d]の文字列との類似度が許容できる最小の類似度MINSIMより大きいか否かを判定する。類似度の判定は、既に説明した通り編集距離等の既存技術を利用してよい。類似度がMINSIMより大きい場合（ステップ９０４：ＹＥＳ）、自動対応付け装置３００は、dag[c]にc番目の目次項目をd行目に対応付ける対応付け(c,d)を示すノードを追加する（ステップ９０６）。類似度がMINSIM以下の場合（ステップ９０４：ＮＯ）、またはステップ９０６の処理の後、自動対応付け装置３００は、第１及び第２の全てのループを抜け出すまで一連の処理を繰り返す。
【００９１】
上記繰り返し処理が終了すると、自動対応付け装置３００は、２次元配列dag[|D|+1]に、探索終了地点を示す仮想ノードEOSを追加する（ステップ９０８）。なお、関数tocと関数lineは仮想ノードEOSに対し、それぞれ|C|+1、|D|+1を返す。そして処理は終了する。
【００９２】
続いて図１０を参照して、DAGのエッジ作成処理の詳細を説明する。ここでは上述したページ番号の制約に基づく第１フィルタリングを採用する。また、ページ抜けに対応すべく上述した第１の方法、即ち、ページ抜けを示すエッジを追加する方法を採用する。図１０に示すDAGのエッジ作成処理はステップ１０００から開始し、自動対応付け装置３００は、DAGのエッジ情報を表す２次元配列leftを用意する。２次元配列leftの各要素への値の設定は続く処理において行うが、２次元配列dagの各要素nに対し、２次元配列left[n]は、要素nが示すノード（以下、単にノードnという）の列の左隣（仮想ノードBOS側）の列にあるノードであって、ノードnとの間にエッジを引くべきノードの配列を表すものとする。
【００９３】
２次元配列leftを用意すると自動対応付け装置３００は、ステップ１００４及び該当する場合はステップ１００６の処理を、入れ子になった４つのループにより繰り返す。第１のループは、変数cを1から目次項目数|C|まで１つずつ増やし繰り返すループである。第２のループは、各変数cの値に対してdag[c]が示すノードの配列から順に１のノードrを取り出して繰り返すループである。第３のループは、各ノードrに対して変数sを0から許容できる最大のページ抜け数MAXSKIPまで１つずつ増やし繰り返すループである。第４のループは、変数c、変数sのそれぞれの値に対してdag[c-s-1]が示すノードの配列から順に１のノードlを取り出して繰り返すループである。
【００９４】
ステップ１００２において自動対応付け装置３００は、ノードrの行番号line(r)の値がノードlの行番号line(l)の値より大きいか否かを判定する。line(r)＞line(l)の場合（ステップ１００２：ＹＥＳ）、自動対応付け装置３００は、left[r]にノードlを追加する（ステップ１００４）。line(r)≦line(l)の場合（ステップ１００２：ＮＯ）、またはステップ１００６の処理の後、自動対応付け装置３００は、４つのループ全てを抜け出すまで一連の処理を繰り返す。そして処理は終了する。
【００９５】
続いて図１１を参照して、スコア関数Sの最大値探索処理の詳細を説明する。図１１に示すスコア関数Sの最大値探索処理はステップ１１００から開始し、自動対応付け装置３００は、生成したDAGのノード数に等しい要素をそれぞれ有する配列Sと配列Bを用意する。配列Sと配列Bのそれぞれの要素への値の設定は続く処理において行うが、S[n]は、仮想ノードBOSを始点としノードnを終点とする経路のスコアのうち最大のスコアを格納するものとする。ここで、経路のスコアとは該経路に含まれるノード及びエッジにそれぞれ付与されるユニグラムスコアu、バイグラムスコアbの合計をいう。また、B[n]は、S[n]に設定される最大のスコアを与える経路に含まれる最後のエッジの情報（ノードnに至る１つ前のノード情報）を格納するものとする。なお、配列Sの0番目の要素S[0]はnullで初期化しておく。
【００９６】
既に説明したとおり、ノードrに付与されるユニグラムスコアuとは、該ノードrが示す対応付けについてのユニグラムスコアu(toc(r), line(r)) である。また、ノードrとノードlを結合するエッジに付与されるバイグラムスコアbとは、該エッジが示す隣接する目次項目のペアの対応付けについてのバイグラムスコアb（toc(r), toc(l), line(r), line(l))である。各ノード、各エッジにそれぞれ付与されるユニグラムスコアuとバイグラムスコアbは、スコア関数Sの最大値探索処理の前に予め求めておいてもよく、或いは以下のステップ１１０４、１１１０において必要に応じて求めてもよい。
【００９７】
上記のように配列Sを定義すると、求めるべきスコア関数Sの最大値はS[EOS]として求められる。ところで仮想ノードBOSを始点としノードrを終点とする経路の最大スコアS[r]は、ノードrに至る１つ前のノードlについての配列Sの値S[l]と、ノードlとノードrを結合するエッジのバイグラムスコアbとを足した値の最大値（以下では、部分最大値という）に、ノードrのユニグラムスコアuを足したものとして求めることができる。従って、S[EOS]の値を求めるには、仮想ノードBOSから仮想ノードEOSへ向う順序で、DAGのノード各々について配列S及び配列Bの値を求める必要がある。なお配列Bは、詳細は図１２を参照して後述するが、スコア関数Sの最大値を与える経路を特定する際に利用される。
【００９８】
そこで自動対応付け装置３００は、仮想ノードBOSから仮想ノードEOSへ向う順序で、DAGのノード各々について配列Sと配列Bの値を求めるべく、ステップ１１０２からステップ１１１０の処理（但しステップ１００８は該当する場合のみ）を第１ループと第２ループにより繰り返す。第１のループは、変数cを1から目次項目数に1加えた（|C|+1）まで１つずつ増やし繰り返すループである。第２のループは、各変数cの値に対してdag[c]が示すノードの配列から順に１のノードrを取り出して繰り返すループである。
【００９９】
ステップ１１０２において、自動対応付け装置３００は、ノードrについて上記部分最大値を求めるための変数maxを用意しこれを−∞で初期化する。自動対応付け装置３００はまた、変数maxに部分最大値の値が設定される際の最後のエッジ情報を保持しておくための変数bestを用意し、これをnullで初期化する。そして自動対応付け装置は、ノードrについて上記部分最大値を求めるために、続くステップ１１０４からステップ１１０８の処理（但しステップ１１０８の処理は該当する場合のみ）を第３ループにより繰り返す。第３のループは、各ノードrに対してleft[r]が示すノードの配列から順に１のノードlを取り出して繰り返すループである。
【０１００】
ステップ１１０４において、自動対応付け装置３００は、一時変数sにノードlとノードrを結合するエッジに付与されたバイグラムスコアb(toc(l),c,line(l),line(r))とS[l]とを足し合わせた値を設定する。続いて自動対応付け装置３００は、一時変数sが変数maxより大きいか否かを判定する（ステップ１１０６）。s＞maxの場合（ステップ１１０６：ＹＥＳ）、自動対応付け装置３００は、変数maxに一時変数sの値を、変数bestにノードlを設定する（ステップ１１０８）。s≦maxの場合（ステップ１１０６：ＮＯ）、またはステップ１１０８の処理の後、自動対応付け装置３００は、第３のループを抜け出すまで一連の処理を繰り返す。
【０１０１】
第３のループを抜け出すと、続いて自動対応付け装置３００は、S[r]に変数maxとユニグラムスコアu(c, line(r))とを足し合わせた値を設定し、またB[r]に変数bestの値を設定する（ステップ１１１０）。続いて自動対応付け装置３００は、第１のループを抜け出すまで上記一連の処理を繰り返す。そして処理は終了する。
【０１０２】
続いて図１２を参照して、スコア関数Sの最大値を与える対応付けMの出力処理の詳細を説明する。図１１に示すスコア関数Sの最大値探索処理において求められた配列Bの各要素B[n]には、上述したように、配列S[n]に設定される最大のスコアを与える経路に含まれる最後のエッジの情報（ノードnに至る１つ前のノード情報）が格納されている。また、スコア関数Sの最大値はS[EOS]により与えられる。従って、スコア関数Sの最大値を与える対応付けMは、B[EOS] を出発点としてB[BOS]までエッジ情報を順次繋ぎ合わせることにより求められる。そこで処理の開始において、自動対応付け装置３００はまず、定義３として説明した対応付けMの配列を用意する（ステップ１２００）。
【０１０３】
続いて自動対応付け装置３００は、ノードを表す変数nに、探索終点を示す仮想ノードEOSを設定する（ステップ１２０２）。続いて自動対応付け装置３００はnにB[n]を設定する（ステップ１２０４）。続いて自動対応付け装置３００は、現在の変数nの値がBOSに等しいか否かを判定する（ステップ１２０６）。変数nの値がBOSに等しくない場合（ステップ１２０６：ＮＯ）、自動対応付け装置３００はステップ１２０８の処理へ進み、M[toc(n)]にline(n)の値を設定する。その後自動対応付け装置３００はステップ１２０４の処理に戻る。
【０１０４】
一方、変数nの値がBOSに等しい場合（ステップ１２０６：ＹＥＳ）、自動対応付け装置３００はステップ１２１０の処理へ進み、配列Mを出力する。そして処理は終了する。
【実施例２】
【０１０５】
実施例２では、目次は木構造を有するものとする。図１３（ａ）に、木構造を有する目次の例を示す。図１３（ａ）において、目次は矩形内の数字によりその索引部分のみが示されている。また、図中矢印は目次項目の親子関係を示し、矩形下に表示された１段目の数字は目次項目番号を、２段目の数字はルートの階層レベルを０とした階層のレベルを示している。矢印の先が同一の兄弟関係にある目次項目の任意のペア（例えば、「1.1」と「1.2」）は、階層のレベルが同一でありフォーマットも共通している。一方、矢印元と矢印先という親子関係にある目次項目の任意ペア（例えば、「1」と「1.1」）は、階層のレベルが一段階異なりフォーマットも異なっている。
【０１０６】
このように目次の木構造において兄弟関係にある目次項目のペアにそれぞれ対応付けられる見出しのフォーマットは同一と考えられる。一方、目次の木構造において親子関係にある目次項目のペアにそれぞれ対応付けられる見出しのフォーマットは同一ではなく、例えばフォントサイズや章番号等、大小関係があると考えられる。従って目次が木構造を有する場合、バイグラムスコアbを求めるべき目次項目のペアは、目次の木構造において同一階層で隣り合う兄弟関係にある目次項目のペア（以下、兄弟関係にある隣接目次項目ペアという）であり、共通度の評価では共通度が高いほど高い評価となる。但し、共通度の評価を、共通度が低いほど高い評価を行うようにすれば、親子関係にある目次項目のペアを選択することも可能である。なお、目次の木構造のデータは、一例としてその階層レベルを示す数値を目次項目順に並べたリストとして記憶して利用してよい。
【０１０７】
そこで実施例２においては、兄弟関係にある隣接目次項目ペアに対しては、バイグラムスコアbとして、目次項目ペアのそれぞれの見出し候補行への対応付けの共通度が高いほど高いスコア値を返す兄弟バイグラムスコアb1を採用する。また、親子関係にある目次項目ペアに対しては、バイグラムスコアbとして、目次項目ペアのそれぞれの見出し候補行への対応付けの共通度が低いほど高いスコア値を返す親子バイグラムスコアb2を採用する。なお、バイグラムスコアbとして兄弟バイグラムスコアb1または親子バイグラムスコアb2いずれか一方のみを採用することも可能であることはいうまでもない。
【０１０８】
従って、実施例２において定義４は次のように書き直される。
S(C,D,M) =Σi u(i,mi,C,D)+ Σib1(i, mi, msib(i), C,D) + Σib2(i, mi, mpar(i), C,D)―（定義６）
ここで、sib(i)は、i番目の目次項目に同一階層において隣接する１つ前の兄ノードの目次項目番号を返す関数である。図１３（ａ）の目次の例では、例えばsib (4)=3、sib (11)=5である。また、par(i)は、i番目の目次項目の親ノードの目次項目番号を返す関数である。図１３（ａ）の目次の例では、例えばpar (4)=1、cpar (5)=0である。上記２つの関数に加えて、i番目の目次項目の最後の子ノードの目次項目番号を返す関数chd(i)を導入する。図１３（ａ）の目次の例では、例えばchd(0)=11、chd(1)=4である。新たに導入した３つの関数の擬似コードを以下に記載しておく。
【０１０９】
par(n): // nより前で、階層がnより小さい最初の項目
for i in {n-1, n-2, ..., 0}:
ifL[i] < L[n]:
returni
return-1
sib(n): // nより前、par(n)よりあとで、階層がnと同じ最初の項目
for i in {n-1, n-2, ..., par(n) + 1}:
ifL[i] == L[n]:
returni
return-1
chd(n):// nより後ろ、nと同じ階層の項目より前で、階層がnより1つ大きい最後の項目
c =-1
for i in {n+1, ..., |L|}:
ifL[i] == L[n]:
returnc
elseif L[i] == L[n]+1:
c = i
return c
【０１１０】
また、定義６の右辺において、第１項のユニグラムスコアuについての和は、全目次項目についての和である。第２項の兄弟バイグラムスコアb1についての和は、兄弟関係にある隣接目次項目のペア全てについての和である。第３項の親子バイグラムスコアb2についての和は、親子関係にある目次項目のペア全てについての和である。各スコアの設計方法は、ユニグラムスコアuと兄弟バイグラムスコアb1については、それぞれ実施例１に関して説明したユニグラムスコアu、バイグラムスコアbと同じであるためここでは説明を省略する。そこで以下では、親子バイグラムスコアb2についてその設計方法を説明する。その後で、定義６で示されるスコア関数Sの最大値の探索方法を説明する。
【０１１１】
親子バイグラムスコアb2(i, mi, mpar(i), C,D)は、一の目次項目（i番目の目次項目 (C[i]））と該一の目次項目の親となる目次項目（par(i)番目の目次項目 (C[par(i)]））のペア、即ち親子関係にある目次項目ペアの見出し候補行（mi行目（D[mi]）とmpar(i)行目（D[mpar(i)]））への対応付けの尤もらしさを、親子関係にある目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価したスコアである。なお上述したように、親子バイグラムスコアb2の共通度の評価は、共通度が低いほど高い評価となる。
【０１１２】
共通度に基づく評価の第１の例は、フォーマットの共通度に基づく評価である。即ち、子の目次項目C[i]を対応付けるD[mi]と、親の目次項目C[par(i)]を対応付けるD[mpar(i)]のフォーマットの共通度が低い場合に高いスコアを返すように親子バイグラムスコアb2を設計する。より具体的には、子の目次項目C[i]に対応するD[mi]のフォントサイズと、親の目次項目C[par(i)]に対応するD[mpar(i)]のフォントサイズとの間に大小関係がある場合に高いスコアを返すように親子バイグラムスコアb2を設計する。これは一般に親見出しの方が子見出しよりもフォントサイズが大きいとの知識に基づくものである。
【０１１３】
上記フォントサイズに代えてまたは加えて、子の目次項目C[i]に対応するD[mi]の索引部分が、親の目次項目C[par(i)]に対応するD[mpar(i)]の索引部分とフォーマットが異なる場合に高いスコアを返すように親子バイグラムスコアb2を設計してもよい。索引部分のフォーマットが異なる例を以下に挙げる。親の索引部分―子の索引部分とすると、第１部―第１章、第１章―１．１、１．１―１．１．１、１―（１）、（１）−（ａ）等があるがこれに限定されない。索引部分のフォーマットの判定は、一例として事前に索引部分のフォーマットの正規表現を用意してこれとマッチングさせ、一致したフォーマットが異なれば互いに異なるフォーマットであると判定してよい。例えば「第１章」や「１．１」に対してはそれぞれ次のような正規表現を用意できる。
/第([0-9]+)章/
/([0-9+])\.([0-9]+)/
バリエーションとして、「第二章」のように漢数字であるならば、
/第([一二三四五六七八九]+)章/
また、「１−１」のように「．」でなく「−」であるならば
/([0-9+])−([0-9]+)/
となる。他のフォーマットについても同様にして正規表現を用意できる。
【０１１４】
共通度に基づく評価の第２の例は、目次におけるページ番号と実際のページ番号、即ち、最初のページからの通し番号との差分の共通度に基づく評価である。但し第２の例については、共通度が高いほど高いスコアを返すように親子バイグラムスコアb2を設計する。即ち、C[i]に含まれるページ番号とC[i]に対応付けるD[mi]を含むページの通し番号との差分と、C[par(i)]に含まれるページ番号とC[par(i)]を対応付けるD[mpar(i)]を含むページの通し番号との差分との共通度が高い場合に高いスコアを返すように親子バイグラムスコアb2を設計する。なお、差分の共通度の高さは、一例として差分が同一である場合に共通度が高いとしてよい。
【０１１５】
親子バイグラムスコアb2は、上述した３つの共通度に基づく評価（スコア）のうち任意の数の評価（スコア）を、重み付けをしつつ組み合わせて評価するものであってもよい。複数の評価（スコア）を足し合わせて評価する場合、対応付けのいくつかについてフォントサイズやページ情報を取得できないため全部の評価(スコア）を取得できないとしても、いずれか１つの評価（スコア）を求めることができれば問題はない。また、重み付けは正解データから各スコアの重みを自動学習してもよい。
【０１１６】
次に定義６により表されるスコア関数Sの最大値の算出方法を説明する。定義６により表されるスコア関数Sを最大にする対応付けMの系列は、2nd order Eisnerアルゴリズムを応用して、時間計算量O(|C||D|3)で求めることができる。従って、本文データDの要素、即ち見出し候補行をフィルタリングすることによって、実際の計算時間は更に少なくすることが可能である。フィルタリングは、一例として、実施例１に関して説明した目次項目と該目次項目に対応付ける見出し候補行の文字列の類似度に基づくフィルタリングを適用可能である。以下、2nd order Eisnerアルゴリズムを応用したスコア関数Sの最大値の探索方法を説明する。
【０１１７】
まず、説明を容易にするため、ユニグラムスコアuとバイグラムスコアbの表記を次のように単純化する。なお、以下ではi、l、rはそれぞれ文書中の位置、即ち行番号を示す整数とする。ユニグラムスコアu(c,i)は、c番目の目次項目をi行目の見出し候補行に対応付けたときのユニグラムスコアuを表す。兄弟バググラムスコアb1(c, sib(c), i, l) は、c番目の目次項目をi行目の見出し候補行に、かつ、兄弟関係にあるsib(c)番目の目次項目をl行目の見出し候補行に対応付けたときの兄弟バググラムスコアb1を表す。親子バググラムスコアb2(c,par(c), i, l) は、c番目の目次項目をi行目の見出し候補行に、かつ、親子関係にあるpar(c)番目の目次項目をl行目の見出し候補行に対応付けたときの親子バググラムスコアb2を表す。
【０１１８】
次に新たに２種類の再帰関数を導入する。再帰関数comp(c, l, r)は、c番目の目次項目をルートとする目次のサブツリーが、行番号が{l,…, r-1}の文書中の範囲に対応付けられるときの最大のスコアを返す関数とする。但し、c番目の目次項目はl行目に対応するものとする。また、再帰関数incomp(c, l, r)は、c番目の目次項目の兄に該当する目次項目をルートとする目次のサブツリーを全兄の目次項目について集めた集合が、行番号が{l+1,…, r-1}の文書中の範囲に対応付けられるときの最大のスコアを返す関数とする。但し、c番目の目次項目はr行目に、また、par(c)番目の目次項目はl行目に対応するものとする。
【０１１９】
すると再帰関数comp(c, l, r)とincomp(c, l, r)は、次の２つの再帰式により計算できる。但し、記号maxi{G}は、Gの値がiに依存する場合において最大のGの値を示すものとする。
再帰式１：
comp(c, l, r) = maxi{ incomp(chd(c), l, i) + comp(chd(c), i, r) + u(chd(c), i) + b2(c, chd(c), l, i)}
再帰式２：
incomp(c, l, r) = maxi{incomp(sib(c), l, i) + comp(sib(c),i, r) + u(sib(c), i) + b2(par(c),sib(c), l, i) + b1(sib(c), c, i,r) } ―（再帰式２）
【０１２０】
再帰式１は、chd(c)番目の目次項目がi行目に対応づけられると仮定して、記号maxiを利用してcomp(c, l, r)を書き換えたものである。即ち、上記仮定において、chd(c)番目の目次項目の兄に該当する目次項目をルートとする目次のサブツリーを全兄の目次項目について集めた集合は、行番号が{l+1,…, i-1}の範囲に対応付けられる。また、chd(c)番目の目次項目をルートとする目次のサブツリーは、行番号が{i,…, r-1}の範囲に対応付けられる。なお、comp(c, l, r)の定義から、c番目の目次項目はl行目に対応付けられることに留意されたい。
【０１２１】
また、再帰式２は、sib(c) 番目の目次項目がi行目に対応づけられると仮定して、記号maxiを利用してincomp(c, l, r)を書き換えたものである。即ち、上記仮定において、sib(c)番目の目次項目の兄に該当する目次項目をルートとする目次のサブツリーを全兄の目次項目について集めた集合は、行番号が{l+1,…, i-1}の範囲に対応付けられる。また、sib(c)番目の目次項目をルートとする目次のサブツリーは、行番号が{i,…, r-1}の範囲に対応付けられる。なお、incomp(c,l, r)の定義から、c番目の目次項目はr行目に、また、par(c)番目の目次項目はl行目に対応対応付けられることに留意されたい。
【０１２２】
スコア関数Sの最大値の探索は、再帰関数comp(c, l, r)において目次のツリー全体の最大スコアを求めることに等しい。即ち、スコア関数Sの最大値は、上記再帰関数を利用して、comp(0, 0, |D|+1)として求められる。そして、スコア関数Sを最大とする目次と本文見出しの対応付けMは、comp(0, 0, |D|+1)を求める際に再帰的に呼び出されるcomp(c,l, r)の各々の計算において最大値を与えるchd(c)番目の目次項目についての対応付けと、同じく再帰的に呼び出されるincomp(c,l, r)の各々の計算において最大値を与えるsib(c) 番目の目次項目についての対応付けの集合として求められる。
【０１２３】
なお、本実施例では、上記対応付けの集合を対応付けMとして出力するために更に２つの再帰関数を用意する。第１の再帰関数getcomp(c,l, r)は、comp(c, l, r)の計算において最大値を与えるchd(c)番目の目次項目の対応付けをM[chd(c)]に設定した後、後述する第２の再帰関数と自分自身とを呼び出す再帰関数である。第２の再帰関数getincomp(c,l, r)は、incomp(c,l, r)の計算において最大値を与えるsib(c)番目の目次項目の対応付けをM[sib (c)]に設定した後、自分自身と第１の再帰関数とを呼び出す再帰関数である。これら２つの再帰関数を計算方法の詳細は、図１８及び図１９に示すフローチャートを参照して後述する。
【０１２４】
次に図１４から１９を参照して、実施例２に係る目次と見出しの自動対応付け装置３００による処理の流れを説明する。図１４は、自動対応付け装置３００による処理の全体の流れの一例を示すフローチャートである。図１５は、図１４に示すフローチャートのステップ１４０４の見出し候補行の決定処理の流れの一例を示すフローチャートである。図１６は、再帰関数comp(c, l, r)の計算処理の流れの一例を示すフローチャートである。図１７は、再帰関数incomp(c, l, r)の計算処理の流れの一例を示すフローチャートである。図１８は、再帰関数getcomp(c, l, r)処理の流れの一例を示すフローチャートである。図１９は、再帰関数getincomp(c, l, r)処理の流れの一例を示すフローチャートである。
【０１２５】
まず、図１４を参照して目次と見出しの自動対応付けの全体処理の流れを説明する。図１４に示す自動対応付けの全体処理はステップ１４００から開始し、自動対応付け装置３００は、記憶装置からまたはネットワークを介して他のコンピュータから、目次項目単位の目次データCと行単位の本文データDを入力する（ステップ１４００、ステップ１４０２）。続いて自動対応付け装置３００は、入力した目次データCと本文データDとを使用して、目次項目ごと、対応付けを検討すべき見出し候補行を決定する（ステップ１４０４）。見出し候補行決定処理の詳細は、図１５を参照して後述する。
【０１２６】
続いて自動対応付け装置３００は、整数の３つ組みを取るハッシュテーブルcmax、imax、cbest、ibestを用意し、それぞれ−∞で初期化する（ステップ１４０６）。ここでcmaxは、(c, l, r)をキーとして再帰関数comp(c,l, r)の最大値を返すハッシュテーブルである。imaxは、(c, l, r)をキーとして再帰関数incomp(c, l, r)の最大値を返すハッシュテーブルである。cbestは、(c, l, r)をキーとして再帰関数comp(c,l, r)の計算において最大値を与えたchd(c)番目の目次項目の対応付け結果を返すハッシュテーブルである。ibestは、(c, l, r)をキーとして再帰関数incomp(c, l, r)の計算において最大値を与えたsib(c)番目の目次項目の対応付け結果を返すハッシュテーブルである。
【０１２７】
続いて自動対応付け装置３００は、comp(0, 0, | D|+1)を呼び出して、スコア関数Ｓの最大値を求める（ステップ１４０８）。comp(0, 0, | D|+1)の呼び出し処理の詳細は、再帰関数comp(c, l, r)の計算処理の詳細に代えて図１６を参照して後述する。続いて自動対応付け装置３００は、対応付けMの配列mを用意する（ステップ１４１０）。続いて自動対応付け装置３００は、getcomp(0,0,|D|+1)を呼び出してスコア関数Ｓを最大にする対応付けを配列mに設定する（ステップ１４１２）。getcomp(0,0,|D|+1)の呼び出し処理の詳細は、再帰関数getcomp (c, l, r)の計算処理の詳細に代えて図１８を参照して後述する。最後に自動対応付け装置３００は、配列mを求めるべき目次と見出しの対応付けとして出力する（ステップ１４１４）。そして処理は終了する。
【０１２８】
次に図１５を参照して、見出し候補行の決定処理の詳細を説明する。ここでは実施例１に関して説明した文字列の類似度に基づく第２フィルタリングを利用して見出し候補行の絞り込みを行う。図１５に示す見出し候補決定処理はステップ１５００から開始し、自動対応付け装置３００はまず２次元配列candsを用意する。２次元配列candsの各要素への値の設定は続く処理において行うが、目次項目のc番目に対しcands[c]は、c番目の目次項目との対応付けを検討すべき見出し候補行の配列を表すものとする。
【０１２９】
２次元配列candsを用意すると続いて自動対応付け装置３００は、２次元配列cands [0]に0を設定する（ステップ１５０２）。続いて自動対応付け装置３００は、ステップ１５０４及び該当する場合はステップ１５０６の処理を、第１のループ及び第２のループにより繰り返す。第１のループは、変数cを1から目次項目数|C|まで１つずつ増やし繰り返すループである。第２のループは、変数cの値に対し変数dを1から本文の全行数|D|まで１つずつ増やしながら繰り返すループである。
【０１３０】
ステップ１５０４において、自動対応付け装置３００は、c番目の目次項目C[c]の文字列とd番目の行D[d]の文字列との類似度が許容できる最小の類似度MINSIMより大きいか否かを判定する。類似度の判定は、既に説明した通り、編集距離等の既存技術を利用してよい。類似度がMINSIMより大きい場合（ステップ１５０４：ＹＥＳ）、自動対応付け装置３００は、cands[c]に見出し候補行としてd番目の行を追加する（ステップ１５０６）。類似度がMINSIM以下の場合（ステップ１５０４：ＮＯ）、またはステップ１５０６の処理の後、自動対応付け装置３００は、第１及び第２の全てのループを抜け出すまで上記一連の処理を繰り返す。そして処理は終了する。
【０１３１】
次に図１６を参照して、再帰関数comp(c, l, r)の計算処理の詳細を説明する。図１６に示す再帰関数comp(c, l, r)の計算処理はステップ１６００から開始し、自動対応付け装置３００は、cmax(c, l, r)が−∞に等しいか否かを判定する。これはcompが再帰関数であることから、同じ引数について対してcompが既に計算済みであるならばその結果を再利用するためである。cmax(c, l, r)≠-∞である場合（ステップ１６００：ＮＯ）、即ち、現在の引数に対しcompの値が既に算出されている場合、自動対応付け装置３００はステップ１６２４へ進み、変数maxにcmax[c, l, r]の値を設定する。一方、cmax(c, l, r)の値が-∞である場合（ステップ１６００：ＹＥＳ）、即ち、現在の引数に対して未だcompの値が算出されていない場合、自動対応付け装置３００はchd(c)の値を変数c’に設定する（ステップ１６０２）。
【０１３２】
続いて自動対応付け装置３００は変数c’の値がnullであるか否かを判定する（ステップ１６０４）。変数c’の値がnullの場合（ステップ１６０４：ＹＥＳ）、即ち、c番目の目次項目に対して子の関係にある目次項目が存在しない場合、自動対応付け装置３００はステップ１６２２へ進み、変数maxに0を設定する。一方、変数c’の値がnullでない場合（ステップ１６０４：ＮＯ）、自動対応付け装置３００は、上述した再帰式１の右辺の最大値を求めるための変数maxを用意し、これを−∞で初期化する（ステップ１６０６）。自動対応付け装置３００はまた、上記右辺の最大値を与えるchd(c)番目の目次項目の対応付けを保持しておくための変数bestを用意し、これを0で初期化する。
【０１３３】
続いて自動対応付け装置３００は、再帰式１の右辺の最大値を求めるために、続くステップ１６０８からステップ１６１４までの処理をループにより繰り返す。ここでループは、c’番目の目次項目についての見出し候補行の配列から順に１の見出し候補行（i番目の行）を取り出して繰り返すループである。ステップ１６０８において、自動対応付け装置３００は、l < i < r であるか否かを判定する。これは、c’番目の目次項目に対応する見出し候補行（i番目の行）が、行番号が{l+1, …, r-1}の範囲にあることを確認するためである。l < i < rである場合（ステップ１６０８：ＹＥＳ）、自動対応付け装置３００は変数sを用意して、これにincomp(c’, l, i) + comp(c’, i,r) + u(c’, i) + b2(c, c’, l, i)の値を設定する（ステップ１６１０）。なお、再帰関数incompの計算処理の詳細は図１７を参照して後述する。
【０１３４】
続いて自動対応付け装置３００は、max< sであるか否かを判定する（ステップ１６１２）。max< sである場合（ステップ１６１２：ＹＥＳ）、自動対応付け装置３００は、変数maxに変数sの値を、また、変数bestに変数iの値を設定する（ステップ１６１４）。ステップ１６０８においてl < i < r でない場合、また、ステップ１６１２においてmax < sでない場合、またはステップ１６１４の後、自動対応付け装置３００は上記ループを抜け出すまで一連の処理を繰り返す。
【０１３５】
ループを抜けると続いて自動対応付け装置３００は、変数maxの値をハッシュテーブルcmax[c,l, r]の値として、また、変数bestの値をハッシュテーブルcbest[c,l, r]の値として設定する（ステップ１６１６、ステップ１６１８）。ステップ１６２２、ステップ１６２４、またはステップ１６１８から、自動対応付け装置３００はステップ１６２０へ進み、変数maxの値を返す。そして処理は終了する。
【０１３６】
次に図１７を参照して、再帰関数incomp(c, l, r)の計算処理の詳細を説明する。図１７に示す再帰関数incomp(c, l, r)の計算処理はステップ１７００から開始し、自動対応付け装置３００は、imax(c, l, r)が−∞に等しいか否かを判定する。これはincompが再帰関数であることから、同じ引数に対してincompが既に計算済みであるならばその結果を再利用するためである。imax(c, l, r)≠-∞である場合（ステップ１７００：ＮＯ）、即ち、現在の引数に対しincompの値が既に算出されている場合、自動対応付け装置３００はステップ１７２４へ進み、変数maxにimax[c, l, r]の値を設定する。一方、imax(c, l, r)の値が-∞である場合（ステップ１６００：ＹＥＳ）、即ち、現在の引数に対して未だincompの値が算出されていない場合、自動対応付け装置３００はsib(c)の値を変数c’に設定する（ステップ１７０２）。
【０１３７】
続いて自動対応付け装置３００は変数c’の値がnullであるか否かを判定する（ステップ１７０４）。変数c’の値がnullの場合（ステップ１７０４：ＹＥＳ）、即ち、c番目の目次項目に対して兄の関係にある目次項目が存在しない場合、自動対応付け装置３００はステップ１７２２へ進み、変数maxに0を設定する。一方、変数c’の値がnullでない場合（ステップ１７０４：ＮＯ）、自動対応付け装置３００は、上述した再帰式２の右辺の最大値を求めるための変数maxを用意し、これを−∞で初期化する（ステップ１７０６）。自動対応付け装置３００はまた、上記右辺の最大値を与えるsib(c)番目の目次項目の対応付けを保持しておくための変数bestを用意し、これを0で初期化する。
【０１３８】
続いて自動対応付け装置３００は、再帰式２の右辺の最大値を求めるために、続くステップ１７０８からステップ１７１４までの処理をループにより繰り返す。ここでループは、c’番目の目次項目についての見出し候補行の配列から順に１の見出し候補行（i番目の行）を取り出して繰り返すループである。ステップ１７０８において、自動対応付け装置３００は、l < i < r であるか否かを判定する。これは、c’番目の目次項目に対応する見出し候補行（i番目の行）が、行番号が{l+1, …, r-1}の範囲にあることを確認するためである。l < i < rである場合（ステップ１７０８：ＹＥＳ）、自動対応付け装置３００は変数sを用意して、これにincomp(c’, l, i) + comp(c’, i,r) + u(c’, i) + b2(par(c’), c’, l, i) + b1(c’ c, i, r)の値を設定する（ステップ１７１０）。
【０１３９】
続いて自動対応付け装置３００は、max< sであるか否かを判定する（ステップ１７１２）。max< sである場合（ステップ１７１２：ＹＥＳ）、自動対応付け装置３００は、変数maxに変数sの値を、また、変数bestに変数iの値を設定する（ステップ１７１４）。ステップ１７０８においてl < i < r でない場合、また、ステップ１６１２においてmax < sでない場合、またはステップ１６１４の後、自動対応付け装置３００は上記ループを抜け出すまで一連の処理を繰り返す。
【０１４０】
ループを抜けると続いて自動対応付け装置３００は、変数maxの値をハッシュ関数imax[c, l, r]の値として、また、変数bestの値をハッシュ関数ibest[c, l, r]の値として設定する（ステップ１７１６、ステップ１７１８）。ステップ１７２２、ステップ１７２４、またはステップ１７１８から、自動対応付け装置３００はステップ１７２０へ進み、変数maxの値を返す。そして処理は終了する。
【０１４１】
次に、再帰関数getcomp、getincompの計算処理の流れを説明する前に、図１３（ｂ）を参照して対応付けMの配列の復元順序を説明する。なお、図１３（ｂ）に示す復元順序は、１３（ａ）に示す目次を例にしており、矩形で示す目次項目の下の数字は復元順序を示している。数字を見ると分かるように、復元順序は、階層レベルの低い順、同階層であるならば右優先である。
【０１４２】
次に図１８を参照して、再帰関数getcomp(c, l, r)の計算処理の詳細を説明する。図１８に示す再帰関数getcomp(c, l, r)の計算処理はステップ１８００から開始し、自動対応付け装置３００は、chd(c)の値を変数c’に設定し、変数c’の値がnullであるか否かを判定する（ステップ１８０２）。変数c’の値がnullの場合（ステップ１８０４：ＹＥＳ）、即ち、c番目の目次項目に対して子の関係にある目次項目が存在しない場合処理は終了する。
【０１４３】
一方、変数c’の値がnullでない場合（ステップ１８０２：ＮＯ）、自動対応付け装置３００は、ハッシュ関数cbest[c, l, r]の値を変数iに設定する（ステップ１８０４）。続いて自動対応付け装置３００は、変数iの値を対応付けMの配列要素m[c’]に設定する（ステップ１８０６）。続いて、自動対応付け装置３００は、再帰関数getincomp(c’, l, i)を呼び出す。再帰関数getincompの計算処理の詳細は図１９を参照して後述する。続いて自動対応付け装置３００は、getcomp(c’, i, r)を呼び出す。そして処理は終了する。
【０１４４】
次に図１９を参照して、再帰関数getincomp(c, l, r)の計算処理の詳細を説明する。図１８に示す再帰関数getincomp(c, l, r)の計算処理はステップ１９００から開始し、自動対応付け装置３００は、sib(c)の値を変数c’に設定し、変数c’の値がnullであるか否かを判定する（ステップ１９０２）。変数c’の値がnullの場合（ステップ１９０４：ＹＥＳ）、即ち、c番目の目次項目に対して兄の関係にある目次項目が存在しない場合処理は終了する。
【０１４５】
一方、変数c’の値がnullでない場合（ステップ１９０２：ＮＯ）、自動対応付け装置３００は、ハッシュ関数ibest[c, l, r]の値を変数iに設定する（ステップ１９０４）。続いて自動対応付け装置３００は、変数iの値を対応付けMの配列要素m[c’]に設定する（ステップ１９０６）。続いて、自動対応付け装置３００は、再帰関数getincomp(c’, l, i)を呼び出す。続いて自動対応付け装置３００は、getcomp(c’, i, r)を呼び出す。そして処理は終了する。
【０１４６】
図２０は、本実施形態に係るコンピュータ５０のハードウェア構成の一例を示した図である。コンピュータ５０は、バス２に接続されたメインＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、及びＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。
【０１４７】
フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ１に命令を与え、本願発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、上記説明した数々の記憶装置には、コンピュータ５０にインストールされ、コンピュータ５０を自動対応付け装置３００として機能させる目次および見出しの自動対応付けプログラムや目次データC、本文データD等のデータ、更には、自動対応付けの結果である出力データMを記録することができる。
【０１４８】
上記自動対応付けプログラムは、入力モジュールと、探索モジュールと、出力モジュールとを含む。これらモジュールは、ＣＰＵ１に働きかけて、コンピュータ５０を、入力部３０２、探索部３０４と、出力部３０６としてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。
【０１４９】
コンピュータ５０は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。コンピュータ５０は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。コンピュータ５０は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。コンピュータ５０は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。
【０１５０】
以上の説明により、本実施形態に係るコンピュータ５０は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本願発明の必須構成要素となるわけではない。
【０１５１】
以上、実施形態を用いて本願発明の説明をしたが、本願発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更又は改良を加えることが可能であることが当業者に明らかである。従って、そのような変更又は改良を加えた形態も当然に本願発明の技術的範囲に含まれる。
【０１５２】
なお、特許請求の範囲、明細書、及び図面中において示した装置、システム、プログラム、及び方法における動作、手順、ステップ、及び段階等の各処理の実行順序は、特段「より前に」、「先立って」等と明示しておらず、また、前の処理の出力を後の処理で用いるのでない限り任意の順序で実現しうることに留意すべきである。また、前の処理の出力を後の処理で用いる場合でも、前の処理と後の処理の間に他の処理が入ることは可能である場合があること、又は間に他の処理が入るように記載されていても前の処理を後の処理の直前に行うよう変更することも可能である場合があることも留意されたい。特許請求の範囲、明細書、及び図面中の動作フローに関して、便宜上「まず、」、「次に、」、「続いて、」等を用いて説明したとしても、この順で実施することが必須であることを必ずしも意味するとは限らない。
【特許請求の範囲】
【請求項１】
コンピュータの演算処理により、文書の目次内の目次項目を前記文書の本文中の見出し行に対応付ける、目次と見出しの対応付け方法であって、
前記コンピュータが、前記文書の目次項目単位の目次データCを受け取るステップと、
前記コンピュータが、前記文書の行単位の本文データDを受け取るステップと、
前記コンピュータが、前記目次データC内の全目次項目の前記本文データD内の見出し候補としての行である見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索するステップと、
前記コンピュータが、前記スコア関数Sを最大にする前記対応付けMを出力するステップとを含み、
前記スコア関数Sは、各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアuを全目次項目について足し合わせた第１の和と、一の目次項目と他の目次項目のペアである目次項目ペアの見出し候補行への対応付けの尤もらしさを前記目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価するバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求められる、
目次と見出しの対応付け方法。
【請求項２】
前記目次はフラット構造を有し、前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列との類似度に基づき求められ、前記バイグラムスコアbは、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度に基づき求められる、請求項１に記載の目次と見出しの対応付け方法。
【請求項３】
前記バイグラムスコアbは更に、前記目次項目ペアのそれぞれの対応付けにおける、目次項目に含まれるページ番号と該目次項目に対応付ける見出し候補行が含まれるページの通し番号との差の共通度に基づいて求められる、請求項２に記載の目次と見出しの対応付け方法。
【請求項４】
前記一の目次項目と前記他の目次項目とは隣接関係にある、請求項１に記載の目次と見出しの対応付け方法。
【請求項５】
前記目次は木構造を有し、前記一の目次項目と隣接関係にある前記他の目次項目を、前記目次の木構造において前記一の目次項目と同一階層において隣り合う兄弟関係にある目次項目に限定する、請求項４に記載の目次と見出しの対応付け方法。
【請求項６】
前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列との類似度に基づき求められ、前記バイグラムスコアbは、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度に基づき求められる、請求項５に記載の目次と見出しの対応付け方法。
【請求項７】
前記フォーマットの共通度は、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォントサイズの共通度と、前記目次項目ペアのそれぞれに対応付ける見出し候補行の文字列の最初の文字又は最初の文字と最後の文字との共通度と、前記目次項目ペアにそれぞれ対応付ける見出し候補行の文字列のうち、対応付ける目次項目の文字列に類似する部分である類似文字列の前後の所定数の文字の共通度のうちの少なくとも１つの共通度である、請求項６に記載の目次と見出しの対応付け方法。
【請求項８】
前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列の類似度に基づき求められ、前記バイグラムスコアbは更に、前記目次項目ペアのそれぞれの対応付けにおける、目次項目に含まれるページ番号と該目次項目に対応付ける見出し候補行が含まれるページの通し番号との差の共通度に基づいて求められる、請求項６に記載の目次と見出しの対応付け方法。
【請求項９】
前記バイグラムスコアbは、前記一の目次項目に対応付ける一の見出し候補行と、前記他の目次項目に対応付ける他の見出し候補行とが隣接している場合に値を減じられる、請求項８に記載の目次と見出しの対応付け方法。
【請求項１０】
前記一の目次項目に隣接する目次項目に、前記一の目次項目に所定の数以下の目次項目を挟んで隣接する目次項目を含める、請求項４に記載の目次と見出しの対応付け方法。
【請求項１１】
前記スコア関数Sの最大値は、Viterbiアルゴリズムに従い探索される、請求項４に記載の目次と見出しの対応付け方法。
【請求項１２】
前記スコア関数Sの最大値は、ダイクストラ法に従い探索される、請求項４に記載の目次と見出しの対応付け方法。
【請求項１３】
前記スコア関数Sの最大値の探索において、前記目次データCに含まれる各目次項目にそれぞれ対応付ける前記見出し候補行を、本文データD内の全行のうち、前記目次項目の文字列と一定以上の類似度を有する文字列の行に限定する、請求項４に記載の目次と見出しの対応付け方法。
【請求項１４】
前記目次は木構造を有し、前記木構造において同一階層において隣り合う兄弟関係にある前記目次項目ペアに対しては、前記バイグラムスコアbとして、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度が高いほど高いスコア値を返す兄弟バイグラムスコアb1を採用し、前記木構造において親子関係にある前記目次項目ペアに対しては、前記バイグラムスコアbとして、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度が低いほど高いスコア値を返す親子バイグラムスコアb2を採用する、請求項１に記載の目次と見出しの対応付け方法。
【請求項１５】
前記親子バイグラムスコアb2は、親である目次項目に対応付ける見出し候補行のフォントサイズと、子である目次項目に対応付ける見出し候補行のフォントサイズの間に大小関係がある場合に高いスコア値を返す、請求項１４に記載の目次と見出しの対応付け方法。
【請求項１６】
前記親子バイグラムスコアb2は、親である目次項目に対応付ける見出し候補行の索引部分と子である目次項目に対応付ける見出し候補行の索引部分のフォーマットが異なる場合に高いスコア値を返す、請求項１４に記載の目次と見出しの対応付け方法。
【請求項１７】
前記スコア関数Sの最大値は、2nd order Eisnerを応用したアルゴリズムに従い探索される、請求項１４に記載の目次と見出しの対応付け方法。
【請求項１８】
前記スコア関数Sの最大値の探索において、前記目次データCに含まれる各目次項目にそれぞれ対応付ける前記見出し候補行を、本文データD内の全行のうち、前記目次項目の文字列と一定以上の類似度を有する文字列を含む行に限定する、請求項１７に記載の目次と見出しの対応付け方法。
【請求項１９】
請求項１乃至１８に記載の方法をコンピュータに実行させる、目次と見出しの対応付けプログラム。
【請求項２０】
文書の目次内の目次項目を前記文書の本文中の見出し行に対応付ける、目次と見出しの対応付け装置であって、
前記文書の目次項目単位の目次データCと、前記文書の行単位の本文データDとを入力する入力部と、
前記目次データC内の全目次項目の前記本文データD内の見出し候補としての行である見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索する探索部と、
前記スコア関数Sを最大にする前記対応付けMを出力する出力部とを含み、
前記探索部は、前記スコア関数Sを、各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアuを全目次項目について足し合わせた第１の和と、一の目次項目と他の目次項目のペアである目次項目ペアの見出し候補行への対応付けの尤もらしさを前記目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価するバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求める、
目次と見出しの対応付け装置。
【請求項１】
コンピュータの演算処理により、文書の目次内の目次項目を前記文書の本文中の見出し行に対応付ける、目次と見出しの対応付け方法であって、
前記コンピュータが、前記文書の目次項目単位の目次データCを受け取るステップと、
前記コンピュータが、前記文書の行単位の本文データDを受け取るステップと、
前記コンピュータが、前記目次データC内の全目次項目の前記本文データD内の見出し候補としての行である見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索するステップと、
前記コンピュータが、前記スコア関数Sを最大にする前記対応付けMを出力するステップとを含み、
前記スコア関数Sは、各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアuを全目次項目について足し合わせた第１の和と、一の目次項目と他の目次項目のペアである目次項目ペアの見出し候補行への対応付けの尤もらしさを前記目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価するバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求められる、
目次と見出しの対応付け方法。
【請求項２】
前記目次はフラット構造を有し、前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列との類似度に基づき求められ、前記バイグラムスコアbは、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度に基づき求められる、請求項１に記載の目次と見出しの対応付け方法。
【請求項３】
前記バイグラムスコアbは更に、前記目次項目ペアのそれぞれの対応付けにおける、目次項目に含まれるページ番号と該目次項目に対応付ける見出し候補行が含まれるページの通し番号との差の共通度に基づいて求められる、請求項２に記載の目次と見出しの対応付け方法。
【請求項４】
前記一の目次項目と前記他の目次項目とは隣接関係にある、請求項１に記載の目次と見出しの対応付け方法。
【請求項５】
前記目次は木構造を有し、前記一の目次項目と隣接関係にある前記他の目次項目を、前記目次の木構造において前記一の目次項目と同一階層において隣り合う兄弟関係にある目次項目に限定する、請求項４に記載の目次と見出しの対応付け方法。
【請求項６】
前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列との類似度に基づき求められ、前記バイグラムスコアbは、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度に基づき求められる、請求項５に記載の目次と見出しの対応付け方法。
【請求項７】
前記フォーマットの共通度は、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォントサイズの共通度と、前記目次項目ペアのそれぞれに対応付ける見出し候補行の文字列の最初の文字又は最初の文字と最後の文字との共通度と、前記目次項目ペアにそれぞれ対応付ける見出し候補行の文字列のうち、対応付ける目次項目の文字列に類似する部分である類似文字列の前後の所定数の文字の共通度のうちの少なくとも１つの共通度である、請求項６に記載の目次と見出しの対応付け方法。
【請求項８】
前記ユニグラムスコアuは、前記目次項目の文字列と、該目次項目に対応付ける前記見出し候補行の文字列の類似度に基づき求められ、前記バイグラムスコアbは更に、前記目次項目ペアのそれぞれの対応付けにおける、目次項目に含まれるページ番号と該目次項目に対応付ける見出し候補行が含まれるページの通し番号との差の共通度に基づいて求められる、請求項６に記載の目次と見出しの対応付け方法。
【請求項９】
前記バイグラムスコアbは、前記一の目次項目に対応付ける一の見出し候補行と、前記他の目次項目に対応付ける他の見出し候補行とが隣接している場合に値を減じられる、請求項８に記載の目次と見出しの対応付け方法。
【請求項１０】
前記一の目次項目に隣接する目次項目に、前記一の目次項目に所定の数以下の目次項目を挟んで隣接する目次項目を含める、請求項４に記載の目次と見出しの対応付け方法。
【請求項１１】
前記スコア関数Sの最大値は、Viterbiアルゴリズムに従い探索される、請求項４に記載の目次と見出しの対応付け方法。
【請求項１２】
前記スコア関数Sの最大値は、ダイクストラ法に従い探索される、請求項４に記載の目次と見出しの対応付け方法。
【請求項１３】
前記スコア関数Sの最大値の探索において、前記目次データCに含まれる各目次項目にそれぞれ対応付ける前記見出し候補行を、本文データD内の全行のうち、前記目次項目の文字列と一定以上の類似度を有する文字列の行に限定する、請求項４に記載の目次と見出しの対応付け方法。
【請求項１４】
前記目次は木構造を有し、前記木構造において同一階層において隣り合う兄弟関係にある前記目次項目ペアに対しては、前記バイグラムスコアbとして、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度が高いほど高いスコア値を返す兄弟バイグラムスコアb1を採用し、前記木構造において親子関係にある前記目次項目ペアに対しては、前記バイグラムスコアbとして、前記目次項目ペアのそれぞれに対応付ける見出し候補行のフォーマットの共通度が低いほど高いスコア値を返す親子バイグラムスコアb2を採用する、請求項１に記載の目次と見出しの対応付け方法。
【請求項１５】
前記親子バイグラムスコアb2は、親である目次項目に対応付ける見出し候補行のフォントサイズと、子である目次項目に対応付ける見出し候補行のフォントサイズの間に大小関係がある場合に高いスコア値を返す、請求項１４に記載の目次と見出しの対応付け方法。
【請求項１６】
前記親子バイグラムスコアb2は、親である目次項目に対応付ける見出し候補行の索引部分と子である目次項目に対応付ける見出し候補行の索引部分のフォーマットが異なる場合に高いスコア値を返す、請求項１４に記載の目次と見出しの対応付け方法。
【請求項１７】
前記スコア関数Sの最大値は、2nd order Eisnerを応用したアルゴリズムに従い探索される、請求項１４に記載の目次と見出しの対応付け方法。
【請求項１８】
前記スコア関数Sの最大値の探索において、前記目次データCに含まれる各目次項目にそれぞれ対応付ける前記見出し候補行を、本文データD内の全行のうち、前記目次項目の文字列と一定以上の類似度を有する文字列を含む行に限定する、請求項１７に記載の目次と見出しの対応付け方法。
【請求項１９】
請求項１乃至１８に記載の方法をコンピュータに実行させる、目次と見出しの対応付けプログラム。
【請求項２０】
文書の目次内の目次項目を前記文書の本文中の見出し行に対応付ける、目次と見出しの対応付け装置であって、
前記文書の目次項目単位の目次データCと、前記文書の行単位の本文データDとを入力する入力部と、
前記目次データC内の全目次項目の前記本文データD内の見出し候補としての行である見出し候補行への対応付けMの尤もらしさを示す、C、D及びMの関数であるスコア関数Sの最大値を探索する探索部と、
前記スコア関数Sを最大にする前記対応付けMを出力する出力部とを含み、
前記探索部は、前記スコア関数Sを、各目次項目の見出し候補行への対応付けの尤もらしさを該対応付け単独で評価するユニグラムスコアuを全目次項目について足し合わせた第１の和と、一の目次項目と他の目次項目のペアである目次項目ペアの見出し候補行への対応付けの尤もらしさを前記目次項目ペアのそれぞれの見出し候補行への対応付けの共通度に基づき評価するバイグラムスコアbを全目次項目ペアについて足し合わせた第２の和との合計として求める、
目次と見出しの対応付け装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２０１２−１６００００（Ｐ２０１２−１６００００Ａ）
【公開日】平成２４年８月２３日（２０１２．８．２３）
【国際特許分類】
【出願番号】特願２０１１−１８９７８（Ｐ２０１１−１８９７８）
【出願日】平成２３年１月３１日（２０１１．１．３１）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２４年８月２３日（２０１２．８．２３）
【国際特許分類】
【出願日】平成２３年１月３１日（２０１１．１．３１）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]