(57)【特許請求の範囲】
【請求項１】
新聞や雑誌のように複数の記事情報が段組された文書のレイアウトを行う装置であって、
前記記事情報を入力する記事情報入力手段と、
段組数として予め指定した数値の範囲内で発生させた乱数によって求めた段組数と、前記段組数によって求めた段組と直交方向の座標値と、前記段組数との関係で定められた数値の範囲内で乱数によって求めた開始段数値及び同じく前記段組数との関係で定められた数値の範囲内で乱数によって求めた終了段数値で表わし、かつ分割線数として予め指定した数値の範囲内で発生させた乱数によって求めた数だけ設けた分割線と、各段の領域を前記分割線で分割することによって仕切られる単位領域に対して乱数によって求めて付加したコラム結合番号とを用いて、上下左右に隣接する同じコラム結合番号をもつ前記単位領域を結合してコラム形状を生成するコラム生成手段と、
前記コラム形状に対して配置処理のランダムな順序付けを行ってコラム配置処理順序付きコラム形状情報を生成するコラム配置処理順序生成手段と、
前記記事情報に対する配置処理のランダムな順序付けである記事配置処理順序を生成する記事配置処理順序生成手段と、
前記記事配置処理順序と前記コラム配置処理順序付きコラム形状情報とからなる配置元情報に基づいて前記コラム形状に対して前記記事情報の配置を順に試みることで配置結果を導出する割当手段と、
前記配置結果に対して評価を行い評価値を算出する配置結果評価手段と、
前記配置元情報とこれに対応する前記配置結果と前記評価結果とからなる配置情報を所定数記憶する配置情報群記憶手段と、
前記配置情報群記憶手段に記憶されている前記配置元情報を２組取り出して乱数を使って交叉させ新たな配置元情報を生成し、当該新たな配置元情報から前記割当手段及び前記配置結果評価手段によって対応する配置結果と評価結果を導出し、当該配置結果と当該評価結果を当該新たな配置元情報とともに配置情報として前記配置情報群記憶手段に記憶させる配置元情報合成手段と、
前記配置情報群記憶手段に記憶される前記評価値の中の最大の評価値に対応する配置結果を出力する最良配置探索手段と、
前記最良配置探索手段の出力する前記配置結果に基づいて前記記事情報を配置して出力する記事出力手段とを具備することを特徴とする記事配置装置。
【請求項２】
新聞や雑誌のように複数の記事情報が段組された文書のレイアウトを行う装置であって、
前記記事情報を入力する記事情報入力手段と、
段組数として予め指定した数値の範囲内で発生させた乱数によって求めた段組数と、前記段組数によって求めた段組と直交方向の座標値と、前記段組数との関係で定められた数値の範囲内で乱数によって求めた開始段数値及び同じく前記段組数との関係で定められた数値の範囲内で乱数によって求めた終了段数値で表わし、かつ分割線数として予め指定した数値の範囲内で発生させた乱数によって求めた数だけ設けた分割線と、各段の領域を前記分割線で分割することによって仕切られる単位領域に対して乱数によって求めて付加したコラム結合番号を用いて、上下左右に隣接する同じコラム結合番号をもつ前記単位領域を結合してコラム形状を生成するコラム生成手段と、
前記コラム形状に対して配置処理のランダムな順序付けを行ってコラム配置処理順序付きコラム形状情報を生成するコラム配置処理順序生成手段と、
前記記事情報に対する配置処理のランダムな順序付けである記事配置処理順序を生成する記事配置処理順序生成手段と、
前記記事配置処理順序と前記コラム配置処理順序付きコラム形状情報とからなる配置元情報に基づいて前記コラム形状に対して前記記事情報の配置を順に試みることで配置結果を導出する割当手段と、
前記配置結果に対して評価を行い評価値を算出する配置結果評価手段と、
前記配置元情報とこれに対応する前記評価結果とからなる配置情報を所定数記憶する配置情報群記憶手段と、
前記配置情報群記憶手段に記憶されている前記配置元情報を２組取り出して乱数を使って交叉させ新たな配置元情報を生成し、当該新たな配置元情報から前記割当手段及び前記配置結果評価手段によって対応する配置結果と評価結果を導出し、当該評価結果を当該新たな配置元情報とともに配置情報として前記配置情報群記憶手段に記憶させる配置元情報合成手段と、
前記配置情報群記憶手段に記憶される前記評価値の中の最大の評価値に対応する配置元情報を出力する最良配置探索手段と、
前記最良配置探索手段の出力する前記配置元情報に基づいて前記コラム形状に対して前記記事情報の配置を順に試みることで最良配置結果を導出する最良配置割当手段と、
前記最良配置結果に基づいて前記記事情報を配置して出力する記事出力手段とを具備することを特徴とする記事配置装置。
【請求項３】
前記割当手段が前記最良配置割当手段を兼ねることを特徴とする請求項２記載の記事配置装置。
【請求項４】
前記配置元情報合成手段が、新しい紙面の前記配置元情報を合成する際に、既存の紙面の前記配置情報群記憶手段が記憶する中から、合成の元になる２組の前記配置元情報を、より高い前記評価値に対応する前記配置元情報ほど大きな確率で選択することを特徴とする請求項１〜請求項３記載の記事配置装置。
【請求項５】
前記配置情報群記憶手段が、前記所定数を超える記憶を要求されたとき、最低の前記評価値に対応する前記配置情報を消去して、新たな情報を記憶することを特徴とする請求項１〜請求項４記載の記事配置装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は例えばワードプロセッサやデスク・トップ・パブリッシングや新聞あるいは雑誌の編集システムに使用される、段組された文書の配置を行う記事配置装置に係わり、特に人手を介することなく配置すなわちレイアウトを行うことのできる記事配置装置に関する。
【０００２】
【従来の技術】
従来、この種の記事配置装置は、ワードプロセッサやＤＴＰ（Ｄｅｓｋ  Ｔｏｐ  Ｐｕｂｌｉｓｈｉｎｇ  ：デスク・トップ・パブリッシング）システムなどで段組された文書をレイアウトする際に、操作性を向上するために用いられている。従来の記事配置装置としては、特開平３−１７６１４８号公報、特開平４−２６３３５７号公報、特開平５−６１８７１号公報、および特開平４−７０９５６号公報に記載がある。これらの従来例について説明する。
【０００３】
まず、第１の従来例について説明する。特開平３−１７６１４８号公報に記載された記事配置装置は、ユーザが指定した文書構成要素データを割り付ける枠表示手段と、ユーザの割付実行指示に対し、枠に対応する領域と、既存領域とが重ならないように割り付ける割付手段とを設けることで、容易な操作で文書の段組を制御することができる。
【０００４】
図１９〜図２３は、この第１の従来例の実施例の画面表示を表す説明図である。図１９に示すような＃０の領域が割り当てられた状態から、新たな＃１の領域を割り付ける場合について説明する。このとき、図２０に示すような、仮枠６０１を表示して、ユーザに移動操作させ、割り付けの位置を決定させる。すると、図２１に示すように、新たに設定した＃１の領域が、既に割り付けられている＃０の領域を避けて変形される。図２２および図２３は、さらに＃２の領域を設定した場合を示したものである。
【０００５】
第２の従来例について説明する。特開平４−２６３３５７号公報に記載された記事配置装置は、文書構成要素データを画面上に配置するためのエリアの大きさを、エリアの配置状況に応じて変更するレイアウト手段を持つ。そのレイアウト手段は、エリア間に設定された主従関係に従って、主エリアの大きさの変更があった際には、従エリアの大きさを変更することで全体のバランスをとることもできる。
【０００６】
図２４は、この第２の従来技術を説明するためのものである。同図に示すエリアｂとエリアｄには主従関係があるとする。ここで、図２４（ａ）のようにエリアｂに流し込まれる文章は、エリアの大きさに対して少なく配分率が６０％程度しか無い場合、レイアウト手段がエリアｂの大きさを自動的に配分率が適正な値になるように小さくする。そしてこれに伴って、レイアウト手段は、エリアｂの従エリアであるエリアｄの大きさを自動的に配分率が適正な値の範囲内で大きくするようになっている。
【０００７】
第３の従来例について説明する。特開平５−６１８７１号公報に記載された記事配置装置は、文書構成要素の実データを記憶する実データ保存部と、作成する文書の大きさや、前記した実データの配置位置や大きさなどを記憶する形式データ保存部と、前記した実データと前記した形式データとの適合性や関連性を記憶する関連付けデータ保存部とを備え、形式データと関連付けデータから、形式データに適合する実データを抽出して、この形式データに従って、実データを割り付けることでレイアウトを行う。
【０００８】
図２５は、この従来技術の内容を示す流れ図である。この先行技術では、ステップＳ１１０３で、形式データと関連付けデータから、形式データに適合する実データを抽出して、ステップＳ１１０４で抽出された形式データと実データとに基づいて、複合文書を作成する。
【０００９】
第４の従来例について説明する。特開平４−７０９５６号公報に記載された記事配置装置は、字間や、文字の並び方向のサイズを、先頭文字位置から最終文字を位置させる行端位置までの距離に基づいて調節する手段を備え、文字展開可能枠内の幅にほぼ一杯になるように文字列を収納するような文字のレイアウトを行う。
【００１０】
図２６はこの第４の従来技術による画面表示を表わしたものである。同図（Ａ）〜（Ｆ）で示したこれらの図で左側は変換前の状態を示しており、右側は変換後の状態を示している。同図（Ａ）の左側は文書をレイアウトする矩形の文字展開可能枠６１１内に文字列６１２を入力した状態を示したもので、同図の右側では先頭文字「Ａ」から最終文字「Ｇ」までが拡大された文字列６１３に変換されることで文字展開可能枠６１１内にほぼ一杯となるように各文字が揃えられている。同図（Ｂ）は、各文字列６１３が文字間のピッチを変えた文字列６１４に変換されることで、同様に文字展開可能枠６１１内にほぼ一杯となるように各文字が揃えられている。同図（Ｃ）では、各文字列６１３の文字の高さは変えずに幅だけ増加させることで、変換後の文字列６１５が文字展開可能枠６１１内にほぼ一杯となるように各文字が揃えられている。
【００１１】
同図（Ｄ）では、文字展開可能枠６１１に２行にわたって文字列６１６が入力された場合を示したものである。この場合にも、個々の文字のサイズは同一で間隔が詰められることによって変換後の文字列６１７は文字展開可能枠６１１内にほぼ一杯となるようにこれらの文字が揃えられている。同図（Ｅ）は、文字列６１８のうち文字“Ｌ”で示した指定範囲以外の文字「Ａ」〜「Ｄ」については、変換後も同一の文字列６１９となり、残りについては文字展開可能枠６１１内の残りの領域にほぼ一杯となるように各文字の文字列６２０が小さい文字として割り振られるようになっている。同図（Ｆ）では、文字例６２１の中の文字“Ｌ”で示した指定範囲の文字列が大きい文字として割り振られ、変換後の文字列６２２が文字展開可能枠６１１内にほぼ一杯となるように揃えられている。
【００１２】
以上、第１ないし第３の従来技術を用いることで、比較的容易に文書構成要素データを配置する枠の大きさや位置を決めることができる。また、例えば第４の従来技術と組み合わせることにより、枠内に文字列を美しく配置することも可能である。
【００１３】
【発明が解決しようとする課題】
しかしながら、これらの従来の記事配置装置では、３つの問題点がある。
１番目の問題点は、人手を必要とすることである。操作する枠の選択や、選択した枠の移動あるいは変形を対話式で行うため、第１の従来技術の場合には、記事の配置に際し、枠の位置や大きさや形状の調節に対して、操作が必要となるからである。
【００１４】
第２の問題点は、枚数を守るのが大変なことと、与えられたすべての記事をレイアウトするのは不可能ということである。与えられた記事情報の納まる枠の形状や大きさは、範囲が決まっている。これに対して、記事情報の占有領域の形状や大きさは一般に未知である。レイアウトを行う条件として、印刷枚数や紙面サイズに制限を与えられた場合、レイアウトが非常に困難となる。その理由としては、第２の従来技術では記事情報のすべてを、また第３の従来技術でも形式データのすべてを配置することを目指しているので、事前に与えられた印刷枚数や紙面サイズの制限を守れるような処理が行われていないためである。特に第３の従来技術の場合には、各枠の大きさの調整機構がない。第２の従来技術の場合には、限定的な大きさの調整機構があるものの、文章を決められた分量になるように自動要約することが困難である現状を考えると、第４の従来技術を用いたとしても、枠の大きさや形状に合わせて記事情報を詰め込むことができる場合は非常に限定されてしまう。
【００１５】
第３の問題点は、所定の場合に空き領域ができる可能性が大きいことと、各領域の位置の調節機構がないこと、ならびにレイアウトの大きさを、主従間でしか調節できないことである。第３の問題点は、枠の大きさの調整機構を唯一持っているところの第２の従来技術を使用しても、自動でレイアウトを行う場合に無駄な空き領域ができる可能性が大きい。各枠の大きさの調節機構があるものの、位置の調節機構が無いためである。また、枠相互間での枠の大きさの調節は、記事間に主従関係があるときに限定されているため、有効な調節が行える場面が少ないからである。
【００１６】
そこで本発明の目的は、人手を介することなく比較的良好にレイアウトを行うことのできる記事配置装置を提供することにある。
【００１７】
【課題を解決するための手段】
請求項１記載の発明では、新聞や雑誌のように複数の記事情報が段組された文書のレイアウトを行う装置に、前記記事情報を入力する記事情報入力手段と、段組数として予め指定した数値の範囲内で発生させた乱数によって求めた段組数と、前記段組数によって求めた段組と直交方向の座標値と、前記段組数との関係で定められた数値の範囲内で乱数によって求めた開始段数値及び同じく前記段組数との関係で定められた数値の範囲内で乱数によって求めた終了段数値で表わし、かつ分割線数として予め指定した数値の範囲内で発生させた乱数によって求めた数だけ設けた分割線と、各段の領域を前記分割線で分割することによって仕切られる単位領域に対して乱数によって求めて付加したコラム結合番号とを用いて、上下左右に隣接する同じコラム結合番号をもつ前記単位領域を結合してコラム形状を生成するコラム生成手段と、前記コラム形状に対して配置処理のランダムな順序付けを行ってコラム配置処理順序付きコラム形状情報を生成するコラム配置処理順序生成手段と、前記記事情報に対する配置処理のランダムな順序付けである記事配置処理順序を生成する記事配置処理順序生成手段と、前記記事配置処理順序と前記コラム配置処理順序付きコラム形状情報とからなる配置元情報に基づいて前記コラム形状に対して前記記事情報の配置を順に試みることで配置結果を導出する割当手段と、前記配置結果に対して評価を行い評価値を算出する配置結果評価手段と、前記配置元情報とこれに対応する前記配置結果と前記評価結果とからなる配置情報を所定数記憶する配置情報群記憶手段と、前記配置情報群記憶手段に記憶されている前記配置元情報を２組取り出して乱数を使って交叉させ新たな配置元情報を生成し、当該新たな配置元情報から前記割当手段及び前記配置結果評価手段によって対応する配置結果と評価結果を導出し、当該配置結果と当該評価結果を当該新たな配置元情報とともに配置情報として前記配置情報群記憶手段に記憶させる配置元情報合成手段と、前記配置情報群記憶手段に記憶される前記評価値の中の最大の評価値に対応する配置結果を出力する最良配置探索手段と、前記最良配置探索手段の出力する前記配置結果に基づいて前記記事情報を配置して出力する記事出力手段とを具備させる。
【００１８】
また、請求項２記載の発明では、新聞や雑誌のように複数の記事情報が段組された文書のレイアウトを行う装置に、前記記事情報を入力する記事情報入力手段と、段組数として予め指定した数値の範囲内で発生させた乱数によって求めた段組数と、前記段組数によって求めた段組と直交方向の座標値と、前記段組数との関係で定められた数値の範囲内で乱数によって求めた開始段数値及び同じく前記段組数との関係で定められた数値の範囲内で乱数によって求めた終了段数値で表わし、かつ分割線数として予め指定した数値の範囲内で発生させた乱数によって求めた数だけ設けた分割線と、各段の領域を前記分割線で分割することによって仕切られる単位領域に対して乱数によって求めて付加したコラム結合番号を用いて、上下左右に隣接する同じコラム結合番号をもつ前記単位領域を結合してコラム形状を生成するコラム生成手段と、前記コラム形状に対して配置処理のランダムな順序付けを行ってコラム配置処理順序付きコラム形状情報を生成するコラム配置処理順序生成手段と、前記記事情報に対する配置処理のランダムな順序付けである記事配置処理順序を生成する記事配置処理順序生成手段と、前記記事配置処理順序と前記コラム配置処理順序付きコラム形状情報とからなる配置元情報に基づいて前記コラム形状に対して前記記事情報の配置を順に試みることで配置結果を導出する割当手段と、前記配置結果に対して評価を行い評価値を算出する配置結果評価手段と、前記配置元情報とこれに対応する前記評価結果とからなる配置情報を所定数記憶する配置情報群記憶手段と、前記配置情報群記憶手段に記憶されている前記配置元情報を２組取り出して乱数を使って交叉させ新たな配置元情報を生成し、当該新たな配置元情報から前記割当手段及び前記配置結果評価手段によって対応する配置結果と評価結果を導出し、当該評価結果を当該新たな配置元情報とともに配置情報として前記配置情報群記憶手段に記憶させる配置元情報合成手段と、前記配置情報群記憶手段に記憶される前記評価値の中の最大の評価値に対応する配置元情報を出力する最良配置探索手段と、前記最良配置探索手段の出力する前記配置元情報に基づいて前記コラム形状に対して前記記事情報の配置を順に試みることで最良配置結果を導出する最良配置割当手段と、前記最良配置結果に基づいて前記記事情報を配置して出力する記事出力手段とを具備させる。
【００１９】
更に、請求項３記載の発明では、請求項２記載の記事配置装置で割当手段が最良配置割当手段を兼ねることを特徴とするものである。
【００２１】
また、請求項４記載の発明では、請求項１乃至３記載の記事配置装置で、前記配置元情報合成手段が、新しい紙面の前記配置元情報を合成する際に、既存の紙面の前記配置情報群記憶手段が記憶する中から、合成の元になる２組の前記配置元情報を、より高い前記評価値に対応する前記配置元情報ほど大きな確率で選択することを特徴とするものである。
【００２２】
更に、請求項５記載の発明では、請求項１乃至４記載の記事配置装置で、前記配置情報群記憶手段が、前記所定数を超える記憶を要求されたとき、最低の前記評価値に対応する前記配置情報を消去して、新たな情報を記憶することを特徴とするものである。
【００２９】
【発明の実施の形態】
【００３０】
【実施例】
以下実施例につき本発明を詳細に説明する。
【００３１】
第１の実施例
【００３２】
図１は、本発明の第１の実施例における記事配置装置の構成を表わしたものである。本実施例の記事配置装置は、コラム形状情報生成手段１０１と、コラム配置処理順序生成手段１０２と、記事配置処理順序生成手段１０３と、乱数発生手段１０４と、図示しないＲＡＭ（ランダム・アクセス・メモリ）や磁気ディスクなどの記憶装置からなる配置情報群記憶手段１０５と、割当手段１０６と、配置結果評価手段１０７と、記事形状制限情報出力手段１０８と、配置元情報合成手段１０９と、最良配置検索手段１１０と、ＲＡＭや磁気ディスクなどの記憶装置、あるいはパソコン通信や文字放送などの通信装置からなり、記事情報を出力する記事入力手段１１１と、図示しないプリンタやＣＲＴからなり、レイアウトした記事を出力する記事出力手段１１２とから構成されている。これらのうち、特に回路装置の構成を記載しないものは、前記した記憶装置に格納されたプログラムを図示しないＣＰＵ（中央処理装置）が制御することによってそれらの機能が実現されている。
【００３３】
コラム形状情報生成手段１０１は、乱数発生手段１０４より乱数１２１を読み出し、これを元にコラム形状情報１２２を生成するもので、生成されたコラム形状情報１２２はコラム配置処理順序生成手段１０２に入力される。コラム配置処理順序生成手段１０２は、乱数発生手段１０４から乱数１２１を読み出し、その乱数１２１を元に各コラムの配置処理の順序を生成し、コラム形状情報生成手段１０１より入力されたコラム形状情報に付加し、配置情報群記憶手段１０５に記憶させる。
【００３４】
記事配置処理順序生成手段１０３は、乱数発生手段１０４より乱数１２１を読み出し、その乱数１２１を元に各記事の配置処理の順序を生成し、配置情報群記憶手段１０５に記憶させる。乱数発生手段１０４は、乱数１２１を発生し、コラム形状情報生成手段１０１、コラム配置処理順序生成手段１０２、記事配置処理順序生成手段１０３および配置元情報合成手段１０９に出力する。配置情報群記憶手段１０５は、配置情報（コラム配置処埋順序付きコラム形状情報１２４と、記事配置処理順序１２５と、配置結果１２６と、評価値１２７）を予め定められた個数分だけ記憶する。また、配置情報群記憶手段１０５は、コラム配置処理順序生成手段１０２からコラム配置処理順序付きコラム形状情報１２４を、記事配置処理順序生成手段１０３から記事配置処理順序１２５を、配置元情報合成手段１０９からコラム配置処理順序付きコラム形状情報１２８と記事配置処理順序１２９を、割当手段１０６から配置結果１２６を、配置結果評価手段１０７から評価値１２７をそれぞれ入力される。
【００３５】
また、配置情報群記憶手段１０５は、割当手段１０６に対して、コラム配置処理順序付きコラム形状情報１２４と、記事配置処理順序１２５とを読み出され、配置元情報合成手段１０９からコラム配置処理順序付きコラム形状情報１２８と、記事配置処理順序１２９とを読み出され、割当手段１０６から配置結果１２６を、配置結果評価手段１０７から評価値１２７をそれぞれ読み出される。
【００３６】
割当手段１０６は、配置情報群記憶手段１０５から、コラム配置処理順序付きコラム形状情報１２４と、記事配置処理順序１２５とを読み出し、記事形状制限情報出力手段１０８から、記事形状制限情報１３１を読み出し、記事を配置可能なコラムに割り当てることで配置を行い、配置結果１２６を、配置情報群記憶手段１０５と、配置結果評価手段１０７に出力する。配置結果評価手段１０７は、割当手段１０６から配置結果１３３を入力され、配置結果１３３に対する善し悪しの度合いを数値化した評価値１２７を配置情報群記憶手段１０５に記憶させる。
【００３７】
記事形状制限情報出力手段１０８は、記事入力手段１１１より記事情報１３５を入力され、各記事の形状制限情報すなわち縦横の比率の最大値や最小値、縦や横の長さの最大値や最小値などを、割当手段１０６に出力する。配置元情報合成手段１０９は、配置元情報（配置情報群記憶手段１０５から読み出した、コラム配置処理順序付きコラム形状情報１２４と記事配置処理順序１２５）と、乱数発生手段１０４から読み出した乱数とから、新しい配置元情報を合成し、配置情報群記憶手段１０５に、新しい配置元情報を記憶させる。
【００３８】
最良配置検索手段１１０は、配置情報群記憶手段１０５から評価値１２７が最大のものを検索し、検索した最大の評価値に対応する配置結果１３６を読み出し、記事出力手段１１２に出力する。記事入力手段１１１は、記事の内容や付随する情報を含む記事情報１３５、１３８を、記事形状制限情報出力手段１０８と、記事出力手段１１２に出力する。記事出力手段１１２は、最良配置検索手段１１０から配置結果を入力され、記事入力手段１１１から各記事の内容（文書構成要素データ）を入力され、配置結果に従って、各記事を画面や紙面上にレイアウトする。
【００３９】
このような構成の記事配置装置の動作を説明する。
【００４０】
このうち図２および図３は、本実施例におけるコラム生成のうちの単位領域生成について示したものである。また、図４〜図７は、本実施例の単位領域の結合によるコラム生成を説明したものである。なお、図４〜図７は、図２および図３に対して、引き続き処理を行った例であり、図５および図７は、第１の実施例で行われるレイアウト処理のうちの紙面のコラムへの分割結果を示したものである。例えば、図４〜図７に示した紙面３０１または紙面４０１は、横方向の３段組になっており、図５に示すコラム３１１の横幅は最大で２段分（最小で１段分）、同図に示すコラム３１２の横幅は１段分になっている。紙面への記事の配置は、このコラムに対応する記事を選択することにより行われる。コラム生成手段１０１は、紙面上を図５や図７に示すような、ランダムな幾つかの領域（コラム）に分割し、コラム配置処理順序生成手段１０２に出力する。
【００４１】
図１に示すコラム生成手段１０１は、次のような動作を行う。まず、段組数を決める。このとき、段組数が予め一意に指定されていれば、その値を用いればよい。それ以外の場合は、予め指定されている範囲の段組数を乱数発生手段１０４から読み出して使用する。以下の説明では、段を分離している線を段組線と呼ぶことにする。図２および図３に示した例では２本の段組線がある。図２ないし図７でこれらは垂直線で表わされている。
【００４２】
次に、段組線と垂直に交わる線分を発生させる。以下の説明ではこれを分割線と呼ぶことにする。分割線は、段組と逆方向の座標値（図２ないし図７ではＹ座標）と、分割線の開始段と終了段によって規定される。例えば、図２に示す分割線２０２は、座標がｙｌで、開始段が１、終了段が３である。図２では６本の分割線がある。予め指定されている範囲の分割線の個数を、乱数発生手段１０４から読み出し、その個数分の座標値と開始段と終了段を、乱数発生手段１０４から読み出す。この結果として例えば、図２のような分割線が得られる。なお、乱数発生手段１０４からの乱数１２１の入力を元にしているため、得られる分割線は個数も位置も毎回同じにならないのが通常である。
【００４３】
このようにして、段組数と分割線を発生することで、図２に示す紙面２０１は、幾つかの領域に分割される。これらの領域を単位領域と呼ぶ。図３の場合、１２個の単位領域２０３に分割されている。さらに、図３のように、それぞれの単位領域２０３は他と区別できるように、番号付けを行う。これらを単位領域番号２１１と呼ぶことにする。図３に示した“１”から“１２”の数字は単位領域番号２１１である。
【００４４】
次に、各単位領域２０３に対して、乱数発生手段１０４から予め決められた範囲の乱数１２１を読み出し、番号付けを行う。これらをコラム結合番号３２１と呼ぶことにする。例えば、図４や図６のように番号付けされる。図４や図６中の“１”から“３”の数字はコラム結合番号３２１であり、これらは乱数１２１による番号付けが行われている。すなわち、図３に示す単位領域番号“１”の単位領域２０３に、図４では“１”が、図６では“２”のコラム結合番号３２１が付けられている。
【００４５】
最後に、上下左右に隣接している単位領域２１１に対して、同一のコラム結合番号３２１が付加されている場合は、それらの単位領域を結合して１つのコラムを生成する。例えば、図５は８つ、図７は７つのコラムが生成されている。具体的に説明すると、図４の単位領域番号“１”（図３参照）の単位領域３０２と、単位領域番号“５”（図３参照）の単位領域３０３は、どちらもコラム結合番号３２１が“１”なので結合して、１つのコラム３１０にする。さらに、図５に示したように、コラムは他と区別できるように、番号付けを行う。以下の説明ではこれらをコラム番号３３１と呼ぶことにする。図５や図７中の番号は、コラム番号３３１を示したものである。
【００４６】
このようにして、コラムを生成し、コラム形状情報（段数と、分割線数と、分割線（座標と開始段と終了段で表わす）と、コラム結合番号列）をコラム配置処理順序生成手段１０２に出力する。なお、乱数発生手段１０４からの乱数１２１を元にしているため、コラムの個数や形状は、図５と図７を比較して分かるとおり、毎回同じではない。
【００４７】
次に、図１と図８および図９を参照して、コラムの配置処理の処理順序の生成に関して説明する。図８および図９は、図５のように分割された各コラムに対して、図１に示す割当手段１０６で行われる配置処理の順序（優先順位）を付加した例を示したものである。コラム３１０に対して、図８では７番目、図９では５番目に配置処理を行うという優先順位を与えている。コラム配置処理順序生成手段１０２は、図８や図９に示すような、コラムの形状情報と各コラムの処理順序を、配置情報群記憶手段１０５に出力する。
【００４８】
コラム配置処理順序生成手段１０２は、次のような動作を行う。各コラムに対して、乱数発生手段１０４から乱数１２１を読み出し、順序付けを行う。以下の説明ではこれをコラム処理順序３４１と呼ぶことにする。これには、１からコラムの個数までの範囲の重複のない乱数列を用いれば良い。なお、乱数発生手段１０４からの乱数１２１の入力を元にしているため、コラム処理順序３４１は、毎回同じではない。
【００４９】
次に、図１０を参照して、記事の配置処理の処理順序の生成に関して説明する。この図は記事配置処理順序と記事番号の関係を表わしている。これは、図１の記事入力手段１１１から入力される図１１で示されるような各記事に対して、割当手段１０６で行われる配置処理の順序（優先順位）を付加した例を示している。図１０に示した例では、番号“１”の記事に対して１番目、また番号“３”の記事に対して６番目に配置処理を行うという優先順位を与えている。記事配置処理順序生成手段１０３は、図１０に示すような、各記事の処理順序を配置情報群記憶手段１０５に出力する。
【００５０】
記事配置処理順序生成手段１０３は、次のような動作を行う。各記事に対して、乱数発生手段１０４から乱数を読み出し、順序付けを行う。以下の説明ではこれを配置処理順序と呼ぶことにする。これには、“１”から記事の個数までの範囲の重複のない乱数列を用いれば良い。なお、乱数発生手段１０４からの乱数１２１の入力を元にしているため、記事の配列処理順序は、毎回同じではない。
【００５１】
次に、図１１を参照して、記事の形状制限に関して説明する。図１１は、本実施例の記事入力手段１１１によって入手された各記事に関する形状制限の例を示したものである。図１１では、記事番号“１”から“１０”の各記事に１つずつの制限を記述しているが、実際には１つの記事に対して複数の制限があるのが通常である。この図では、記事番号“１”の記事は３段組の場合の２段以上のスペースを必要とすることが、また記事番号“２”の記事は３０文字以上のスペースを必要とすることが記載されている。
【００５２】
記事形状制限情報出力手段１０８は、図１１に示すような、各記事の記事形状制限情報１３１を割当手段１０６に出力する。記事形状制限情報出力手段１０８は、次のような動作を行う。記事形状制限情報出力手段１０８は、予めすべての記事に適応するべく定められた、縦横の比率の最大値や最小値、縦や横の長さの最大値や最小値などの形状制限を記憶している。また、予め各記事の分野ごとなどに定められた、画像サイズやフオントの最大値や最小値、字間や行間の最大値や最小値、字間と行間の比率の最大値や最小値などの形状制限情報を記憶している。そして、記事形状制限情報出力手段１０８は、記事入力手段１１１より記事情報１３８を読み出し、各記事の固有の情報すなわち記事の分野、段落ごとの文字数、文書全体の文字数、元画像のサイズ、表の行方向文字数や列方向文字数などを得る。そして、記事形状制限情報出力手段１０８は、記憶しているすべての記事に適応する形状制限情報と、各分野ごとの形状制限情報とを加えて、各記事ごとの記事形状制限情報１３１すなわち縦横の比率の最大値や最小値、縦や横の長さの最大値や最小値などを生成し、割当手段１０６に出力する。
【００５３】
以上説明した記事形状制限情報出力手段１０８の動作を、具体例で説明する。例えば、記事番号“４”のスコア表の列方向の文字数（１０文字）と、スコア表に用いるフオントの最小値と文字間の最小値などから、記事番号“４”の記事を配置するために必要となる横幅の長さの最小値を計算し、割当手段１０６に出力する。次に、図４、図５と図９ないし図１１を参照して、コラムと記事とを対応させることによって配置を行う割り当て処理に関して説明する。
【００５４】
割当手段１０６は、配置情報群記憶手段１０５から、コラム配置処理順序付きコラム形状情報と、記事配置処理順序とを読み出し、記事形状制限情報出力手段１０８から、記事形状制限情報１３１を読み出し、配置処理優先順位の高い記事から順に、配置可能なコラムの中で最も配置処理順位の高いコラムへ割り当てることで配置を行う。そして、配置結果を、配置情報群記憶手段１０５と、配置結果評価手段１０７に出力する。ここで、配置可能か否かの判定にはコラムの形状情報を用いる。例えば、記事番号“１”の記事には３段組の２段分の横幅を必要とするという形状制限がある。このため、２段分の横幅を持つコラム３１０には割り当てられるが、１段分の横幅しかないコラム３１２には割り当てることはできないと判定することができる。また、既に記事を割り当てたコラムに対して、別の記事を割り当てることは当然できない。
【００５５】
図１２を参照して、さらに詳しく割当手段１０６の動作を説明する。図１２は、この第１の実施例の割当手段１０６の制御動作を示したものである。配置情報群記憶手段１０５から読み出した記事配置処理順序を参照して、未割り当ての記事の中で最も配置処理の優先順位の高い記事が選択可能であるか否かをチェックする（ステップＳ１０１）。もし、選択すべき記事が無ければ（Ｎ）、ステップＳ１０２に進んで配置結果を出力して処理を終了する（エンド）。
【００５６】
ステップＳ１０１で最も配置処理の優先順位の高い記事が選択可能であれば（Ｙ）、この選択した記事に対応する記事の形状制限情報を記事形状制限情報出力手段１０８から読み出し、記事の最大幅Ｗｎと最大高Ｈｎを求める（ステップＳ１０３）。そして、配置情報群記憶手段１０５から読み出したコラム配置処理順序を参照して、ステップＳ１０１で選択した記事に対してステップＳ１０５以降の処理を行っておらずかつ未割り当てのコラムの中で、最も配置処理の優先順位の高いコラムを選択する（ステップＳ１０４）。
【００５７】
この結果として、選択すべきコラムが無ければ（Ｎ）、ステップＳ１０１に進む。あれば、ステップＳ１０５へ進む。ステップＳ１０４の処理で選択したコラムの形状情報から、コラムの最大幅Ｗｃと最大高Ｈｃを求める（ステップＳ１０５）。ステップＳ１０３で求めた記事の最大幅Ｗｎと最大高Ｈｎと、ステップＳ１０５で求めたコラムの最大幅Ｗｃと最大高Ｈｃとを比較し、Ｗｃ≧Ｗｎ、かつＨｃ≧Ｈｎならば（ステップＳ１０６；Ｙ）、ステップＳ１０７へ進む。それ以外はステップＳ１０４へ進む。
【００５８】
ステップＳ１０７では、ステップＳ１０４で選択したコラムに対して、ステップＳ１０１で選択した記事をその記事の記事形状制限情報に従って、流し込んでみるなどして、厳密に配置可能かどうかを判定する。このとき用いたフオントサイズ、字問、行間などを一時記憶する。配置可能なとき（Ｙ）は、ステップＳ１０８へ進み、不可能なときはステップＳ１０４へ進む。
【００５９】
ステップＳ１０１で選択した記事をステップＳ１０４で選択したコラムに割り当てる。すなわち、ステップＳ１０１で選択した記事とステップＳ１０４で選択したコラムを割り当て済みとして、ステップＳ１０１やステップＳ１０４で選択される候補からはずれるようにする。また、ステップＳ１０１で選択した記事番号と、ステップＳ１０４で選択したコラム番号と、ステップＳ１０７で求めたフオントサイズ、字間、行間などの情報とを対応させて配置結果に追加する（ステップＳ１０８）。そして、配置情報群記憶手段１０５から読み出したコラム配置処理順序を参照して、未割り当てのコラムの有無を判定する（ステップＳ１０９）。もし、未割り当てのコラムが無ければ（Ｙ）、ステップＳ１０２へ進む。あれば（ステップＳ１０９；Ｎ）、ステップＳ１０１へ進む。最後に、配置結果を配置情報群記憶手段１０５と配置結果評価手段１０７へ出力し（ステップＳ１０２）、処理を終了する（エンド）。
【００６０】
次に、配置結果の評価処理に関して説明する。配置結果評価手段１０７は、割当手段１０６から配置結果１３３を入力され、配置結果１３３に対する善し悪しの度合いを数値化した評価値１２７を配置情報群記憶手段１０５に記憶させる。本実施例の記事配置装置は、この評価値１２７のより高い配置を検索する装置であると考えることができる。配置結果１３３に対する善し悪しの判断には、多くの判断基準が考えられる。しかしながら、本発明はどのような判断基準を用いるかということに無関係に利用可能である。理解を容易にするため、配置結果１３３の評価処理として、どのようなことが行われるかに関して、図１３および図１４を基に説明を行う。
【００６１】
図１３は、この第１の実施例の配置結果評価手段の制御の流れを表わしたものである。また、図１４は、各記事番号と登載優先度の関係を示したものである。ここでは、各記事に図１４に示すような登載優先度という情報３６１（図１参照）が記事入力手段１１１から得られることにする。たとえば、記事番号“１”番の記事は登載優先度が“１０”であり、記事番号“２”の記事は登載優先度が“２０”である。ここでは次のような配置結果の判断基準に用いているものとする。
▲１▼基準１：限られた紙面の中に登載される記事の登載優先度の合計ができるだけ高いこと。
▲２▼基準２：紙面上の空き領域を一定以下にすること。
【００６２】
２つ目の判断基準は、複数枚の紙面へのレイアウトをすると、すべての記事を登載しても紙面に余りが出る場合に、各ページの記事の量を均等化することによって、異常に大きな空き領域を作らないことを狙った判断基準である。図１３に示すように配置結果評価手段１０７は、次のように動作する。
【００６３】
まず、割当手段１０６から入力された配置結果情報と、記事入力手段１１１から入力された記事の登載優先度情報とから、登載された記事の登載優先度を合計し、評価値に加算する（ステップＳ２０１）。計算方法は登載優先度の取り得る範囲等に応じて、予め設定してあればよい。例えば、登載優先度の和を求める替わりに、自乗和や積を用いても良い。また、評価値の初期値は通常は零でよいが、ステップＳ２０３で行う減算に備えて、正の初期値を入れておき、必ず正の数に保てるようにするのも良い。
【００６４】
次に、割当手段１０６から入力された配置結果情報から、記事が配置されておらず、かつ記事間のスペーサにも使用されていない紙面上の領域の面積の和が紙面全体に占める割合を求め、予め設定した閾値Ｓと比較する（ステップＳ２０２）。空き領域の割合の方が大きければ（Ｙ）ステップＳ２０３へ、それ以外の場合はステップＳ２０４へ進む。
【００６５】
空き領域の割合の方が大きい場合には、評価値から予め設定した値を減算する（ステップＳ２０３）。最後に、評価値を配置結果評価情報として配置情報群記憶手段１０５に出力する（ステップＳ２０４）。また、空き領域への減点に関しては、予め設定した闇値Ｓとの比較によるのでなく空き領域の紙面に対する割合に応じて減点量を計算してもよい。
【００６６】
次に配置元情報合成処理に関して説明する。
【００６７】
図１５は、配置元情報の一点交叉による合成を説明したものである。例として、コラム形状情報の一部であるコラム結合番号列の合成を用いている。図１６は、配置元情報の順序型交叉による合成に関する説明図である。例としては、コラム配置処理の優先順位の合成を用いている。配置処理順序は、コラム配置処理順序順のコラム番号列で表現している。図１５では、図４と図６に相当する２つのコラム結合番号列Ｃｂ１  とＣｂ２  とから、新しいコラム結合番号列Ｃｂｎｅｗ  を合成している。ここで符号Ｒは乱数を示している。
【００６８】
図１６では、図８と図９に相当する２つのコラム配置処理の処理順位（配置処理の処理順に並んだのコラム番号列で表わす。）Ｇｄ１  とＧｄ２  から、新しいコラム配置処理の処理順位Ｇｄｎｅｗ  を合成している。配置元情報合成手段１０９は、配置情報群記憶手段１０５から読み出した評価値で計算した、すべての評価値の和に対する各評価値の割合と、乱数発生手段１０４から読み出した乱数とを元にして、配置元情報（コラム配置処理順序付きコラム形状情報と記事配置処理順序）を１組選択し、選択した配置元情報と、乱数発生手段１０４から読み出した乱数とを元にして、新しい配置元情報を合成し、配置情報群記憶手段１０５に、新しい配置元情報を記憶させる。
【００６９】
配置元情報合成手段１０９は、次のような動作を行う。まず、配置情報群記憶手段１０５から、評価値を読み出して、各評価値Ｐｉに対して、それまでの評価値の累積と評価値の和ＳＰｉを、次式のように求める。
ＳＰｉ＝ＳＰｉ−１  ＋Ｐｉ      （ｉ＝１：配置情報の個数）
ただしＳＰ０＝０
【００７０】
また、乱数発生手段１０４から１から評価値全体の和の範囲の乱数Ｒを２つ読み出す。読み出した乱数Ｒについて、次式が成り立つＳＰｉを検索する。
ＳＰｉ−１  ＜Ｒ≦ＳＰｉ
【００７１】
このＳＰｉに対応する配置元情報（ｉ番目の配置元情報）を選択する。２つの乱数に対して行うので、２つの配置元情報を配置情報群記憶手段１０５から、読み出すことになる。
【００７２】
次に、コラム配置処理順序付きコラム形状情報のうち、段数と、分割線を表わす座標、開始段、終了段を、以下のような方法で合成する。
▲１▼方法１：２つの段数を平均して、新しい段数を合成する。座標、開始段、終了段についても同様である。
▲２▼方法２：２つの段数のうち、乱数発生手段１０４から得た乱数によってどちらか一方を選択する。座標・開始段・終了段についても同様に行うことで、新しい分割線や、新しい段数と分割線の組み合わせが合成できる。
二つの方法を、乱数発生手段１０４から得た乱数によってランダムに選択してもよい。
【００７３】
次に、コラム配置処理順序付きコラム形状情報のうち、コラム結合番号列を、次のように合成する。
【００７４】
まず、元になるコラム結合番号列を２つ選択し、その後、１からコラム結合番号列に含まれるコラム結合番号の個数−１までの範囲の乱数を、乱数発生手段１０４から読み出し、読み出した乱数の位置で各コラム結合番号列をそれぞれ２つに分割する。これを組み合わせて新しいコラム結合番号列を合成する。
【００７５】
例えば、図１５では選択した２つのコラム結合番号列が、
Ｃｂ１“１、２、１、２、１、２、３、３、３、１、３、２”と、
Ｃｂ２“２、１、３、１、１、１、２、２、３、３、１、２”とであり、乱数発生手段１０４から読み出した乱数が“５”であった場合を示している。そこで、左から５番目の境目で、コラム結合番号列を分割する。すなわち、Ｃｂ１を“１、２、１、２、１”と“２、３、３、３、１、３、２”に、Ｃｂ２を“２、１、３、１、１”と“１、２、２、３、３、１、２”に分割する。そして、Ｃｂ１の前半とＣｂ２の後半を組み合わせて、新しいコラム結合番号列“１、２、１、２、１、１、２、２、３、３、１、２”を合成する。
【００７６】
次に、コラム配置処理順序付きコラム形状情報のうち、コラム配置処理順序を、次のように合成する。まず、元になるコラム結合番号列を２つ選択し、次にコラム配置処理順序の最大値と等しい桁数の２進数の乱数を、乱数発生手段１０４から読み出し、読み出した２進乱数のビットが立っている桁に対応するコラム番号を、片側のコラム配置処理順序からそのままの位置で新しいコラム配置順序にコピーし、残りの位置のコラム番号を、もう片方のコラム配置処理順序の順番と同じになるように埋める。例えば、図１６では、選択した２つのコラム配置順序順のコラム番号列がＧｄ１“５、３、８、７、６、４、１、２”と、Ｇｄ２“３、６、４、２、１、５、８、７”とであり、乱数発生手段１０４から読み出した乱数が“１１０１１０００”の場合を示している。
【００７７】
そこで、Ｇｄ１から“１番目と２番目と４番目と５番目”を新しいコラム配置処理順序にコピーする。すると、この時点で新しいコラム配置処理順序は“５、３、？、７、６、？、？、？”になる。ここで“？”は未決定部分を表わしている。次に、“５と３と７と６”以外のコラム番号をＧｄ２から抜き出す。すると抜き出されたコラム番号列は“４、２、１、８”になる。これを新しいコラム配置処理順序の未決定の位置に埋める。すると新しいコラム配置処理順序として“５、３、４、７、６、２、１、８”が、得られる。次に、記事配置処理順序をコラム配置順序と同様に合成する。最後に、新しく合成された配置元情報を、配置情報群記憶手段１０５に記憶させる。
【００７８】
次に、記事配置装置全体の動作に関して説明する。図１７は、この第１の実施例の記事配置装置の全体の動作を示したものである。まず、コラム形状情報生成手段１０１は、乱数発生手段１０４より乱数を読み出し、その乱数を元にコラム形状情報を生成し、コラム配置処理順序生成手段１０２に出力する。そして、コラム配置処理順序生成手段１０２は、コラム形状情報生成手段１０１より入力されたコラム形状情報に対して、乱数発生手段１０４より読み出した乱数を元にして生成した各コラムの配置処理の順序を付加し、コラム配置順序付きコラム形状情報を生成する。また、記事配置処理順序生成手段１０３は、乱数発生手段１０４より読み出した乱数を元に各記事の配置処理の順序を生成する。このようにして、配置元情報を予め決められた個数分生成し、配置情報群記憶手段１０５に記憶させる（ステップＳ３０１）。
【００７９】
そして、割当手段１０６は、配置情報群記憶手段１０５に記憶されている配置元情報のすべてについて、配置元情報を１つずつ読み出し、記事形状制限情報出力手段１０８から、記事形状制限情報を読み出し、記事を配置可能なコラムに割り当てることで配置を行い、配置結果を、配置情報群記憶手段１０５と、配置結果評価手段１０７に出力する。配置情報群記憶手段１０５は、配置元情報に対して配置結果を関連づけて記憶する（ステップＳ３０２）。配置結果評価手段１０７は、割当手段１０６から入力された（ステップＳ３０２で計算された）すべての配置結果について、配置結果の評価値を計算し、評価値を配置情報群記憶手段１０５に記憶させる。配置情報群記憶手段１０５は、配置元情報に対して評価値を関連づけて記憶する（ステップＳ３０３）。
【００８０】
配置元情報合成手段１０９は、配置情報群記憶手段１０５から読み出した評価値で計算した、すべての評価値の和に対する各評価値の割合と、乱数発生手段１０４から読み出した乱数とを元にして、配置元情報を１つ選択する（ステップＳ３０４）。そして、配置元情報合成手段１０９は、ステップＳ３０４にて選択した配置元情報と、乱数発生手段１０４から読み出した乱数とを元にして、新しい配置元情報を合成する（ステップＳ３０５）。さらに、配置情報群記憶手段１０５に、新しい配置元情報を記憶させる。
【００８１】
割当手段１０６は、記事形状制限情報出力手段１０８から、記事形状制限情報を読み出し、新しい配置元情報を用いて、記事を配置可能なコラムに割り当てることで配置を行い、配置結果を、配置情報群記憶手段１０５と、配置結果評価手段１０７に出力する。配置情報群記憶手段１０５は、新しい配置元情報に対して、今求めた配置結果を関連づけて記憶する（ステップＳ３０５）。そして、配置結果評価手段１０７は、ステップＳ３０５で求めた新しい配置結果について配置結果の評価値を計算し、評価値を配置情報群記憶手段１０５に記憶させる。配置情報群記憶手段１０５は、新しい配置元情報に対して、今求めた評価値を関連づけて記憶する（ステップＳ３０６）。次に、終了条件が満たされたか否かを判定し（ステップＳ３０７）、満たされていなければ（Ｎ）、ステップＳ３０４へ戻り、満たされていれば（Ｙ）ステップＳ３０８へ進む。
【００８２】
終了条件には以下のような条件が考えられる。また、これらの任意の組み合わせを用いても良い。
▲１▼新しい配置元情報を合成した回数が、予め定めた回数を越えたか。
▲２▼ステップＳ３０１を開始してからの処理時間が、予め定めた時間を越えたか。
▲３▼配置情報群記憶手段１０５に記憶された評価値の最大値が、予め定めた値を越えたか。
▲４▼配置情報群記憶手段１０５に記憶された評価値の最大値が更新されない回数が、予め定めた回数を越えたか。
▲５▼配置情報群記憶手段１０５に記憶された評価値の最大値が更新されない時間が、予め定めた時間を越えたか。
【００８３】
最後に、最良配置検索手段１１０は、配置情報群記憶手段１０５から評価値が最大のものを検索し、対応する配置結果を記事出力手段１１２に出力する（ステップＳ３０８）。そして、記事出力手段１１２は、最良配置検索手段１１０から入力された配置結果と、記事入力手段１１１から入力された各記事の内容（文書構成要素データ）とから、各記事を画面や紙面上にレイアウトする。
【００８４】
第２の実施例
【００８５】
次に、本発明の第２の実施例についてその要部を説明する。
【００８６】
図１８は、本発明の第２の実施例の記事配置装置の構成を表わしたものである。この第２の実施例の記事配置装置で第１の実施例と同一部分には同一の符号を付しており、これらの説明を適宜省略する。本実施例の記事配置装置は、コラム形状情報生成手段１０１と、コラム配置処理順序生成手段１０２と、記事配置処理順序生成手段１０３と、乱数発生手段１０４と、ＲＡＭや磁気ディスクなどの記憶装置からなる第２の配置情報群記憶手段１３０５と、第２の割当手段１３０６と、配置結果評価手段１０７と、記事形状制限情報出力手段１０８と、配置元情報合成手段１０９と、第２の最良配置検索手段１３１０と、ＲＡＭや磁気デイスクなどの記憶装置、あるいはパソコン通信や文字放送などの通信装置からなり、記事情報を出力する記事入力手段１１１と、プリンタやＣＲＴからなり、レイアウトした記事を出力する記事出力手段１１２と、から構成される。これらのうち、特に回路装置の構成を記載しないものは、前記した記憶装置に格納されたプログラムを図示しないＣＰＵが制御することによって機能が実現されている。
【００８７】
第２の配置情報群記憶手段１３０５は、第２の配置情報（コラム配置処理順序付きコラム形状情報と、記事配置処理順序と、評価値）を予め定められた個数分だけ記憶する。コラム配置処理順序生成手段１０２からコラム配置処理順序付きコラム形状情報を、記事配置処理順序生成手段１０３から記事配置処理順序を、配置元情報合成手段１０９からコラム配置処理順序付きコラム形状情報と記事配置処理順序を、配置結果評価手段１０７から評価値を入力される。
【００８８】
また、第２の割当手段１３０６に、コラム配置処理順序付きコラム形状情報と、記事配置処理順序とを読み出され、配置元情報合成手段１０９からコラム配置処理順序付きコラム形状情報と記事配置処理順序とを読み出され、最良配置検索手段から、評価値とコラム配置処理順序付きコラム形状情報と記事配置処理順序とを読み出される。
【００８９】
第２の割当手段１３０６は、第２の配置情報群記憶手段１３０５から配置元情報を読み出し、記事形状制限情報出力手段１０８から記事形状制限情報を読み出し、記事を配置可能なコラムに割り当てることで配置を行い、配置結果を、配置結果評価手段１０７に出力する。また、第２の最良配置検索手段１３１０から最良の評価値を持つ配置元情報を入力され、記事を配置可能なコラムに割り当てることで配置を行い、配置結果を、第２の記事出力手段１３１２に出力する。類２の最良配置検索手段１３１０は、第２の配置情報群記憶手段１３０５から評価値が最大のものを検索し、検索した最大の評価値に対応する配置元情報を読み出し、第２の割当手段１３０６に出力する。第２の記事出力手段１３１２は、第２の割当手段１３０６から配置結果を入力され、記事入力手段１１１から各記事の内容（文書構成要素データ）を入力され、配置結果に従って、各記事を画面や紙面上にレイアウトする。
【００９０】
次に図１２、図１７および図１８を参照して、第２の実施例の記事配置装置の動作について説明する。まず、第２の割り当て処理に関して説明する。第２の割り当て処理は、第１の実施例の割り当て処理とほぼ同じである。
【００９１】
図１２を参照して、第２の実施例の第２の割当手段１０６の動作を説明する。第１の実施例の割り当て処理と異なるのは、ステップＳ１０１、ステップＳ１０２およびステップＳ１０４の３ステップだけである。
【００９２】
配置情報群記憶手段１０５から読み出した記事配置処理順序、もしくは第２の最良配置検索手段１３１０から入力された記事配置処理順序を参照して、未割り当ての記事の中で最も配置処理の優先順位の高い記事を選択する。もし、選択すべき記事が無ければステップＳ１０２へ進む。あれば、ステップＳ１０３へ進む（第２の割り当て処理のステップＳ１０１）。
【００９３】
配置情報群記憶手段１０５から読み出したコラム配置処理順序、もしくは第２の最良配置検索手段１３１０から入力されたコラム配置処理順序を参照して、（第２の割り当て処理の）ステップＳ１０１で選択した記事に対してステップＳ１０５以降の処理を行っておらず、かつ未割り当てのコラムの中で、最も配置処理の優先順位の高いコラムを選択する。もし、選択すべきコラムが無ければ、（第２の割り当て処理の）ステップＳ１０１へ進む。あれば、ステップＳ１０５へ進む。（第２の割り当て処理のステップＳ１０４）最後に、配置結果を配置結果評価手段１０７へ出力し、処理を終了する（第２の割り当て処理のステップＳ１０２）。
【００９４】
次に、第２の実施例の記事配置装置全体の動作を説明する。第２の実施例の記事配置装置全体の動作は、第１の実施例の動作とほぼ同じである。図１７を参照して、第２の実施例の記事配置装置の全体の動作を説明する。
【００９５】
第１の実施例と動作が異なるのは、ステップＳ３０２、ステップＳ３０５、ステップＳ３０８の３ステップだけである。第２の割当手段１３０６は、第２の配置情報群記憶手段１３０５に記憶されている配置元情報のすべてについて配置元情報を１つずつ読み出し、記事形状制限情報出力手段１０８から、記事形状制限情報を読み出し、記事を配置可能なコラムに割り当てることで配置を行い、配置結果を、配置結果評価手段１０７に出力する（第２の実施例のステップＳ３０２）。
【００９６】
配置元情報合成手段１０９は、ステップＳ３０４にて選択した配置元情報と、乱数発生手段１０４から読み出した乱数とを元にして、新しい配置元情報を合成する。さらに、配置情報群記憶手段１０５に、新しい配置元情報を記憶させる。第２の割当手段１３０６は、記事形状制限情報出力手段１０８から、記事形状制限情報を読み出し、新しい配置元情報を用いて、記事を配置可能なコラムに割り当てることで配置を行い、配置結果を配置結果評価手段１０７に出力する（第２の実施例のステップＳ３０５）。
【００９７】
最後に、第２の最良配置検索手段１３１０は、第２の配置情報群記憶手段１３０５から評価値が最大のものを検索し、検索した最大の評価値に対応する配置元情報を読み出し、第２の割当手段１３０６に出力する。第２の記事出力手段１３１２は、第２の割当手段１３０６から配置結果を入力され、記事入力手段１１１から各記事の内容（文書構成要素データ）を入力され、配置結果に従って、各記事を画面や紙面上にレイアウトする（第２の実施例のステップＳ３０８）。
【００９８】
第２の実施例は、第１の実施例と異なり、配置情報群記憶手段中に配置結果を記憶しない。このため、配置情報群記憶手段１０５に比べて、第２の配置情報群記憶手段１３０５は、消費メモリ容量が小さいという利点がある。逆に、最良配置結果の出力の際に第２の割当手段１３０６を用いて配置結果を再度計算する必要がある。しかし、再計算に必要とする処理時間は、全体の処理時間から見れば無視できる程度である。
【００９９】
本発明の変形例として、図２に示す分割線の開始段や終了段を段数で表現する代わりに、紙面幅のＸ座標値で表わして、配置情報群記憶手段１０５（１３０５）に記憶させておき、割当手段１０６（１３０６）において段数に丸めても良い。このようにすると、異なる段数を持つ配置元情報の場合に、より良い新しい配置元情報を合成できる。
【０１００】
また別の変形例として、コラム生成手段において、登場順に昇順や降順に正規化されたコラム結合番号を用いて、単位領域の結合を行っても良い。このようにすると、コラム形状に対するコラム形状情報を一意にできる。
【０１０１】
たとえば、図７のようなコラムを得るのは、図６のようなコラム結合番号列（２、１、３、１、１、１、２、２、３、３、１、２）を使用した時だけでなく、“１、２、３、２、２、２、１、１、３、３、２、１”のようなコラム結合番号列を使用してもよい。このコラム結合番号列は、登場順に昇順になっている。このような多様性は同一の配置を異なる配置とみなす原因となり、同一の配置に対する評価値を分散させる結果となり、その配置結果に不当に小さな評価を与えることとなる。この間題を、昇順もしくは降順などのような一意性のある並びに正規化することにより、防ぐことが可能である。
【０１０２】
【発明の効果】
以上説明したように請求項１〜請求項１２記載の発明によれば、次のような各種効果を得ることができる。
まず、第１の効果は、人手を介すること無く、比較的良好なレイアウトができることである。これによって、検索による記事の入手から印刷までを自動で行うことができる。その理由は、多くの配置結果を自動的に生成し、それらの評価を行うことで、最良の配置結果を自動的に選択することができるからである。
【０１０３】
第２の効果は、本発明で述べたコラム生成手段を用いることで、紙面の有効利用が期待できる。その理由は、生成されるコラムは矩形の形状をとるコラムの複数個の集合であり、複雑な形状をとることが可能であるためである。このため、記事と記事との複雑な噛み合わせを試すことができる。
【０１０４】
第３の効果は、記事配置装置にいわゆる遺伝子アルゴリズムを適応する際の重要点である、配置元情報の合成ができることである。これは、記事配置のバリエーションの元になる情報を、つぎのようにパラメータ化したことによる。ここで遺伝子アルゴリズムとは、生物の適応的進化メカニズムをモデルにした準最適解を探索するアルゴリズムである。「配置元情報」は「遺伝子」に例えることができ、「配置元情報の合成」は「交配」に例えることができる。
▲１▼パラメータ化方法の１番目としては、コラム形状情報として、段数・分割線数・座標と開始段と終了段で表した分割線・コラム結合番号を用いることができる。
▲２▼パラメータ化方法の２番目としては、配置を試行する元情報として、コラム配置処理順序、記事配置処理順序を用いることができる。このようにパラメータ化することで、合成されたパラメータが配置元情報として使用可能な値となる。
【０１０５】
第４の効果は、高速に良好な配置結果を得ることができるというものである。その理由は、以下のとおりである。配置元情報の合成時に、元になる配置元情報を、より良好な配置結果の配置情報が確率的に多くなるように選択するため、良好な配置結果を生む可能性の高い配置情報を合成する確率が高くなる。そうすると、ランダムに多くの配置元情報を生成するのに比べて、検討する配置情報が少なくても、良好な配置が得られる可能性が高くなるからである。
第５の効果は、コラム生成手段が、段組数として予め指定した数値の範囲内で発生させた乱数によって求めた段組数と、段数によって求めた段組と直交方向の座標値と、段組数との関係で定められた数値の範囲内で乱数によって求めた開始段数値と、同じく段組数との関係で定められた数値の範囲内で乱数によって求めた終了段数値で表わし、かつ分割線数として予め指定した数値の範囲内で発生させた乱数によって求めた数だけ設けられた分割線と、各段の領域を分割線で分割することによって仕切られる単位領域に対して乱数によって求めて付加したコラム結合番号を用いて、上下左右に隣接する同じコラム結合番号をもつ単位領域を結合してコラムを生成するようにしたことにより生じる。すなわち、単に乱数を発生させて段組数や開始段数値、終了段数値および分割線の数を定めるのではなくて、発生させる乱数の範囲を指定したり発生する値の範囲を定めることにしたので、全く考慮外となる配置を排除しながら配置を自動的に生成するので、処理に要する負荷を軽減させると共に、処理時間を短縮することができることになる。
【図面の簡単な説明】
【図１】本発明の第１の実施例における記事配置装置の構成を表わしたブロック図である。
【図２】第１の実施例でコラム生成のうちの単位領域生成の第１段階を示す説明図である。
【図３】第１の実施例でコラム生成のうちの単位領域生成の第２段階を示す説明図である。
【図４】図３に引続き単位領域の結合によるコラム生成を示した説明図である。
【図５】図３に引続き単位領域の結合によるコラム生成で紙面のコラムへの分割結果を示した説明図である。
【図６】単位領域の結合によるコラム生成を示した説明図である。
【図７】単位領域の結合によるコラム生成を示した説明図である。
【図８】単位領域の結合によるコラム生成で紙面のコラムへの分割結果を示した説明図である。
【図９】単位領域の結合によるコラム生成で紙面のコラムへの分割結果の他の例を示した説明図である。
【図１０】本実施例で記事配置処理順序と記事番号の関係を表わした説明図である。
【図１１】本実施例で記事の形状制限を示した説明図である。
【図１２】第１の実施例の割当手段の制御動作を示した流れ図である。
【図１３】第１の実施例の配置結果評価手段の制御の流れを表わした流れ図である。
【図１４】各記事番号と登載優先度の関係を示した説明図である。
【図１５】配置元情報の一点交叉による合成を示した説明図である。
【図１６】図８と図９に相当する２つのコラム配置処理の処理順位から、新しいコラム配置処理の処理順位を合成する説明図である。
【図１７】第１の実施例の記事配置装置の全体の動作を示した流れ図である。
【図１８】本発明の第２の実施例の記事配置装置の構成を表わした流れ図である。
【図１９】第１の従来例における画面表示の第１段階を示す説明図である。
【図２０】第１の従来例における画面表示の第２段階を示す説明図である。
【図２１】第１の従来例における画面表示の第３段階を示す説明図である。
【図２２】第１の従来例における＃２の領域を設定した場合を示す説明図である。
【図２３】第１の従来例における＃２の領域を設定した場合を示す説明図である。
【図２４】第２の従来例におけるエリアの再配置の前後を示す説明図である。
【図２５】第３の従来技術の内容を示した流れ図である。
【図２６】第４の従来技術における画面表示を示した説明図である。
【符号の説明】
１０１  コラム形状情報生成手段
１０２  コラム配置処理順序生成手段
１０３  記事配置処理順序生成手段
１０５  配置情報群記憶手段
１０６  割当手段
１０７  配置結果評価手段
１０８  記事形状制限情報出力手段
１０９  配置元情報合成手段
１１０  最良配置検索手段
１１１  記事入力手段
１１２  記事出力手段
２０１  紙面
３２１  コラム結合番号
３３１  コラム番号
３４１  コラム処理順序
【図１】
0003544422.tif 000002
【図２】
0003544422.tif 000003
【図３】
0003544422.tif 000004
【図４】
0003544422.tif 000005
【図５】
0003544422.tif 000006
【図６】
0003544422.tif 000007
【図７】
0003544422.tif 000008
【図８】
0003544422.tif 000009
【図９】
0003544422.tif 000010
【図１０】
0003544422.tif 000011
【図１１】
0003544422.tif 000012
【図１２】
0003544422.tif 000013
【図１３】
0003544422.tif 000014
【図１４】
0003544422.tif 000015
【図１５】
0003544422.tif 000016
【図１６】
0003544422.tif 000017
【図１７】
0003544422.tif 000018
【図１８】
0003544422.tif 000019
【図１９】
0003544422.tif 000020
【図２０】
0003544422.tif 000021
【図２１】
0003544422.tif 000022
【図２２】
0003544422.tif 000023
【図２３】
0003544422.tif 000024
【図２４】
0003544422.tif 000025
【図２５】
0003544422.tif 000026
【図２６】
0003544422.tif 000027