JP7264240B2

JP7264240B2 - 順序同型照合装置、順序同型照合方法、及び、プログラム

Info

Publication number: JP7264240B2
Application number: JP2021514779A
Authority: JP
Inventors: 耀一佐々木; 志穂杉本
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2019-04-19
Filing date: 2019-04-19
Publication date: 2023-04-25
Anticipated expiration: 2039-04-19
Also published as: US20220179915A1; JPWO2020213165A1; WO2020213165A1

Description

本発明は順序同型照合装置、順序同型照合方法、及び、プログラムが格納されたコンピュータ可読媒体に関し、特に、文字列の並び順のうち並んだ値の大小関係の順序が合致するか否かを特定する順序同型照合問題を順序同型照合装置、順序同型照合方法、及び、プログラムが格納されたコンピュータ可読媒体に関する。

近年、地図データ、画像データ、購買履歴等のＰＯＳデータ等のビックデータに対する処理に対する要求が大きくなってきている。このようなビックデータに対する処理では、データの中から探し出したい特徴を抽出することが行われる。このような、データの特徴を見つけるマイニング手法が多く提案されている。このマイニング手法では、パターンの完全一致箇所を特定する照合問題（Pattern Matching, PM）と、パターン中の文字列の大小関係の並び順が一致する箇所を特定する順序同型照合問題（Order Preserving Pattern Matching, OPPM）とに分類することができる。

一次元データに対する順序同型照合問題の解決手法が例えば非特許文献１、２に開示されている。また、二次元データに対する照合問題の解決手法が例えば、非特許文献３、４に開示されている。

Kim, J., Eades, P., Fleischer, R., Hong, S., Iliopoulos, C.SW., Park, K M. Kubica, T. Kulczynski, J. Radoszewski, W. Rytter, and T. Walen.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett., 113(12):430－433, 2013. T.P.Baker,: A technique for extending rapid exact-match string-matching to arrays of more tha none dimensions, SIAM J.Comput. 7, 1978. R.S.Bird,: Two-dimensional pattern-matching, Info. Proc. Lett. 6, 1977

しかしながら、上記の提案手法では、二次元データに対する順序同型照合問題を解決することが出来ない問題がある。

本発明にかかる順序同型照合装置の一態様は、二次元で配置されたテキストデータにより構成される検索パターンを、一次元で前記テキストデータが配置される照合パターンに変換するパターン変換部と、前記照合パターンについて、前記照合パターンと順序同型となる検索対象パターンを特定する索引を索引情報として生成する文字列照合索引作成部と、二次元に配置されたテキストデータにより構成され、前記検索パターンよりも大きな配列を有する探索対象二次元パターンに対して、前記索引情報を適用して、前記探索対象二次元パターンにおいて前記照合パターンに一致する箇所に所定のＩＤ番号を付す照合部と、前記照合部において前記所定のＩＤ番号が付された箇所を照合位置として出力する出力部と、を有する。

本発明にかかる順序同型照合方法の一態様は、データベースに格納され、かつ、二次元に配置されたテキストデータにより構成された探索対象二次元パターンについて、二次元で配置されたテキストデータにより構成される検索パターンに合致する順序同型パターンをコンピュータを用いて探索する順序同型照合方法であって、前記検索パターンを、一次元で前記テキストデータが配置される照合パターンに変換し、前記照合パターンについて、前記照合パターンと順序同型となる検索対象パターンを特定する索引を索引情報として生成し、前記探索対象二次元パターンに対して、前記索引情報を適用して、前記探索対象二次元パターンにおいて前記照合パターンに一致する箇所に所定のＩＤ番号を付し、前記所定のＩＤ番号が付された箇所を照合位置として出力する。

本発明にかかるコンピュータ可読媒体の一態様は、データベースに格納された二次元に配置されたテキストデータにより構成された探索対象二次元パターンについて、二次元で配置されたテキストデータにより構成される検索パターンに合致する順序同型パターンを探索する順序同型照合処理を、コンピュータに実行させる順序同型照合プログラムが格納されたコンピュータ可読媒体であって、前記順序同型照合プログラムは、二次元で配置されたテキストデータにより構成される検索パターンを、一次元で前記テキストデータが配置される照合パターンに変換するパターン変換処理と、前記照合パターンについて、前記照合パターンと順序同型となる検索対象パターンを特定する索引を索引情報として生成する文字列照合索引作成処理と、二次元に配置されたテキストデータにより構成され、前記検索パターンよりも大きな配列を有する探索対象二次元パターンに対して、前記索引情報を適用して、前記探索対象二次元パターンにおいて前記照合パターンに一致する箇所に所定のＩＤ番号を付す照合処理と、前記照合処理において前記所定のＩＤ番号が付された箇所を照合位置として出力する出力処理と、を前記コンピュータに実行させる。

本発明にかかる順序同型照合装置、順序同型照合方法、及び、プログラムが格納されたコンピュータ可読媒体によれば、二次元データに対する順序同型照合問題を解決することができる。

二次元データに対する順序同型照合問題に関する課題を説明する図である。実施の形態１にかかる順序同型照合装置の構成を説明するブロック図である。実施の形態１にかかる順序同型照合装置のパターン変換部及び文字列照合索引作成部の動作を概略的に説明する図である。実施の形態１にかかる順序同型照合装置のパターン変換部及び文字列照合索引作成部の動作を具体的に説明する図である。実施の形態１にかかる順序同型照合装置の照合部の動作を説明する図である。

実施の形態１
以下、図面を参照して本発明の実施の形態について説明する。まず、実施の形態１にかかる順序同型照合装置１の処理対象となる二次元パターンに対する順序同型照合問題について説明する。そこで、図１に二次元データに対する順序同型照合問題に関する課題を説明する図を示す。

図１では、上図に非特許文献３、４に示されている二次元データに対する照合問題における照合方向を示した。図１の上図に示すように、二次元に配置されたデータに対する照合問題では、横方向（例えば、Ｘ方向）と縦方向（例えば、Ｙ方向）の２つの方向でデータが一致することで、検索パターンの探索が可能である。これは、照合問題では、ａ＝ｂかつｂ＝ｃであればａ＝ｃとの関係が保証されるため、斜め方向のパターンの探索を行う必要がないためである。

一方、図１の下図に二次元データを対象とした順序同型照合問題における課題を示した。二次元データを対象とした順序同型照合では、照合問題と異なり、配置される文字列の大小関係を検索対象の問題とする。そのため、斜め方向の文字列の関係を考慮しない探索を行うと問題が生じる。具体的には、斜め方向の探索を行わない場合、ａ＜ｃかつｂ＜ｃであってもａとｂとの大小関係が不明である問題が生じる。一方、ａ＜ｂかつｂ＜ｃであれば、ａ＜ｃの関係は補償できる。このように、二次元データを対象とする順序同型照合問題では、斜め方向の探索を行わないと、探索対象パターンと検索パターンとが合致しているか否かの補償ができない問題が生じる。

以下で説明する実施の形態１にかかる順序同型照合装置１では、二次元（例えば、ｍ行ｍ列）でテキストデータが配置される検索データから一次元でテキストデータが配置される照合パターン（以下、一次元パターンＭと称す。）を生成する。そして、実施の形態１にかかる順序同型照合装置１では、一次元パターンＭについての索引情報Ｓを生成する。また、実施の形態１にかかる順序同型照合装置１では、二次元（例えば、ｎ行ｎ列）でテキストデータが配置される探索対象二次元パターンＴについて、索引情報Ｓを適用して、検索パターンＰと順序同型パターンが一致する箇所を特定する。このように、検索パターンＰを一次元パターンＭに変換して、一次元パターンＭに基づき生成される索引情報Ｓを探索対象二次元パターンＴに適用することで、斜め方向の順序同型パターンの一致を補償する。なお、以下で説明する例では、実施の形態１にかかる順序同型照合装置１では、探索対象二次元パターンＴ内にｎ行ｍ列の探索対象領域を設定し、当該探索対象領域を列方向にずらしながら探索対象二次元パターンＴに対する一次元パターンＭの照合箇所の探索を行う。

そこで、図２に実施の形態１にかかる順序同型照合装置１の構成を説明するブロック図を示す。なお、図２で示した構成は、順序同型照合装置１で行われる処理を処理毎にブロックとしたものであり、各ブロックの処理内容は、専用ハードウェア、コンピュータ上で実行されるソフトウェア等により実現することができる。以下の説明では、コンピュータ上で実行されるソフトウェアによって処理が行われる例について説明する。

実施の形態１にかかる順序同型照合装置１は、ファイルＤ１として検索パターンＰを読み込み、探索対象二次元パターンデータベースＤ４に格納されている探索対象二次元パターンＴ内に検索パターンＰに合致する部分があるか否かを探索する。ここで、実施の形態１にかかる順序同型照合装置１では、検索パターンＰと探索対象二次元パターンＴは、いずれも二次元で配置されるテキストデータにより構成されるパターンである。また、探索対象二次元パターンＴは、検索パターンＰよりも大きな二次元配列パターンを有する。検索パターンＰのパターンの大きさをｍ×ｍとし、探索対象二次元パターンＴのパターンの大きさをｎ×ｎとすると、ｍ＜ｎの関係が成り立つ。

図２に示すように、実施の形態１にかかる順序同型照合装置１は、処理ブロックとして、パターン変換部１０、文字列照合索引作成部１１、照合部１２、出力部（例えば、照合解出力部１３）を有する。

パターン変換部１０は、検索パターンＰを、一次元でテキストデータが配置される一次元パターンＭに変換する。パターン変換部１０は、一次元パターンＭをファイルＤ２として出力する。文字列照合索引作成部１１は、一次元パターンＭについて、一次元パターンＭと順序同型となる検索対象パターンを特定する索引を索引情報Ｓとして生成する。文字列照合索引作成部１１は、索引情報ＳをファイルＤ３として出力する。照合部１２は、二次元に配置されたテキストデータにより構成され、探索対象二次元パターンＴに対して、索引情報Ｓを適用して、探索対象二次元パターンにおいて照合パターンに一致する箇所に所定のＩＤ番号を付す。照合解出力部１３は、照合部１２において所定のＩＤ番号が付された箇所を、照合位置として出力する。

ここで、順序同型照合装置１の各処理ブロックのうちパターン変換部１０、文字列照合索引作成部１１の動作について詳細に説明する。そこで、図３に実施の形態１にかかる順序同型照合装置１のパターン変換部１０及び文字列照合索引作成部１１の動作を概略的に説明する図を示す。図３に示す例は、ｍ行ｍ列の検索パターンＰに対して一次元パターンＭを生成するものである。

図３に示すように、パターン変換部１０は、検索パターンＰを行毎に分解し、分解した行を、行順に一次元に配置することで、一次元パターンＭを生成する。そして、文字列照合索引作成部１１は、一次元パターンＭに対して索引情報Ｓを生成する。ここで、実施の形態１にかかる順序同型照合装置１では、索引情報Ｓとして、オートマトンを生成する。このオートマトンは、連続する値の大小関係を示す受理状態が連鎖するように構築される文字列の索引である。

また、図３に示した処理を具体的な数値例を挙げて説明する。そこで、図４に実施の形態１にかかる順序同型照合装置のパターン変換部及び文字列照合索引作成部の動作を具体的に説明する図を示す。図４に示す例では、検索パターンＰとして３行３列に並べられた９個の数値を有する。パターン変換部１０は、検索パターンＰを行毎に分解して、行順に分解した行を一次元で並べる。図４に示す例では、一次元パターンＭは、検索パターンＰの１行目の３２３に続いて、検索パターンＰの２行目の１４５が並び、その後に検索パターンＰの３行目の２５５が並ぶ。

そして、図４に示すように、文字列照合索引作成部１１が生成するオートマトンの各受理状態は、連続する数値のうち最も後ろの数値と、最後の数値のひとつ前の数値との大小関係が比較対象の数列と一致した場合に、次の受理状態に遷移するように、受理状態が連鎖したものとなる。また、図４に示すオートマトンの各受理状態は、最後の数値と最後の数値の１つ前の数値との大小関係が比較対象の数列と一致しなかった場合には、最初の受理状態Ｓ０に戻る形態となっている。

続いて、照合部１２について説明する。照合部１２は、探索対象二次元パターンデータベースＤ４から探索対象二次元パターンＴを読み出し、読み出した探索対象二次元パターンＴに対してファイルＤ３として生成された索引情報Ｓを適用した探索を行う。照合部１２は、探索対象二次元パターンＴに対して、索引情報Ｓを適用して、探索対象二次元パターンＴにおいて検索パターンＰに一致する箇所に所定のＩＤ番号を付す。また、実施の形態１にかかる順序同型照合装置１では、照合部１２による照合方法の１つの態様として、以下のような動作を行う。実施の形態１にかかる照合部１２は、探索対象二次元パターンＴに含まれるテキストデータから、検索パターンＰの列方向の文字数に対応する列数と、探索対象二次元パターンＴの行方向の文字数に対応する行数とで構成される探索対象領域を設定する。そして、実施の形態１にかかる照合部１２は、探索対象領域を列方向にずらしながら探索対象二次元パターンＴに対する検索パターンＰの照合箇所の探索を行う。

そこで、図５に実施の形態１にかかる順序同型照合装置１の照合部１２の動作を説明する図を示す。図５に示す例は、ｎ行ｎ列の探索対象二次元パターンＴ内にｍ行ｍ列の検索パターンＰが存在するか否かを探索するものである。図５に示すように、照合部１２は、検索パターンＰの列数に対応する列数（例えば、ｎ列）と、探索対象二次元パターンＴの行数に対応する行数（例えば、ｎ行）と、で構成される探索対象領域Ａを探索対象二次元パターンＴ内に設定する。そして、探索対象領域Ａ内の行の先頭となるテキストを探索開始文字として、索引情報Ｓを用いた探索を行う。また、照合部１２は、探索対象領域Ａにおいて行を順にずらしながらすべて先頭文字を探索開始文字として索引情報Ｓを用いた探索を行う。さらに、照合部１２は、探索対象領域Ａとして設定する領域を列方向に順にずらしながら、索引情報Ｓを用いた探索を行う。そして、照合部１２は、索引情報Ｓの最終受理状態（例えば、図４の受理状態Ｓ９）まで照合が完了したときの先頭文字に予め設定された所定のＩＤ番号を付す。一方、照合部１２は、索引情報Ｓの最終受理状態まで達しない場合には、その照合サイクルにおける先頭文字を、不一致を示すＩＤ番号（例えば、０）に置き換える。

そして、照合解出力部１３は、照合部１２において所定のＩＤ番号が付された箇所を、照合位置として出力する。

上記説明より、実施の形態１にかかる順序同型照合装置１では、二次元配列を有する検索パターンＰを一次元配列の一次元パターンＭに変換する。そして、一次元パターンＭに基づき索引情報Ｓを生成し、探索対象二次元パターンＴに当該索引情報Ｓを適用した探索を行う。これにより、順序同型照合装置１は、検索パターンＰのあらゆる方向に関する探索を照合部１２における一連の照合処理により行うことができる。また、順序同型照合装置１では、生成する照合パターン（例えば、一次元パターンＭ）及び索引情報Ｓの数を１つとすることができる。

これにより、実施の形態１にかかる順序同型照合装置１は、少ない演算回数で探索対象二次元パターンＴ内から検索パターンＰと順序同型となるパターンの存在の有無を探索することができる。例えば、実施の形態１にかかる順序同型照合装置１を用いることで、演算回数Ｏは、Ｏ（ｍｎ２）となる。

なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。

上述の例において、プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ－ＲＯＭ（Read Only Memory）、ＣＤ－Ｒ、ＣＤ－Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（Random Access Memory））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。

１順序同型照合装置
１０パターン変換部
１１文字列照合索引作成部
１２照合部
１３照合解出力部
Ｐ検索パターン
Ｔ探索対象二次元パターン
Ｍ一次元パターン
Ｓ索引情報
Ｄ１ファイル
Ｄ２ファイル
Ｄ３ファイル
Ｄ４探索対象二次元パターンデータベース
Ａ探索対象領域

Claims

二次元で配置されたテキストデータにより構成される検索パターンを、一次元で前記テキストデータが配置される照合パターンに変換するパターン変換部と、
前記照合パターンについて、前記照合パターンと順序同型となる検索対象パターンを特定する索引を索引情報として生成する文字列照合索引作成部と、
二次元に配置されたテキストデータにより構成され、前記検索パターンよりも大きな配列を有する探索対象二次元パターンに対して、前記索引情報を適用して、前記探索対象二次元パターンにおいて前記照合パターンに一致する箇所に所定のＩＤ番号を付す照合部と、
前記照合部において前記所定のＩＤ番号が付された箇所を、照合位置として出力する出力部と、を有し、
前記索引情報は、連続する値の大小関係を示す受理状態が連鎖するように構築されるオートマトンである順序同型照合装置。
前記パターン変換部は、前記検索パターンを行毎に分解し、行の順番に従って分解した行に含まれるテキストデータを並べて前記照合パターンを生成する請求項１に記載の順序同型照合装置。
前記照合部は、前記探索対象二次元パターンに含まれるテキストデータから、前記検索パターンの列方向の文字数に対応する列数と、前記探索対象二次元パターンの行方向の文字数に対応する行数とで構成される探索対象領域を設定し、当該探索対象領域を列方向にずらしながら前記探索対象二次元パターンに対する前記照合パターンの照合箇所の探索を行う請求項１または２のいずれか１項に記載の順序同型照合装置。
データベースに格納され、かつ、二次元に配置されたテキストデータにより構成された探索対象二次元パターンについて、二次元で配置されたテキストデータにより構成される検索パターンに合致する順序同型パターンの探索をプログラムに従ってコンピュータが行う自動処理により行う順序同型照合方法であって、
前記検索パターンを、一次元で前記テキストデータが配置される照合パターンに変換し、
前記照合パターンについて、前記照合パターンと順序同型となる検索対象パターンを特定する索引を索引情報として生成し、
前記探索対象二次元パターンに対して、前記索引情報を適用して、前記探索対象二次元パターンにおいて前記照合パターンに一致する箇所に所定のＩＤ番号を付し、
前記所定のＩＤ番号が付された箇所を、照合位置として出力し、
前記索引情報は、連続する値の大小関係を示す受理状態が連鎖するように構築されるオートマトンである順序同型照合方法。
データベースに格納された二次元に配置されたテキストデータにより構成された探索対象二次元パターンについて、二次元で配置されたテキストデータにより構成される検索パターンに合致する順序同型パターンを探索する順序同型照合処理を、コンピュータに実行させる順序同型照合プログラムであって、
前記順序同型照合プログラムは、
二次元で配置されたテキストデータにより構成される検索パターンを、一次元で前記テキストデータが配置される照合パターンに変換するパターン変換処理と、
前記照合パターンについて、前記照合パターンと順序同型となる検索対象パターンを特定する索引を索引情報として生成する文字列照合索引作成処理と、
二次元に配置されたテキストデータにより構成され、前記検索パターンよりも大きな配列を有する探索対象二次元パターンに対して、前記索引情報を適用して、前記探索対象二次元パターンにおいて前記照合パターンに一致する箇所に所定のＩＤ番号を付す照合処理と、
前記照合処理において前記所定のＩＤ番号が付された箇所を、照合位置として出力する出力処理と、
を前記コンピュータに実行させ、
前記索引情報は、連続する値の大小関係を示す受理状態が連鎖するように構築されるオートマトンである順序同型照合プログラム。