(57)【特許請求の範囲】
【請求項１】
数値表データが入力されると、
前記数値表データから、上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域である数値部データを分離して抽出し、
前記数値部データから、左右方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、
前記数値表データから、抽出した前記複数の入力領域の何れかの入力領域の上方向に配置された入力領域である属性部データを分離して抽出し、
前記属性部データのうち、少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、
処理をコンピュータが実行することを特徴とするデータ処理方法。
【請求項２】
数値表データが入力されると、
前記数値表データから、上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域である数値部データを分離して抽出し、
前記数値部データから、上下方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、
前記数値表データから、抽出した前記複数の入力領域の何れかの入力領域の左方向に配置された入力領域である属性部データを分離して抽出し、
前記属性部データのうち、の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、
処理をコンピュータが実行することを特徴とするデータ処理方法。
【請求項３】
前記算術的な関係を有する複数の入力領域を抽出する処理は、前記算術的な関係を総和入出力関係または総積入出力関係とし、入力範囲と出力位置が連続しているとして連続部分集合和問題または連続部分集合積問題の解により前記算術的な関係を有する複数の入力領域を抽出する、
ことを特徴とする請求項１または２に記載のデータ処理方法。
【請求項４】
前記算術的な関係を有する複数の入力領域を抽出する処理は、出力位置を順次に固定し、二分探索により入力範囲を特定する、
ことを特徴とする請求項３に記載のデータ処理方法。
【請求項５】
前記算術的な関係を有する複数の入力領域を抽出する処理は、特定された入力範囲を削除し、入力領域が抽出されなくなるまで、前記算術的な関係を有する複数の入力領域の抽出を繰り返す、
ことを特徴とする請求項３または４に記載のデータ処理方法。
【請求項６】
数値表データが入力されると、
前記数値表データから、上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域である数値部データを分離して抽出し、
前記数値部データから、左右方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、
前記数値表データから、抽出した前記複数の入力領域の何れかの入力領域の上方向に配置された入力領域である属性部データを分離して抽出し、
前記属性部データのうち、少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、
処理をコンピュータに実行させるデータ処理プログラム。
【請求項７】
数値表データが入力されると、
前記数値表データから、上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域である数値部データを分離して抽出し、
前記数値部データから、上下方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、
前記数値表データから、抽出した前記複数の入力領域の何れかの入力領域の左方向に配置された入力領域である属性部データを分離して抽出し、
前記属性部データのうち、の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、
処理をコンピュータに実行させるデータ処理プログラム。
【請求項８】
数値表データが入力されると、
前記数値表データから、上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域である数値部データを分離して抽出する手段と、
前記数値部データから、左右方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出する手段と、
前記数値表データから、抽出した前記複数の入力領域の何れかの入力領域の上方向に配置された入力領域である属性部データを分離して抽出する手段と、
前記属性部データのうち、少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける手段と、
を備えたことを特徴とする情報処理装置。
【請求項９】
数値表データが入力されると、
前記数値表データから、上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域である数値部データを分離して抽出する手段と、
前記数値部データから、上下方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出する手段と、
前記数値表データから、抽出した前記複数の入力領域の何れかの入力領域の左方向に配置された入力領域である属性部データを分離して抽出する手段と、
前記属性部データのうち、の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける手段と、
を備えたことを特徴とする情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理方法、データ処理プログラムおよび情報処理装置に関する。
【背景技術】
【０００２】
国や企業の持つ情報を第三者が再利用可能にするオープンデータ（Open Data）の試みがトレンドになっている。リンクトデータ（Linked Data）のように多種多様な情報を組み合わせることで、従来技術ではできなかった高度な検索や分析が可能になると期待されている。公開されているデータはＲＤＦ（Resource Description Framework）のように機械処理しやすい形式もあれば、ExcelデータやＣＳＶ（Comma-Separated Values）のように機械処理しにくい（数値と属性との対応付けの設計が甘い）形式もある。今後は、このような数値表データを如何に効率よく処理しやすい形式に変換するかが重要である。
【０００３】
図１は数値表データの例を示す図であり、数値が設定された数値部データと、文字列（テキスト）が設定された属性部データとを含んでいる。この例では、数値部データの左部（左方向）と上部（上方向）に属性部データが設けられている。数値表データによっては、属性部データが数値部データの左部か上部の一方にのみ存在する場合もある。
【０００４】
図２は、図１に示した数値表データにおいて、太枠で示した数値「37,825,636」が、左部の属性「現金給付」と上部の属性「平成１７年度」に関連付けられていることを示している。
【０００５】
図３は、図１に示した数値表データにおいて、太枠で示した属性が、明示的でない階層構造を含んでいることを示している。すなわち、太枠内の「現金給付」に対し、「退職年金」等の属性は、文字の先頭位置がずらされていることから下位の関係にあることを暗に示しているが、明確に階層構造を判断できるものではない。「現金給付」「退職年金」等の属性の意味を理解している人が見れば階層構造を理解することができるが、機械的に処理する場合には正確な処理を行うことは困難である。
【０００６】
図４は、図３で説明した太枠内の属性に対応する数値の間に和の入出力関係があることを示している。すなわち、「現金給付」に対応する数値「37,188,026」は、「退職年金」〜「その他の現金給付」に対応する数値「36,724,189」〜「61,174」の和となっている。なお、数値表データによっては、和の入出力関係に代えて、積の入出力関係が存在する場合もある。
【０００７】
図５は、図１に示した数値表データにおいて、太枠で示した属性「Ｉ  高齢」〜「その他の現金給付」について、階層構造を適切に認識した属性ラベリングの例であり、このような属性ラベリングが自動的に行えることが望まれる。
【０００８】
以下、従来における自動的な属性ラベリングの手法について説明する。なお、左右方向に数値の入力領域（セル）が広がり、上部に属性が配置される場合について説明するが、上下方向に数値の入力領域が広がり、左部に属性が配置される場合についても同様である。また、入力領域の数値の間に和の入出力関係がある場合について説明するが、積の入出力関係が存在する場合も同様である。
【０００９】
図６は従来における属性ラベリングの例を示す図であり、入力となる数値表データとして、「交通事故」と「水難事故」のそれぞれについて、「総数」「死亡」「けが」のそれぞれの数を表したものを例としている。
【００１０】
従来は、このような数値表データに対し、「直上のセルを親ラベルとする    もし空欄ならば、直上の左側で一番近い非空欄セルを親ラベルとする    複数段ある場合は下段から上段の行ごとに再帰的に処理する」といった属性ラベリングパターンを処理担当者が情報処理装置に設定し、自動的にラベリングを行わせていた。例えば、数値表データの左端のラベル「総数」については、直上のラベル「交通事故」が親ラベルとされ、「交通事故−総数」という階層構造のあるラベルとされる。隣のラベル「死亡」については、直上が空欄であるため、その左側で一番近い「交通事故」が親ラベルとされ、「交通事故−死亡」という階層構造のあるラベルとされる。他についても同様である。この例では、階層構造が正確に反映されたラベリングが行われている。
【００１１】
図７は従来における属性ラベリングの他の例を示す図であり、入力となる数値表データの「交通事故」「水難事故」の位置が図６の場合に比べて右に１セルだけずれている。人間が見る資料としては、「総数」「死亡」「けが」のまとまりの中央に表示されているということで、不自然ではないスタイルである。
【００１２】
この場合、前述したのと同じ属性ラベリングパターンを適用すると、数値表データの左端のラベル「総数」については、直上およびその左側、さらには上部にも他のラベルが存在しないため、本来は「交通事故−総数」とすべきものが、単に「総数」と誤ってラベリングされてしまう。また、「水難事故」に属する「総数」については、直上の空欄の左側で一番近い「交通事故」が親ラベルとされてしまい、本来は「水難事故−総数」とすべきものが、「交通事故−総数」と誤ってラベリングされてしまう。
【００１３】
図８は従来における属性ラベリングの他の例を示す図であり、入力となる数値表データとして、図６に示したものの左側に、「災害」に属する「地震」「津波」についての「総数」「死亡」「けが」と、「災害」についての「総数」が追加されたものである。この例は、深さが違う構造関係が複数ある場合となる。
【００１４】
この場合、前述したのと同じ属性ラベリングパターンを適用すると、「交通事故」「水難事故」について、上の行にある「災害」が親ラベルとされてしまい、上位に「災害」が付された誤ったラベルが大量に発生してしまうことになる。
【００１５】
一方、表データの属性値の階層構造を定義した情報から階層構造を判断する手法や、セル内の文字列の形式や意味に基づいて階層構造を判断する手法が開示されている（例えば、特許文献１、２等を参照。）。
【００１６】
また、インデントやフォントを特徴量として、セル同士が親子関係にあるか否かを判別し、木構造になる組み合わせを抽出する手法が開示されている（例えば、非特許文献１等を参照。）。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】特開２０１３−２５７８５２号公報
【特許文献２】特公平７−４３７０７号公報
【非特許文献】
【００１８】
【非特許文献１】"Automatic Web Spreadsheet Data Extraction", Zen Chen and Michael Cafarella, VLDB 2013
【発明の概要】
【発明が解決しようとする課題】
【００１９】
上述した図７または図８に示したような、誤った属性ラベリングに対処するためには、数値表データの様々なパターンを考慮する必要がある。しかし、網羅的な属性ラベリングパターンの作成は容易ではなく、作成のためにコストもかかるという問題があった。特に、図８に示したような、深さが違う複数の階層構造を正確に認識する属性ラベリングパターンは複雑となり、作成のためのコストも大きくなる。
【００２０】
一方、表データの属性値の階層構造を定義した情報から階層構造を判断する手法では、予め属性値の階層構造を定義しなければならず、分野を問わない広範な数値表データを処理するのは困難である。
【００２１】
また、セル内の文字列の形式や意味に基づいて階層構造を判断する手法は、処理対象とできる数値表データの分野が限られ、分野を問わない広範な数値表データを処理するのは困難である。インデントやフォントを特徴量として用いる手法では、ＣＳＶのような、文字に修飾がされていない単純な表データには適用が困難である。
【００２２】
そこで、一側面では、数値表データにおけるそれぞれの数値データに対応付ける属性情報を簡単に特定することを目的とする。
【課題を解決するための手段】
【００２３】
一つの形態では、数値表データが入力されると、前記数値表データから、上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域である数値部データを分離して抽出し、前記数値部データから、左右方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、前記数値表データから、抽出した前記複数の入力領域の何れかの入力領域の上方向に配置された入力領域である属性部データを分離して抽出し、前記属性部データのうち、少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、処理をコンピュータが実行する。
【発明の効果】
【００２４】
数値表データにおけるそれぞれの数値データに対応付ける属性情報を簡単に特定することができる。
【図面の簡単な説明】
【００２５】
【図１】数値表データの例を示す図（その１）である。
【図２】数値表データの例を示す図（その２）である。
【図３】数値表データの例を示す図（その３）である。
【図４】数値表データの例を示す図（その４）である。
【図５】数値表データの例を示す図（その５）である。
【図６】従来における属性ラベリングの例を示す図（その１）である。
【図７】従来における属性ラベリングの例を示す図（その２）である。
【図８】従来における属性ラベリングの例を示す図（その３）である。
【図９】一実施形態にかかる情報処理装置のソフトウェア構成例を示す図である。
【図１０】情報処理装置のハードウェア構成例を示す図である。
【図１１】実施形態の処理例を示すフローチャートである。
【図１２】属性ラベリングパターンの例を示す図である。
【図１３】数値表データ、数値部データおよび属性部データの例を示す図（その１）である。
【図１４】数値表データ、数値部データおよび属性部データの例を示す図（その２）である。
【図１５】入れ子を考慮しない場合の総和入出力範囲の抽出の処理例を示すフローチャートである。
【図１６】連続部分集合和問題を説明する図である。
【図１７】累積和配列と二分探索を用いた総和入出力関係の抽出の処理例を示すフローチャートである。
【図１８】総和入出力範囲の抽出の例を示す図（その１）である。
【図１９】入れ子を考慮する場合の総和入出力範囲の抽出の処理例を示すフローチャートである。
【図２０】総和入出力範囲の抽出の例を示す図（その２）である。
【図２１】属性ラベリングの例を示す図（その１）である。
【図２２】属性ラベリングの例を示す図（その２）である。
【発明を実施するための形態】
【００２６】
以下、本発明の好適な実施形態につき説明する。
【００２７】
＜構成＞
図９は一実施形態にかかる情報処理装置１のソフトウェア構成例を示す図である。なお、入力領域の数値の間に和の入出力関係がある場合に対応した例について説明するが、積の入出力関係が存在する場合についても同様に適用することができる。
【００２８】
図９において、情報処理装置１は、ユーザ（作業担当者）からの入力データとなる属性ラベリングパターン１１および数値表データ１２と、属性部・数値部分離部１３と、属性部・数値部分離部１３の出力データとなる数値部データ１４および属性部データ１５を備えている。また、情報処理装置１は、総和入出力範囲抽出部１６と、総和入出力範囲抽出部１６の出力データとなる総和入出力範囲１７と、属性ラベリング部１８と、属性ラベリング部１８の出力データとなるラベルデータ１９とを備えている。
【００２９】
属性ラベリングパターン１１は、属性ラベリング部１８による属性ラベリングに用いられる情報である。属性ラベリングパターン１１の具体例については後述する。数値表データ１２は、処理の対象となるデータであり、ExcelデータやＣＳＶのように機械処理しにくい、設計が甘い形式の数値表データである。また、数値表データ１２は、数値データ同士に和や積の入出力関係が含まれており、属性間に階層構造が含まれる場合があるものとしている。数値表データ１２の具体例については後述する。
【００３０】
属性部・数値部分離部１３は、数値表データ１２から数値部データ１４と属性部データ１５を分離して抽出する機能を有している。数値部データ１４は、数値表データ１２に含まれる数値部のデータである。数値部データ１４の具体例については後述する。属性部データ１５は、数値表データ１２に含まれる属性部のデータである。属性部データ１５の具体例については後述する。
【００３１】
総和入出力範囲抽出部１６は、数値部データ１４から和の入出力関係がある範囲（領域範囲）を抽出する機能を有している。処理の詳細については後述する。総和入出力範囲１７は、総和入出力範囲抽出部１６により抽出された和の入出力関係がある範囲の情報である。総和入出力範囲１７の具体例については後述する。和の入出力関係に代えて積の入出力関係に対応する場合には、総和入出力範囲抽出部１６に代えて「総積入出力範囲抽出部」とし、積の入出力関係がある範囲を抽出するようにする。また、和の入出力関係と積の入出力関係が併存する場合には、総和入出力範囲抽出部１６と「総積入出力範囲抽出部」を併存させる。
【００３２】
属性ラベリング部１８は、属性部データ１５に対し、総和入出力範囲１７と属性ラベリングパターン１１を参照して属性ラベリングを行う機能を有している。処理の詳細については後述する。ラベルデータ１９は、属性ラベリング部１８により属性ラベリングが行われた結果のデータである。ラベルデータ１９の具体例については後述する。
【００３３】
図１０は情報処理装置１のハードウェア構成例を示す図である。図１０において、情報処理装置１は、システムバス１０１に接続されたＣＰＵ（Central Processing Unit）１０２、ＲＯＭ（Read Only Memory）１０３、ＲＡＭ（Random Access Memory）１０４、ＮＶＲＡＭ（Non-Volatile Random Access Memory）１０５を備えている。また、情報処理装置１は、Ｉ／Ｆ（Interface）１０６と、Ｉ／Ｆ１０６に接続された、Ｉ／Ｏ（Input/Output Device）１０７、ＨＤＤ（Hard Disk Drive）／フラッシュメモリ１０８、ＮＩＣ（Network Interface Card）１０９と、Ｉ／Ｏ１０７に接続されたモニタ１１０、キーボード１１１、マウス１１２等を備えている。Ｉ／Ｏ１０７にはＣＤ／ＤＶＤ（Compact Disk/Digital Versatile Disk）ドライブ等を接続することもできる。
【００３４】
図９で説明した情報処理装置１の機能は、ＣＰＵ１０２において所定のプログラムが実行されることで実現される。プログラムは、記録媒体を経由して取得されるものでもよいし、ネットワークを経由して取得されるものでもよい。
【００３５】
＜動作＞
図１１は上記の実施形態の処理例を示すフローチャートである。図１１において、情報処理装置１は、属性ラベリングパターン１１の入力（予め用意されたものの中から選択する場合を含む）を行う（ステップＳ１）。図１２は属性ラベリングパターン１１の例を示す図であり、「直上のセルを関連ラベルとする    もし空欄ならば、総和入出力関係の範囲で行方向に最近傍の入れ子の入出力関係に含まれない非空欄セルを関連ラベルとする    複数段ある場合は下段から上段の行ごとに再帰的に処理する」といった内容である。なお、左右方向に数値の入力領域（セル）が広がり、上部に属性が配置される場合に対応した例となっている。上下方向に数値の入力領域が広がり、左部に属性が配置される場合は、「直上」を「直左」、「行」を「列」、「下段」を「右段」、「上段」を「左段」等に読み替えることにより、同様に適用することができる。また、属性ラベリングパターン１１の内部的なデータの形式としては、記号等を用いたものとすることができる。
【００３６】
図１１に戻り、情報処理装置１は、処理対象となる数値表データ１２の入力を行う（ステップＳ２）。図１３（ａ）は数値表データ１２の例を示しており、従来において抽出が正常に行えない場合（図７）と同じものとしている。また、図１４（ａ）は数値表データ１２の他の例を示しており、従来において抽出が正常に行えない場合（図８）と同じものとしている。
【００３７】
図１１に戻り、入力データが揃った後に実質的な処理を開始すると、属性部・数値部分離部１３は、数値表データ１２から数値部データ１４と属性部データ１５を分離して抽出する（ステップＳ３）。すなわち、属性部・数値部分離部１３は、数値表データ１２の各セルをスキャンして数値が設定されているか文字列が設定されているかを認識し、数値が設定されている領域を数値部データ１４とし、文字列が設定されている領域を属性部データ１５として抽出する。数値部データ１４と属性部データ１５は、数値表データ１２におけるセルの位置を特定する列または行の位置を示す情報も含む。
【００３８】
図１３（ｂ）は図１３（ａ）の数値表データ１２から抽出された数値部データ１４を示し、図１３（ｃ）は図１３（ａ）の数値表データ１２から抽出された属性部データ１５を示している。また、図１４（ｂ）は図１４（ａ）の数値表データ１２から抽出された数値部データ１４を示し、図１４（ｃ）は図１４（ａ）の数値表データ１２から抽出された属性部データ１５を示している。
【００３９】
図１１に戻り、総和入出力範囲抽出部１６は、数値部データ１４から総和入出力範囲を抽出する（ステップＳ４）。以下、総和入出力範囲の抽出の詳細について説明する。
【００４０】
図１５は入れ子を考慮しない場合の総和入出力範囲の抽出（図１１のステップＳ４）の処理例を示すフローチャートである。入れ子とは、一の総和入出力範囲の中に他の総和入出力範囲が含まれる場合である。図１５に示した処理では、総和入出力関係を抽出するのは高コストであるのに対し、ある総和入出力関係に対して、その関係を満足するかどうかを検証することは低コストであることから、サンプルした行から総和入出力関係を抽出し、抽出した関係が全ての行で満足するかを検証するようにしている。これにより、トータルのコストを削減することができる。
【００４１】
図１５において、総和入出力範囲抽出部１６は、数値部データ１４からsample数個の行を抽出する（ステップＳ４１）。sample数は、候補となる入出力関係を計算する行の個数であり、予め設定される。
【００４２】
次いで、総和入出力範囲抽出部１６は、抽出フェーズとして、サンプルした各行について誤差e以下の総和入出力関係（input, out)を抽出する（ステップＳ４２）。誤差eは、数値の丸め等により発生する数値上の微差を許容する上限を示す値であり、小さな値である。誤差eは、数値データの差の値で定義してもよいし、比率（入力総和と出力の大きい側の値に対する入力総和と出力の差の比率）で定義してもよい。
【００４３】
総和入出力関係（input, out)を抽出するということは、入力範囲と出力位置が連続していると仮定した場合、「連続部分集合和問題」（総積入出力関係については連続部分集合積問題と読み替える）を解くことに帰着する。図１６（ａ）は、整数配列Ｓ（配列の長さをｎとすると、要素はＳ［１］〜Ｓ［ｎ］）に対し、出力位置ｉ、入力範囲開始位置ｊ、入力範囲終了位置ｋとした場合に、誤差eの範囲に収まる場合の条件式を示している。入力範囲開始位置ｊと入力範囲終了位置ｋで既定される入力範囲は総和入出力関係のinputとなり、出力位置ｉは、総和入出力関係のoutputに対応する。出力位置ｉに対して右側に入力範囲が存在する場合は図１６（ｂ）のようになり、出力位置ｉに対して左側に入力範囲が存在する場合は図１６（ｃ）のようになり、図１６（ａ）の条件式は両者の場合を含んでいる。
【００４４】
図１７は累積和配列と二分探索を用いた総和入出力関係の抽出（図１５のステップＳ４２）の処理例を示すフローチャートである。この処理例では、整数配列Ｓについての累積和配列Ｒ（総積入出力関係については累積積配列と読み替える）を導入し、二分探索を用いることで、O(n log n)時間（O：オーダ）で計算が可能となる。
【００４５】
図１７において、総和入出力範囲抽出部１６は、出力位置ｉを配列Ｓの先頭（または末尾）に固定する（ステップＳ４２１）。
【００４６】
次いで、総和入出力範囲抽出部１６は、出力位置ｉの右側に入力範囲があると仮定した場合と、出力位置ｉの左側に入力範囲があると仮定した場合とについて、並行してまたは順次に、二分探索によるｋまたはｊの導出を行う（ステップＳ４２２、Ｓ４２３）。
【００４７】
出力位置ｉの右側に入力範囲があると仮定した場合の二分探索は次のようになる。先ず、上界ｕｐを配列Ｓのサイズ、下界ｌｏｗをｉ＋１（＝ｊ）として二分探索を行う。中央値ｃを上界ｕｐと下界ｌｏｗの中間の位置とすると、ｃ＝（ｕｐ＋ｌｏｗ）／２となる。
【００４８】
ここで、求めたいのは｜Ｓ［ｉ］−（Ｒ［ｋ］−Ｒ［ｉ］）｜≦ｅを満たすｋである。よって、ｋ＝ｃとして条件を満たすなら二分探索は終了となる。条件を満たさない場合、新たに上界ｕｐと下界ｌｏｗを設定して探索を続ける。Ｒ［ｃ］−Ｒ［ｉ］＞Ｓ［ｉ］＋ｅならばｋはｃより小さいのでｕｐ＝ｃ−１とし、再帰的に処理を行う。また、Ｒ［ｃ］−Ｒ［ｉ］＜Ｓ［ｉ］−ｅならばｋはｃより大きいのでｌｏｗ＝ｃ＋１とし、再帰的に処理を行う。もし、ｕｐ＜ｌｏｗとなれば現在のｉに対して解なしとなる。出力位置ｉの左側に入力範囲があると仮定した場合についても、処理の考え方は同様である。
【００４９】
次いで、総和入出力範囲抽出部１６は、出力位置iを移動し（ステップＳ４２４）、全範囲について未了であればｋまたはｊの導出（ステップＳ４２２、Ｓ４２３）から繰り返し、全範囲について完了すれば、総和入出力範囲（i, j, k）を出力する（ステップＳ４２５）。
【００５０】
図１８は総和入出力範囲の抽出の例を示す図であり、図１３（ｂ）の数値部データ１４について処理を行った場合である。図１８（ａ）において、出力位置ｉ＝１の場合にｊ＝２、ｋ＝３、出力位置ｉ＝４の場合にｊ＝５、ｋ＝６で条件を満たし、それが図１８（ｂ）に示すように総和入出力範囲１７として出力される。図１８（ｂ）では可視的に描いてあるが、内部的にはｉ、ｊ、ｋの値を保持することにより総和入出力範囲１７を表すことができる。
【００５１】
図１５に戻り、総和入出力範囲抽出部１６は、検証フェーズとして、抽出した関係を満足する行数を計算し、満足する割合がサポート値support以上の入出力関係のみを出力する（ステップＳ４３）。supportは、候補となる入出力関係を出力するしきい値であり、予め設定される。
【００５２】
図１９は入れ子を考慮する場合の総和入出力範囲の抽出の処理例を示すフローチャートである。この処理例では、入れ子の深さｄを１から順次に深くしていき、抽出された総和入出力範囲の入力値を削除することで、入れ子にも対応できるようにしている。この処理では、図１７の累積和配列Ｒと二分探索と相まって、入れ子の最大深さをｍとして、O(mn log n)時間で計算が可能となる。
【００５３】
図１９において、総和入出力範囲抽出部１６は、深さｄに１を設定する（ステップＳ４０１）。
【００５４】
次いで、総和入出力範囲抽出部１６は、数値部データ１４からsample数個の行を抽出する（ステップＳ４０２）。この処理は、前述した処理（図１５のステップＳ４１）と同様である。
【００５５】
次いで、総和入出力範囲抽出部１６は、抽出フェーズとして、サンプルした各行について誤差e以下の総和入出力関係（input, out)を抽出する（ステップＳ４０３）。この処理は、前述した処理（図１５のステップＳ４２）と同様である。
【００５６】
次いで、総和入出力範囲抽出部１６は、検証フェーズとして、抽出した関係を満足する行数を計算し、満足する割合がサポート値support以上の入出力関係のみを抽出する（ステップＳ４０４）。この処理は、前述した処理（図１５のステップＳ４３）と同様である。
【００５７】
次いで、総和入出力範囲抽出部１６は、フィルタリングフェーズとして、入出力関係を満足する行数が多いものから順に重複しないように選択し、d, input, outを出力する（ステップＳ４０５）。
【００５８】
出力した入出力関係の個数が０でない場合（ステップＳ４０６のＮｏ）、総和入出力範囲抽出部１６は、深さｄをインクリメントし（ステップＳ４０７）、出力した入出力関係の入力値を削除（実際には無視）し（ステップＳ４０８）、行の抽出（ステップＳ４０２）から処理を繰り返す。出力した入出力関係の個数が０である場合（ステップＳ４０６のＹｅｓ）、総和入出力範囲抽出部１６は、処理を終了する。
【００５９】
図２０は総和入出力範囲の抽出の他の例を示す図であり、図１４（ｂ）の数値部データ１４について処理を行った場合である。図２０（ａ）において、１回目の抽出フェーズ（ステップＳ４０３）で、出力位置ｉ＝２についてｊ＝３、ｋ＝４、出力位置ｉ＝５についてｊ＝６、ｋ＝７、出力位置ｉ＝８についてｊ＝９、ｋ＝１０、出力位置ｉ＝１１についてｊ＝１２、ｋ＝１３で条件を満たす。
【００６０】
１回目の検証フェーズ（ステップＳ４０４）で上記の総和入出力範囲が抽出され、フィルタリングフェーズ（ステップＳ４０５）で出力されて、入力値が削除（ステップＳ４０８）された状態を図２０（ｂ）に示す。削除された配列位置は再付番号される。この状態において、２回目の抽出フェーズ（ステップＳ４０３）で、出力位置ｉ＝１についてｊ＝２、ｋ＝３で条件を満たす。図２０（ｃ）は出力される総和入出力範囲１７を示している。なお、入力値の削除により再付番号された配列位置は元の位置に変換（後ろに削除された入力値が続く場合はその後端まで延長することも含む）される。
【００６１】
図１１に戻り、属性ラベリング部１８は、属性部データ１５に対し、総和入出力範囲１７と属性ラベリングパターン１１を参照して属性ラベリングを行い、属性ラベリングが行われた結果をラベルデータ１９として出力する（ステップＳ５）。
【００６２】
図２１は属性ラベリングの例を示す図であり、図１３の例に対応したものである。図２１において、属性部データ１５の左端のラベル「総数」については、直上のセルが空欄であるため、従来（図７）の手法では誤ってラベリングされてしまっていた。しかし、本実施形態では、自らが属する総和入出力範囲で行方向に最近傍の「交通事故」を関連ラベル（親ラベル）とするため、本来の「交通事故−総数」としてラベリングされる。また、「水難事故」に属する「総数」についても、従来（図７）の手法では誤ってラベリングされてしまっていたが、本実施形態では、本来の「水難事故−総数」としてラベリングされる。
【００６３】
図２２は属性ラベリングの他の例を示す図であり、図１４の例に対応したものである。図２２において、属性部データ１５の「交通事故」「水難事故」について、上の行にある「災害」によって、従来（図８）の手法では誤ってラベリングされてしまっていた。しかし、本実施形態では、自らが属する総和入出力範囲で判断されるため、「災害」が誤って親ラベルとされることはなくなる。
【００６４】
なお、図５に示した上下方向に属性および数値が並ぶ場合についても、上下方向に対応した総和入出力関係の抽出により正確にラベリングを行うことができる。
【００６５】
＜総括＞
以上説明したように、本実施形態によれば、数値表データにおけるそれぞれの数値データに対応付ける属性情報を簡単に特定することができる。また、様々なパターンをより簡潔なパターンにより処理することが可能となり、パターン作成コストを従来よりも低減することができる。更に、和・積入出力関係により抽出範囲を限定することで、誤ったラベリングの減少や質の向上が期待できる。
【００６６】
以上、好適な実施の形態により説明した。ここでは特定の具体例を示して説明したが、特許請求の範囲に定義された広範な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更を加えることができることは明らかである。すなわち、具体例の詳細および添付の図面により限定されるものと解釈してはならない。
【００６７】
数値部データ１４は「数値が入力された複数の入力領域」の一例である。総和入出力関係または総積入出力関係は「算術的な関係」の一例である。属性部データ１５は「左方向または上方向に配置された入力領域」の一例である。
【００６８】
以上の説明に関し、更に以下の項を開示する。
（付記１）  上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域を特定し、
特定した前記複数の入力領域の内、左右方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、
抽出した前記複数の入力領域の何れかの入力領域の上方向に配置された入力領域の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、
処理をコンピュータが実行することを特徴とするデータ処理方法。
（付記２）  上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域を特定し、
特定した前記複数の入力領域の内、上下方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、
抽出した前記複数の入力領域の何れかの入力領域の左方向に配置された入力領域の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、
処理をコンピュータが実行することを特徴とするデータ処理方法。
（付記３）  前記算術的な関係を有する複数の入力領域を抽出する処理は、前記算術的な関係を総和入出力関係または総積入出力関係とし、入力範囲と出力位置が連続しているとして連続部分集合和問題または連続部分集合積問題の解により前記算術的な関係を有する複数の入力領域を抽出する、
ことを特徴とする付記１または２に記載のデータ処理方法。
（付記４）  前記算術的な関係を有する複数の入力領域を抽出する処理は、出力位置を順次に固定し、二分探索により入力範囲を特定する、
ことを特徴とする付記３に記載のデータ処理方法。
（付記５）  前記算術的な関係を有する複数の入力領域を抽出する処理は、特定された入力範囲を削除し、入力領域が抽出されなくなるまで、前記算術的な関係を有する複数の入力領域の抽出を繰り返す、
ことを特徴とする付記３または４に記載のデータ処理方法。
（付記６）  上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域を特定し、
特定した前記複数の入力領域の内、左右方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、
抽出した前記複数の入力領域の何れかの入力領域の上方向に配置された入力領域の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、
処理をコンピュータに実行させるデータ処理プログラム。
（付記７）  上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域を特定し、
特定した前記複数の入力領域の内、上下方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出し、
抽出した前記複数の入力領域の何れかの入力領域の左方向に配置された入力領域の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける、
処理をコンピュータに実行させるデータ処理プログラム。
（付記８）  前記算術的な関係を有する複数の入力領域を抽出する処理は、前記算術的な関係を総和入出力関係または総積入出力関係とし、入力範囲と出力位置が連続しているとして連続部分集合和問題または連続部分集合積問題の解により前記算術的な関係を有する複数の入力領域を抽出する、
付記６または７に記載のデータ処理プログラム。
（付記９）  前記算術的な関係を有する複数の入力領域を抽出する処理は、出力位置を順次に固定し、二分探索により入力範囲を特定する、
付記８に記載のデータ処理プログラム。
（付記１０）  前記算術的な関係を有する複数の入力領域を抽出する処理は、特定された入力範囲を削除し、入力領域が抽出されなくなるまで、前記算術的な関係を有する複数の入力領域の抽出を繰り返す、
付記８または９に記載のデータ処理プログラム。
（付記１１）  上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域を特定する手段と、
特定した前記複数の入力領域の内、左右方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出する手段と、
抽出した前記複数の入力領域の何れかの入力領域の上方向に配置された入力領域の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける手段と、
を備えたことを特徴とする情報処理装置。
（付記１２）  上下方向および左右方向に並べて配置された複数の入力領域の内、数値が入力された複数の入力領域を特定する手段と、
特定した前記複数の入力領域の内、上下方向に連続的に配置され、且つ、入力された数値間に算術的な関係を有する複数の入力領域を抽出する手段と、
抽出した前記複数の入力領域の何れかの入力領域の左方向に配置された入力領域の少なくとも何れかの入力領域内の文字列を、抽出した前記複数の入力領域に入力された数値に対応付ける手段と、
を備えたことを特徴とする情報処理装置。
（付記１３）  前記算術的な関係を有する複数の入力領域を抽出する手段は、前記算術的な関係を総和入出力関係または総積入出力関係とし、入力範囲と出力位置が連続しているとして連続部分集合和問題または連続部分集合積問題の解により前記算術的な関係を有する複数の入力領域を抽出する、
ことを特徴とする付記１１または１２に記載の情報処理装置。
（付記１４）  前記算術的な関係を有する複数の入力領域を抽出する手段は、出力位置を順次に固定し、二分探索により入力範囲を特定する、
ことを特徴とする付記１３に記載の情報処理装置。
（付記１５）  前記算術的な関係を有する複数の入力領域を抽出する手段は、特定された入力範囲を削除し、入力領域が抽出されなくなるまで、前記算術的な関係を有する複数の入力領域の抽出を繰り返す、
ことを特徴とする付記１３または１４に記載の情報処理装置。
【符号の説明】
【００６９】
１        情報処理装置
１１      属性ラベリングパターン
１２      数値表データ
１３      属性部・数値部分離部
１４      数値部データ
１５      属性部データ
１６      総和入出力範囲抽出部
１７      総和入出力範囲
１８      属性ラベリング部
１９      ラベルデータ
【図１】
0006716873.tif 000002
【図２】
0006716873.tif 000003
【図３】
0006716873.tif 000004
【図４】
0006716873.tif 000005
【図５】
0006716873.tif 000006
【図６】
0006716873.tif 000007
【図７】
0006716873.tif 000008
【図８】
0006716873.tif 000009
【図９】
0006716873.tif 000010
【図１０】
0006716873.tif 000011
【図１１】
0006716873.tif 000012
【図１２】
0006716873.tif 000013
【図１３】
0006716873.tif 000014
【図１４】
0006716873.tif 000015
【図１５】
0006716873.tif 000016
【図１６】
0006716873.tif 000017
【図１７】
0006716873.tif 000018
【図１８】
0006716873.tif 000019
【図１９】
0006716873.tif 000020
【図２０】
0006716873.tif 000021
【図２１】
0006716873.tif 000022
【図２２】
0006716873.tif 000023