(57)【要約】【課題】ヘッダ／フッタ等のページ区切り要素が本文テキストの流れを妨げ例えば後段の処理にて雑音になることを防ぎ、既存文書群を効率的且つロバスト的に構造化文書化できるようにする。【解決手段】既存文書１０の構造化文書化（１２）に当たり、然るべき概略位置にある文書内コンテンツを識別乃至特定し（１４）、その文書内コンテンツにおけるテキスト変異度２０を計算し（１８）、テキスト変異度計算結果をテキスト変異度２０によるヘッダ／フッタ該当条件と照合し（２２）、何れもヘッダ／フッタ該当条件を満足している互いに隣り合った文書内コンテンツを選択し（２２）、選択した文書内コンテンツ同士を関連付け関連付けた文書内コンテンツ群をヘッダ／フッタと認定する（２４）。【選択図】図１
2006195980.tif 000002
【特許請求の範囲】
【請求項１】
既存文書の構造化文書化の際に使用される文書内ヘッダ／フッタ識別乃至特定方法であって、
然るべき概略位置にある文書内コンテンツを識別乃至特定するステップと、
識別乃至特定された文書内コンテンツにおけるテキスト変異度を計算するステップと、
このテキスト変異度計算結果をテキスト変異度によるヘッダ／フッタ該当条件に照合するステップと、
何れもヘッダ／フッタ該当条件を満足している互いに隣り合った文書内コンテンツ同士を関連付け関連付けた文書内コンテンツ群をヘッダ／フッタと認定するステップと、
を有する方法。
【請求項２】
請求項１記載の方法であって、関連付けステップが、ヘッダ／フッタと見なして然るべき概略位置にあり且つテキスト変異度によるヘッダ／フッタ該当条件を満足している文書内コンテンツをヘッダ／フッタゾーン内コンテンツとして初期識別するステップと、ヘッダ／フッタゾーン内コンテンツとして識別済の文書内コンテンツと隣り合っており且つテキスト変異度による上記の又は別のヘッダ／フッタ該当条件を満足している文書内コンテンツをヘッダ／フッタゾーン内コンテンツとして識別済の文書内コンテンツと統合していくステップと、を含み、これによりヘッダ／フッタを識別乃至特定する方法。
【請求項３】
文書内ヘッダ／フッタ識別乃至特定装置であって、
文書を複数ページ及び複数テキストブロックに細分することにより、互いに区別可能で且つそのページ内概略位置乃至概略ゾーンを識別可能な複数個のテキストブロックを得るテキストフラグメンタと、
ページ内所定概略位置乃至概略ゾーン内にあるテキストブロックの総数対総種類数の関係を示すテキスト変異度スコア（ＴＶＳ）をテキストブロック毎に計算するプロセッサと、
ヘッダ／フッタ内要素であることを示すＴＶＳ値を有するテキストブロックをヘッダ／フッタ内テキストブロック候補として選んでそのテキストブロック内のテキスト型コンテンツを集め、集めたヘッダ／フッタ内コンテンツ候補群をヘッダ／フッタと認定するセレクタと、
を備える装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報記憶処理技術に関する。本発明の用途としては例えば電子文書の文書フォーマット変換がある。特に、既存文書群（legacy documents）からＸＭＬ（extensible markup language）、ＳＧＭＬ（standard generalized markup language）、ＨＴＭＬ（hypertext markup language）等のマークアップ言語フォーマットによる既存文書目録を作成する際に、本発明を利用することができる。そのため、以下の説明においてはこの種の用途を中心に記述を行うが、本発明が他種類似用途にも適用可能なものであること及びそのように変形可能なものであることを、理解されたい。
【背景技術】
【０００２】
既存文書変換（legacy document conversion）は、非構造化文書から構造化文書への変換即ち構造化文書化に基礎を置く処理である。非構造化文書とは、Ａｄｏｂｅ（商標）ＰＤＦ（portable document format）、各種テキストフォーマット、各種ワードプロセッサフォーマット等のフォーマットで作成済の文書をいう。また、構造化文書とは、適当な区切り要素によって複数個のセクションに区切られた組織的構造を有する文書であり、例えばＸＭＬ、ＳＧＭＬ、ＨＴＭＬ等のマークアップ言語を用いて記述されている。構造化文書における区切り要素には、例えば各ページに付されたヘッダ／フッタ、各表のヘッダ等がある。例えばページ割りされている文書においては、そのコンテンツがヘッダ／フッタ等の適当なページ区切り要素（pagination construct）により複数個の文書ページに区切られている。また、１個の表が複数ページにまたがっていてその表の中であるテキストが繰り返し現れている場合は、そのテキストがテキスト型ページ区切り要素として使用される。また、構造化文書におけるこうした組織的構造は、通常はマークアップタグを用いて実現される。ある種の構造化文書フォーマット例えばＸＭＬフォーマットにおいては、ＤＴＤ（document type definition:文書型定義）又はこれに類する文書部分によって、各セクションを識別する情報等、その文書全体についての情報が与えられる。こうした文書部分があるので、ＸＭＬ等の構造化文書フォーマットは、複数個のセクションによる入れ子構造等といった複雑な構造を有する文書を作成するのに、好都合である。
【０００３】
構造化文書化に興味が集まっているのは、適当な構造さえあればより便利に既存文書の保存及び既存文書に対するアクセスを行えるからである。構造化文書化に特有の動機は多様であるが、大抵は文書又は文書構成部分の再利用及び転用という意図の下に、情報格納データベース全体に亘り文書の均一性を高め、それによって文書検索等を至便に行えるようにすることが目論まれている。従って、技術マニュアル、ユーザマニュアルその他の有価値参照文書群が、広範に既存文書変換の対象となり得る。
【０００４】
【特許文献１】米国特許第５４３４９６２号明細書
【特許文献２】米国特許第５４９１６２８号明細書
【特許文献３】米国特許第６２９８３５７号明細書（Ｂ１）
【特許文献４】米国特許第６４８７５６６号明細書（Ｂ１）
【特許文献５】米国特許第６４９０６０３号明細書（Ｂ１）
【特許文献６】米国特許出願公開第２００２／１４３８１８号明細書（Ａ１）
【特許文献７】米国特許出願公開第２００３／２０８５０２号明細書（Ａ１）
【特許文献８】米国特許出願公開第２００３／９３７６０号明細書（Ａ１）
【非特許文献１】S. Alder et al., "Extensible stylesheet language (XSL), Version 1.0", W3C 2001, [online] Internet URL http://www.w3.org/TR/2001/REC-xsl-20011015/
【非特許文献２】M. Aiello, C. Monz, L. Todoran, M. Worring, "Document understanding for a broad class of documents", International Journal on Document Analysis and Recognition (IJDAR), vol.5, 2002, Springer-Verlag, pp.1-16
【非特許文献３】A. Anjewierden, "AIDAS: Incremental logical structure discovery in PDF documents", Proceedings of the International Conference on Document Analysis and Recognition (ICDAR), Seattle, 2001
【非特許文献４】A. Belaid, L. Pierron, N. Valverde, "Part-of-speech tagging for table of contents recognition", International Conference on Pattern Recognition (ICPR 2000), vol.4, September 3-8, 2000, Barcelona, Spain
【非特許文献５】D. Dori, D. Doermann, C. Shin, R. Haralick, I. Phillips, M. Buchman, D. Ross, "The representation of document structure: A generic object-process analysis", Chapter XX, 'Handbook on Optical Character Recognition and Document Image Analysis', World Scientific Publishing Company, 1995/1996, pp.000-000
【非特許文献６】D. Dori, D. Doermann, C. Shin, R. Haralick, I. Phillips, M. Buchman, D. Ross, "The representation of document structure: A generic object-process analysis", Chapter 16, 'Handbook of Character Recognition and Document Image Analysis', World Scientific Publishing Company, 1997, pp.421-456
【非特許文献７】S. Klink, A. Dengel, T. Kieninger, "Document structure analysis based on layout and textual features", Proceedings of Fourth IAPR International Workshop on Document Analysis Systems, DAS 2000, Rio de Janeiro, Brazil, 2000, pp.99-111
【非特許文献８】C. C. Lin, Y. Niwa, S. Narita, "Logical structure analysis of book document images using contents of information", 4th International Conference on Document Analysis and Recognition (ICDAR'97), Ulm, Germany, August 1997, pp.1048-1054
【非特許文献９】X. Lin, "Header and footer extraction by page-association", Hewlett-Packard Company Technical Report, 2002, [online] Internet URL http://www.hpl.hp.com/techreports/2002/hpl-2002-129.pdf
【非特許文献１０】X. Lin, "Text-mining based journal splitting", Proceedings of the Seventh International Conference on Document Analysis and Recognition (ICDAR 2003), vol.II, August 3-6, 2003, Edinburgh, Scotland
【非特許文献１１】X. Lin, S. Simske, "Automatic document navigation for digital content re-mastering", SPIE Conference on Document Recognition and Retrieval XI, 18-22 January 2004, San Jose, California
【非特許文献１２】R. Power, D. Scott, N. Bouayad-Agha, "Document Structure", Computational Linguistics, Vol.29, No.2, 2003, pp.211-260
【非特許文献１３】S. Satoh, A. Takasu, E. Katsura, "An automated generation of electronic library based on document image understanding", Proceedings of the Third International Conference on Document Analysis and Recognition (ICDAR'95), vol.1, August 14-15, 1995, Tokyo, Japan, pp.163-166
【非特許文献１４】K. M. Summers, "Automatic discovery of logical document structure", PhD thesis, Cornell University, Computer Science Department, August 1998, pp.1-181
【非特許文献１５】R. Virk, "Converting PDF files into XML", CambridgeDocs, 2004, [online] Internet URL http://www.cambridgedocs.com/ConvertingPDF2XML.pdf
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ここに、構造化文書化プロセスに特有の問題としては、文書構造に関わる情報の再構築乃至保存という問題がある。まず、構造化文書化の仕方によっては、それを施す前の文書とは大きく異なった文書になることがある。例えば、章やセクション等の要素を論理ユニットとする論理表現においては、ヘッダ／フッタ等のページ区切り情報を無視することが普通である。即ち、構造化文書化前の文書内にあるヘッダ／フッタ等のページ区切り要素は本来であれば注意深く処理しなければならないのに、ページは単なる物理的要素とされ論理表現内には現れない。また、ＰＤＦ２ＸＭＬやＰＤＦ２ＨＴＭＬ（何れも商品名）等の従来型文書コンバータにおいては、ヘッダ／フッタが文書本体要素と区別されないため、ヘッダ／フッタが本文テキストの流れを妨げることがあった。このような妨げがあると、論理的に狂いのある文書が生成されてしまうだけでなく、後続の処理例えば自然言語処理に対し雑音が導入されてしまいかねない。即ち、既存文書群の構造化文書化に際し従来用いられていたページ区切り要素識別抽出方法及び装置は、効率性及びロバスト性に欠けるものであった。
【０００６】
なお、説明の便宜上、本願においては、その文書を印刷したときに各ページの上部にくるもの、典型的には各ページのトップマージン内にあるテキスト型コンテンツを指して、「ヘッダ」と呼ぶこととする。その例としては、タイトル、ページ番号、ファイル名、改訂日、著者名等、その文書についての情報であって文書の全体又は一部を通して繰り返される情報がある。同様に、本願においては、これらの情報と同種乃至類種の情報であって各ページのボトムマージン内に配置される情報のことを指して、「フッタ」と呼ぶこととする。そして、本願においては、“ヘッダのみ”、“フッタのみ”、“ヘッダ及びフッタ双方”のいずれをも包含する意味で、「ヘッダ／フッタ」なる表記を使用することとする。
【課題を解決するための手段】
【０００７】
本発明の一実施形態はページ区切り要素を検出する方法及び装置であり、特に、既存文書変換時に構造化文書化を従来より効率的に行える点で有用である。ページ区切り要素とは、ページ割りの際にその文書に導入されたテキスト型要素のことであり、その特徴は、ページ割りされた文書内におけるその個数がその文書内のページサイズにはっきりと依存している点である。例えば、ページサイズが十分大きく１ページの中に文書全体が収まるという極端な場合には、各ページ区切り要素はその文書内にそれぞれ１個ずつしか現れない。ページ区切り要素の例としては各ページに付されるヘッダやフッタがあるが、本実施形態によればそれら以外のページ区切り要素、例えば複数ページに跨るテーブルのテキスト型ヘッダ等も検出できる（本願ではそれらも含めてヘッダ／フッタと呼びより広義にはページ区切り要素と呼ぶ）。ページ割りされた文書の文書のモデルとしては、各ページがある程度のサイズを有し、各ページ内に複数個のテキスト要素（テキストボックス）があり、各テキストボックスが何らかのページ内座標値（ｘ，ｙ，幅，高さ）と関連付けられており且つ何らかのテキスト型コンテンツを含んでいる、というモデルを、想定できる。このモデル下では、テキストボックス間類似度、例えばそれらテキストボックス内のテキスト型コンテンツ、ページ内エリアにおけるそれらテキストボックスの位置、並びにテキストボックス掲載ページ間にあるページ数による文書内テキストボックス間距離等の特徴によって定義されるテキストボックス間類似度を計測できる。そして、こうして計測したテキストボックス間類似度があるしきい値を上回っている要素群を、ページ区切り要素として識別乃至特定する。
【０００８】
本発明の他の実施形態はヘッダ／フッタ検出方法及び装置である。ヘッダ／フッタゾーンにおけるコンテンツ的なテキスト変異度（text variability）は、事実上、本文テキストにおけるコンテンツ的な変異度よりも低いため、本実施形態においては、この事実に依拠して文書内のヘッダ／フッタゾーンを識別乃至特定する。本実施形態に係る方法及び装置は、ヘッダやフッタによってもたらされる雑音を除去するための前処理工程として、また既存文書変換のようなコンテンツベース処理を好適に実施できるようにするための前処理工程として、特に有用である。本実施形態を用いて文書内ヘッダ／フッタを識別乃至特定する際には、まずその文書内にあるテキスト型コンテンツのうち然るべき概略位置（所属ゾーン内）にあるものを識別乃至特定し、然るべき概略位置にあると識別乃至特定したテキスト型コンテンツ内におけるテキスト変異度を計算し、然るべく設定されている所定のテキスト変異度値とこのテキスト変異度計算結果とを比較することにより、そのテキスト型コンテンツがヘッダ／フッタ内コンテンツであるかどうかを調べる。そして、こうした比較判別をクリアするテキスト変異度を有しており且つ相連なっている要素群のコンテンツ同士を関連付け（寄せ集め）たもの（及びその占有エリア）を以て、その文書内のヘッダ／フッタ（ゾーン）と認定する。なお、概略位置とは、例えばその文書内での縦方向位置を識別乃至特定可能な情報、典型的にはその文書内の各ページで個々に振られた行番号をいう。テキスト変異度は、そのテキスト型コンテンツを複数個のテキストブロックに細分し、得られたテキストブロック群を所定の何種類かのテキストブロック種別へと種類分けした結果から計算する。例えば、文書内特定部分内テキストブロック総種類数を同部分内テキストブロック総数で除して得られる比（パーセンテージ）を、その文書部分がヘッダ／フッタ候補としてどの程度ふさわしいものであるかを示す指標として使用する。その文書部分内のテキスト型コンテンツをヘッダ／フッタ内コンテンツと見なしてよいかどうかを調べるための比較対象値（しきい値）は、経験的乃至実験的に信頼の置ける値に設定しておく。
【０００９】
本実施形態においては、好ましくは更に、上述のようにして識別乃至特定したヘッダ／フッタ内コンテンツを集めて識別済ヘッダ／フッタ要素リストを作成し、その周辺にあるテキスト型コンテンツをこの識別済ヘッダ／フッタ要素リストと一括又は順次統合して拡張ヘッダ／フッタ要素リストを作成する。統合対象となるテキスト型コンテンツは、そのテキスト型コンテンツにおけるテキストブロック総数及び総種類数を識別済又は拡張ヘッダ／フッタ要素リスト全体でのテキストブロック総数及び総種類数とそれぞれ加算しその結果から計算したテキスト変異度即ち当該リスト全体でのテキスト変異度が、加算前の状態で計算した当該リスト全体でのテキスト変異度に対して増えないと認められるような、周辺のテキスト型コンテンツである。そのようなテキスト型コンテンツであれば、仮にそれ自身のテキスト変異度がヘッダ／フッタ候補たり得ないことを示しているものであっても、統合の対象とする。加算前に対して加算後のテキスト変異度が増加しない、という状況は、一般に、統合しようとしているテキスト型コンテンツ内に含まれている各テキストブロックと同種のテキストブロックが、既に統合検討先のリスト内にあり、従ってそのテキスト型コンテンツもヘッダ／フッタ内コンテンツの一部と見なしうる場合に生じる。
【００１０】
本発明の他の実施形態は、文書内にあるヘッダ／フッタ等のページ区切り要素を識別乃至特定する装置であり、テキストフラグメンタ、プロセッサ及びセレクタを備える。テキストフラグメンタは、文書を複数のページに分割し更にそのページを互いに区別可能な複数個のテキストブロックに分割する。各テキストブロックについては、そのページ内概略位置（所属ゾーン）を、例えばページ上半分、ページ下半分というように識別可能である。プロセッサは、テキストブロック毎にテキスト変異度スコア（textual variability score:ＴＶＳ）を計算する。ＴＶＳは、ページ内任意ゾーン内におけるテキストブロック総数対テキストブロック総種類数の関係を示す数値である。セレクタは、テキストブロック群のうち、そのテキスト型コンテンツがヘッダ／フッタ内コンテンツであることを示すＴＶＳ値を有するテキストブロックから、そのテキスト型コンテンツをヘッダ／フッタ内コンテンツ候補として集め、集めたヘッダ／フッタ内コンテンツ候補を集積統合したものをヘッダ／フッタとして選択及び認定する。その際、セレクタはまず、そのテキスト型コンテンツに基づき計算したテキストブロック毎のＴＶＳ値（文書の要素毎例えばページ内行毎のＴＶＳ値）から見てヘッダ／フッタの一部と見なせるテキストブロック内のテキスト型コンテンツを集め、次いで個別の又は統合後のＴＶＳ値から見てヘッダ／フッタの一部と見なせる隣接要素内のテキスト型コンテンツを集める。
【発明を実施するための最良の形態】
【００１１】
これから説明する実施形態はページ区切り要素と呼ばれるゾーンを検出するという大目的を有している。ページ区切り要素とは、例えば、文書ページの頂部にあるヘッダや文書ページの下部にあるフッタを指している。本願においてヘッダ／フッタゾーンの最たる特徴と見ているのは、それらのゾーンにおけるテキスト変異度が同文書ページ本文におけるそれに比べてかなり小さいことである。本願にて例示描像する実施形態においては、ヘッダ／フッタ検出を、次の通り
１．位置割り振り、
２．テキスト正規化、
３．テキスト変異度計算、そして
４．ヘッダ／フッタゾーン検出
という少なくとも４段階にて行っている。
【００１２】
以下、これらのステップを含め本発明の実施形態にて実行されるステップについて図面を参照しつつ詳細に説明する。まず、図１に示すアセンブリは、非構造化文書１０例えばＰＤＦフォーマットで作成された技術マニュアル等の文書を、その構造化文書化用プロセッサ１２によって、別の言語フォーマット例えばＸＭＬへとフォーマット変換（構造化文書化）するアセンブリである。このアセンブリにおいては、構造化文書化した既存文書を上記目的を含む様々な目的に従い処理することができる。また、既に見てきたように、構造化文書化に伴い文書内に組み込まれるヘッダ／フッタは、既存文書に対するアクセスを阻害する不要な雑音をもたらす原因になりうる。そのため、その前処理工程においてヘッダ／フッタを識別乃至特定することは、文書に対するアクセス効率を向上させる上で特に有益なことといえる。
【００１３】
テキストフラグメンタ１４は、構造化文書化された文書を複数ページ及び複数テキストブロック乃至テキストフラグメントへと細分し、更にそれらテキストブロックに一連の番号を割り振る。図中、細分して得られたテキストブロックの集まりを指して、ページ／テキストブロック群１６と表してある。このページ／テキストブロック群１６は、通常、入手使用可能な文書フォーマットコンバータを用い元の文書から作成済の文書ファイル、例えばＸＭＬファイル内のテキストから、テキスト文字列リストとしてロードされる。入手使用可能な文書フォーマットコンバータは、例えばＯＣＲ（optical character recognition:光学的文字認識手段）やＰＤＦ２ＸＭＬコンバータであり、プロセッサ１２又はフラグメンタ１４にて実行される。例えば、元の文書が紙の文書である場合は、その文書を光学スキャナを用いて走査し、ＯＣＲによって処理させ、認識結果をテキストフラグメンタ１４にて行毎に細分させることによって、フラグメンタ１４から好適にテキストフラグメント群を得ることができる。このとき得られるテキストフラグメントは、その文書中の各行毎に同行のコンテンツから作成されたものであり、また行の順に並んでいる。元の文書がＸＭＬ文書又はＨＴＭＬ文書である場合は、例えばプロセッサ１２又はフラグメンタ１４にてその文書を構文解析させ、構文解析結果に係るＰＣＤＡＴＡ（parsed character data:構文解析済文字データ）に従いフラグメンタ１４にて処理を実行させることによって、フラグメンタ１４から好適にテキストフラグメント群を得ることができる。また、フラグメンタ１４の機能のうち文書内テキストブロック群への番号割り振りは、位置割り振りとして実施される。この位置割り振りは、ページ割り及びページ内テキストブロック縦方向位置が元通り保持されるように行う。その際縦方向位置として使用される情報は、（元の文書が）プレーンテキストフォーマットの文書であればページ毎の又は通しでの行番号（及びページ番号）であるが、より高付加価値的な文書フォーマットであれば、一旦プレーンテキストフォーマットに変換し行番号等を縦方向位置として使用するか、或いは縦方向位置を規定する情報を伴う文書フォーマットに変換し当該情報を縦方向位置として使用する。例えば、ＰＤＦ２ＸＭＬコンバータを用いれば、ページ番号及びテキストブロック位置情報を得ることができる。
【００１４】
図３Ａに、テキスト型コンテンツを含む要素（例えば行；以下同様）を有する文書ページを示す。このような文書ページであれば、その文書ページ内のテキストブロックの空間位置即ち図３Ｂ中のｙ軸に沿った位置を識別乃至特定することを通じて、そのテキストブロックの概略位置乃至所属ゾーンを識別乃至特定することができる。即ち、識別乃至特定した行番号（図３Ａ）又はｙ座標値（図３Ｂ）を、そのテキストブロック内にあるべきテキスト型コンテンツの位置として用い、文書フォーマットコンバータに併設又は搭載されている位置決めアプリケーションによって、その文書ページ内にあるテキストブロック群（より一般にはライン等も含めた要素群）の特徴を抽出する。ここで抽出される特徴は文書ページ内の要素の縦方向位置に関わる特徴であり、プレーンテキストであれば行番号Ｙにまた高付加価値的なフォーマットであれば文書フォーマットコンバータにより与えられるｙ座標値に応じて定まる特徴である。例えば、行番号Ｙ又はｙ座標値から見てその文書ページの上半分内にあるか下半分内にあるかといった特徴のことを指している。ヘッダであればページの上半分内にまたフッタであれば下半分内にあるであろう、と仮定できるから、こうして抽出した特徴をヘッダ／フッタゾーン識別乃至特定に役立てることができる。
【００１５】
以上述べた処理のうち、構造化文書化は図２中のステップ６０にて、細分はステップ６２にて、そして縦方向位置特徴抽出（位置によるヘッダ／フッタ内コンテンツ候補概定）はステップ６４にて実行される。
【００１６】
テキストブロック群及びそれらの縦方向位置特徴の識別乃至特定を行ったら、それらのテキストブロック内のテキスト型コンテンツに正規化処理を施す。ここで施す正規化処理は、テキスト型コンテンツ内の数字（０〜９）をあるユニークな文字（例えばＤ）に置換する処理である。即ち、ヘッダ／フッタ内には例えばページ番号、章番号、セクション番号、日付等の数字が頻繁に現れるが、そうした数字はただ無闇にテキスト変異度を増大させるだけで、本実施形態の目的にとり重要でなく又は妨げになる。数字をユニーク文字に置き換える正規化処理を適用すれば、テキスト変異度が不要に大きくなることを防ぐことができる。また、適用する正規化処理はこの種の正規化処理にとどめる。
【００１７】
ＴＶＳ計算用プロセッサ１８はテキスト変異度を計算する（６６）。即ち、文書内における位置毎に且つ全テキストブロックを対象としてテキストブロックのリストを作成した上で、文書の全体（例えば全ページ）を考慮に入れて、文書内の各位置（例えば行番号Ｙ）にあるテキストブロックの総数と、その位置にあるテキストブロックの総種類数とを、文書内位置毎に数学的に結び付けるテキスト変異度計算を行う。テキスト変異度としてＴＶＳを計算する場合、ある位置ＹにおけるＴＶＳの値ｔｖ＿ｓｃｏｒｅ（Ｙ）は次の式
（数１）
ｔｖ＿ｓｃｏｒｅ（Ｙ）＝テキストブロック総種類数／テキストブロック総数
で計算できる。
【００１８】
次の表
【表１】
2006195980.tif 000003
に、ある文書（この例では技術マニュアル）内の全ページを通じ図４Ａ中の位置１０８に現れるテキストブロックの種類及びその個数を示す。
【００１９】
表１に示した例においては、テキストブロック種類数が７個と比較的少数であるのに対し、それら７種類を合計したテキストブロック個数は７９個になっている。従って、表１に示したテキスト型コンテンツに数１を適用することによって位置１０８におけるＴＶＳの値を求めると、７÷７９＝０．０８９（約０．０９）となる。
【００２０】
次の表
【表２】
2006195980.tif 000004
に、文書ページ内にある別々の６個の位置について、ＴＶＳ値を示す。
【００２１】
表２中、第１列は各要素の概略位置（９６、１０８等々）を、第２列はその位置におけるテキストブロック総数（５、７９等々）を、第３列はその位置におけるテキストブロック総種類数（３、７等々）を、そして最終列はその位置についてのＴＶＳ計算値（０．６、０．０９等々）を、それぞれ表している。
【００２２】
表２に示されているように、各位置に存する要素即ちテキストブロックにおけるテキスト変異度を表すＴＶＳ値は、位置１５６では非常に大きいのに対して位置１０８では非常に小さい。即ち、後者の位置１０８にあるテキストブロックの個数は７９個である（即ち位置Ｙ＝１０８にテキストブロックが７９個ある）のに、それら７９個のテキストブロックを種類分けしてもたったの７種類しかない。文書内の全ての位置（行）についてＴＶＳ計算が終わったら、プロセッサ１８は位置毎のＴＶＳ計算値２０をデータベースに格納する。更に、それらＴＶＳ計算値２０に基づき、それらのデータの中から何個かの要素に係るデータを選び、ヘッダ／フッタ内要素候補データ即ちヘッダ／フッタゾーンを検出するもとになる要素に係るデータとして識別乃至特定してリスト化する（６８）。より詳細には、ＴＶＳ計算の対象となる要素はその文書内位置にあるテキストブロックの個数についての情報を含んでいるので、テキスト型コンテンツを含む要素それぞれのＴＶＳ値をこの情報を利用して計算し、しかる後に、その文書にヘッダ／フッタゾーンがあるかどうか、またあるとしたらそれはどこかについて、識別乃至特定を試みる。その方法としては、まず、テキスト型コンテンツを含みそのＴＶＳ値が所定値（即ちヘッダ／フッタゾーンの一部と見なしてよい値）である要素をヘッダ／フッタ内要素候補として初期識別乃至特定し、その後、これに連なるヘッダ／フッタ内要素候補を検出してヘッダ／フッタ内要素リスト（ヘッダ／フッタ内要素候補のリスト）に統合しそのリストをヘッダ／フッタゾーンと見なしうる最大範囲まで拡張していく方法、言い換えればテキスト型コンテンツを含む隣の要素であってヘッダ／フッタと見なしうるものをヘッダ／フッタ内要素リストに次々に統合してその範囲を拡張していくという方法を用いる。
【００２３】
あるテキスト型コンテンツを有する要素がヘッダフッタ内要素候補であると識別乃至特定するためのヘッダ／フッタ該当条件は、そのＴＶＳ値を有していれば経験的乃至実験的にいってヘッダ／フッタ内要素であると見なしうるようなＴＶＳしきい値を予め選択することによって、定めることができる。本実施形態におけるこのしきい値θは０．５に設定されている。従って、そのＴＶＳ値が０．５未満のテキスト型コンテンツを有する要素は皆、ヘッダ／フッタ内要素候補と識別乃至特定される。なお、しきい値θは経験的乃至実験的に設定できる数値であるため、文書フォーマット変換、格納及びアクセスの対象となる既存文書の種類に応じ且つ任意な値に（従って上掲の例とは別の値に）設定され得る。
【００２４】
一例として、表１第１行に記した位置１０８にあるテキストブロック群を対象としてこの識別乃至特定を行う場合を考えると、その場合には、ヘッダ／フッタ内要素候補たり得るかどうかが次の表
【表３】
2006195980.tif 000005
に示す如くに判別されることとなる。
【００２５】
ステップ６８を実行するに当たり、隣接要素群内ヘッダ／フッタ候補セレクタ２２は、まずそのページ先頭及び末尾を開始点として、ＴＶＳ値によるヘッダ／フッタ該当条件を満足する要素を探索する。それによって、テキスト型コンテンツを有する要素即ちテキストブロックの中で、ページ先頭から探して最初に行き当たったヘッダ該当条件満足要素及びページ末尾から探して最初に行き当たったフッタ該当条件満足要素を、ヘッダ／フッタゾーン内にあるはずの要素即ちヘッダ／フッタ内要素候補として初期識別乃至特定する。初期識別乃至特定されたヘッダ／フッタ内要素候補（拡張開始要素）は、暫定的に、ヘッダゾーン内で一番上にあるもの及びフッタゾーン内で一番下にあるものと見なされる（テキスト変異度条件による初期識別乃至特定）。但し、ヘッダと見なしてよいのはそのページの上半分内にあるものだけであるためそうしたものしかヘッダ内要素候補とはせず、またフッタと見なしてよいのはそのページの下半分内にあるものだけであるためそうしたものしかフッタ内要素候補とはしない（ページ内概略位置乃至ゾーンによる制限）。従って、もし、所定の概略位置内にヘッダ／フッタ基準満足要素がなければ、本実施形態に係る方法ではヘッダ／フッタなしと認定する。表３に示した例では、テキスト型コンテンツを有する要素１０８がヘッダ内要素候補として、またテキスト型コンテンツを有する要素６８４がフッタ内要素候補として、それぞれ初期識別乃至特定されることとなる。
【００２６】
セレクタ２２は、更に、テキスト型コンテンツを有する拡張開始要素からヘッダ／フッタ内要素候補の補充を始める。この補充は、拡張開始要素の隣にある要素のうちヘッダ／フッタ該当条件を満足するもの（隣接統合要素）を選択してヘッダ／フッタゾーン拡張開始要素と共にヘッダ／フッタ内要素リスト（識別済リスト）を作成し、更にこの識別済リスト内の要素の隣にある要素のうちヘッダ／フッタ該当条件を満足するもの（これも隣接統合要素）を選択して識別済リストに統合していく手順によって、実行する。即ち、例えばそのＴＶＳ値がそのしきい値θ未満であって拡張開始要素又は識別済要素リスト内要素に隣接する要素もまた、ヘッダ／フッタゾーンの一部と見なしてよい。そこで、拡張開始要素から始めてその隣、更にその隣といった具合に隣接するヘッダ／フッタ内要素候補を糾合することで識別済リストを作成する。こうして作成した識別済リストは、それ自体、拡張開始要素により規定されるゾーンより広く且つより実際のヘッダ／フッタゾーンに近いゾーンを規定するものとなる。セレクタ２２又はこれと連携するプロセッサは、作成した識別済要素リスト全体についてのＴＶＳ値を数１の適用により計算する（７０）。即ち、このリストに含まれるテキストブロックの総種類数を同じく総個数で除して、そのリスト全体についてのＴＶＳ値を求める。その計算によって得られるＴＶＳ値（より一般にはテキスト変異度）は、必ずしきい値θ未満になる。例えば表に示した例においては、拡張開始要素の位置１０８に隣り合う位置１２２の要素が位置１０８の要素と共にヘッダについて識別済内要素リストを形成し、そのリスト全体でのＴＶＳ値が０．２３となる一方、位置６８４の隣の位置にはそのＴＶＳ値がしきい値θ未満となる要素がないため、フッタについての識別済リストは位置６８４の要素のみで形成される。
【００２７】
こうした隣接要素統合プロセスは、テキスト型コンテンツを有する拡張開始要素に位置ばらつきがある場合に、それを均すことができる点で、特に有用である。例えばＰＤＦからＸＭＬに文書フォーマット変換された文書等、変換によって得られた文書においては、ページ毎に要素位置が若干ずれることがあり得る。あるページでは本文第１段落が位置６１から始まり、別のページでは位置６２から始まり、更に別のページでは位置６３から始まる、といった具合である。本実施形態に係る方法においては、このように位置ずれを伴っている要素について特に（前）処理を施すことなしで、テキスト型コンテンツを有し且つそのＴＶＳ値がしきい値θ以上の要素が、ヘッダ／フッタゾーンに隣り合うゾーンに含まれるページ本文内要素とされる。
【００２８】
本実施形態においては、更に、周辺要素選択統合用プロセッサ２４が、識別済要素リスト内要素の上又は下に位置する要素について、その要素がヘッダ／フッタ内要素候補と見なされるべきものであるかを調べ、見なすべきとされた要素と識別済リスト内要素とにより拡張リストを作成し、拡張リスト内要素の上又は下に位置する要素についてその要素がヘッダ／フッタ内要素候補と見なされるべきものであるかを調べ、見なすべきとされた要素（周辺統合要素）を拡張リストに統合していく、という特徴的処理を実行している（７２；周辺要素統合）。当該周辺要素のＴＶＳ値がしきい値θ以上であっても排除しない。この周辺要素統合は、仮にＴＶＳ値が高くても、その周辺要素を拡張リストに仮に含めたらそのリストにおけるＴＶＳ値（より一般にはテキスト変異度）が従前の（即ち識別済リスト又はそれまでの拡張リストの）ＴＶＳ値より小さくなるなら、その周辺要素をヘッダ／フッタゾーン内要素と見なしてよく従って拡張リストに取り込むのが適切である、という原理に依拠している。より具体的に図４Ａ、図４Ｂ又は図４Ｃに示す表中の位置１０８、１２２及び９６について考えると、位置１０８にある要素及び位置１２２にある要素は、それ自体のＴＶＳ値がＴＶＳ値によるヘッダ該当条件を満足していることが理由で統合され（隣接要素統合）、識別済リストを形成する。次いで、識別済リスト内要素の周辺にある要素即ち位置９６にある要素について、ヘッダに係る周辺統合要素たり得るかどうか即ちその要素と識別済リスト内要素と共に拡張リストを作成したとしたら識別済リストのＴＶＳ値に比べその拡張リストのＴＶＳ値の方が小さくなるかどうかが調べられる。拡張リストのＴＶＳ値は、識別済リスト内テキストブロック総数及び総種類数にそれぞれ位置９６にあるテキストブロック総数又は総種類数（但し重複種類は省く）を加算しその結果に基づき計算する。表に示した例では、実際、識別済リストにおけるＴＶＳ値０．２２９４に比べ、位置９６にある要素を含めたと仮定したときの拡張リストにおけるＴＶＳ値がより小さな０．２２８６となるため、識別済リスト内要素及び位置９６にある要素によって拡張リストが作成されることになる（周辺要素統合）。続いて、位置１４３の要素も同様に調べられるものの、既存の拡張リストに位置１４３にある要素を統合したらそのＴＶＳ値が約０．２４と従前の約０．２３より大きくなるため、位置１４３にありテキスト型コンテンツを有する要素は、ヘッダゾーン内にあると見なせないとしてヘッダに係る拡張リストに取り込まないでおく（テキスト変異度条件による制限）。位置１４３にある要素を拡張リストに取り込まないとした時点で、拡張リストへの周辺要素統合によるヘッダ識別乃至特定処理は停止する（ヘッダゾーンの識別乃至特定）。フッタ側についても、フッタ内要素候初期識別乃至特定、隣接要素統合及び周辺要素統合を実行することによって、フッタゾーンの識別乃至特定が行われる。プロセッサ２４は以上の結果に基づきヘッダ／フッタを認定する（７４）。
【００２９】
こうして周辺要素を統合していく処理を実行することによって、それ自体のＴＶＳ値はしきい値より高いが実際にはヘッダ／フッタ内要素内にあるテキスト型コンテンツであるといえるテキスト型コンテンツを、寄せ集めることができる。
【００３０】
本実施形態には、更に、識別済又は拡張リストがページ先頭（ヘッダの場合）又は末尾（フッタの場合）から始まっていなくてもよい、という特徴がある。例えば、図４Ｃに示す位置９６にある要素は先行する統合処理にてヘッダゾーン内要素候補と認められておらず、従ってこの場合の識別済リストはページ最上位置から始まっていない。より一般的にいえば、上掲の如き拡張リスト内要素の周辺にある要素群の中には、その要素自体はテキスト変異度が高い（例えばＴＶＳ値＞しきい値θである）けれども、ヘッダ／フッタゾーン内要素候補として拡張リスト内に取り込むべき要素があり得る。例えば、その要素に含まれるテキストブロックの個数が非常に少ない要素が、通常、これに該当する。要素内テキストブロック総数が、例えば位置９６における５個、位置１４３における１個のように非常に少ないと、それが原因で、その要素位置におけるテキスト変異度がある程度大きくなる。即ち、例えばその要素が文書内にたった１個しかなければその要素位置におけるＴＶＳ値は１になるため、隣接要素統合の条件は満たされずまた往々にして周辺要素統合の条件も満たされない。本実施形態においては、この点に着目した特徴的な処理を実行できる。即ち、作成した識別済又は拡張リスト内の要素とページ先頭（ヘッダの場合）又は末尾（フッタの場合）との間にある要素、即ち隙間要素は経験的にいって全てヘッダ／フッタゾーンの一部と見なすのが妥当であるから、全ての隙間要素をリスト内に取り込めなかった場合即ち要素取込不可現象が生じた場合に、そのことを警報するようにするとよい。更に、そうした要素取込不可現象が生じたページのリストを作成して、後の時点で訂正乃至評価を実行できるようにするとよい。何れにせよ、隙間要素の存在によって示されている潜在的な文書内問題点を知るには、こうした警報機構を設けて利用するのが簡便である。また、要素取込不可現象が生じた旨の警告に応じ折返し統合を（自動）実行するようにするとよい。折返し統合とは、対象となるリスト内の要素のうち最下に位置する要素（ヘッダの場合）又は最上に位置する要素（フッタの場合）を折り返し点として、その位置より位置番号が小さく従って上側にある要素（ヘッダの場合）又は位置番号が大きく従って下側にある要素（フッタの場合）をそのリストに統合する処理である。この機能を設けた場合、先に示した例でいえば、ヘッダ側の拡張リスト内最下位置１２２及びフッタ側の拡張リスト内最上位置６４８が折り返し点とされ、各ページ内の要素のうち位置１２２とページ先頭とに挟まれその位置番号が１２２以下の位置の要素が全てヘッダ側の拡張リスト内に取り込まれてヘッダゾーンの一部と認識され、また位置６４８とページ末尾とに挟まれその位置番号が６４８以上の位置の要素が全てフッタ側の拡張リスト内に取り込まれてフッタゾーンの一部と認識される。
【００３１】
また、処理時間を短縮したいのであれば、ページ先頭から下にｎ個目の要素まで及びページ末尾から上にｎ個目の要素までに絞って、本実施形態に係る処理を実施するようにするとよい（ｎ：ページサイズより小さい任意の自然数）。実際問題としては、文書内全要素を処理対象としたとしても、本実施形態に係る方法のパフォーマンスは総体としてさほど悪くならず、１５００ページを有する文書を２〜３秒以内に処理できるという超高速性能を実現できる。
【００３２】
図５に、既存文書変換に伴うページ割りにより文書内に発生したページ区切り要素を検出する方法を示す。変換後の文書に現れるテキスト型のページ区切り要素の特徴としては、そのページ割り文書内での個数がその文書におけるページサイズに直結している点がある。極端な例をいうと、その文書におけるページサイズが十分大きくその文書のコンテンツ全てを収められるのであれば、その文書のページ数は１となり、従って各ページ区切り要素はその文書内にそれぞれ１回しか現れない。こうしたページ区切り要素としては例えばヘッダ／フッタがあるが、別にヘッダ／フッタに限られるわけではなく、例えば、複数ページに跨る表の中に繰り返し現れるテキスト型ヘッダもページ区切り要素に該当する。技術マニュアル等においては、このように表が複数ページに跨っていることは普通のことである。図５に示した実施形態の原理は、適当な距離指標範囲内にある要素をページ区切り要素と見なしてクラスタリングする、というものである。ページ区切り要素が後々の処理に当たって雑音となることからすれば、既存文書変換時にこうしたクラスタリングを行うことは有意義である。
【００３３】
本実施形態に係る方法を実施するため、ステップ９０においては文書が複数個のテキストボックスに分割される。ここでは、ページ割りされていて一般に複数ページを有する文書であり、各ページが所定サイズを有しており、各ページ内に何個かのテキスト型要素（本願ではこれをテキストボックスと称する）が含まれており、ページ上の各テキストボックスに対してある種の座標値（ｘ，ｙ，幅、高さ）が関連付けられており、また各テキストボックスが何らかのテキスト型コンテンツを含んでいる文書モデルを考える。このモデルは、大抵のＰＤＦ２ＨＴＭＬコンバータにて用いられている一般的なモデルである。ステップ９０にて形成されたテキストボックスについては、ステップ９２において類似度指標の比較が行われる。この類似度指標は、第１にそれらテキストボックス内のテキスト型コンテンツ、第２にページ内所定エリアにおけるそれらテキストボックスの位置、第３にそれらのテキスト型コンテンツの掲載ページ間距離（間隔ページ数）、という三種類の特徴を考慮に入れて、計測される。より詳細には、ステップ９２にて比較される類似度指標は、これら三種類の特徴それぞれに係る三種類の指標、即ちテキスト類似度、幾何学的類似度及びページ近接度を適宜組合せ又は結合させたものである。第１の指標であるテキスト類似度は、２個のテキストボックスに含まれるテキスト型コンテンツが同じであれば１となり、等しくなければ０となる。テキスト類似度に代えて、ある種のテキスト正規化が施されている編集距離（edit distance）を用いてもよい。特に、例えばページ番号はページ毎に違う数字であるため厳密一致テスト（strict equality test）ではページ番号をページ区切り要素として検出できないが、編集距離にテキスト正規化（例えば全数字の特定文字への置換）を施しておけば、ページ番号をページ区切り要素として検出することができる。但し、テキスト正規化が施されていない編集距離も、テキスト型コンテンツに係る指標として使用できる。第２の指標である幾何学的類似度の導出に当たっては、例えば、ページ内センタリング及びテキストボックス輪郭強調を行う。ページ内センタリングは各ページ内座標系変更操作の一種であり、これを行うことによって、そのページの座標系の原点は、それまでの位置（通常は左上隅）から、そのページ上の全テキストボックスを取り囲むボックスの中央へと、移動する。ページ内センタリングという操作は、ドーム文書を対象として奇数ページ偶数ページ間テキストボックス大移動を行う上で有用であるが、そうした操作が必要でない文書群もあろう。また、テキストボックス輪郭強調、例えばテキストボックスの輪郭をＴ画素分（Ｔ：経験的乃至実験的に定めた値）太くする処理は、ページ間でのテキストボックス位置差を広げないようにするための操作であり、幾何学的類似度を評価する上で有用である。幾何学的類似度は、これらの操作を施した上で、例えば面積重複率９４として導出する。面積重複率９４とは、２個のテキストボックス間の重複面積を、それら２個のテキストボックスを一体として見たときの面積によって除した比の値である。そして、第３の指標であるページ近接度９６は、一方のテキストボックスが掲載されているページと他方のテキストボックスが掲載されているページとの間に挟まっているページ数が所定値Ｐ未満であれば１、そうでなければ０となる。この所定値Ｐは、各テキストボックスを中心としてページ近接度窓を定義する数値であり、この窓から外れたらページ近接度は０になる。
【００３４】
ステップ９８においては、類似しているテキスト同士を、古典的な凝集最短距離クラスタリングアルゴリズム（agglomerative single-link clustering algorithm）によってクラスタリングする。類似度しきい値θは例えば０．５とし、この類似度しきい値θを上回る類似度を有する要素群をクラスタリングしてひとまとまりにすることにより、ページ区切り要素を含むグループ乃至クラスタが形成される。それ以外のクラスタ例えばテキストボックスを１個しか含んでいないクラスタは無視する。
【００３５】
以上、本発明の実施形態を何個か説明したが、本発明の技術的範囲は、出願当初の（補正がされた場合は補正後の）特許請求の範囲により画定されるものであり、以上説明した実施形態により本発明を限定解釈すべきではない。本発明の技術的範囲には、本願中に実施形態として開示した構成及び本願中で示唆した構成だけでなく、その別態様、代替物、変形物、改良物、均等物乃至実質的等価物等も包含される。更に、本発明の技術的範囲には、現今のところ発見されておらず又は知見に上っていないものも、それが本願出願人により提案されたものであるかそれとも他人により提案されたものであるかを問わず、包含される。
【図面の簡単な説明】
【００３６】
【図１】文書内ヘッダ／フッタ部分を識別乃至特定する装置を示す図である。
【図２】文書内ヘッダ／フッタ部分を識別乃至特定する方法を示すフローチャートである。
【図３Ａ】テキスト型コンテンツを有する要素のページ内空間位置を識別乃至特定する方法を示す図である。
【図３Ｂ】テキスト型コンテンツを有する要素のページ内空間位置を識別乃至特定する方法を示す図である。
【図４Ａ】テキスト型コンテンツを有する隣接要素及び周辺要素をヘッダ／フッタゾーンに統合する方法を示す図である。
【図４Ｂ】テキスト型コンテンツを有する隣接要素及び周辺要素をヘッダ／フッタゾーンに統合する方法を示す図である。
【図４Ｃ】テキスト型コンテンツを有する隣接要素及び周辺要素をヘッダ／フッタゾーンに統合する方法を示す図である。
【図５】他のページ区切り要素検出プロセスを示すフローチャートである。
【符号の説明】
【００３７】
１０  非構造化文書、１２  構造化文書化用プロセッサ、１４  テキストフラグメンタ、１６  ページ／テキストブロック群、１８  ＴＶＳ計算用プロセッサ、２０  位置毎ＴＶＳ計算値、２２  隣接要素群内ヘッダ／フッタ候補セレクタ、２４  周辺要素選択統合用プロセッサ、６０  マークアップ言語変換ステップ、６２  細分ステップ、６４  ヘッダ／フッタゾーン候補識別ステップ、６６  ＴＶＳ計算ステップ、６８  ヘッダ／フッタ内要素候補リスト作成ステップ、７０  隣接要素込みＴＶＳ計算ステップ、７２  周辺要素統合ステップ、７４  ヘッダ／フッタ認定ステップ、９０  テキストボックス分割ステップ、９２  類似度比較ステップ、９４  面積重複率、９６  ページ近接度、９８  類似テキストボックス群クラスタリングステップ。
【図１】
2006195980.tif 000006
【図２】
2006195980.tif 000007
【図３Ａ】
2006195980.tif 000008
【図３Ｂ】
2006195980.tif 000009
【図４Ａ】
2006195980.tif 000010
【図４Ｂ】
2006195980.tif 000011
【図４Ｃ】
2006195980.tif 000012
【図５】
2006195980.tif 000013