(57)【要約】【課題】  分割ファイルの最大サイズを小さくし、かつファイル分割の時間を短縮し、メモリ使用量及び外部記憶装置アクセスの削減を可能にする。【解決手段】  本発明は、分割数と分割重複数を取得し、入力ファイルの先頭位置をポインタ格納領域に設定し、該入力ファイルから該ポインタ格納領域のポインタに対応する行を読み出し、同一の主キーの行は同一振分先となるように分割数のうち分割重複数（但し、分割重複数＜分割数）の振分先を決定し、該分割重複数に応じた複製を行うことで行の振分を行い、分割ファイルに追加格納する処理を、該入力ファイルの終端位置のポインタになるまで繰り返し、分割完了後に、分割ファイルのサイズ（行数）を比較し、行数の大きい上位Ｎ（Ｎ＝分割重複数―１）件の分割ファイルを排除する。【選択図】  図１
2011186852.tif 000002
【特許請求の範囲】
【請求項１】
主キーの重複が許されている処理対象の入力ファイルを分割し、同一主キー値の行は同一振分先となるように分割ファイルに格納するファイル分割装置であって、
分割数が格納された分割数情報記憶手段と、
分割重複数が格納された分割重複数情報記憶手段と、
前記分割数情報記憶手段から分割数を取得し、前記分割重複数情報記憶手段から分割重複数を取得し、前記入力ファイルの先頭位置をポインタ格納領域に設定する設定手段と、
前記入力ファイルから該ポインタ格納領域のポインタに対応する行を読み出し、同一の主キーの行は同一振分先となるように前記分割数のうち前記分割重複数（但し、分割重複数＜分割数）の振分先を決定し、該分割重複数に応じた複製を行うことで行の振分を行い、前記分割ファイルに追加格納する処理を、該ポインタが該入力ファイルの終端位置になるまで繰り返すファイル出力手段と、
分割完了後に、前記分割ファイルのサイズ（行数）を比較し、行数の大きい上位Ｎ（Ｎ＝分割重複数―１）件の分割ファイルを排除する分割ファイル排除手段と、
を有することを特徴とするファイル分割装置。
【請求項２】
主キー毎に振り分け先を格納する振分先リストを有する振分先情報記憶手段と、
主キー毎に振り分け先候補を格納する振分先候補リスト振分先候補情報記憶手段と、を有し、
前記ファイル出力手段は、
前記格納領域から行を読み出し、該行から主キーを抽出する手段と、
前記主キーに対応する前記振分先候補リストに初期値として１から分割数まで（｛１，２，…，分割数｝）の要素を設定し、振分先候補から公平に選抜した分割重複数の振分先を決定し、前記主キーに対応する前記振分先リストに格納する手段を含む
請求項１記載のファイル分割装置。
【請求項３】
主キーの重複が許されている処理対象の入力ファイルを分割し、同一主キー値の行は同一振分先となるように分割ファイルに格納するファイル分割方法であって、
分割数が格納された分割数情報記憶手段と、分割重複数が格納された分割重複数情報記憶手段と、を有する装置において、
前記分割数情報記憶手段から分割数を取得する分割数取得ステップと、
前記分割重複数情報記憶手段から分割重複数を取得する分割重複数取得ステップと、
前記分割数情報記憶手段から分割数を取得し、前記分割重複数情報記憶手段から分割重複数を取得し、前記入力ファイルの先頭位置をポインタ格納領域に設定するステップと、
前記入力ファイルから該ポインタ格納領域のポインタに対応する行を読み出し、同一の主キーの行は同一振分先となるように前記分割数のうち前記分割重複数（但し、分割重複数＜分割数）の振分先を決定し、該分割重複数に応じた複製を行うことで行の振分を行い、前記分割ファイルに追加格納する処理を、該ポインタが該入力ファイルの終端位置になるまで繰り返すファイル出力ステップと、
分割完了後に、前記分割ファイルのサイズ（行数）を比較し、行数の大きい上位Ｎ（Ｎ＝分割重複数―１）件の分割ファイルを排除する分割ファイル排除ステップと、
を行うことを特徴とするファイル分割方法。
【請求項４】
前記ファイル出力ステップにおいて、
前記格納領域から行を読み出し、該行から主キーを抽出する手段と、
前記主キーに対応する振分先候補リストに初期値として１から分割数まで（｛１，２，…，分割数｝）の要素を設定し、振分先候補から公平に選抜した分割重複数の振分先を決定し、前記主キーに対応する振分先リストに格納する
請求項３記載のファイル分割方法。
【請求項５】
請求項１または２に記載のファイル分割装置を構成する各手段としてコンピュータを機能させるためのファイル分割プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ファイル分割装置及び方法及びプログラムに係り、特に、入力された処理対象ファイル（入力ファイル）を複数のファイルに分割するためのファイル分割装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
ファイル分割を行うために、周回する境界条件で順番に振り分け先を決定する方式（ラウンドロビン）がある（例えば、非特許文献１参照 ）。
【０００３】
また、キー重複数を入力ファイルに付加し、キー重複数の大きな順にサイズの小さな分割ファイルから振り分ける方法がある（例えば、特許文献１参照）。
【０００４】
また、入力ファイルの統計情報を元に最適な均等振り分け計画を構築する方法（整数計画法）がある（例えば、非特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−８６９５１号公報
【非特許文献】
【０００６】
【非特許文献１】相磯秀夫、田中英彦編集「第２版コンピュータの辞典」、p502,  朝倉書店
【非特許文献２】相磯秀夫、田中英彦編集「第２版コンピュータの辞典」、p731,  朝倉書店
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記のラウンドロビンによる方法では、入力ファイルのキー重複数の分布が非一様の場合に分割ファイルのサイズが均等化されないという問題がある。
【０００８】
また、キー重複数の大きな順にサイズの小さな分割ファイルから振り分ける技術や整数計画法を用いる技術は、入力ファイルの全体読み込みが完了する（キー重複数情報作成）まで振り分けを開始することができない。そのため、入力ファイルの全体読み込みが完了してから振り分けを開始するためメモリ使用量、外部記憶装置アクセスが余計に発生してしまうという問題がある。
【０００９】
本発明は、上記の点に鑑みなされたもので、分割ファイルの最大サイズを小さくし、かつファイル分割の時間を短縮することが可能なファイル分割装置及び方法及びプログラムを提供することを目的とする。
【００１０】
さらに、メモリ使用量及び外部記憶装置アクセスの削減が可能なファイル分割装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
図１は、本発明の原理構成図である。
【００１２】
本発明（請求項１）は、主キーの重複が許されている処理対象の入力ファイル１を分割し、同一主キー値の行は同一振分先となるように分割ファイル３に格納するファイル分割装置であって、
分割数が格納された分割数情報記憶手段６と、
分割重複数が格納された分割重複数情報記憶手段７と、
分割数情報記憶手段６から分割数を取得し、分割重複数情報記憶手段７から分割重複数を取得し、前記入力ファイルの先頭位置をポインタ格納領域に設定し、該入力ファイル１から該ポインタ格納領域のポインタに対応する行を読み出し、同一の主キーの行は同一振分先となるように分割数のうち分割重複数（但し、分割重複数＜分割数）の振分先を決定し、該分割重複数に応じた複製を行うことで行の振分を行い、分割ファイル３に追加格納する処理を、該ポインタが該入力ファイルの終端位置になるまで繰り返すファイル出力手段２３と、
分割完了後に、分割ファイル３のサイズ（行数）を比較し、行数の大きい上位Ｎ（Ｎ＝分割重複数―１）件の分割ファイルを排除する分割ファイル排除手段２４と、を有する。
【００１３】
また、本発明（請求項２）は、主キー毎に振り分け先を格納する振分先リストを有する振分先情報記憶手段と、
主キー毎に振り分け先候補を格納する振分先候補リスト振分先候補情報記憶手段と、を有し、
ファイル出力手段２３は、
格納領域から行を読み出し、該行から主キーを抽出する手段と、
前記主キーに対応する前記振分先候補リストに初期値として１から分割数まで（｛１，２，…，分割数｝）の要素を設定し、振分先候補から公平に選抜した分割重複数の振分先を決定し、前記主キーに対応する振分先リストに格納する手段を含む。
【００１４】
図２は、本発明の原理を説明するための図である。
【００１５】
本発明（請求項３）は、主キーの重複が許されている処理対象の入力ファイルを分割し、同一主キー値の行は同一振分先となるように分割ファイルに格納するファイル分割方法であって、
分割数が格納された分割数情報記憶手段と、分割重複数が格納された分割重複数情報記憶手段と、を有する装置において、
分割数情報記憶手段から分割数を取得する分割数取得ステップ（ステップ１）と、
分割重複数情報記憶手段から分割重複数を取得する分割重複数取得ステップ（ステップ２）と、
分割数情報記憶手段から分割数を取得し（ステップ１）、分割重複数情報記憶手段から分割重複数を取得し（ステップ２）、入力ファイルの先頭位置をポインタ格納領域に設定する（ステップ３）設定ステップと、
入力ファイルから該ポインタ格納領域のポインタに対応する行を読み出し（ステップ４）、同一の主キーの行は同一振分先となるように前記分割数のうち前記分割重複数（但し、分割重複数＜分割数）の振分先を決定し（ステップ５）、該分割重複数に応じた複製を行うことで行の振分を行い（ステップ６）、分割ファイルに追加格納する（ステップ７）処理を、該ポインタが該入力ファイルの終端位置になるまで繰り返す（ステップ８）ファイル出力ステップと、
分割完了後に、分割ファイルのサイズ（行数）を比較し、行数の大きい上位Ｎ（Ｎ＝分割重複数―１）件の分割ファイルを排除する分割ファイル排除ステップ（ステップ９）と、
を行う。
【００１６】
また、本発明（請求項４）は、ファイル出力ステップにおいて、
格納領域から行を読み出し、該行から主キーを抽出する手段と、
主キーに対応する振分先候補リストに初期値として１から分割数まで（｛１，２，…，分割数｝）の要素を設定し、振分先候補から公平に選抜した分割重複数の振分先を決定し、主キーに対応する振分先リストに格納する。
【００１７】
本発明（請求項５）は、請求項１または２に記載のファイル分割装置を構成する各手段としてコンピュータを機能させるためのファイル分割プログラムである。
【発明の効果】
【００１８】
入力ファイルの主キー値は入力ファイル全体で重複が許されており、ファイル分割時に同一主キー値の行は同一振分先となる制約条件の下で、分割重複数に基づいて、行単位での複製を用いた振分により分割候補生成を行い、分割完了後に分割ファイルのサイズが大きな上位Ｎ（分割重複数−１）件の分割ファイルを排除することにより、分割ファイルの最大サイズを小さくし、かつ、ファイル分割の時間短縮が可能となる。
【００１９】
また、入力ファイルの先頭位置をポインタ格納領域に設定し、当該ポインタ格納領域の先頭位置から行を読み出し、行の振分を入力ファイルの終端位置まで行うことで、入力ファイルのスキャンは１回で済むため、メモリ使用量、外部記憶装置のアクセス回数の削減が可能である。
【図面の簡単な説明】
【００２０】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の一実施の形態におけるファイル分割装置の構成図である。
【図４】本発明の一実施の形態における入力ファイルのフォーマットである。
【図５】本発明の一実施の形態における振分先情報記憶部の例である。
【図６】本発明の一実施の形態における振分先候補情報記憶部の例である。
【図７】本発明の一実施の形態におけるファイル分割処理部の構成図である。
【図８】本発明の一実施の形態におけるファイル分割部のフローチャートである。
【図９】本発明の一実施の形態におけるファイル出力処理（Ｓ１２０）のフローチャートである。
【図１０】本発明の一実施の形態における行の振分処理（Ｓ１２３）の詳細なフローチャートである。
【図１１】本発明の一実施の形態における振分先決定処理（Ｓ１２３３）の詳細なフローチャートである。
【図１２】本発明の一実施の形態における分割ファイル排除処理（Ｓ１３０）の詳細なフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面と共に本発明の実施の形態を説明する。
【００２２】
図３は、本発明の一実施の形態におけるファイル分割装置の構成を示す。
【００２３】
同図に示すファイル分割装置は、入力ファイル１、ファイル分割部２、分割ファイル３、振分先情報記憶部４、振分先候補情報記憶部５、分割数情報記憶部６、分割重複数情報記憶部７、メモリ８から構成される。このうち、振分先情報記憶部４、振分先候補情報記憶部５、分割数情報記憶部６、分割重複数情報記憶部７はファイル分割処理部２とデータバスで接続された記憶装置に格納されている。また、メモリ８は、読み込まれた入力ファイル１のハンドルに基づいて格納するポインタ格納領域を有する。
【００２４】
入力ファイル１は、図４に示すように、主キーａ、副キーｂ、データ部ｃから構成された行の集まりであり、主キーａと副キーｂにより行が特定可能であるが、主キー値は入力ファイル全体で重複が許されている。ファイル分割は、主キー値による集約計算を並列処理する目的で行われるため、同一主キー値の行は同一振分先となる制約条件を課す。
【００２５】
振分先情報記憶部４は、図５に示すような振分先リストを有し、当該振分先リストには、主キー毎の振分先が設定される。
【００２６】
振分先候補記憶部５は、図６に示すような振分先候補リストを有し、主キー毎に振分先候補が設定される。
【００２７】
分割数情報記憶部６は、分割数を格納している。
【００２８】
分割重複数情報記憶部７は、分割重複数を格納している。
【００２９】
ファイル分割部２は、入力ファイル１から分割ファイル３を生成する。
【００３０】
図７は、本発明の一実施の形態におけるファイル分割処理部の構成を示す。
【００３１】
ファイル分割処理部２は、分割数取得部２１、分割重複数取得部２２、ファイル出力部２３、分割ファイル排除部２４を有する。ファイル出力部２３は、ポインタ格納領域設定部２３１、振分先決定部２３２、分割ファイル格納部２３３を有する。
【００３２】
分割数取得部２１は、分割数情報記憶部６から分割数を取得し、振分先決定２３２に出力する。
【００３３】
分割重複数取得部２２は、分割重複数情報記憶部７から分割重複数を取得して分割ファイル排除部２４及び振分先決定部２３２に出力する。
【００３４】
ファイル出力部２３のポインタ格納領域設定部２３１は、入力ファイル１を読み込み、メモリ８内のポインタ格納領域Ｐに入力ファイルの行の位置を格納する。
【００３５】
振分先決定部２３２は、メモリ８のポインタ格納領域Ｐから入力ファイルの行の位置を取得し、行を読み出し、分割ファイル３に振り分けて格納する。この際に、振分先決定部２３２は、読み出した行から主キーを抽出し、当該主キーが振分先情報記憶部４に登録されていれば、同じ主キーの行は同一振分先となるように、分割数のうち、分割重複数（但し、分割重複数＜分割数）分の行を分割ファイル３に追加格納する。登録されていない場合は、図１１で後述する処理により振分先を決定し、振分先情報記憶部４に追加する。
【００３６】
以下に、上記の構成における入力ファイル１から分割ファイル３を生成する処理を説明する。
【００３７】
図８は、本発明の一実施の形態におけるファイル分割部のフローチャートである。
【００３８】
ステップ１００）  ファイル分割部２は、分割数情報ファイル６を読み込んで、分割数を抽出する。
【００３９】
ステップ１１０）  分割重複数情報記憶部７を読み込んで、分割重複数を抽出する。
【００４０】
ステップ１２０）  ファイル出力処理として、図９に示す処理を行う。
【００４１】
ステップ１３０）  分割ファイル排除処理として、図１２の処理を行う。
【００４２】
次に、上記のステップ１２０の処理を説明する。
【００４３】
図９は、本発明の一実施の形態におけるファイル出力処理のフローチャートである。
【００４４】
ステップ１２１）  入力ファイル１のハンドルを元に、入力ファイル先頭位置を取得し、メモリ８のポインタ格納領域Ｐに格納する。
【００４５】
ステップ１２２）  入力ファイル１からポインタ格納領域Ｐのポインタに対応する行の読み出しを行う。
【００４６】
ステップ１２３）  読み出された行の振分を行う。以下に詳細な動作を、図１０に基づいて説明する。
【００４７】
ステップ１２３１）  読み出された行の内容から主キーを抽出する。
【００４８】
ステップ１２３２）  主キーを元に振分先情報記憶部４を検索し、登録済みか判定し、未登録であればステップ１２３３に移行し、登録済みであればステップ１２３５に移行する。
【００４９】
ステップ１２３３）  振分先を決定する。詳細は図１１において後述する。
【００５０】
ステップ１２３４）  決定された振分先を振分先記憶部４の振分先リストに追加格納し、ステップ１２３６に移行する。
【００５１】
ステップ１２３５）  振分先情報記憶部４に主キーが登録されている場合は、主キーに基づいて振分先情報記憶部４を検索し、振分先を取得する。
【００５２】
ステップ１２３６）  行の内容を振分先の分割ファイル３に追記出力する。
【００５３】
ステップ１２４）  ポインタ格納領域Ｐのポインタが入力ファイル１の終端位置に到達したかを判定し、到達していない場合はステップ１２５に移行し、到達した場合はステップ１３０に移行する。
【００５４】
ステップ１２５）  ポインタ格納領域Ｐに次の行の位置を格納し、ステップ１２２に移行する。
【００５５】
次に、上記のステップ１２３３の振分先決定処理について、図１１に沿って説明する。
【００５６】
図１１は、本発明の一実施の形態における振分先決定処理のフローチャートである。
【００５７】
同図の処理は、モンテカルロ法を用いた一例であるが、分割数の候補から分割重複数の振分先を公平に選抜できる方法であれば、この例に限定されない。
【００５８】
ステップ１２３３１）  最初に、振分情報記憶部４の主キーに対応する振分先リストを空に初期化する。
【００５９】
ステップ１２３３２）  主キーに基づいて振分先候補情報記憶部５を検索し、対応する振分先候補リストに初期値として｛１，２，…，分割数｝を設定する。
【００６０】
ステップ１２３３３）  振分先候補情報記憶部５の主キーに対応する振分先リストの要素数を取得し、「区間０以上１以下」を要素数で等分し、等分した部分区間に対し、順番に振分先候補リストの要素に１対１で割り当てる。例えば、分割数＝５である場合は、５つの部分区間に等分され、各要素数の番号（振分先）を割り当てる。
【００６１】
ステップ１２３３４）  「区間０以上１以下」での一様な疑似乱数を取得する。
【００６２】
ステップ１２３３５）  ステップ１２３３３で得られた部分区間に対し、疑似乱数の値がどの部分区間に入るか（何番目の部分区間に乱数ｘが含まれるか）判定し、割り当てた対応付けを表現する構造体を元に振分先を決定する。
【００６３】
ステップ１２３３６）  決定された振分先（ｍ番目）の振分先候補を主キーに対応する振分先情報記憶部４の振分先リストに追加する。
【００６４】
ステップ１２３３７）  決定された振分先（ｍ番目）の振分先候補を主キーに対応する振分先候補情報記憶部５の振分先候補リストから除去する。
【００６５】
ステップ１２３３８）  主キーの振分先情報記憶部４の要素数が分割重複数以上であれば処理を終了し、そうでなければステップ１２３３３に移行する。
【００６６】
次に、上記のステップ１３０の分割ファイル排除処理について説明する。
【００６７】
図１２は、本発明の一実施の形態における分割ファイル排除処理の詳細なフローチャートである。
【００６８】
ステップ１３１）  分割ファイル３のサイズ（行数）を取得し、サイズの大きな上位Ｎ件（分割重複数―１）の分割ファイルのハンドルを取得する。
【００６９】
ステップ１３２）  ステップ１３１で取得した分割ファイルのハンドルを元にファイル排除（例えば、ファイル削除）を実行する。
【００７０】
上記のように、入力ファイル１のキー重複数がキー集合の一部の要素（上位Ｌ位とする）に偏って行数が大きな場合、分割候補の生成を行い、分割完了後にサイズの大きな分割ファイルを排除することにより、「上位Ｌ位のキーで識別される全ての行が同一振分先に収容されてしまう確率」を組み合わせ数が急速に増大する性質を用いることで小さくすることが可能であるため、分割ファイルサイズの最大サイズを小さくし、かつ、ファイル分割の時間短縮が可能となる。
【００７１】
なお、上記のファイル分割処理部２の動作をプログラムとして構築し、ファイル分割装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００７２】
また、構築されたプログラムをハードディスクや、フレキシブルディスクまたはＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００７３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００７４】
１  入力ファイル
２  ファイル分割処理（ＣＰＵ）
３  分割ファイル
４  振分先情報記憶部
５  振分先候補情報記憶部
６  分割数情報記憶部
７  分割重複数情報記憶部
８  メモリ
２１  分割数取得部
２２  分割重複数取得部
２４  ファイル出力部
２４  分割ファイル排除部
２３１  ポインタ格納領域設定部
２３２  振分先決定部
２３３  分割ファイル格納部
【図１】
2011186852.tif 000003
【図２】
2011186852.tif 000004
【図３】
2011186852.tif 000005
【図４】
2011186852.tif 000006
【図５】
2011186852.tif 000007
【図６】
2011186852.tif 000008
【図７】
2011186852.tif 000009
【図８】
2011186852.tif 000010
【図９】
2011186852.tif 000011
【図１０】
2011186852.tif 000012
【図１１】
2011186852.tif 000013
【図１２】
2011186852.tif 000014