(57)【要約】【課題】データ列の整列を高速に実行可能なデータ列整列方法を提供すること。【解決手段】クイックソート実行部７がデータ列に対して実行した分割処理の回数を計数処理部４によって計数し、整列制御部３は、分割処理の回数がしきい値記憶部５に記憶したしきい値を超えた場合に、データ列をデータ比較部６に送信する。データ比較部６によってデータ列の内容を比較し、データ内容が重複する範囲における分割処理をスキップし、データ内容が異なるデータ要素から分割処理を再開する。【選択図】　　　図１
2004094504.tif 000002
【特許請求の範囲】
【請求項１】
データ集合に含まれる複数のデータ列を、所定の規則に従って複数の部分データ集合のいずれかに振り分ける分割処理を再帰的に実行する分割処理工程と、
前記分割処理工程によって実行された前記分割処理の回数を計数する計数工程と、
前記計数工程によって計数された分割処理回数が所定のしきい値を超えた場合に、分割処理対象のデータ列のデータ要素を比較し、各データ列のデータ要素が互いに一致する範囲に対する前記分割処理をスキップし、各データ列のデータ要素が互いに異なる場合に前記分割処理工程を再開するデータ比較工程と、
を含むことを特徴とするデータ列整列方法。
【請求項２】
前記分割処理工程は、前記データ列のデータ要素と任意に定めた基準データとを比較し、前記データ要素と前記基準データとの大小関係によって前記データ列を振り分けるクイックソートをおこなうことを特徴とする請求項１に記載のデータ列整列方法。
【請求項３】
前記データ集合は、第１のデータ列と、当該第１のデータ列を所定量ずつずらして形成した複数の巡回データ列とを含むことを特徴とする請求項１または２に記載のデータ列整列方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、複数のデータ列を含むデータ集合に対し、所定の規則に従って前記データ列を複数のデータ集合に分割する分割処理工程を繰り返し実行することで前記データ列の整列をおこなうデータ列整列方法に関し、特に、データ列の整列を高速に実行可能なデータ列整列方法に関する。
【０００２】
【従来の技術】
従来、複数のデータ列をその配列にしたがって整列する整列方式が数多く考案されてきた。データ列の整列方法は、そのアルゴリズムによって速度や使用する記憶領域の量がそれぞれ異なる。また、整列方法によっては、データ列の内容によって速度に差が生じるデータ依存性を有している。したがって、データ列の整列を実行する場合には、利用環境や対象となるデータに応じて整列方法を選択する必要があった。
【０００３】
この従来の整列方式の中でよく利用される整列方法として、クイックソートがある。クイックソートは、対象となるデータ集合に含まれるデータ列を基準データと比較し、基準データに比して大きいデータによって構成される部分データ集合と、基準データ以下のデータによって構成される部分データ集合とに分割する分割処理を順次繰り返すことでデータ列の整列をおこなう方式である。また、対象となるデータ列が、ある程度大きい場合、クイックソートは、データ列の一部であるデータ要素と基準データとを比較し、データ要素が基準データに比して大きい部分データ集合、データ要素が基準データに比して小さい部分データ集合、データ要素が基準データに等しい部分データ集合の３つの部分データ集合に分割する分割処理を再帰的に繰り返すことでデータ列の整列をおこなう。
【０００４】
このクイックソートでは、ｎ個のデータ列を整列するのに最低限必要な計算量が「ｎｌｏｇｎ」のオーダーであり、現在の配列方法の中で最速と言われている。一方で、クイックソートの計算量は、基準データ列の選択やデータ列の内容によって大きく変動し、最大の計算量が「ｎ２」のオーダーとなる。具体的には、それぞれの分割処理によってデータ列を均等に分割することができた場合、必要な分割処理の回数が減少するので全体の計算量が少なくなり、高速に整列を実行できる。しかし、それぞれの分割処理によってデータを均一に分割できない場合、必要な分割処理の回数が増大するので全体の計算量が多くなり、整列の速度が著しく低下する。
【０００５】
この速度の低下を避ける方法として、従来、安全クイックソートが使用されてきた。安全クイックソートは、クイックソートにおける分割処理の回数を計数し、分割処理の回数が所定の回数を超えた場合にクイックソートによる整列を中止し、残りの未整列部分をヒープソートによって整列する方法である。
【０００６】
ヒープソートは、整列速度がクイックソートの半分であるが、データの内容に依存することなく安定した速度で整列をおこなうことができる。したがって、クイックソートによる分割処理の回数が著しく大きい場合、すなわちデータ列の内容がクイックソートの速度を低下させるものである場合に、クイックソートによる整列を中止してヒープソートに切り替えることで、最後までクイックソートを用いた場合に比して高速に整列を終了させるようにしていた。
【０００７】
【発明が解決しようとする課題】
しかしながら、この従来の安全クイックソートでは、分割処理の回数がしきい値を超えてヒープソートに移行した場合、クイックソートに復帰することができなかった。すなわち、データ列の一部分がクイックソートに不向きなデータ列であった場合にヒープソートに移行するため、ヒープソートに移行した後のデータ列がクイックソートによって高速に実行可能であったとしてもクイックソートに復帰せず、結果として整列速度が低下する場合があった。このため、安全クイックソートにおいてはしきい値の値を適切に設定することが非常に困難であるという問題点があった。
【０００８】
なお、クイックソートに不向きなデータ列として、複数のデータ列の間で内容が重複している場合がある。データ内容が重複する範囲では、データ列の分割処理の結果は常に「基準データとデータ要素が等しい部分データ集合」となるため、データ列の間の大小関係を決定するためにはより多くの分割処理が必要である。したがって、データ列の内容に重複がある場合、クイックソートの処理速度が低下することとなる。
【０００９】
すなわち、従来のクイックソートでは、データ列の重複時に整列速度が低下するという問題点があった。さらに、安全クイックソートを用いた場合においても、適切なしきい値を設定することが困難であり、かえって整列速度を低下させる虞があるという問題点があった。
【００１０】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、重複したデータ列を整列する場合の整列速度を向上し、データ列の整列を高速に実行可能なデータ列整列方法を提供することを目的とする。
【００１１】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、本発明に係るデータ列整列方法は、データ集合に含まれる複数のデータ列を、所定の規則に従って複数の部分データ集合のいずれかに振り分ける分割処理を再帰的に実行する分割処理工程と、前記分割処理工程によって実行された前記分割処理の回数を計数する計数工程と、前記計数工程によって計数された分割処理回数が所定のしきい値を超えた場合に、分割処理対象のデータ列のデータ要素を比較し、各データ列のデータ要素が互いに一致する範囲に対する前記分割処理をスキップし、各データ列のデータ要素が互いに異なる場合に前記分割処理工程を再開するデータ比較工程と、を含むことを特徴とする。
【００１２】
この発明によれば、データ列に対する分割処理の実行回数を計数し、この分割処理の実行回数が所定のしきい値を超えた場合に、分割処理対象のデータ列の内容を比較して、データ列の内容が同一の範囲に対しては分割処理をスキップするので、重複した内容のデータに対する分割処理の回数を減少させることができる。
【００１３】
また、本発明に係るデータ列整列方法では、前記分割処理工程は、前記データ列のデータ要素と任意に定めた基準データとを比較し、前記データ要素と前記基準データとの大小関係によって前記データ列を振り分けるクイックソートをおこなうことを特徴とする。
【００１４】
この発明によれば、クイックソートにおける分割処理の実行回数が所定のしきい値を超えた場合に、分割処理対象のデータ列の内容を比較して、データ列の内容が同一の範囲に対しては分割処理をスキップするので、データ内容の重複を原因とするクイックソートの速度低下を防止することができる。
【００１５】
また、本発明に係るデータ列整列方法では、前記データ集合は、第１のデータ列と、当該第１のデータ列を所定量ずつずらして形成した複数の巡回データ列とを含むことを特徴とする。
【００１６】
この発明によれば、所定のデータ列をずらして形成した巡回行列に対してクイックソートを実行し、クイックソートにおける分割処理の実行回数が所定のしきい値を超えた場合に、分割処理対象のデータ列の内容を比較し、データ列の内容が同一の範囲に対しては分割処理をスキップするようにしている。
【００１７】
また、本発明に係るデータ列整列方法では、前記複数のデータ列は、当該データ列の先頭部分に対して基数整列を用いて整列済みであることを特徴とする。
【００１８】
この発明によれば、基数整列を用いて先頭部分を整列済みであるデータ列に対してクイックソートを実行し、クイックソートにおける分割処理の実行回数が所定のしきい値を超えた場合に、分割処理対象のデータ列の内容を比較し、データ列の内容が同一の範囲に対しては分割処理をスキップするようにしている。
【００１９】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係るデータ列整列方法の好適な実施の形態を詳細に説明する。
【００２０】
まず、本実施の形態に係るデータ列整列方法の概念について説明する。このデータ列整列方法では、データ列をクイックソートによって整列し、かつクイックソートにおける分割処理の回数を計数する。さらに、分割処理の回数が所定数を超えた場合に処理対象のデータ列の内容を比較し、各データ列の内容、すなわちデータ要素が一致する範囲に対しては分割処理をスキップし、各データ列のデータ要素が異なる場合にそのデータ要素から分割処理を再開する。
【００２１】
このデータ列整列方法は、データ列の種類を問わず、任意のデータ列の整列に用いることができるが、ここでは文字列を整列する場合を例示して説明する。また、データ列のデータ要素を、２バイト分のテキストデータとする。これは、２バイトのテキストデータを日本語１文字に対応させ、文字データ列を文字ごとに整列させるためである。
【００２２】
さらに、本実施例では、クイックソートによって整列をおこなう前に、あらかじめ基数整列法によってデータ列の整列をおこなう。基数整列法は、整列する桁数が小さい場合にはクイックソートに比して高速であるが、整列する桁数が大きい場合にはクイックソートに比して遅くなる。したがって、データ列の先頭部分の所定バイトのみ基数整列法で整列しておき、残りをクイックソートによって整列することで、データ列の整列をさらに高速に実行可能なためである。なお、ここでは、日本語の文字列の整列を前提とし、データ要素を２バイトのテキストデータとしているため、基数整列法による整列は、２バイト、もしくはその倍数とする。
【００２３】
図１に、本実施の形態にかかるデータ列整列装置の概要構成を示す。この図１に示したデータ列整列装置では、まず、データ入力部１が整列対象である文字データ列を基数整列部２に入力する。基数整列部２は、入力された文字データ列の先頭２バイトを基数整列法によって整列した後、整列制御部３に文字データ列を送信する。整列制御部３は、文字データ列を受信した場合に、計数処理部４に設けたカウンタの値を１増やし、計数処理部４のカウンタの値としきい値記憶部５が記憶するしきい値とを比較する。この計数処理部４のカウンタの値がしきい値以下であれば、整列制御部３は、文字データ列をクイックソート実行部７に送信する。また、計数処理部４のカウンタの値がしきい値を超えた場合、整列制御部３は、文字データ列をデータ比較部６に送信し、計数処理部４のカウンタをリセットする。
【００２４】
クイックソート実行部７は、受信した文字データ列を分割処理し、この分割処理によって文字データ列の整列が終了した場合に文字データ列をデータ出力部８に送信する。また、分割処理によって文字データ列の整列が終了していない場合には、文字データ列を再度整列制御部３に送信する。したがって、計数処理部４のカウンタは、文字データ列に対して分割処理が実行された回数を記憶することとなり、整列制御部３は、分割処理の実行回数がしきい値を超えた場合に文字データ列をデータ比較部６に送信することとなる。
【００２５】
データ比較部６は、文字データ列を受信した場合に、その未整列領域の先頭２バイト、すなわち未整列領域の１文字目を比較する。各文字データ列の未整列領域の１文字目が全て同一であれば、データ比較部６は、各文字列データの１文字目を整列済みとし、各文字列データの次の文字である、新たな未整列領域の１文字目を比較する。
【００２６】
このように、データ比較部６は、各文字データ列の文字の比較を繰り返し、比較した文字が全て同一であればその文字を整列済みとする。また、データ比較部６は、文字データ列に互いに異なる文字が現れた場合、文字の比較を終了し、文字データ列をクイックソート実行部７に送信する。なお、このデータ比較部６の処理によって文字データ列が全て整列済みとなった場合、データ比較部６は、整列済みとなった文字データ列をデータ出力部８に送信する。
【００２７】
したがって、データ比較部６は、クイックソート実行部７が分割処理を所定回数おこなった場合に、文字データ列の未整列領域の文字を比較し、比較した文字が同一か否か、すなわち、文字データ列の内容が重複しているか否かを判定し、重複部分を整列済みとしてクイックソート実行部７に送信することで、クイックソート実行部７による分割処理回数を減少させることとなる。
【００２８】
文字データ列に重複がある場合における整列処理の一例を図２に示す。図２において、データ列１１，１２，１３は、それぞれ２バイト文字からなる文字データ列である。このデータ列１１，１２，１３を整列する場合、まず、先頭の２バイトを基数整列部２によって整列する。したがって、先頭の１文字に相当するデータ領域２１は、基数整列部２によって整列処理されることとなる。
【００２９】
つぎに、データ列１１，１２，１３は、クイックソート実行部７によって分割処理される。ここで、しきい値記憶部５が記憶するしきい値の値を「１０」とした場合、クイックソート実行部７による分割処理は１０回繰り返される。したがって、データ列１１，１２，１３の２文字目から１１文字目に相当するデータ範囲２２は、クイックデータ実行部７によって分割処理されることとなる。
【００３０】
データ範囲２２の処理終了によって、分割処理の実行回数がしきい値に達するため、データ列１１，１２，１３の１２文字目から始まるデータ範囲２３は、データ比較部６によって処理されることとなる。ここで、データ列１１，１２，１３の１２文字目から２０文字目までは、「うええええおおおお」と同一の値であり、この範囲においてデータ列１１，１２，１３の内容は重複している。したがって、データ比較部６は、データ列１１，１２，１３の１２文字目から２０文字目までに相当するデータ範囲２３を整列済みとする。
【００３１】
データ比較部６は、さらにデータ列１１，１２，１３の２１文字目を比較する。しかし、データ列１１およびデータ列１２の２１文字目は「か」、データ列１３の２１文字目は「あ」であり、データ列１１，１２，１３の２１文字目は同一ではない。そこで、データ比較部６は、データ列１１，１２，１３の２１文字目を未整列としたままで、データ列１１，１２，１３をクイックソート実行部７に送信する。すなわち、データ列１１，１２，１３の２１文字目からはじまるデータ範囲２４は、再びクイックソート実行部７によって処理されることとなる。
【００３２】
つぎに、このデータ列整列方法の処理動作について、さらに詳細に説明する。図３は、このデータ列整列方法の処理動作を説明するフローチャートである。このデータ列整列方法を用いて文字列を整列する場合、まず、データ入力部１によって文字データ列を入力し（ステップＳ１０１）、文字データ列の先頭２バイトを基数整列法によって整列する（ステップＳ１０２）。つぎに、基数整列の結果、幅が２行以上となった領域の全てを処理したかを判定する（ステップＳ１０３）。ここで、幅２行以上の領域を全て処理した場合（ステップＳ１０３，Ｙｅｓ）、整列した文書を出力し（ステップＳ１２３）、処理動作を終了する。
【００３３】
一方、基数整列を実行した後の文字データ列で、幅２行以上の未処理領域が残っている場合（ステップＳ１０３，Ｎｏ）、同領域を１文字進めて未整列領域とし、処理対象に設定する（ステップＳ１０４）。つぎに、計数処理部４のカウンタが記憶する分割処理回数を１増やし（ステップＳ１０５）、分割処理回数がしきい値を超えたか否かを判定する（ステップＳ１０６）。
【００３４】
分割処理回数がしきい値を超えていない場合（ステップＳ１０６，Ｎｏ）、クイックソート実行部７が文字データ列の分割処理を開始する。まず、クイックソート実行部７は、処理対象の未整列領域から基準データを算出する（ステップＳ１０７）。この基準データは、各データ列の未整列領域における先頭の文字を抽出し、抽出した文字を比較して、中央値（ｍｅｄｉａｎ）を選択することで得られる。
【００３５】
つぎに、クイックソート実行部７は、処理対象の未整列領域における各データ列の先頭文字と基準データとを比較し、先頭文字が基準データに比して大きいデータ列を新規の未整列領域として分割し、処理対象から取り除く（ステップＳ１０８）。また、クイックソート実行部７は、処理対象の未整列領域における各データ列の先頭文字と基準データとを比較し、先頭文字が基準データに比して小さいデータ列を新規の未整列領域として分割し、処理対象から取り除く（ステップＳ１０９）。
【００３６】
さらに、クイックソート実行部７は、先頭文字が基準データに同一の文字データ列について、先頭文字を整列済みとして処理対象から取り除く。すなわち、処理対象の未整列領域を文字データ列の後方に１文字進める（ステップＳ１１０）。つぎに、このステップＳ１０８〜ステップＳ１１０で得られた未整列領域で、幅が２行以上、かつ残りの長さが１文字以上のものを処理対象に設定する（ステップＳ１１１）。ここで、処理対象の条件（幅２行以上、残り長さ１文字以上）を満たす領域がもはや残っていないかの判断をおこなう（ステップＳ１１２）。この結果、処理対象の条件を満たす領域が残っている場合（ステップＳ１１２，Ｎｏ）、ステップＳ１０５に戻って分割処理を再帰的に続行する。また、処理対象の条件を満たす領域が残っていない場合（ステップＳ１１２，Ｙｅｓ）、ステップＳ１０３の判断に戻る。
【００３７】
一方、分割処理回数がしきい値を超えた場合（ステップＳ１０６，Ｙｅｓ）、整列制御部３は、文字データ列をデータ比較部６に送信する。データ比較部６は、処理対象である文字データ列について、未整列領域の１文字目を比較する（ステップＳ１２１）。未整列領域の１文字目が同一ではない場合（ステップＳ１２１，Ｎｏ）、文字データ列は、クイックソート実行部７に送信され、分割処理が実行される（ステップＳ１０７）。
【００３８】
また、未整列領域の１文字目が同一である場合（ステップＳ１２１，Ｙｅｓ）、データ比較部６は、未整列領域の１文字目を整列済みとして処理対象から取り除く。すなわち、処理対象の未整列領域を文字データ列の後方に１文字進めた（ステップＳ１２２）後、ステップＳ１２１に戻って比較処理を続行する。
【００３９】
つぎに、図４〜図６を参照し、文字データ列の整列処理の具体例について説明する。ここで、整列処理の対象は、含まれる文字が文書を形成する文字データ列と、この文字データ列を２バイト、すなわち１文字ずつずらして形成した複数の文字データ列とを含むデータ集合を想定する。このように、所望の文書を１文字ずつずらして形成したデータ集合は、文字列の巡回行列と呼ばれる。文字列の巡回行列を整列することで、文書のデータ圧縮の効率化や、文字列探索の高速化が図れるため、文字列の巡回行列の整列は非常に有用である一方、繰り返しによって重複が発生し易いので、クイックソートの速度低下が懸念されるデータである。
【００４０】
図４（ａ）に、元文書データである文字データ列Ｄ０１を示す。この文字データ列Ｄ０１は、２４バイトのデータであり、その内容は、「咲いた咲いた桜が咲いた＃」である。ここで、最後の２バイト「＃」は、文章の終端を示す終端記号である。
【００４１】
また、図４（ｂ）に、文字データ列Ｄ０１から形成した巡回行列を示す。この巡回行列は、文字列データＤ０１と、文字列データＤ０１を１文字ずつずらした文字列データＤ０２〜Ｄ１２によって形成される。ここで、文字データ列Ｄ０２は、文字列データＤ０１を１文字ずらして形成した文字データ列であり、その内容は「いた咲いた桜が咲いた＃咲」となる。また、文字データ列Ｄ０３は、文字データ列Ｄ０１を２文字ずらして形成した文字データ列であり、その内容は「た咲いた桜が咲いた＃咲い」となる。以下同様に順次文字をずらした文字データ列Ｄ０４〜Ｄ１２を形成する。なお、ここでは元となる文字データ列Ｄ０１が２４バイト、すなわち１２文字であるので、文字データ列Ｄ１２まで形成し、巡回行列が１２２となるようにする。処理対象となる元データ列のデータ要素数がｎ個である場合は、巡回行列がｎ２となるようにデータ列を形成する必要がある。
【００４２】
このように、文字データ列Ｄ０１〜Ｄ１２によって形成された巡回行列であるデータ集合３１を、本実施の形態にかかるデータ列整列方法によって整列する場合を考える。まず、文字データ列Ｄ０１〜Ｄ１２について、それぞれのデータ列の１文字目からなる開始列３２を基数整列し、整列結果にしたがって文字データ列Ｄ０１〜Ｄ１２を並べ替える。
【００４３】
図４（ｃ）は、基数整列による並べ替え実行後のデータ集合を示す図である。図４（ｃ）において、データ列Ｄ０１〜Ｄ１２は、１文字目に依存して整列されている。この結果として、１文字目が「＃」であるデータ集合４１が先頭となり、１文字目が「い」であるデータ集合４２が続く。さらに、１文字目が「が」であるデータ集合４３、１文字目が「た」であるデータ集合４４、１文字目が「咲」であるデータ集合４５、１文字目が「桜」であるデータ集合４６が順次続くこととなる。
【００４４】
具体的には、データ集合４１に含まれるのは、文字データ列Ｄ１２である。また、データ集合４２は、文字データ列Ｄ０２，Ｄ０５，Ｄ１０によって形成される。さらに、データ集合４３は、文字データ列Ｄ０８によって形成され、データ集合４４は、文字データ列Ｄ０３，Ｄ０６，Ｄ１１によって形成され、データ集合４５は、文字データ列Ｄ０１，Ｄ０４，Ｄ０９によって形成され、データ集合４６は、文字データ列Ｄ０７によって形成される。
【００４５】
この図４（ｃ）に示したように、各データ列の１文字目は、基数整列法によって整列済みとなり、各文字列の２文字目以降が未整列領域となる。したがってクイックソートを用いて分割処理するのは、各データ列の２文字目以降である。
【００４６】
つぎに、図５を参照し、クイックソートを用いた分割処理について説明する。クイックソートを用いた分割処理は、データ集合４１〜４６の各々に対して実行するが、ここでは、データ集合４４における分割処理を例として示す。また、図４（ｃ）において、データ集合４４は、文字データ列Ｄ０３，Ｄ０６，Ｄ１１の３つの文字データ列によって構成されているが、図５においては、便宜上、文字データ列を追加して４つのデータ列によって構成しているものとして説明する。
【００４７】
図５（ａ）に示すように、データ集合４４は、基数整列によって整列された整列済領域５１と未整列領域５２とを有する。この未整列領域５２をクイックソートによって分割処理する場合、クイックソート実行部７は、まず、図５（ｂ）に示すように、各文字データ列の未整列領域における１文字目を抽出し、先頭文字データ５３を形成する。
【００４８】
つぎに、クイックソート実行部７は、先頭文字データ５３から基準データの算出をおこなう。ここでは、先頭文字データ５３に含まれる文字の大小関係を比較し、文字符号の中央値を基準データとして選択する。ここで、文字の大小関係とは、文字符号の値の大小関係をいうものとする。先頭文字データ５３に含まれる文字は、「咲」、「＃」、「桜」の３種であり、
「＃」＜「咲」＜「桜」
という大小関係が成り立つので、基準データは中央値である「咲」となる。
【００４９】
つづいて、クイックソート実行部７は、各データ列の未整列領域の１文字目と基準データとを比較し、未整列領域５２の分割をおこなう。具体的には、図５（ｃ）に示すように、未整列領域の１文字目が基準データに比して小さい文字データ列を未整列領域５４に振り分け、未整列領域の１文字目が基準データに比して大きい文字データ列を未整列領域５５に振り分ける。この新規に作成した未整列領域５４，５５を処理対象から外して独立させることで、文字データ列の１文字目が基準データと同一の「咲」である未整列領域５２ａを得ることができる。
【００５０】
この未整列領域５２ａでは、全ての文字データ列の１文字目が「咲」であるので、クイックソート実行部７は、図５（ｄ）に示すように、各データ列の１文字目を整列済みとして未整列領域５２ａから取り除き、整列済領域５１に加える。したがって、処理対象の未整列領域５２ａは、文字データ列の後方に１文字進み、未整列領域５２ｂを形成することとなる。
【００５１】
このように、クイックソート実行部７は、分割処理によって未整列領域５２を未整列領域５４，５２ａ，５５の３つの未整列領域に分割することとなる。ここで、１文字目が基準データと同一であった未整列領域５２ｂは、１文字目が整列済みとなることで、未整列領域が１文字減少している。この未整列領域５２ｂ、５４、５５の各々からさらに基準データを選択し、分割処理を実行することで、１文字目が基準データに比して大きい領域、１文字目が基準データに比して小さい領域、１文字目が基準データと同一である領域に分割することができる。また、このとき、基準データと同一である領域では、未整列領域が文字データ列の後方にさらに１文字進む。したがって、分割処理を再帰的に実行することで、データ列を整列することができる。
【００５２】
図６は、クイックソートによる整列実行後のデータ集合を示す図である。図６において、データ列Ｄ０１〜Ｄ１２は、文字の順序によって完全に整列されている。この結果として、１文字目が「＃」である文字データ列Ｄ１２が先頭となり、文字データ列Ｄ１０，Ｄ０５，Ｄ０８，Ｄ１１，Ｄ０３，Ｄ０６、Ｄ０９，Ｄ０１，Ｄ０４，Ｄ０７の順に並んでいる。
【００５３】
このようにして、整列済み巡回行列７０を得ることができ、文書のデータ圧縮の効率化や、文字列探索の高速化が図れる。たとえば、文書データの圧縮においては、各データ列の末尾の１文字を採った末尾データ列７１を作成し、この末尾データ列を圧縮することで、文書データの圧縮率を向上することができる。このような文書データの圧縮方法は、ブロック整列圧縮と呼ばれる。また、文字列探索を高速化する場合には、元の文書データから巡回行列を形成する場合に、各文字データ列が元の文書データに対してどれだけずれているかを示す位置情報を付加した後に巡回行列の整列を実行し、位置情報の並びを接尾辞配列（Ｓｕｆｆｉｘ　ａｒｒａｙ）として記憶することで、文字列の探索を高速化できる。
【００５４】
上述してきたように、本実施の形態では、クイックソート実行部７が実行する分割処理の回数を計数し、分割処理の回数が所定数を超えた場合に処理対象のデータ列の内容を比較し、各データ列の内容、すなわちデータ要素が一致する範囲に対しては分割処理をスキップし、各データ列のデータ要素が異なる場合にそのデータ要素から分割処理を再開することとしたので、データ列の内容が重複する場合におけるクイックソートの速度低下を防止し、データ列の整列を高速に実行することができる。
【００５５】
なお、本実施の形態ではデータ列整列方法の実現に必要な機能を物理的な処理手段として備えたデータ列整列装置について説明したが、必要な機能をソフトウェアによって実現することで、データ列整列方法を実行するデータ列整列プログラムを得ることができる。
【００５６】
（付記１）データ集合に含まれる複数のデータ列を、所定の規則に従って複数の部分データ集合のいずれかに振り分ける分割処理を再帰的に実行する分割処理工程と、
前記分割処理工程によって実行された前記分割処理の回数を計数する計数工程と、
前記計数工程によって計数された分割処理回数が所定のしきい値を超えた場合に、分割処理対象のデータ列のデータ要素を比較し、各データ列のデータ要素が互いに一致する範囲に対する前記分割処理をスキップし、各データ列のデータ要素が互いに異なる場合に前記分割処理工程を再開するデータ比較工程と、
を含むことを特徴とするデータ列整列方法。
【００５７】
（付記２）前記分割処理工程は、前記データ列のデータ要素と任意に定めた基準データとを比較し、前記データ要素と前記基準データとの大小関係によって前記データ列を振り分けるクイックソートをおこなうことを特徴とする付記１に記載のデータ列整列方法。
【００５８】
（付記３）前記データ集合は、第１のデータ列と、当該第１のデータ列を所定量ずつずらして形成した複数の巡回データ列とを含むことを特徴とする付記１または２に記載のデータ列整列方法。
【００５９】
（付記４）前記複数のデータ列は、当該データ列の先頭部分に対して基数整列を用いて整列済みであることを特徴とする付記１〜３のいずれか一つに記載のデータ列整列方法。
【００６０】
（付記５）データ集合に含まれる複数のデータ列を、所定の規則に従って複数の部分データ集合のいずれかに振り分ける分割処理を再帰的に実行する分割処理工程と、
前記分割処理工程によって実行された前記分割処理の回数を計数する計数工程と、
前記計数工程によって計数された分割処理回数が所定のしきい値を超えた場合に、分割処理対象のデータ列のデータ要素を比較し、各データ列のデータ要素が互いに一致する範囲に対する前記分割処理をスキップし、各データ列のデータ要素が互いに異なる場合に前記分割処理工程を再開するデータ比較工程と、
をコンピュータに実行させることを特徴とするデータ列整列プログラム。
【００６１】
（付記６）データ集合に含まれる複数のデータ列を、所定の規則に従って複数の部分データ集合のいずれかに振り分ける分割処理を再帰的に実行する分割処理手段と、
前記分割処理手段によって実行された前記分割処理の回数を計数する計数手段と、
前記計数手段によって計数された分割処理回数が所定のしきい値を超えた場合に、分割処理対象のデータ列のデータ要素を比較し、各データ列のデータ要素が互いに一致する範囲に対する前記分割処理をスキップし、各データ列のデータ要素が互いに異なる場合に前記分割処理を再開するデータ比較手段と、
を備えたことを特徴とするデータ列整列装置。
【００６２】
【発明の効果】
以上説明したように、この発明によれば、データ列に対する分割処理の実行回数を計数し、この分割処理の実行回数が所定のしきい値を超えた場合に、分割処理対象のデータ列の内容を比較して、データ列の内容が同一の範囲に対しては分割処理をスキップすることで、重複した内容のデータに対する分割処理の回数を減少させることができるので、重複したデータ列を整列する場合の整列速度を向上し、データ列の整列を高速に実行可能なデータ列整列方法を提供することができるという効果を奏する。
【００６３】
また、この発明によれば、クイックソートにおける分割処理の実行回数が所定のしきい値を超えた場合に、分割処理対象のデータ列の内容を比較して、データ列の内容が同一の範囲に対しては分割処理をスキップすることで、データ内容の重複を原因とするクイックソートの速度低下を防止することができるので、重複したデータ列を整列する場合におけるクイックソートの整列速度を向上し、データ列の整列を高速に実行可能なデータ列整列方法を提供することができるという効果を奏する。
【００６４】
また、この発明によれば、所定のデータ列をずらして形成した巡回行列に対してクイックソートを実行し、クイックソートにおける分割処理の実行回数が所定のしきい値を超えた場合に、分割処理対象のデータ列の内容を比較し、データ列の内容が同一の範囲に対しては分割処理をスキップするようにしているので、任意のデータ列の整列を高速に実行可能なデータ列整列方法を提供することができるという効果を奏する。
【００６５】
また、この発明によれば、基数整列を用いて先頭部分を整列済みであるデータ列に対してクイックソートを実行し、クイックソートにおける分割処理の実行回数が所定のしきい値を超えた場合に、分割処理対象のデータ列の内容を比較し、データ列の内容が同一の範囲に対しては分割処理をスキップするようにしているので、重複したデータ列を整列する場合の整列速度をさらに向上し、データ列の整列を高速に実行可能なデータ列整列方法を提供することができるという効果を奏する。
【図面の簡単な説明】
【図１】本実施の形態にかかるデータ列整列装置の概要構成を示す図である。
【図２】文字データ列に重複がある場合における整列処理の一例を示す図である。
【図３】データ列整列方法の処理動作を説明するフローチャートである。
【図４】巡回行列の作成および基数整列について説明する説明図である。
【図５】クイックソートを用いた分割処理について説明する説明図である。
【図６】クイックソートによる整列実行後のデータ集合を示す図である。
【符号の説明】
１　データ入力部
２　基数整列部
３　整列制御部
４　計数処理部
５　しきい値記憶部
６　データ比較部
７　クイックソート実行部
８　データ出力部
１１，１２，１３，Ｄ０１〜Ｄ１２　文字データ列
２１，２２，２３，２４　データ範囲
３１，４１〜４６　データ集合
３２　開始列
５１　整列済領域
５２，５２ａ，５２ｂ，５４，５５　未整列領域
５３　先頭文字データ
７０　整列済み巡回行列
７１　末尾データ列
【図１】
2004094504.tif 000003
【図２】
2004094504.tif 000004
【図３】
2004094504.tif 000005
【図４】
2004094504.tif 000006
【図５】
2004094504.tif 000007
【図６】
2004094504.tif 000008