(57)【要約】【課題】ウェーブレット木およびウェーブレット行列の生成を現実的かつ高速に行うこと【解決手段】情報処理装置は、それぞれｎビットで表現される複数の要素からなる第０段の配列を取得し、第ｋ−１段の配列または部分配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該配列または部分配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置し、前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の配列を決定する。前記第ｋ段の配列を決定するステップでは、ビット演算を含むプロセッサ命令を実行することにより、前記第ｋ段の第１の部分配列および／または前記第ｋ段の第２の部分配列を生成する。【選択図】図２
2020060844.tif 000002
【特許請求の範囲】
【請求項１】
それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得する配列取得手段と、
第ｋ−１段（ｋ：１以上ｎ−１以下の整数）の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置し、前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の配列を決定する振り分け手段と、
を含み、
前記振り分け手段は、第ｋ−１段の配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する、
情報処理装置。
【請求項２】
請求項１に記載の情報処理装置において、
前記振り分け手段は、第ｋ−１段の配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ第１の追加データおよび／または前記各要素のうち上位から前記第ｋ番目のビットが１である要素が順序を崩さずに並ぶ第２の追加データを生成し、前記第１の追加データを前記第１の部分配列に追加し、前記第２の追加データを前記第２の部分配列に追加する、
情報処理装置。
【請求項３】
それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得する配列取得手段と、
第０段の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第１段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第１段の第２の部分配列に配置し、
第ｋ−１段（ｋ：２以上ｎ−１以下の整数）の第１および第２の部分配列のそれぞれについて、当該部分配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該部分配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置する、振り分け手段と、
を含み、
前記振り分け手段は、第ｋ−１段の第１の部分配列および／または第２の部分配列のそれぞれについて、当該部分配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する、
情報処理装置。
【請求項４】
請求項３に記載の情報処理装置において、
前記振り分け手段は、第ｋ−１段の第１の部分配列および／または第２の部分配列のそれぞれについて、当該部分配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ第１の追加データおよび／または前記各要素のうち上位から前記第ｋ番目のビットが１である要素が順序を崩さずに並ぶ第２の追加データを生成し、前記第１の追加データを前記第１の部分配列に追加し、前記第２の追加データを前記第２の部分配列に追加する、
情報処理装置。
【請求項５】
請求項１から４のいずれかに記載の情報処理装置において、
前記振り分け手段は、前記レジスタに格納される各要素の上位から第ｋ番目のビットに基づいて、前記レジスタに格納される要素のうち、上位から第ｋ番目のビットが０である１または複数の要素を連続して配置させ、かつ、上位から第ｋ番目のビットが１である１または複数の要素を連続して配置させるための、前記レジスタに格納される各要素のシフト量を示すシフトパラメータと、前記第１の部分配列および／または前記第２の部分配列のそれぞれに配置される要素を抽出するためのビットパターンと、を取得し、前記レジスタに格納されるデータに対し前記取得されたビットパターンに基づく論理積を実行することにより中間データを抽出し、前記抽出された中間データに対し前記取得されたシフトパラメータに基づくビット演算を含むプロセッサ命令を実行することにより、前記第ｋ段の第１の部分配列および／または第２の部分配列を生成する、
情報処理装置。
【請求項６】
請求項５に記載の情報処理装置において、
前記レジスタに格納される各要素の上位から第ｋ番目のビットが連続して並ぶパックデータを生成する手段と、
前記パックデータがとりうる複数の値にそれぞれ関連付けられる複数のシフトパラメータ候補であって、それぞれがレジスタに格納される複数の要素のシフト量を示す複数のシフトパラメータを記憶する記憶手段と、
をさらに含み、
前記振り分け手段は、前記記憶手段に記憶される複数のシフトパラメータから、前記パックデータに関連付けられたシフトパラメータを取得する、
情報処理装置。
【請求項７】
請求項５に記載の情報処理装置において、
前記振り分け手段は、前記レジスタに格納される各要素の上位から第ｋ番目のビットを論理積により抽出し、前記抽出された情報に対して所定の整数値の掛け算を含むプロセッサ命令を実行することにより、前記シフトパラメータを算出する、
情報処理装置。
【請求項８】
請求項１から４のいずれかに記載の情報処理装置において、
前記レジスタに格納される要素の上位から第ｋ番目のビットが連続して並ぶパックビット列を生成する手段と、
前記パックビット列がとりうる複数の値にそれぞれ関連付けられる複数の配置データであって、それぞれが、前記第１の部分配列に順に配置されるレジスタの要素、および、前記第２の部分配列に順に配置される前記レジスタの要素を特定する複数の配置データを記憶する記憶手段と、をさらに含み、
前記振り分け手段は、前記記憶手段から、前記パックデータに関連付けて記憶される配置データを取得し、前記レジスタおよび前記取得された配置データに対し所定のプロセッサ命令を実行することにより、前記第１の部分配列および／または前記第２の部分配列を生成する、
情報処理装置。
【請求項９】
請求項１から４のいずれかに記載の情報処理装置において、
前記レジスタに格納される各要素の上位から第ｋ番目のビットが連続して並ぶパックビット列を生成する手段と、
前記パックビット列がとりうる複数の値にそれぞれ関連付けられる複数のビットパターンであって、それぞれが、レジスタにおける、前記第１の部分配列および前記第２の部分配列のうちいずれかに配置される要素のビット位置を示す複数のビットパターンを記憶する記憶手段と、をさらに含み、
前記振り分け手段は、前記記憶手段から、前記パックデータに関連付けて記憶されるビットパターンを取得し、前記レジスタに対し前記取得されたビットパターンに基づく所定のプロセッサ命令を実行することにより、前記第１の部分配列および／または前記第２の部分配列を生成する、
情報処理装置。
【請求項１０】
請求項１または２に記載の情報処理装置において、
第０段の配列に含まれる複数の要素に基づいて、前記複数の要素のそれぞれを構成する複数のビットのうち所定の範囲のビットを抽出し、前記抽出された各要素の複数のビットが並んでなる第０段の縮小配列を生成する縮小手段をさらに含み、
前記振り分け手段は、前記第ｋ−１段の縮小配列に基づいて、前記第１の部分配列および前記第２の部分配列を生成し、前記生成された前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の縮小配列を決定することにより第ｋ段の配列を決定する、
情報処理装置。
【請求項１１】
請求項１０に記載の情報処理装置において、
前記縮小手段は、第０段の配列に含まれる複数の要素に基づいて、前記複数の要素のそれぞれを構成する各要素の１番目からτ番目のビットからなる部分ビット列を抽出し、前記抽出された各要素の部分ビット列が順序を崩さずに並ぶ第０段の縮小配列を生成し、
前記縮小手段は、第α×τ段（αは、１以上ｎ／τ未満の整数）の縮小配列に格納される要素の順序に基づいて前記第０段の配列に含まれる複数の要素を並び替え、前記並び替えられた複数の要素のα×τ＋１番目から（α＋１）×τ番目のビットからなる部分ビット列を抽出し、前記抽出された各要素の部分ビット列が順序を崩さずに並ぶ新たな第α×τ段の縮小配列を生成する、
情報処理装置。
【請求項１２】
請求項３または４に記載の情報処理装置において、
第０段の配列に含まれる複数の要素に基づいて、前記複数の要素のそれぞれを構成する複数のビットのうち所定の範囲のビットを抽出し、前記抽出された各要素の複数のビットが並んでなる第０段の縮小配列を生成する縮小手段をさらに含み、
前記振り分け手段は、前記第０段の縮小配列に基づいて、第１段の第１の部分配列および第２の部分配列を生成する、
情報処理装置。
【請求項１３】
請求項１２に記載の情報処理装置において、
前記縮小手段は、第０段の配列に含まれる複数の要素に基づいて、前記複数の要素のそれぞれを構成する各要素の１番目からτ番目のビットからなる部分ビット列を抽出し、前記抽出された各要素の部分ビット列が順序を崩さずに並ぶ第０段の縮小配列を生成し、
前記縮小手段は、第α×τ段（αは、１以上ｎ／τ未満の整数）の第１の部分配列および第２の部分配列に格納される要素の順序に基づいて前記第０段の配列に含まれる複数の要素を並び替え、前記並び替えられた複数の要素のα×τ＋１番目から（α＋１）×τ番目のビットからなる部分ビット列を抽出することにより、新たな第α×τ段の第１の部分配列および第２の部分配列を生成する、
情報処理装置。
【請求項１４】
請求項１または２に記載の情報処理装置において、
前記第ｑ段（ｑは０以上ｎ−１以下の整数）の配列に格納される各要素のｑ番目のビットが連続して並ぶ第ｑ段のパックデータを生成するパックデータ生成手段と、
前記パックデータ生成手段により生成された第０段から第ｎ−１段のパックデータに基づいて、最大値、最小値、中央値、最頻値のうちいずれかを含む統計処理を実行する統計手段と、
をさらに含む、
情報処理装置。
【請求項１５】
請求項３または４に記載の情報処理装置において、
第ｑ段（ｑは０以上ｎ−１以下の整数）のパックデータを生成するパックデータ生成手段と、
前記パックデータ生成手段により生成された第０段から第ｎ−１段のパックデータに基づいて、最大値、最小値、中央値、最頻値のうちいずれかを含む統計処理を実行する統計手段と、
をさらに含み、
前記振り分け手段は、第ｑ段（ｑは０以上ｎ−１以下の整数）の第１の部分配列および第２の部分配列に基づいて第ｑ段の配列を決定し、
前記パックデータ生成手段は、前記第ｑ段（ｑは０以上ｎ−１以下の整数）の配列に格納される各要素のｑ番目のビットが連続して並ぶ第ｑ段のパックデータを生成する、
情報処理装置。
【請求項１６】
それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得するステップと、
第ｋ−１段（ｋ：１以上ｎ−１以下の整数）の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置し、前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の配列を決定する振り分けステップと、
を含み、
前記振り分けステップでは、第ｋ−１段の配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する、
情報処理方法。
【請求項１７】
それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得するステップと、
第０段の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第１段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第１段の第２の部分配列に配置するステップと、
第ｋ−１段（ｋ：２以上ｎ−１以下の整数）の第１および第２の部分配列のそれぞれについて、当該部分配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該部分配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置する、振り分けステップと、
を含み、
前記振り分けステップでは、第ｋ−１段の第１の部分配列および／または第２の部分配列のそれぞれについて、当該部分配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する、
情報処理装置。
【請求項１８】
それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得する配列取得手段、
第ｋ−１段（ｋ：１以上ｎ−１以下の整数）の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置し、前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の配列を決定する振り分け手段、
としてコンピュータを機能させ、
前記振り分け手段は、第ｋ−１段の配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する、
プログラム。
【請求項１９】
それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得する配列取得手段、
第０段の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第１段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第１段の第２の部分配列に配置し、
第ｋ−１段（ｋ：２以上ｎ−１以下の整数）の第１および第２の部分配列のそれぞれについて、当該部分配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該部分配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置する、振り分け手段、
としてコンピュータを機能させ、
前記振り分け手段は、第ｋ−１段の第１の部分配列および／または第２の部分配列のそれぞれについて、当該部分配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する、
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
大規模なデータを効率的に解析することに適したデータ構造として、ウェーブレット木およびウェーブレット行列が注目されている。これらはそれぞれ要素値を含む複数の要素からなる配列を表現するデータ構造である。これらのデータ構造は、最大値や最頻値の計算などの統計処理や、情報の圧縮処理など、さまざまな処理に活用できることが知られている。
【０００３】
非特許文献１および非特許文献２には、入力される配列からウェーブレット木を生成する方法が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Babenko, M., Gawrychowski, P., Kociumaka, T., Starikovskaya, T.: Wavelet trees meet suffix trees. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 572‐591, SODA’15 (2015)
【非特許文献２】Munro, J.I., Nekrich, Y., Vitter, J.S.: Fast construction of wavelet trees, Theor. Comput. Sci. 638(C), 91‐97 (July 2016)
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ウェーブレット木およびウェーブレット行列は、要素値が設定された配列を変換することで生成される。この変換では、配列に含まれる複数の要素のうち所定のビットが０である要素を順序が崩れないように抽出する処理、および、所定のビットが１であるものを順序が崩れないように抽出する処理が必要である。この処理を、現実的かつ高速に実装することが困難であった。仮に、配列のうち数個の要素をまとめ、その数個の要素の組み合わせと、抽出後の要素とを対応付けたルックアップテーブルを準備することも考えられるが、とりうる組み合わせの数が膨大になるために現実的には実現が困難であった。
【０００６】
本発明は上記課題を鑑みてなされたものであって、その目的は、ウェーブレット木およびウェーブレット行列の生成を現実的かつ高速に行うことのできる技術を提供することにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明にかかる情報処理装置は、それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得する配列取得手段と、第ｋ−１段（ｋ：１以上ｎ−１以下の整数）の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置し、前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の配列を決定する振り分け手段と、を含む。前記振り分け手段は、第ｋ−１段の配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する。
【０００８】
また、本発明にかかる情報処理方法は、それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得するステップと、第ｋ−１段（ｋ：１以上ｎ−１以下の整数）の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置し、前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の配列を決定する振り分けステップと、を含む。前記振り分けステップでは、第ｋ−１段の配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する。
【０００９】
また、本発明にかかるプログラムは、それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得する配列取得手段、第ｋ−１段（ｋ：１以上ｎ−１以下の整数）の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置し、前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の配列を決定する振り分け手段、としてコンピュータを機能させる。前記振り分け手段は、第ｋ−１段の配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する。
【００１０】
本発明の一形態では、前記振り分け手段は、第ｋ−１段の配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ第１の追加データおよび／または前記各要素のうち上位から前記第ｋ番目のビットが１である要素が順序を崩さずに並ぶ第２の追加データを生成し、前記第１の追加データを前記第１の部分配列に追加し、前記第２の追加データを前記第２の部分配列に追加してもよい。
【００１１】
また、本発明にかかるもう１つの情報処理装置は、それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得する配列取得手段と、第０段の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第１段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第１段の第２の部分配列に配置し、第ｋ−１段（ｋ：２以上ｎ−１以下の整数）の第１および第２の部分配列のそれぞれについて、当該部分配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該部分配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置する、振り分け手段と、を含む。前記振り分け手段は、第ｋ−１段の第１の部分配列および／または第２の部分配列のそれぞれについて、当該部分配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する。
【００１２】
また、本発明にかかるもう１つの情報処理方法は、それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得するステップと、第０段の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第１段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第１段の第２の部分配列に配置するステップと、第ｋ−１段（ｋ：２以上ｎ−１以下の整数）の第１および第２の部分配列のそれぞれについて、当該部分配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該部分配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置する、振り分けステップと、を含む。前記振り分けステップでは、第ｋ−１段の第１の部分配列および／または第２の部分配列のそれぞれについて、当該部分配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する。
【００１３】
また、本発明にかかるもう１つのプログラムは、それぞれｎビット（ｎ：正の整数）で表現される要素値を含む複数の要素からなる第０段の配列を取得する配列取得手段、第０段の配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第１段の第１の部分配列に配置し、当該配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第１段の第２の部分配列に配置し、第ｋ−１段（ｋ：２以上ｎ−１以下の整数）の第１および第２の部分配列のそれぞれについて、当該部分配列に含まれ上位からｋ番目のビットが０である要素を、順序を崩さないように第ｋ段の第１の部分配列に配置し、当該部分配列に含まれ上位からｋ番目のビットが１である要素を、順序を崩さないように第ｋ段の第２の部分配列に配置する、振り分け手段、としてコンピュータを機能させる。前記振り分け手段は、第ｋ−１段の第１の部分配列および／または第２の部分配列のそれぞれについて、当該部分配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ前記第ｋ段の第１の部分配列および／または前記各要素のうち上位から第ｋ番目のビットが１である要素が順序を崩さずに並ぶ前記第ｋ段の第２の部分配列を生成する。
【００１４】
本発明の一形態では、前記振り分け手段は、第ｋ−１段の第１の部分配列および／または第２の部分配列のそれぞれについて、当該部分配列に含まれる複数の要素のうち連続する２以上の要素が並んでなるデータをレジスタに格納し、前記レジスタに格納される各要素の位置に応じたビット演算を含むプロセッサ命令を実行することにより、前記レジスタに格納される要素のうち上位から第ｋ番目のビットが０である要素が順序を崩さずに並ぶ第１の追加データおよび／または前記各要素のうち上位から前記第ｋ番目のビットが１である要素が順序を崩さずに並ぶ第２の追加データを生成し、前記第１の追加データを前記第１の部分配列に追加し、前記第２の追加データを前記第２の部分配列に追加してもよい。
【００１５】
本発明の一形態では、前記振り分け手段は、前記レジスタに格納される各要素の上位から第ｋ番目のビットに基づいて、前記レジスタに格納される要素のうち、上位から第ｋ番目のビットが０である１または複数の要素を連続して配置させ、かつ、上位から第ｋ番目のビットが１である１または複数の要素を連続して配置させるための、前記レジスタに格納される各要素のシフト量を示すシフトパラメータと、前記第１の部分配列および／または前記第２の部分配列のそれぞれに配置される要素を抽出するためのビットパターンと、を取得し、前記レジスタに格納されるデータに対し前記取得されたビットパターンに基づく論理積を実行することにより中間データを抽出し、前記抽出された中間データに対し前記取得されたシフトパラメータに基づくビット演算を含むプロセッサ命令を実行することにより、前記第ｋ段の第１の部分配列および／または第２の部分配列を生成してもよい。
【００１６】
本発明の一形態では、情報処理装置は、前記レジスタに格納される各要素の上位から第ｋ番目のビットが連続して並ぶパックデータを生成する手段と、前記パックデータがとりうる複数の値にそれぞれ関連付けられる複数のシフトパラメータ候補であって、それぞれがレジスタに格納される複数の要素のシフト量を示す複数のシフトパラメータを記憶する記憶手段と、をさらに含み、前記振り分け手段は、前記記憶手段に記憶される複数のシフトパラメータから、前記パックデータに関連付けられたシフトパラメータを取得してもよい。
【００１７】
本発明の一形態では、前記振り分け手段は、前記レジスタに格納される各要素の上位から第ｋ番目のビットを論理積により抽出し、前記抽出された情報に対して所定の整数値の掛け算を含むプロセッサ命令を実行することにより、前記シフトパラメータを算出してもよい。
【００１８】
本発明の一形態では、情報処理装置は、前記レジスタに格納される要素の上位から第ｋ番目のビットが連続して並ぶパックビット列を生成する手段と、前記パックビット列がとりうる複数の値にそれぞれ関連付けられる複数の配置データであって、それぞれが、前記第１の部分配列に順に配置されるレジスタの要素、および、前記第２の部分配列に順に配置される前記レジスタの要素を特定する複数の配置データを記憶する記憶手段と、をさらに含み、前記振り分け手段は、前記記憶手段から、前記パックデータに関連付けて記憶される配置データを取得し、前記レジスタおよび前記取得された配置データに対し所定のプロセッサ命令を実行することにより、前記第１の部分配列および／または前記第２の部分配列を生成してもよい。
【００１９】
本発明の一形態では、情報処理装置は、前記レジスタに格納される各要素の上位から第ｋ番目のビットが連続して並ぶパックビット列を生成する手段と、前記パックビット列がとりうる複数の値にそれぞれ関連付けられる複数のビットパターンであって、それぞれが、レジスタにおける、前記第１の部分配列および前記第２の部分配列のうちいずれかに配置される要素のビット位置を示す複数のビットパターンを記憶する記憶手段と、をさらに含み、前記振り分け手段は、前記記憶手段から、前記パックデータに関連付けて記憶されるビットパターンを取得し、前記レジスタに対し前記取得されたビットパターンに基づく所定のプロセッサ命令を実行することにより、前記第１の部分配列および／または前記第２の部分配列を生成してもよい。
【００２０】
本発明の一形態では、情報処理装置は、第０段の配列に含まれる複数の要素に基づいて、前記複数の要素のそれぞれを構成する複数のビットのうち所定の範囲のビットを抽出し、前記抽出された各要素の複数のビットが並んでなる第０段の縮小配列を生成する縮小手段をさらに含み、前記振り分け手段は、前記第ｋ−１段の縮小配列に基づいて、前記第１の部分配列および前記第２の部分配列を生成し、前記生成された前記第１の部分配列および前記第２の部分配列が連結された第ｋ段の縮小配列を決定することにより第ｋ段の配列を決定してもよい。
【００２１】
本発明の一形態では、前記縮小手段は、第０段の配列に含まれる複数の要素に基づいて、前記複数の要素のそれぞれを構成する各要素の１番目からτ番目のビットからなる部分ビット列を抽出し、前記抽出された各要素の部分ビット列が順序を崩さずに並ぶ第０段の縮小配列を生成し、前記縮小手段は、第α×τ段（αは、１以上ｎ／τ未満の整数）の縮小配列に格納される要素の順序に基づいて前記第０段の配列に含まれる複数の要素を並び替え、前記並び替えられた複数の要素のα×τ＋１番目から（α＋１）×τ番目のビットからなる部分ビット列を抽出し、前記抽出された各要素の部分ビット列が順序を崩さずに並ぶ新たな第α×τ段の縮小配列を生成してもよい。
【００２２】
本発明の一形態では、第０段の配列に含まれる複数の要素に基づいて、前記複数の要素のそれぞれを構成する複数のビットのうち所定の範囲のビットを抽出し、前記抽出された各要素の複数のビットが並んでなる第０段の縮小配列を生成する縮小手段をさらに含み、前記振り分け手段は、前記第０段の縮小配列に基づいて、第１段の第１の部分配列および第２の部分配列を生成してもよい。
【００２３】
本発明の一形態では、前記縮小手段は、第０段の配列に含まれる複数の要素に基づいて、前記複数の要素のそれぞれを構成する各要素の１番目からτ番目のビットからなる部分ビット列を抽出し、前記抽出された各要素の部分ビット列が順序を崩さずに並ぶ第０段の縮小配列を生成し、前記縮小手段は、第α×τ段（αは、１以上ｎ／τ未満の整数）の第１の部分配列および第２の部分配列に格納される要素の順序に基づいて前記第０段の配列に含まれる複数の要素を並び替え、前記並び替えられた複数の要素のα×τ＋１番目から（α＋１）×τ番目のビットからなる部分ビット列を抽出することにより、新たな第α×τ段の第１の部分配列および第２の部分配列を生成してもよい。
【００２４】
本発明の一形態では、情報処理装置は、前記第ｑ段（ｑは０以上ｎ−１以下の整数）の配列に格納される各要素のｑ番目のビットが連続して並ぶ第ｑ段のパックデータを生成するパックデータ生成手段と、前記パックデータ生成手段により生成された第０段から第ｎ−１段のパックデータに基づいて、最大値、最小値、中央値、最頻値のうちいずれかを含む統計処理を実行する統計手段と、をさらに含んでもよい。
【００２５】
本発明の一形態では、情報処理装置は、第ｑ段（ｑは０以上ｎ−１以下の整数）のパックデータを生成するパックデータ生成手段と、前記パックデータ生成手段により生成された第０段から第ｎ−１段のパックデータに基づいて、最大値、最小値、中央値、最頻値のうちいずれかを含む統計処理を実行する統計手段と、をさらに含み、前記振り分け手段は、第ｑ段（ｑは０以上ｎ−１以下の整数）の第１の部分配列および第２の部分配列に基づいて第ｑ段の配列を決定し、前記パックデータ生成手段は、前記第ｑ段（ｑは０以上ｎ−１以下の整数）の配列に格納される各要素のｑ番目のビットが連続して並ぶ第ｑ段のパックデータを生成してもよい。
【００２６】
これらの発明によれば、ウェーブレット木およびウェーブレット行列を現実的かつ高速に生成することができる。
【図面の簡単な説明】
【００２７】
【図１】情報処理装置のハードウェア構成の一例を示す図である。
【図２】情報処理装置が実現する機能を示すブロック図である。
【図３】ウェーブレット行列の一例を示す図である。
【図４Ａ】ウェーブレット行列を説明する図である。
【図４Ｂ】ウェーブレット行列を説明する図である。
【図５】ウェーブレット行列を作成する処理を概略的に示すフローチャートである。
【図６】配列Ｘ０と縮小配列Ｌ０との関係を説明する図である。
【図７】ビットパックを生成する処理の一例を示すフローチャートである。
【図８】ビットパックを生成する処理を説明する図である。
【図９】振り分け部の処理の一例を示すフローチャートである。
【図１０】振り分け部における演算の一例を説明する図である。
【図１１】パラメータテーブルの一例を示す図である。
【図１２】振り分け部の処理の他の一例を示すフローチャートである。
【図１３】要素配置テーブルの一例を示す図である。
【図１４】配置パラメータを用いた演算の一例を説明する図である。
【図１５】振り分け部の処理の他の一例を示すフローチャートである。
【図１６】マスクを用いた演算の一例を説明する図である。
【図１７】ウェーブレット木の一例を示す図である。
【図１８】ウェーブレット木を作成する処理を概略的に示すフローチャートである。
【発明を実施するための形態】
【００２８】
以下では、本発明の実施形態について図面に基づいて説明する。出現する構成要素のうち同一機能を有するものには同じ符号を付し、その説明を省略する。
【００２９】
図１は、本発明の実施形態にかかる情報処理装置の一例を示す図である。本発明の実施形態にかかる情報処理装置は、プロセッサ１１、記憶部１２、通信部１３、入出力部１４を含む。この情報処理装置は、例えばパーソナルコンピュータや携帯情報端末（タブレット、電子書籍端末など）である。
【００３０】
プロセッサ１１は、記憶部１２に格納されているプログラムに従って動作する。またプロセッサ１１は通信部１３、入出力部１４を制御する。なお、上記プログラムは、インターネット等を介して提供されるものであってもよいし、フラッシュメモリやＤＶＤ−ＲＯＭ等のコンピュータで読み取り可能な記憶媒体に格納されて提供されるものであってもよい。
【００３１】
記憶部１２は、ＲＡＭやフラッシュメモリ等のメモリ素子やハードディスクドライブによって構成されている。記憶部１２は、上記プログラムを格納する。また、記憶部１２は、各部から入力される情報や演算結果を格納する。
【００３２】
通信部１３は、他の装置と通信する機能を実現するものであり、例えば有線ＬＡＮの集積回路やコネクタ端子、無線ＬＡＮの集積回路やアンテナなどにより構成されている。通信部１３は、プロセッサ１１の制御に基づいて、他の装置から受信した情報をプロセッサ１１や記憶部１２に入力し、他の装置に情報を送信する。
【００３３】
入出力部１４は、表示出力手段をコントロールするビデオコントローラや、入力デバイスからのデータを取得するコントローラなどにより構成される。入力デバイスとしては、キーボード、マウス、タッチパネルなどがある。入出力部１４は、プロセッサ１１の制御に基づいて、表示出力デバイスに表示データを出力し、入力デバイスをユーザが操作することにより入力されるデータを取得する。表示出力デバイスは例えば外部に接続されるディスプレイ装置や情報処理装置に内蔵されるディスプレイパネルである。
【００３４】
図２は、情報処理装置が実現する機能を示すブロック図である。情報処理システムは、機能的に、初期配列取得部５１、配列変換部５２、統計処理部５３を含む。また配列変換部５２は、機能的に、配列圧縮部５４、ビットパック生成部５５、振り分け部５６を含む。本実施形態では、初期配列取得部５１、配列変換部５２、統計処理部５３は、プロセッサ１１が記憶部１２に格納されるプログラムを実行し、通信部１３や入出力部１４を制御することで実現される。なお、統計処理部５３の処理が、他のコンピュータに含まれるプロセッサ１１等より実現されてもよい。
【００３５】
初期配列取得部５１は、プロセッサ１１および記憶部１２を中心として実現される。初期配列取得部５１は、複数の要素Ｅ（図３参照）からなる初期配列を記憶部１２などから取得する。複数の要素Ｅのそれぞれは、ｎビットで表現される要素値を含む。ｎは正の整数である。
【００３６】
配列変換部５２は、プロセッサ１１および記憶部１２を中心として実現される。初期配列Ｘ０のデータを、ウェーブレット木またはウェーブレット行列の形式のデータに変換する。配列圧縮部５４、ビットパック生成部５５および振り分け部５６については後述する。
【００３７】
統計処理部５３は、プロセッサ１１および記憶部１２を中心として実現される。統計処理部５３は、生成されたウェーブレット木またはウェーブレット行列の形式のデータを用いて、初期配列Ｘ０に含まれる複数の要素Ｅについて、最大値、最小値、中央値、最頻値のうちいずれかを算出する統計処理を実行する。また、統計処理部５３は、統計処理により算出された、最大値、最小値、中央値、最頻値のうちいずれかを表示出力手段や記憶部１２へ出力する。
【００３８】
次に、ウェーブレット行列について説明する。図３は、ウェーブレット行列の一例を示す図である。初期配列Ｘ０に含まれる要素Ｅがｎビットで表現される場合、ウェーブレット行列は、第０段から第ｎ−１段のビットパックＢ０〜Ｂｎ−１を含む。ｑが、０以上ｎ−１以下の整数であるとすると、第ｑ段のビットパックＢｑは、第ｑ段の配列Ｘｑに含まれる各要素Ｅのｑ＋１番目のビットが、要素Ｅが並ぶ順序に従って並ぶビット列である。ここで、初期配列Ｘ０は第０段の配列Ｘ０である。ｋが１以上ｎ−１以下の整数であるとすると、第ｋ段の配列Ｘｋは、第ｋ−１段の配列Ｘｋ−１に含まれる要素Ｅを、順序を崩さないように第１の部分配列Ｓ（０）および第２の部分配列Ｓ（１）に振り分け、振り分けられた第１の部分配列Ｓ（０）および第２の部分配列Ｓ（１）を連結することにより生成される。
【００３９】
図４Ａおよび４Ｂは、ウェーブレット行列を説明する図である。第ｋ段の配列Ｘｋから生成される第１の部分配列Ｓ（０）は、その配列Ｘｋに含まれる要素Ｅのうち、ｋ＋１番目のビットが０である要素Ｅが、その順序を崩さないように配置されたものであり、第ｋ段の配列Ｘｋから生成される第２の部分配列Ｓ（１）は、その配列Ｘｋに含まれる要素Ｅのうち、ｋ＋１番目のビットが１である要素Ｅが、その順序を崩さないように配置されたものである。ここで、順序を崩さないように配置されるとは、再配置された配列（ここでは第１の部分配列Ｓ（０）および第２の部分配列Ｓ（１）のそれぞれ）において、任意の要素Ｅの前（または後）にある要素Ｅが、もとの配列（ここでは第ｋ段の配列Ｘｋ）においても前（または後）にあることをいう。
【００４０】
図３，４Ａ，４Ｂの例では、説明の容易のため、各要素Ｅは４ビットで表現されている。第０段のビットパックＢ０は第０段の配列Ｘ０の１番目のビットが並んだものである。また図３に示されるように、第１段の配列Ｘ１は、前半にある第１の部分配列Ｓ（０）と後半にある第２の部分配列Ｓ（１）とを含む。図４Ａ，４Ｂに示されるように、第１の部分配列Ｓ（０）には、第０段の配列Ｘ０に含まれる要素Ｅのうち、１番目のビットが０である要素Ｅ（１番目，４番目，７番目，…の要素Ｅ）が配置され、第２の部分配列Ｓ（１）には、１番目のビットが１である要素Ｅ（２番目，３番目，５番目，…の要素Ｅ）が配置される。第２段以降も同様であり、第２段の配列Ｘ２は、前半にある第１の部分配列Ｓ（０）と後半にある第２の部分配列Ｓ（１）とを含み、第１の部分配列Ｓ（０）には、第１段の配列Ｘ１に含まれる要素Ｅのうち、２番目のビットが０である要素Ｅ（３番目，４番目，７番目，…の要素Ｅ）が配置されており、第２の部分配列Ｓ（１）には、２番目のビットが１である要素Ｅ（１番目，２番目，５番目，…の要素Ｅ）が配置されている。同様に第３段の配列Ｘ０も第１の部分配列Ｓ（０）と第２の部分配列Ｓ（１）とを含んでいる。第１段から第３段のビットパックＢ１〜Ｂ３は、第１段から第３段の配列Ｘ１〜Ｘ３のうち太字であらわされるビットが並べられたものである。第０段から第３段の配列Ｘ０〜Ｘ３は、ビットパックＢ０からＢ３の生成に必要なものであり、ウェーブレット木およびウェーブレット行列のデータとしては必ずしも必要ではない。
【００４１】
なお、第２段の第１の部分配列Ｓ（０）および第２の部分配列Ｓ（１）のそれぞれにおいて、先頭側には１番目のビットが０の要素Ｅが、終端側には１番目のビットが１の要素Ｅが配置されている。第３段の第１の部分配列Ｓ（０）および第２の部分配列Ｓ（１）のそれぞれにおいて、１，２番目のビットが０である要素Ｅと、１番目のビットが１で２番目のビットが０である要素Ｅと、１番目のビットが０で２番目のビットが１である要素Ｅと、１，２番目のビットが１である要素Ｅが順に並んでいる。
【００４２】
ウェーブレット行列およびウェーブレット木では、ビットパックＢ０〜Ｂｎ−１のすべてのビット数を加算すると、初期配列Ｘ０と同じビット数となる。一方で、ビットパックＢ０〜Ｂｎ−１を用いて最大値、最小値、中央値、最頻値の算出や、初期配列Ｘ０においてある範囲内にある要素Ｅのうち一番大きい値の要素Ｅの検索などが可能であり、またこれらの統計処理をする手法は公知である。ウェーブレット行列およびウェーブレット木をデータの圧縮に用いることも可能である。ウェーブレット行列およびウェーブレット木は、データ量をあまり増大させずに、統計処理や情報の圧縮を可能にするデータ形式である。
【００４３】
次に、初期配列Ｘ０をウェーブレット行列へ変換する処理について説明する。図５は、ウェーブレット行列を作成する処理を概略的に示すフローチャートである。以下ではこのフローチャートの記載に基づいて、情報処理装置が実現する各機能の処理の詳細について説明する。
【００４４】
はじめに、初期配列取得部５１は、記憶部１２から複数の要素Ｅが並んでなる第０段の配列Ｘ０を取得する（ステップＳ１０１）。第０段の配列Ｘ０が含む複数の要素Ｅは、それぞれｎビットの数値であるが、初期配列取得部５１は、例えば１６ビットで表現される文字（要素Ｅに相当）がならぶ文字列のデータを配列Ｘ０として取得してもよいし、複数のビットベクトル（要素Ｅに相当）が並ぶデータを配列Ｘ０として取得してもよい。
【００４５】
配列圧縮部５４は、初期配列Ｘ０に含まれる複数の要素Ｅのそれぞれについて、その要素Ｅを構成する複数のビットのうち所定の範囲のビットを抽出し、抽出された各要素Ｅのビットからなる、抽出された要素Ｒが並んでなる第０段の縮小配列Ｌ０を生成する。ここでは、配列圧縮部５４は、配列Ｘ０に含まれる複数の要素Ｅのそれぞれの最上位からτビットが抽出された要素Ｒである部分ビット列として抽出し、抽出された部分ビット列が並ぶ第０段の縮小配列Ｌ０を生成する（ステップＳ１０２）。τは定数であり、２以上ｎ以下のうちいずれかの整数である。
【００４６】
図６は、配列Ｘ０と縮小配列Ｌ０との関係を説明する図である。ここでは、要素Ｅのビット数であるｎが８であり、τが４である場合の図である。図６には説明の容易のため４つの要素Ｅが示されているが、実際には要素Ｅの数は大きくてもよい。図６に示されるように、縮小配列Ｌ０は、配列Ｘ０を構成する各要素Ｅの１番目のビットから４ビットからなる縮小された要素Ｒが、順序を崩さずに並ぶ配列である。縮小配列Ｌ０では、一つの要素Ｅに対応する縮小された要素Ｒのビット数はτである。縮小配列Ｌ０は、配列Ｘ０の代わりにビットパックＢ０の生成および以降の段の配列Ｘｋの決定などの処理に用いられる。縮小配列Ｌ０はデータ長が短いので、ＣＰＵキャッシュを生かすようτの値を調整することで処理速度を向上させることができる。
【００４７】
縮小配列Ｌ０が生成されると、配列変換部５２は変数ｉに初期値０を設定し、変数αに初期値１を設定する（ステップＳ１０３）。変数ｉは処理対象となる段の番号を示す。そして、ビットパック生成部５５は、第ｉ段の縮小配列Ｌｉから、第ｉ段のビットパックＢｉを生成する（ステップＳ１０４）。
【００４８】
図７は、ビットパックＢｉを生成する処理の一例を示すフローチャートである。また、図８は、ビットパックＢｉを生成する処理を説明する図である。はじめに、ビットパック生成部５５は変数ｊに初期値０を設定する（ステップＳ２０１）。
【００４９】
次にビットパック生成部５５は、第ｉ段の縮小配列Ｌｉのうち、（ｊ×ｍ＋１）番目の要素Ｒからｍ個の要素Ｒを、それぞれレジスタＸｄ内の複数のブロックにロードする（ステップＳ２０２）。ここで、レジスタＸｄはｍ個のブロックに論理的に分割されており（図８の(1）参照）、ブロックのそれぞれの長さはτビットである。ｍはレジスタ長（レジスタＸｄのビット数）をτで割った値の小数点以下を切り捨てた値である。
【００５０】
次にビットパック生成部５５は、要素Ｅのｉ＋１番目のビット（厳密にはレジスタＸｄ
に格納される各要素Ｒの対応するビット）が対応するブロック内の所定の位置にくるようにシフトする（ステップＳ２０３）。例えば、図８の例では、要素Ｅにおける１番目のビット（要素Ｒでも１番目のビット）が各ブロックの最下位のビットに来るように、ＣＰＵ命令により右に３ビットシフトさせる（図８の(2)参照）。シフト量は、τから、ｉ＋１をτで割った余りを引いた数である。
【００５１】
そしてビットパック生成部５５は、シフトされたレジスタＸｄの値と所定のマスクＮｂとの論理積により、各ブロックの所定の位置に配置されるビットが抽出されたビット列ＥｂをレジスタＸｄに生成する（ステップＳ２０４）。マスクＮｂは、各ブロックの所定の位置（図８の例では最下位）のビットに１が設定され、他のビットに０が設定されたレジスタ長のデータである。ビットが抽出されると、ビットパック生成部５５はレジスタＸｄにマジックナンバＮｍをかけ、レジスタＸｄに格納される複数の要素Ｒに対応する要素Ｅのｉ＋１番目のビットが連続して並ぶパックビット列Ｂｐを生成する（ステップＳ２０５）。図８の例では、生成されたデータの上位τビットがパックビット列Ｂｐであり、その他のビットは切り捨てられる。マジックナンバＮｍは、ｈ番目のブロックの下位からｈ番目のビットに１が設定され、ほかに０が設定されたレジスタ長のデータである。マジックナンバＮｍによる算出を可能にするには、ｍ≦τの条件を満たす必要がある。
【００５２】
そして、生成されたパックビット列Ｂｐを、第ｉ段のビットパックＢｉに追加する（ステップＳ２０６）。ビットパック生成部５５はｊに１を加算し、すべての要素Ｒに対して処理が行われたか判定する（ステップＳ２０８）。すべての要素Ｒに対して処理がされた場合には（ステップＳ２０８のＹ）処理を終了し、まだ処理されていない要素Ｒが存在する場合には（ステップＳ２０８のＮ）ステップＳ２０２からの処理を繰り返す。
【００５３】
なお、ステップＳ２０４，Ｓ２０５の代わりに、ビットパック生成部５５はレジスタＸｄのうちマスクＮｂに相当するビットを抽出し連続して並べるＣＰＵ命令（ｐｅｘｔ）を用いてパックビット列Ｂｐを生成してもよい。
【００５４】
ビットパックＢｉが生成されると、振り分け部５６は、第ｉ段の縮小配列Ｌｉから第ｉ＋１段の縮小配列Ｌｉ＋１を生成する（ステップＳ１０５）。この処理は、図４Ａ，４Ｂに示されるデータ操作を行う処理であるが、処理の詳細については後述する。
【００５５】
縮小配列Ｌｉ＋１が生成されると、配列変換部５２は変数ｉに１を加算する（ステップＳ１０６）。そしてｉがατと等しくない場合には（ステップＳ１０７のＮ）、ステップＳ１０４からの処理を繰り返す。一方、ｉがατと等しい場合には（ステップＳ１０７のＹ）、ｉがｎと等しいか判定する（ステップＳ１０８）。ｉがｎと等しい場合は（ステップＳ１０８のＹ）、すべての段について処理がされているので、配列変換部５２は生成された全段のビットパックＢ０からＢｎ−１をウェーブレット行列として記憶部１２などに出力し（ステップＳ１１１）、処理を終了する。
【００５６】
ｉがｎと等しくない場合は（ステップＳ１０８のＮ）、配列圧縮部５４は、複数の要素Ｅのそれぞれのατ＋１番目のビットからτビットを部分ビット列として抽出し、抽出された部分ビット列（新たな要素Ｒ）が元の縮小配列Ｌｉにおける要素Ｒの並びにしたがって順に配置される新たな第ｉ段の縮小配列Ｌｉを生成する（ステップＳ１０８）。新たな縮小配列Ｌｉの要素Ｒにおける１からτ番目のビットは、それぞれ対応する要素Ｅにおけるα×τ＋１からα×（τ＋１）ビットに対応する。
【００５７】
新たな縮小配列Ｌｉが生成されると、配列変換部５２は変数αを１増やし（ステップＳ１１０）、ステップＳ１０４からの処理を繰り返す。
【００５８】
ウェーブレット行列やウェーブレット木において、振り分け部５６のステップＳ１０５の処理によるプロセッサ１１の処理負荷が大きい。そこで、この処理負荷を減らし、処理を高速化する手法について説明する。
【００５９】
図９は、振り分け部５６の処理の一例を示すフローチャートであり、ステップＳ１０５の処理をより詳細に説明する図である。図１０は、振り分け部５６における演算の一例を説明する図である。はじめに、振り分け部５６は変数ｊに初期値０を設定する（ステップＳ３０１）。
【００６０】
次に振り分け部５６は、第ｉ段の縮小配列Ｌｉのうち、（ｊ×ｍ＋１）番目の要素Ｒからｍ個の要素Ｒを、それぞれレジスタＸｄ内の複数のブロックにロードする（ステップＳ３０２）。この処理は、ビットパック生成部５５におけるステップＳ２０２の処理と同様であるので詳細の説明は省略する。
【００６１】
要素ＲがレジスタＸｄにロードされると、振り分け部５６はレジスタＸｄに格納される各要素Ｒのシフト量を示すシフトパラメータＰｓを取得する（ステップＳ３０３）。また、振り分け部５６はレジスタＸｄに格納される各要素Ｒのうち、対応する要素Ｅにおけるｉ＋１番目のビット（つまりそのビットに対応する要素Ｒのビット）が１である要素Ｒを抽出するマスクＭｓと、対応する要素Ｅにおけるｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）が０である要素Ｒを抽出するマスクＭｎとを取得する（ステップＳ３０４）。
【００６２】
ステップＳ３０３およびステップＳ３０４の処理は、より具体的には、レジスタＸｄに格納される各要素Ｒのうち、対応する要素Ｅにおけるｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）が１である要素Ｒが抽出されたビット列Ｅｂを取得する処理Ａ１と、ビット列Ｅｂに基づいてシフトパラメータＰｓを生成する処理Ａ２と、レジスタＸｄに格納される要素Ｒのデータおよびビット列Ｅｂに基づいてマスクＭｓやマスクＭｎを取得する処理Ａ３とを含む。
【００６３】
処理Ａ１はビットパック生成部５５のステップＳ２０３，Ｓ２０４の処理に類似する。具体的には、処理Ａ１では、振り分け部５６はレジスタＸｄに格納される各要素Ｒのビットであって、対応する要素Ｅのｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）が対応するブロック内の所定の位置（図１０の例ではブロックの最下位のビット位置）にくるようにシフトし、シフトされたデータと所定のマスクＮｂとの論理積により、各ブロックの所定の位置に配置されるビットが抽出されたビット列Ｅｂを生成する。ビット列Ｅｂは、ステップＳ２０３，Ｓ２０４で生成されたものを他のレジスタ等に保存しておくことにより取得してもよい。
【００６４】
処理Ａ２では、振り分け部５６はビット列ＥｂとビットパターンＮ１とを乗算することによりシフトパラメータＰｓを取得する。ビットパターンＮ１では、各ブロックの最下位ビットに１が設定され、他のビットに０が設定される。図１０の例では、マスクＮｂとビットパターンＮ１とは同じである。シフトパラメータＰｓの各ブロックの部分ビット列を値とみなすと、各ブロックの値は対応する要素Ｅのｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）が１である要素Ｒがそのブロックおよびその下位のブロックにいくつあるかを示している。
【００６５】
処理Ａ３では、振り分け部５６はビットパターンＮ２からビット列Ｅｂを減算し、減算されたデータとビットパターンＮ３との排他的論理和を算出することによりマスクＭｓを取得する。ビットパターンＮ２，Ｎ３では、各ブロックの最上位ビットに１が設定され、他のビットに０が設定される。図１０には図示されていないが、振り分け部５６はマスクＭｓのＮＯＴ演算により、マスクＭｎを取得する。
【００６６】
ステップＳ３０４，Ｓ３０５のあとに、振り分け部５６は、マスクＭｓ，Ｍｎと、レジスタＸｄに格納される各要素Ｒとに基づいて、ｉ＋１番目のビットが１である要素と、ｉ＋１番目のビットが０である要素とを抽出する（ステップＳ３０５）。振り分け部５６は、より具体的には、マスクＭｓと複数の要素Ｒが格納されるレジスタＸｄとの論理積を算出することによりｉ＋１番目のビットが１である要素が抽出されたビット列Ｅｓを生成し、マスクＭｎと複数の要素Ｒが格納されるレジスタＸｄとの論理積を算出することによりｉ＋１番目のビットが０である要素が抽出されたビット列Ｅｎを生成する。
【００６７】
ビット列Ｅｓ，Ｅｎが生成されると、振り分け部５６は、ビット列Ｅｓ，Ｅｎと、シフトパラメータＰｓとに基づいて、抽出された要素Ｒが連続して並ぶ追加データＤａ（０），Ｄａ（１）を生成する（ステップＳ３０６）。より具体的には、振り分け部５６は、ビット列Ｅｓに含まれる各ブロックの要素Ｒに対し、シフトパラメータＰｓの各ブロックの値に応じたビット数だけシフトさせる演算を行う。シフト量そのものは、下位からｃ番目（ｃは１以上ｍ以下の整数）のブロックにｃ−１が設定されたデータに対してシフトパラメータＰｓを減算することによりシフトデータＳｈとして求められる。振り分け部５６は、ビット列ＥｓとシフトデータＳｈとに対してモノトーンルーティング（MONOTONE ROUTING）として知られる複数のビット演算などを行うことにより追加データＤａ（０）を算出し、ビット列ＥｎとシフトデータＳｈとに対して同様のビット演算などを行うことにより追加データＤａ（１）を算出する。
【００６８】
モノトーンルーティングは、シフトデータＳｈに含まれる各ブロックのうち最下位ビットが１であるブロックに対応するビット列Ｅｓ（およびビット列Ｅｎ）のブロックをブロック長だけシフトさせる演算と、下位からｄ番目（ｄは２以上τ以下の整数）のビットが１であるブロックに対応するビット列Ｅｓ（およびビット列Ｅｎ）のブロックをブロック長の２の（ｄ−１）乗倍だけシフトさせる演算と、を含む。モノトーンルーティングの処理は、「F. Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Arrays ・ Trees ・ Hypercubes, Section 4.3.3.」および「Yusaku Kaneta, Hiroki Arimura, Rajeev Raman. Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism, Section 5.」に記載されるように公知である。
【００６９】
追加データＤａ（０），Ｄａ（１）が算出されると、振り分け部５６は、算出された追加データＤａ（０），Ｄａ（１）を、それぞれ第１の部分配列Ｓ（０）、第２の部分配列Ｓ（１）に追加する（ステップＳ３０７）。そして、縮小配列Ｌｉに含まれるすべての要素Ｒについて処理が行われていない場合は（ステップＳ３０９のＮ）、ステップＳ３０２からの処理を繰り返す。
【００７０】
一方、縮小配列Ｌｉに含まれるすべての要素について処理が行われた場合には（ステップＳ３０９のＹ）、振り分け部５６は、第１の部分配列Ｓ（０）、第２の部分配列Ｓ（１）から第ｉ＋１段の縮小配列Ｌｉ＋１を決定する（ステップＳ３１０）。より具体的には、振り分け部５６は、第１の部分配列Ｓ（０）および第２の部分配列Ｓ（１）を連結することにより第ｉ＋１段の縮小配列Ｌｉ＋１を決定する。なお、必ずしも第１の部分配列Ｓ（０）および第２の部分配列Ｓ（１）に含まれる要素Ｒのそれぞれが記憶部１２の連続する領域に配置されなくてもよい。ここで、前段の縮小配列Ｌｉに格納されたすべての要素Ｒのビットであって対応する要素Ｅのｉ＋１番目のビットが０である場合には、第２の部分配列Ｓ（０）は空配列であり、縮小配列Ｌｉに格納されたすべての要素Ｒのビットであって対応する要素Ｅのｉ＋１番目のビットが１である場合には、第２の部分配列Ｓ（１）は空配列となる。
【００７１】
追加データＤａ（０），Ｄａ（１）を算出する処理は、プロセッサ１１がビット演算や加算、乗算などを用い、複数の要素Ｒを一括で計算しつつ条件分岐を用いないプログラムを実行することで実現される。これにより、条件分岐に伴うプロセッサ１１のパイプライン制御に伴う速度低下を防ぎ、またこれらの処理を並列で実行することが容易になる。また、大規模なキーをもつルックアップテーブルを設ける必要がないので、ＣＰＵキャッシュを有効に利用できる。
【００７２】
なお、これまでに説明された処理について、要素Ｒの代わりに要素Ｅを用い、配列Ｘ０に基づいて縮小配列Ｌｉを生成する処理を行わなくてもよい。この場合、τは要素Ｅのビット長と同じである。
【００７３】
ここで、振り分け部５６は、パックビット列Ｂｐに基づいて、シフトパラメータＰｓおよびマスクＭｓをルックアップテーブルの一種であるパラメータテーブルから取得してもよい。図１１は、パラメータテーブルの一例を示す図である。図１１に示されるように、パックビット列Ｂｐがとりうる複数の値のそれぞれに対応するシフトパラメータＰｓおよびマスクＭｓが記憶部１２に格納されている。
【００７４】
そして、振り分け部５６は、ステップＳ２０３，Ｓ２０４で生成されたパックビット列Ｂｐに関連付けられたシフトパラメータＰｓおよびマスクＭｓを取得し、マスクＭｓにＮＯＴ演算をすることによりマスクＭｎも取得する。マスクＭｎはパラメータテーブルから取得されてもよい。振り分け部５６は要素Ｒが格納されるレジスタＸｄとマスクＭｓ，Ｍｎとに基づいてビット列Ｅｓ，Ｅｎを取得し、これらに対してモノトーンルーティングの処理をすることにより追加データＤａ（０），Ｄａ（１）を算出する。なお、パラメータテーブルに格納されるシフトパラメータＰｓは図１０に示されるものと異なっていてもよく、各ブロックのシフト量が各ブロックに配置されるビットパターンであってもよい。
【００７５】
パックビット列Ｂｐのビット長は、レジスタＸｄに格納される要素Ｒ（ブロックに対応する）の数に等しい。したがって、パラメータテーブルはレジスタ長が１６ビットでτが４の場合は１６種類のパックビット列Ｂｐについて格納すればよく、レジスタ長が６４ビットでτが８の場合でも２５６種類について格納すればよい。パラメータテーブルの大きさが限られるので、現実的かつ高速に処理することができる。
【００７６】
振り分け部５６の処理は、最新のＣＰＵに装備される特殊なＣＰＵ命令を用いて実行されてもよい。図１２は、振り分け部５６の処理の他の一例を示すフローチャートであり、ステップＳ１０５の処理をより詳細に説明する図である。ここでは、レジスタ長が６４ビット、τが８、レジスタＸｄに格納される要素Ｒの数が８であるとする。なお、各要素Ｅのビット数が８である場合には、要素Ｒの代わりに要素Ｅを用い、配列Ｘ０に基づいて縮小配列Ｌｉを生成する処理を行わなくてもよい。
【００７７】
はじめに、振り分け部５６は変数ｊに初期値０を設定する（ステップＳ３４１）。次に振り分け部５６は、第ｉ段の縮小配列Ｌｉのうち、（ｊ×ｍ＋１）番目の要素Ｒからｍ個の要素Ｒについてのパックビット列Ｂｐを取得する（ステップＳ３４２）。具体的には、振り分け部５６はビットパック生成部５５が生成したパックビット列Ｂｐを取得してもよいし、ビットパック生成部５５と同様の処理を実行してパックビット列Ｂｐを算出してもよい。
【００７８】
パックビット列Ｂｐが取得されると、振り分け部５６は、パックビット列Ｂｐに基づいて、ルックアップテーブルの一種である配置テーブルから、レジスタＸｄに格納される各要素Ｒの変換後の配置を示す配置パラメータＰａ０，Ｐａ１を取得する（ステップＳ３４３）。図１３は、配置テーブルの一例を示す図である。図１３に示されるように、パックビット列Ｂｐがとりうる複数の値のそれぞれに対応する配置パラメータＰａ０，Ｐａ１が記憶部１２に格納されている。配置パラメータＰａ０，Ｐａ１は、処理後の各ブロックに対する、それぞれ対応する要素Ｅのｉ番目のビット（そのビットに対応する要素Ｒのビット）が０の要素Ｒ、そのビットが１の要素Ｒが存在する位置を示す数値（図１３の例では８ビットで表される数値）が並ぶデータである。
【００７９】
次に振り分け部５６は、第ｉ段の縮小配列Ｌｉのうち、（ｊ×ｍ＋１）番目の要素Ｒからｍ個の要素Ｒを、それぞれレジスタＸｄ内の複数のブロックにロードする（ステップＳ３４４）。この処理は、ビットパック生成部５５におけるステップＳ２０２の処理と同様であるので詳細の説明は省略する。
【００８０】
そして、振り分け部５６は、ＰＳＨＵＦＢ命令を実行することにより、配置パラメータＰａ０，Ｐａ１に応じてレジスタＸｄに格納される要素Ｒを再配置し、それぞれ追加データＤａ（０），Ｄａ（１）を生成する（ステップＳ３４５）。
【００８１】
図１４は、配置パラメータＰａ０，Ｐａ１を用いたＰＳＨＵＦＢ命令の演算の一例を説明する図である。図１３，１４の例では、配置パラメータＰａ０またはＰａ１の各ブロックに配置される数値は、そのブロックに再配置される要素Ｒが下位から何番目の位置に配置されるかを示している。ただし、１２８の数値はそのブロックに何も配置されないことを示している。振り分け部５６は、ＰＳＨＵＦＢ命令を実行することにより、配置パラメータＰａ０を用いて、対応する要素Ｅのｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）が０である要素Ｒが連続して配置された追加データＤａ（０）を生成し、またＰＳＨＵＦＢ命令を実行することにより、配置パラメータＰａ１を用いて、対応する要素Ｅのｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）が１である要素Ｒが連続して配置された追加データＤａ（１）を生成する。
【００８２】
なお、ステップＳ３４７からステップＳ３５０の処理は、図９におけるステップＳ３０７からステップＳ３１０の処理と同様であるので説明を省略する。図１２から１４の例においても、配置テーブルの大きさは抑えられ、かつ少ないＣＰＵ命令で振り分け部５６の処理を行うことができ、現実的かつ高速に処理を実行することができる。
【００８３】
振り分け部５６の処理は、最新のＣＰＵに装備される他の特殊なＣＰＵ命令を用いて実行されてもよい。図１５は、振り分け部５６の処理の他の一例を示すフローチャートであり、ステップＳ１０５の処理をより詳細に説明する図である。ここでは、レジスタ長が１６ビット、τが４、レジスタＸｄに格納される要素Ｒの数ｍが４であるとして説明する。
【００８４】
はじめに、振り分け部５６は変数ｊに初期値０を設定する（ステップＳ３６１）。次に振り分け部５６は、第ｉ段の縮小配列Ｌｉのうち、（ｊ×ｍ＋１）番目の要素Ｒからｍ個の要素Ｒについてのパックビット列Ｂｐを取得する（ステップＳ３６２）。
【００８５】
パックビット列Ｂｐが取得されると、振り分け部５６は、パックビット列Ｂｐと他の配置テーブルとに基づいて、マスクＭｓ，Ｍｎを取得する（ステップＳ３６３）。マスクＭｓ，Ｍｎは、図９から１１の例で説明されるものと実質的に同じである。他の配置テーブルには、パックビット列Ｂｐが取りうる複数の値にそれぞれ関連付けられるマスクＭｓが格納されている。配置テーブルはパックビット列Ｂｐが取りうる複数の値にそれぞれ関連付けられるマスクＭｎを格納してもよい。振り分け部５６は、取得されたパックビット列Ｂｐに関連付けて記憶されたマスクＭｓを取得する。また、振り分け部５６は、マスクＭｓにＮＯＴ演算を行うことで、マスクＭｎを取得する。振り分け部５６は、マスクＭｎを配置テーブルから取得してもよい。マスクＭｓ，Ｍｎは、それぞれ、レジスタＸｄにおける、第１の部分配列Ｓ（０）および第２の部分配列Ｓ（１）に配置される要素のビット位置を示すビットパターンである。
【００８６】
次に振り分け部５６は、第ｉ段の縮小配列Ｌｉのうち、（ｊ×ｍ＋１）番目の要素Ｒからｍ個の要素Ｒを、それぞれレジスタＸｄ内の複数のブロックにロードする（ステップＳ３４４）。この処理は、ビットパック生成部５５におけるステップＳ２０２の処理と同様であるので詳細の説明は省略する。
【００８７】
そして、振り分け部５６は、ＰＥＸＴ命令を実行することにより、マスクＭｓ，Ｍｎに応じてレジスタＸｄに格納される要素Ｒを再配置し、それぞれ追加データＤａ（０），Ｄａ（１）を生成する（ステップＳ３６５）。
【００８８】
図１６は、マスクＭｓ，Ｍｎを用いたＰＥＸＴ命令の演算の一例を説明する図である。振り分け部５６は、ＰＥＸＴ命令を実行することにより、マスクＭｓのビットが１となっている位置にある要素Ｒを抽出し、抽出された要素Ｒが連続して並ぶように再配置することで、追加データＤａ（０）を算出する。また振り分け部５６は、ＰＥＸＴ命令を実行することにより、マスクＭｎのビットが１となっている位置にある要素Ｒを抽出し、抽出された要素Ｒが連続して並ぶように再配置することで、追加データＤａ（１）を算出する。これにより、振り分け部５６は、レジスタＸｄに格納される要素Ｒのうち、対応する要素Ｅのｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）が０である要素Ｒが連続して配置された追加データＤａ（０）と、対応する要素Ｅのｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）が１である要素Ｒが連続して配置された追加データＤａ（１）とを生成する。
【００８９】
なお、ステップＳ３６７からステップＳ３７０の処理は、図９におけるステップＳ３０７からステップＳ３１０の処理と同様であるので説明を省略する。図１２から１４の例においても、配置テーブルの大きさは抑えられ、かつ少ないＣＰＵ命令で振り分け部５６の処理を行うことができ、現実的かつ高速に処理を実行することができる。
【００９０】
ここまでは、ウェーブレット行列における処理について説明してきたが、ウェーブレット木においても同様の処理により現実的かつ高速にデータを変換することができる。以下では初期配列Ｘ０をウェーブレット木のデータ形式に変換する処理について、主にウェーブレット行列との相違点を説明する。
【００９１】
図１７は、ウェーブレット木の一例を示す図であり、ウェーブレット行列を説明する図３に対応する図である。初期配列Ｘ０に含まれる要素Ｅがｎビットで表現される場合、ウェーブレット木は、第０段から第ｎ−１段のビットパックＢ０〜Ｂｎ−１を含む。ｑが、０以上ｎ−１以下の整数であるとすると、第ｑ段のビットパックＢｑは、第ｑ段の配列Ｘｑに含まれる各要素Ｅのｑ＋１番目のビットが、要素Ｅが並ぶ順序に従って並ぶビット列である。また、第１段の部分配列Ｓ１（０）は、第０段の配列Ｘ０に含まれる要素Ｅのうち、１番目のビットが０である要素Ｅが、その順序を崩さないように配置されたものであり、第１段の部分配列Ｓ（１）は、第０段の配列Ｘ０に含まれる要素Ｅのうち、１番目のビットが１である要素Ｅが、その順序を崩さないように配置されたものである。配列Ｘ１は第１段の部分配列Ｓ（０），Ｓ（１）が連結されたものである。
【００９２】
また、ｋが２以上ｎ−１以下の整数であり、ｒが０以上２の（ｋ−１）乗未満の整数であるとすると、第ｋ段の部分配列Ｓｋ（２ｒ）は、第ｋ−１段の部分配列Ｓｋ−１（ｒ）に含まれる要素Ｅのうち、ｋ番目のビットが０である要素Ｅが、その順序を崩さないように配置されたものである。また第ｋ段の部分配列Ｓ（２ｒ＋１）は、第ｋ−１段の部分配列Ｓｋ−１（ｒ）に含まれる要素Ｅのうち、ｋ番目のビットが１である要素Ｅが、その順序を崩さないように配置されたものである。部分配列Ｓｋ（２ｒ）は第１の部分配列Ｓ（０）に対応し、部分配列Ｓｋ（２ｒ＋１）は第２の部分配列Ｓ（１）に対応する。配列Ｘｋは、第ｋ段のすべての部分配列Ｓｋが連結されたものである。ウェーブレット木では、部分配列Ｓのそれぞれについて振り分けが行われるため、図３の例とは、第２段の配列Ｘ２以降において要素Ｅの並びが異なる。
【００９３】
図１８は、ウェーブレット木を作成する処理を概略的に示すフローチャートであり、図５に対応する図である。以下では主に図５の例との相違点について説明する。
【００９４】
はじめに、初期配列取得部５１は、記憶部１２から複数の要素Ｅが並んでなる第０段の配列Ｘ０を取得する（ステップＳ１５１）。次に、配列圧縮部５４は、配列Ｘ０に含まれる複数の要素Ｅのそれぞれの最上位からτビットを縮小された要素Ｒである部分ビット列として抽出し、抽出された部分ビット列が並ぶ第０段の縮小配列Ｌ０を生成する（ステップＳ１５２）。また配列変換部５２は変数ｉに初期値０を設定し、変数αに初期値１を設定する（ステップＳ１５３）。
【００９５】
また、第０段の部分配列Ｓ０（０）として、縮小配列Ｌ０を設定する（ステップＳ１５４）。これは、第１段の部分配列Ｓ１（０），Ｓ１（１）を生成する処理を第２段以降の処理と共通にするための動作であり、この処理の代わりに、第１段の部分配列Ｓ１（０），Ｓ１（１）を生成するプログラムを実行してもよい。
【００９６】
そして、ビットパック生成部５５は、第ｉ段の部分配列Ｓｉ（ｐ）が連結された縮小配列Ｌｉから、第ｉ段のビットパックＢｉを生成する（ステップＳ１５５）。ここで、ｐは０以上２のｉ乗未満の整数である。この処理は、ステップＳ１０４と同様であるので詳細の説明を省略する。
【００９７】
ビットパックＢｉが生成されると、振り分け部５６は、第ｉ段の部分配列Ｓｉ（ｐ）から第ｉ＋１段の部分配列Ｓｉ＋１（２ｐ），Ｓｉ＋１（２ｐ＋１）を生成する（ステップＳ１５６）。この処理の詳細は、図９，１２，１５に示されるような処理に対し、主に、処理の対象が縮小配列Ｌｉから部分配列Ｓｉ（ｐ）のそれぞれになり、生成される第１の部分配列Ｓ（０）、第２の部分配列Ｓ（１）がそれぞれ部分配列Ｓｉ＋１（２ｐ），Ｓｉ＋１（２ｐ＋１）になった点が異なるだけであるので説明を省略する。なお、複数の部分配列Ｓｉ（ｐ）が連続するメモリ領域に配置される場合には、振り分け部５６は、処理のためにレジスタＸｄに要素Ｒを格納する際に、処理対象となる部分配列Ｓｉと異なる部分配列ＳｉのデータがレジスタＸｄに格納されないように、マスクなどの処理を行う。
【００９８】
ここで、パックビット列Ｂｐにより、部分配列Ｓｉに含まれる１または複数の要素Ｒのビットであって、対応する複数の要素Ｅのｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）のすべてが０であるとわかる場合には、振り分け部５６は、単に部分配列Ｓｉ＋１（２ｐ）として部分配列Ｓｉ（ｐ）を設定し、部分配列Ｓｉ（２ｐ＋１）に空配列を設定してもよい。またパックビット列Ｂｐにより、部分配列Ｓｉに含まれる１または複数の要素Ｒのビットであって、対応する要素Ｅのｉ＋１番目のビット（そのビットに対応する要素Ｒのビット）のすべてが１であるとわかる場合には、振り分け部５６は、単に部分配列Ｓｉ＋１（２ｐ＋１）として部分配列Ｓｉ（ｐ）を設定し、部分配列Ｓｉ（２ｐ）に空配列を設定してもよい。
【００９９】
部分配列Ｓｉ＋１（２ｐ），Ｓｉ＋１（２ｐ＋１）が生成されると、配列変換部５２は変数ｉに１を加算する（ステップＳ１５７）。そしてｉがατと等しくない場合には（ステップＳ１５８のＮ）、ステップＳ１５５からの処理を繰り返す。一方、ｉがατと等しい場合には（ステップＳ１５８のＹ）、ｉがｎと等しいか判定する（ステップＳ１５９）。ｉがｎと等しい場合は（ステップＳ１５９のＹ）、すべての段について処理がされているので、配列変換部５２は生成された全段のビットパックＢ０からＢｎ−１をウェーブレット木として記憶部１２などに出力し（ステップＳ１６２）、処理を終了する。
【０１００】
ｉがｎと等しくない場合は（ステップＳ１５９のＮ）、配列圧縮部５４は、複数の要素Ｅのそれぞれのατ＋１番目のビットからτビットを部分ビット列として抽出し、抽出された部分ビット列（新たな要素Ｒ）が元の部分配列Ｓｉ（ｐ）における要素Ｒの並びにしたがって順に配置される新たな第ｉ段の部分配列Ｓｉ（ｐ）を生成する（ステップＳ１６０）。そして、配列変換部５２は変数αを１増やし（ステップＳ１６１）、ステップＳ１５５からの処理を繰り返す。
【０１０１】
ウェーブレット木においても、複数の要素Ｒを一括で計算しつつ条件分岐を用いないプログラムを実行することで実現される。これにより、条件分岐に伴うプロセッサ１１のパイプライン制御に伴う速度低下を防ぎ、またこれらの処理を並列で実行することが容易になる。
【符号の説明】
【０１０２】
１１  プロセッサ、１２  記憶部、１３  通信部、１４  入出力部、５１  初期配列取得部、５２  配列変換部、５３  統計処理部、５４  配列圧縮部、５５  ビットパック生成部、５６  振り分け部、Ｂ０，Ｂ１，Ｂ２，Ｂ３，Ｂｉ，Ｂｑ  ビットパック、Ｘ０，Ｘ１，Ｘ２，Ｘ３，Ｘｋ，Ｘｑ  配列、Ｌ０，Ｌ１，Ｌｉ  縮小配列、Ｓ  部分配列、Ｅ，Ｒ  要素、Ｂｐ  パックビット列、Ｄａ  追加データ、Ｅｂ，Ｅｓ，Ｅｎ  ビット列、Ｍｓ，Ｍｎ，Ｎｂ  マスク、Ｎ１，Ｎ２，Ｎ３  ビットパターン、Ｎｍ  マジックナンバ、Ｐａ０，Ｐａ１  配置パラメータ、Ｐｓ  シフトパラメータ、Ｘｄ  レジスタ。
【図１】
2020060844.tif 000003
【図２】
2020060844.tif 000004
【図３】
2020060844.tif 000005
【図４Ａ】
2020060844.tif 000006
【図４Ｂ】
2020060844.tif 000007
【図５】
2020060844.tif 000008
【図６】
2020060844.tif 000009
【図７】
2020060844.tif 000010
【図８】
2020060844.tif 000011
【図９】
2020060844.tif 000012
【図１０】
2020060844.tif 000013
【図１１】
2020060844.tif 000014
【図１２】
2020060844.tif 000015
【図１３】
2020060844.tif 000016
【図１４】
2020060844.tif 000017
【図１５】
2020060844.tif 000018
【図１６】
2020060844.tif 000019
【図１７】
2020060844.tif 000020
【図１８】
2020060844.tif 000021