(57)【要約】【課題】可能なソースパターンの順序シーケンス内におけるソースパターンおよびターゲットパターンの位置番号を考慮するだけで、パターンマッチングを達成する。【解決手段】ターゲットパターンを含むソースパターンの位置番号は、複数のグループを形成する。各グループ内のソースパターンの個数およびグループ間のギャップにおけるソースパターンの個数は、ソースパターン内におけるターゲットパターンの位置、長さおよびアルファベット集合の要素数に依存する。各グループは、位置番号を有する。入力されたソースパターンのグループ位置番号は、ターゲットパターンの位置番号、長さおよびアルファベット集合の要素数から導出された級数と比較される（９）。グループ位置番号が級数の元である場合（１０）、ソースパターンはターゲットパターンを含む（１１）。
2006522401.tif 000002
【特許請求の範囲】
【請求項１】
ターゲットパターンが、アルファベット集合からの１つ又は２つ以上の文字から成るソースパターン内に存在するかどうかを判断する方法であって、
可能なパターンのシーケンス内における前記ソースパターンの位置が、前記ターゲットパターンを含む該可能なパターンのシーケンス内における位置と相関する位置であるかどうかを判断することによって判断する
方法。
【請求項２】
ｉ．ソースパターンのグループリーダが、アルファベット系の基数に従って可能な位置番号のシーケンスをグループに分割することにより形成された各グループにおける最も高い位置番号である、このグループリーダを特定するステップと、
ｉｉ．前記ソースパターンの前記グループリーダの値が、前記ターゲットパターンを含む前記可能なパターンのシーケンス内における前記ターゲットパターンの前記位置と相関するグループリーダの値であるかどうかを判断するステップと
を含む請求項１に記載の方法。
【請求項３】
行よりも１つ小さな数でアルファベットの基数をべき乗した値に対応するグループサイズを有するグループに、昇順の可能な位置番号のシーケンスを分割することによって、前記ソースパターンの前記グループリーダの値は、行ごとに直接的又は間接的に求められ、前記行は、前記ソースパターン内の前記ターゲットパターンの位置に対応する
請求項２に記載の方法。
【請求項４】
前記グループリーダの値が、前記ターゲットパターンにとって妥当であるか否かを判断するために、グループリーダ位置が使用され、このグループリーダ位置は、その行のグループのうちで前記グループリーダのグループの位置である
請求項３に記載の方法。
【請求項５】
ソースパターンの前記グループリーダの位置は、以下のアルゴリズムに従って計算され、
Ｎ＝１＋Ｑｕｏｔｉｅｎｔ（（Ｓｐ−１）／ｂｒ−１）
ここで、
Ｎ＝ソースパターンのグループリーダの位置番号、
Ｓｐ＝ソースパターンの位置番号、
ｂ＝アルファベットの基数、
ｒ＝行番号
である
請求項２〜４のいずれかに記載の方法。
【請求項６】
前記ステップｉｉにおいてマッチがあるかどうかを判断するためには、以下のアルゴリズムの結果が０でなければならず、
Ｒ＝ｒｅｍａｉｎｄｅｒ（（Ｎ−Ｔｐ）／ｂＴＩ）
ここで、
Ｒ＝剰余、
Ｔｐ＝前記ターゲットパターンの位置番号、
ＴＩ＝前記ターゲットパターンの長さ
である
請求項５に記載の方法。
【請求項７】
複数の行が存在し、この方法は各行に連続して適用される
請求項３に記載の方法。
【請求項８】
２つ以上のソースパターンに同時に適用される
請求項３に記載の方法。
【請求項９】
前記行を探索する順序は、前記ソースパターンの特性に依存する
請求項３に記載の方法。
【請求項１０】
前記ターゲットパターンが行に見つかる確率が見積もられ、前記行を探索する順序を決定するために使用される
請求項３に記載の方法。
【請求項１１】
前記ターゲットパターンが行に見つかる確率が判明しており、前記行を探索する順序を決定するために使用される
請求項３に記載の方法。
【請求項１２】
前記ソースパターンは、算術符号化データである
請求項１に記載の方法。
【請求項１３】
前記ターゲットパターンは、算術符号化データである
請求項１２に記載の方法。
【請求項１４】
前記ソースパターンは、算術符号化を使用して圧縮される
請求項１２に記載の方法。
【請求項１５】
前記ターゲットパターンは、算術符号化を使用して圧縮される
請求項１３に記載の方法。
【請求項１６】
前記ターゲットパターンは、
２つ以上の要素
を有する
請求項１に記載の方法。
【請求項１７】
｛Ｘ１…Ｘｍ｝および｛Ｙ１…Ｙｑ｝が、有限順序集合｛Ｚ１…Ｚｏ｝の元であるときに、ターゲットシーケンス［Ｘ１…Ｘｍ］が、ソースシーケンス［Ｙ１…Ｙｑ］内に存在するかどうかを判断する方法であって、
ｉ．Ｖｋ＝ｊ：Ｙｋ＝Ｚｊである場合に、基数ｏにおけるソース部分シーケンス値の集合｛［Ｖ１］，…［Ｖ１…Ｖｋ］，…［Ｖ１…Ｖｎ］｝を構成するステップと、
ｉｉ．Ｄｋ＝ｈ：Ｘｋ＝Ｚｈとなるようにｐが基数ｏにおける番号［Ｄ１…Ｄｎ］である場合に、前記集合のいずれかの値がターゲット値の級数｛ｐ，…ｐ＋ｋｏｍ，…ｐ＋ｎｏｍ｝に対応するかどうかを判断するステップと
を含む方法。
【請求項１８】
前記ステップｉｉにおいて、前記集合のいずれかの値が前記級数に対応するか否かを判断するためには、前記集合のすべての元について、以下のアルゴリズムの結果が０でなければならず、
Ｒ＝ｒｅｍａｉｎｄｅｒ（（Ｎ−ｐ）／ｏｍ）
ここで、Ｎは基数１０の集合の元である、
請求項１７に記載の方法。
【請求項１９】
前記ソースシーケンスは、画像データである
請求項１７に記載の方法。
【請求項２０】
前記ソースシーケンスは、ビデオデータである
請求項１７に記載の方法。
【請求項２１】
前記ソースシーケンスは、生物医学データである
請求項１７に記載の方法。
【請求項２２】
ターゲットパターンが、アルファベットの１つ又は２つ以上の文字からなるソースパターン内に存在するか否かを判断するためのデータ処理装置であって、
ｉ．ターゲットパターンを記憶するための第１のメモリと、
ｉｉ．ソースパターンを記憶するための第２のメモリと、
ｉｉｉ．可能なパターンのシーケンスにおける前記ソースパターンの位置を求めるための処理手段と、
ｉｖ．前記可能なパターンのシーケンスにおける前記ターゲットパターンの位置を求めるための処理手段と、
ｖ．前記ソースの位置を、前記ターゲットの位置と相関させるための処理手段と
を備えるデータ処理装置。
【請求項２３】
ターゲットシーケンスが、アルファベットの１以上の文字からなるソースシーケンス内に存在するか否かを判断するためのデータ処理装置であって、
ｉ．前記アルファベットの文字のすべての可能な組み合わせの語彙（lexicon）内における前記ターゲットシーケンスの位置であるターゲットシーケンス位置を記憶するための第１のメモリと、
ｉｉ．前記語彙内における前記ソースシーケンスの位置であるソースシーケンス位置を記憶するための第２のメモリと、
ｉｉｉ．前記ソースシーケンスの部分シーケンスの位置の集合であって、該部分シーケンスの位置が前記語彙内における該部分シーケンスの位置であり、該部分シーケンスが前記ソースシーケンスの最初の文字の位置を含む、位置の集合を計算するための処理手段と、
ｉｖ．前記ターゲットシーケンスを含む前記語彙内におけるシーケンスのすべての位置を定義する級数を求めるための処理手段と、
ｖ．前記集合を前記級数と相関させるための処理手段と
を備えるデータ処理装置。
【請求項２４】
前記ソースシーケンスは、画像データである
請求項２２に記載のデータ処理装置。
【請求項２５】
前記ソースシーケンスは、ビデオデータである
請求項２２に記載のデータ処理装置。
【請求項２６】
前記ソースシーケンスは、生物医学データである
請求項２２に記載のデータ処理装置。
【請求項２７】
前記処理手段は、コンピュータシステムである
請求項２２に記載のデータ処理装置。
【請求項２８】
請求項１に記載の方法に従って動作するように適合される
データ処理装置。
【請求項２９】
請求項１７に記載の方法に従って動作するように適合される
データ処理装置。
【請求項３０】
請求項１に記載の方法において実行するコンピュータプログラム。
【請求項３１】
請求項１７に記載の方法において実行するコンピュータプログラム。
【請求項３２】
請求項３０に記載のコンピュータプログラムを実施する
コンピュータ可読媒体。
【請求項３３】
請求項３１に記載のコンピュータプログラムを実施する
コンピュータ可読媒体。
【請求項３４】
請求項３０に記載のコンピュータプログラムを実施する
信号。
【請求項３５】
請求項３１に記載のコンピュータプログラムを実施する
コンピュータ可読媒体。
【請求項３６】
請求項１に記載の方法に従って動作するようにプログラミングされる
コンピュータ。
【請求項３７】
請求項１７に記載の方法に従って動作するようにプログラミングされる
コンピュータ。
【請求項３８】
請求項１に記載の方法によって生成される
パターンマッチング情報。
【請求項３９】
請求項１７に記載の方法によって生成される
パターンマッチング情報。
【請求項４０】
請求項３８に記載のパターンマッチング情報を実施する
信号。
【請求項４１】
請求項３９に記載のパターンマッチング情報を実施する
信号。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、パターンマッチングに関する。パターンマッチングは、ソースパターンにおけるターゲットパターンの存在の一部又はすべてを見つけるプロセスである。圧縮パターンマッチングは、ソースパターンを伸張することなく、圧縮ソースパターンにおけるターゲットパターンの存在の一部又はすべてを見つけるプロセスである。
【背景技術】
【０００２】
［発明の背景］
パターンマッチングは、データブロックに解析ルールを適用して、当該データブロックの特徴を識別することである。
【０００３】
最も一般的なパターンマッチング問題は、大きな要素シーケンス［Ｘ１…Ｘｎ］（ソースパターン）内における要素シーケンス［Ｙ１…Ｙｍ］（ターゲットパターン）の存在の一部又はすべてを見つけるプロセスである。
これらの要素は、アルファベットの集合といった有限の要素集合から得られる。
この集合は、英語のアルファベット、｛０，１｝、自然数等とすることができる。
この問題について最もよく知られているアルゴリズムは、クヌース−モリス−プラット（Knuth-Morris-Pratt）アルゴリズム、ボイア−ムーア（Boyer-Moore）アルゴリズム、及びラビン−カープ（Rabin-Karp）アルゴリズムである。
【０００４】
パブリックドメインには、多数のパターンマッチングツールがある。
これらのうち最も有名なものは、グレップファミリー（grep family）である。
【０００５】
パターンマッチングは、簡単なテキスト検索や、画像データ、会話データ、ビデオデータ、音響データ、生物医学的な配列解析等におけるデータの検索に使用される。
【０００６】
データ圧縮は、主として、記憶空間の削減及びデータ伝送の高速化に使用される。
さまざまな圧縮形式が知られている。
特に興味深いのは、これまで圧縮パターンマッチングが可能でなかった算術符号化圧縮である。
【０００７】
算術符号化は、１９７０年代及び１９８０年代に端を発する（例えば、米国特許第４，１２２，４４０号参照）。
算術符号化は、会話圧縮及び医学用画像圧縮を含めて、いくつかの用途に使用される。
【０００８】
圧縮パターンマッチングでは、パターンマッチングは圧縮領域で行われる。
簡潔に言うと、例えば、テキスト文字列の圧縮パターンマッチングは、
ａｃを所与の圧縮アルゴリズムとし、ａｃ（Ｄ）を、ａｃがデータＤを圧縮した結果とすると、
入力：圧縮テキストａｃ（Ｔ）及び圧縮パターンａｃ（Ｐ）
出力：パターンＰが出現する、Ｔにおけるすべての位置又は一部の位置
として示すことができる。
【０００９】
Amir及びBenson（「Efficient Two-dimensional Compressed Matching」, in Proc. Second IEEE Data Compression Conference, pp 279-288, March 1992）は、パターンマッチングの複雑さが、解凍領域におけるあらゆる従来の方法と比較して圧縮領域で削減されることを示した。
【００１０】
しかしながら、「算術符号」のデータを伸張することなく、「算術符号」に対してパターンマッチングを行うことが可能であるとは考えられていなかった（http://www.cosc.canterbury.ac.nz/research/reports/TechReps/2001/tr_0107.pdfにおいて入手可能なTim Bell他による「TR-COSC 07/01 Pattern Matching in Compressed Texts and Images」, Technical Reports, University of Canterbury）。
【特許文献１】米国特許第４，１２２，４４０号
【非特許文献１】BELL ET AL: "Pattern Matching in Compressed Text and Images" TECHNICAL REPORTS, TR-COSC, 'Online! no. 07/01, 29 May 2001 (2001-05-29), XP002292206 UNIVERSITY OF CATERBURY Retrieved from the Internet: URL:http://www.cosc.canterbury.ac.nz/research/reports/TechReps/2001/tr_0107.pdf'retrieved on 2004-08-10! cited in the application the whole document
【非特許文献２】WITTEN I H ET AL: "ARITHMETIC CODING FOR DATA COMPRESSION" COMMUNICATIONS OF THE ASSOCIATION FOR COMPUTING MACHINERY, ASSOCIATION FOR COMPUTING MACHINERY. NEW YORK, US, vol. 30, no. 6, 1 June 1987 (1987-06-01), pages 520-540, XP000615171 ISSN: 000l-0782 the whole document
【非特許文献３】LANGDON G: "An introduction to arithmetic coding" IBM JOURNAL OF RESEARCH AND DEVELOPMENT, IBM CORPORATION, ARMONK, US, vol. 28, no. 2, 1 March 1984 (1984-03-01), pages 135-149, XP002086019 ISSN: 0018-8646 the whole document
【発明の開示】
【発明が解決しようとする課題】
【００１１】
［発明の概要］
本発明の目的は、算術符号をマッチングするのに適したパターンマッチングの方法を提供すること、又は、公衆に有益な選択肢を少なくとも提供することである。
【課題を解決するための手段】
【００１２】
本発明の第１の態様によれば、ターゲットパターンが、アルファベット集合からの１つ又は２つ以上の文字から成るソースパターン内に存在するかどうかを判断する方法であって、可能なパターンのシーケンス内におけるソースパターンの位置が、ターゲットパターンを含む可能なパターンのシーケンス内における位置と相関する位置であるかどうかを判断することによって、判断する方法が提供される。
【００１３】
本発明のさらなる態様によれば、｛Ｘ１…Ｘｍ｝及び｛Ｙ１…Ｙｑ｝が有限順序集合｛Ｚ１…Ｚｏ｝の元である場合にターゲットシーケンス［Ｘ１…Ｘｍ］がソースシーケンス［Ｙ１…Ｙｑ］内に存在するかどうかを判断する方法であって、
ｉ．Ｖｋ＝ｊ：Ｙｋ＝Ｚｊである場合に、基数ｏにおけるソース部分シーケンス値の集合｛［Ｖ１］，…［Ｖ１…Ｖｋ］，…［Ｖ１…Ｖｎ］｝を構成するステップ、及び
ｉｉ．Ｄｋ＝ｈ：Ｘｋ＝Ｚｈとなるようにｐが基数ｏにおける番号［Ｄ１…Ｄｎ］である場合に、集合のいずれかの値がターゲット値の級数｛ｐ，…ｐ＋ｋｏｍ，…ｐ＋ｎｏｍ｝に対応するかどうかを判断するステップ
を含む、方法が提供される。
【００１４】
本発明の別の態様によれば、ターゲットパターンが、アルファベットの１つ又は２つ以上の文字から成るソースパターン内に存在するかどうかを判断するためのデータ処理装置であって、
ｉ．ターゲットパターンを記憶するための第１のメモリ、
ｉｉ．ソースパターンを記憶するための第２のメモリ、
ｉｉｉ．可能なパターンのシーケンスにおけるソースパターンの位置を求めるための処理手段、
ｉｖ．可能なパターンのシーケンスにおけるターゲットパターンの位置を求めるための処理手段、及び
ｖ．ソースの位置をターゲットの位置と相関させるための処理手段
を備える、データ処理装置が提供される。
【００１５】
本発明のさらなる態様によれば、ターゲットシーケンスが、アルファベットの１つ又は２つ以上の文字から成るソースシーケンス内に存在するかどうかを判断するためのデータ処理装置であって、
ｉ．アルファベットの文字のすべての可能な組み合わせの語彙内におけるターゲットシーケンスの位置であるターゲットシーケンス位置を記憶するための第１のメモリ、
ｉｉ．語彙内におけるソースシーケンスの位置であるソースシーケンス位置を記憶するための第２のメモリ、
ｉｉｉ．ソースシーケンスの部分シーケンスの位置の集合であって、部分シーケンスの位置が語彙内における部分シーケンスの位置であり、部分シーケンスがソースシーケンスの最初の文字の位置を含む、位置の集合を計算するための処理手段、
ｉｖ．ターゲットシーケンスを含む語彙内におけるシーケンスのすべての位置を定義する級数を求めるための処理手段、及び
ｖ．集合を級数と相関させるための処理手段、
を備える、データ処理装置が提供される。
【００１６】
次に、例として、添付図面に関して本発明を説明する。
【発明を実施するための最良の形態】
【００１７】
［発明の実施の形態の詳細な説明］
本発明を、データを圧縮することもできるし、解凍することもできる例に関して説明する。
【００１８】
ソースパターン文字列ｔ及びターゲットパターン文字列ｐについて考える。
これらの文字列は、それぞれ長さＬｔ及びＬｐを有し、Ｌｔ≧Ｌｐであることを必要とする（この発明は、この条件が満たされる場合に、任意の長さの文字列に適用できることに留意されたい）。
順序付けられた一連のソースパターン文字列内におけるソースパターン文字列の位置Ｐｔを定義する。
例えば、Ｌｔ＝４に場合に、アルファベット集合｛ａ，ｂ，ｃ，ｄ，ｅ｝について、最初の１１個のソースパターン文字列、及び、辞書に従った順序集合におけるそれらソースパターン文字列の位置は、表１に示される。
【００１９】
【表１】
2006522401.tif 000003
【００２０】
同様に、ターゲットパターン文字列の位置Ｐｐも定義する。
Ｌｐ＝１の場合に、同じアルファベット集合｛ａ，ｂ，ｃ，ｄ，ｅ｝について、可能なターゲットパターン文字列、及び、辞書に従った順序集合におけるそれらターゲットパターン文字列の位置は、表２に示される。
【００２１】
【表２】
2006522401.tif 000004
【００２２】
ソースパターン文字列には、ターゲットパターン文字列に照合するものが０個の場合もあるし、１つ又は数個を含む場合もある。
【００２３】
図１は、例示の目的の簡単なシナリオを示している。
図１において、アルファベット集合｛０，１｝及びソースデータ長Ｌｔが４について説明を始めるものとする。
この場合、可能なソースパターン文字列は、００００から１１１１のすべての２進数である。
数字に基づく順序集合におけるソースパターン文字列の位置も、この図に示されている。
次に、ターゲットパターン「１」とのパターンマッチについて考える。
行１から行４には、ソースパターン文字列内における４つの可能なターゲットパターンの位置について、パターンマッチ条件を満たすソースパターン文字列の位置番号が示されている。
例えば、行４では、ターゲットパターン「１」は、ソースパターン文字列の最初の位置を占める。
この条件は、２進数１０００から１１１１について満たされ、これらの２進数は、９から１６の位置番号を有する。
【００２４】
より一般的には、所与の行において、ターゲットパターンが出現するソースパターン文字列の位置番号は、連続した番号の１つ又は数個のグループを形成し、グループ間には切れ目を有することに留意されたい。
各グループの要素数は行に依存し、したがって、ソースパターン文字列内におけるターゲットパターンの位置に依存する。
行１では、各グループは単一の要素を含み、各グループ間には１のギャップを有する。
行３では、各グループは４つの要素を有し、各グループ間は４のギャップを有する。
【００２５】
明らかなように、行１の要素は等差級数を形成する。
この等差級数では、開始要素ｂ０は、ターゲットパターンの位置Ｐｐに等しく、階差は、アルファベット集合の要素数Ｎをターゲットパターンの長さＬｐでべき乗したもの（すなわち、ターゲットパターンの要素数）である。
ｂｍ＝ｂ０＋（ｍ−１）ＮＬｐ          方程式（１）
【００２６】
次に、各グループの中で最も高い位置をグループリーダとして定義する。
この場合、各行はグループリーダ級数を有する。
どの行のグループリーダ級数も、アルファベット集合の要素数Ｎの因数（factor）だけ隣接した行のグループリーダ級数と関連している。
本発明では、行１の群リーダ級数をルートグループリーダ級数として定義する。
【００２７】
図２から図４において、第２のシナリオを提示する。
本発明では、アルファベット集合｛ａ，ｂ，ｃ，ｄ，ｅ｝及びソースデータ長Ｌｔが４について説明を始める。
ターゲットパターン「ｂ」とのパターンマッチングを行いたい。
この場合、ターゲットパターンＰｐの位置番号は２である。
図２は、ターゲットパターン「ｂ」を含むすべての可能なソースパターン文字列を示している。
破線は、すべてのソースパターン文字列がこのエリアに表示されているとは限らないことを示している。
図３は、ソースパターン文字列がその位置番号によって表されているという点を除けば、図２に正確に対応する。
図４は、位置番号がほぼ一定の倍率で拡大されるように、位置番号軸が追加されたという点を除けば、図３に対応する。
上記方程式（１）から、ルートグループリーダ級数は、以下によって表される。
ｂｍ＝２＋（ｍ−１）５１
＝｛２，７，１２，１７…｝
【００２８】
行のいずれにおけるグループリーダ級数も、Ｎ＝５の因数だけ隣接した行のグループリーダ級数に関連している。
【００２９】
ソースデータ長が４の可能なグループリーダ及び長さＬｐ＝１のすべての可能なターゲットパターンが表３に表されている。
ターゲットパターンが「ｂ」（したがって、Ｐｐ＝２）である場合、｛２，７，１２，…｝のグループリーダ位置を有するグループのみがパターンマッチを表すことに留意されたい。
表の対応する列は網掛けされている。
【００３０】
【表３】
2006522401.tif 000005
【００３１】
次に、図３及び図５に関してパターンマッチングアルゴリズムを説明する。
この説明では、関連したステップを括弧書きの番号によって示す。
【００３２】
このアルゴリズムは、ソースパターン文字列内の可能な各ターゲットパターン位置においてパターンマッチを探索する。
このソースパターン文字列は一時に１行である。
行数は、ソースパターン文字列とターゲットパターン文字列との長さの差に１を加えたものＬｔ−Ｌｐ＋１＝ＬＤ＋１に等しい。
ここで、ＬＤ＝Ｌｔ−Ｌｐである（１）。
したがって、本発明では、一度に１行移動するために１つだけインクリメント又はディクリメントされるＬｉｔｅｒを定義する（２）。
【００３３】
ソースパターン文字列の位置番号及びターゲットパターン文字列の位置番号を計算する。
ＬＤが０に等しく、かつ、ＰｔがＰｐに等しい場合、ターゲットパターン文字列は、ソースパターン文字列と同一である（３）。
そうである場合（４）、明らかに、１つだけのパターンマッチを有し（５）、このアルゴリズムは終了する（６）。
そうでない場合（７）、ソースパターン文字列を含むグループのグループリーダ位置を計算する（８）。
次に、このグループリーダ位置が、ルートグループリーダ級数と比較される（９）。
次に、グループリーダ位置がルートグループリーダ級数の要素でない場合（１２）、処理は次のステップに進む（１３）。
グループリーダ位置がルートグループリーダ級数の要素である場合（１０）、対応する行にパターンマッチが存在する（１１）。
Ｌｉｔｅｒが０に等しくない場合（１３、１４）、このアルゴリズムは、Ｌｉｔｅｒをディクリメントすることによって、残りの行をループし（１５）、各行のパターンマッチをチェックする。
行のすべてがチェックされると、Ｌｉｔｅｒ＝０となり（１３、１６）、このアルゴリズムは終了する（１７）。
【００３４】
このアルゴリズムは、ソースデータのすべてのパターンマッチを探索することは明らかである。
しかしながら、類似のアルゴリズムも、単一のパターンマッチを容易に探索でき、パターンマッチが見つかると直ちに終了する。
この場合、関与した文字列の経験的な知識がそのアルゴリズムを大幅に高速にすることができる。
探索シーケンスは、ソースパターン文字列の特性に依存することがある。
ターゲットパターンがソースパターン文字列の終点に向かって含まれている可能性があるとアプリオリに分かっている場合、本発明では、ターゲットパターンが行１に含まれていると仮定して開始し、行（ＬＤ＋１）に向かって一度に１行累進的に進むべきである。
他方、ターゲットパターンがソースパターン文字列の始点に向かって含まれる可能性がある場合、本発明では、行（ＬＤ＋１）から行１へ累進的に進むべきである。
別の類似のアルゴリズムは、ソースパターン文字列の特定の位置におけるパターンマッチを探索することができる。
代替的に、探索シーケンスは、ソースパターン文字列の解析に基づくことができ、行ごとに見積もられた確率に従って行うことができる。
ソースデータの特性に応じて、さまざまな探索シーケンスを使用できることが理解されよう。
【００３５】
上述したグループリーダの位置を計算するステップは、以下のように行うことができる。
可能な各グループの最下位の元の位置Ｐｊは以下によって表すことができる。
Ｐｊ＝１＋（ｊ−１）Ｎｒ−１
ここで、ｊ＝｛１，２，３…｝であり、Ｎはアルファベットの要素数であり、ｒは行番号である。
【００３６】
したがって、
（ｊ−１）＝（Ｐｊ−１）／Ｎｒ−１
【００３７】
よって、任意の位置Ｐｔのソースパターン文字列について、グループリーダの位置ｎを求めるには、
ｎ＝１＋ｑｕｏｔｉｅｎｔ（Ｐｔ−１）／Ｎｒ−１
となる。
【００３８】
グループリーダの位置ｎがルートグループリーダ級数の要素であるかどうかを判断するステップは、この方程式を使用して行うことができる。
Ｒ＝ｒｅｍａｉｎｄｅｒ（（ｎ−Ｐｐ）ＮＬｐ）
ここで、Ｐｐは、可能なターゲットパターンの順序列内におけるターゲットパターンの位置であり、Ｌｐは、ターゲットパターンの要素数である。
【００３９】
Ｒ＝０の場合、グループリーダの位置は、ルートグループリーダ級数の要素である。
【実施例１】
【００４０】
上記ステップを実行するアルゴリズムを本明細書では擬似コードで提示する。
Ｎ−アルファベットの要素数
Ｔ−ソースパターン文字列
Ｐ−ターゲットパターン文字列
Ｌｔ−Ｔの長さ
Ｌｐ−Ｐの長さ
Ｐｔ−Ｔの位置番号
Ｐｐ−Ｐの位置番号
Ｒｈ−特定の文字列のａｃ出力の範囲の高い値
Ｒｌ−特定の文字列のａｃ出力の範囲の低い値
【００４１】
function Pattern_match
{                                                             /* 一時変数 */
int Liter, z, d, n, m, temp;
Ld = Lt - Lp;
Liter = Ld;
/* Pt & Ppは、以下で与えられる方程式（２）から計算される */
If (Ld = 0 ) and (Pt = Pp)                         /* 等しい長さの文字列 */
Msg("Both match")
Exit Function;
/* ２つの等差級数は、an = a0 +(n-1)及びbm = b0 + (m-1)zによって与えられる */
Loop for Ld + 1 times
{
/* グループ等差級数においてソースデータのグループリーダ位置（ｎ）を見つける */
an = Pt;    a0 = 1;    d = power(N, Liter);
temp = quotient((an - a0)/d);
n = temp + 1;
/* 「n」がルートグループリーダ級数に含まれるかどうかをチェックする */
bm = n;    b0 = Pp;    z = power(N, Lp);
r = remainder((bm - b0)/z);
if (r = 0)
Msg("pattern match success at position:" ((Ld + 1) - Liter));
Liter = Liter - 1;
}                                  /* ループ終了 */
}
【００４２】
次に、図２から図４に示す例を使用してこのアルゴリズムを処理する。
ソースデータの位置Ｐｔ＝１５８となるように、ソースパターン文字列が入力されるものと考える。
【００４３】
まず、行４においてパターンマッチを探す。
【００４４】
Liter = Lt - Lp = 4 - 1 = 3
/* グループ等差級数においてソースデータのグループリーダ位置（ｎ）を見つける */
an = Pt = 158     a0 = 1     d = power (N, Liter) = 53 = 125
temp = quotient((an - a0)/d) = quotient((158 - 1)/125) = 1;
n = temp + 1 = 2;
/* 「n」がルートグループリーダ級数に含まれるかどうかをチェックする */
bm = n = 2;    b0 = Pp = 2;    z = power(N, Lp) = 5;
r = remainder((bm - b0)/z) = remainder((2-2)/5) = 0;
r = 0 したがって、位置１においてパターンマッチがある
【００４５】
次に、行３においてパターンマッチを探す。
【００４６】
Liter = Liter - 1 = 2
/* グループ等差級数においてソースデータのグループリーダ位置（ｎ）を見つける */
an = Pt = 158     a0 = 1     d = power (N, Liter) = 52 = 25
temp = quotient((an - a0)/d) = quotient((158 - 1)/25) = 6;
n = temp + 1 = 7;
/* 「n」がルートグループリーダ級数に含まれるかどうかをチェックする */
bm = n = 7;    b0 = Pp = 2;    z = power(N, Lp) = 5;
r = remainder((bm - b0)/z) = remainder((7-2)/5) = 0;
r = 0 したがって、位置２においてパターンマッチがある
【００４７】
次に、行２においてパターンマッチを探す。
【００４８】
Liter = Liter - 1 = 1
/* グループ等差級数においてソースデータのグループリーダ位置（ｎ）を見つける */
an = Pt = 158     a0 = 1     d = power (N, Liter) = 51 = 5 
temp = quotient((an - a0)/d) = quotient((158 - 1)/5) = 31;
n = temp + 1 = 32;
/* 「n」がルートグループリーダ級数に含まれるかどうかをチェックする */
bm = n = 32;    b0 = Pp = 2;    z = power(N, Lp) = 5;
r = remainder((bm - b0)/z) = remainder((32-2)/5) = 0;
r = 0 したがって、位置３においてパターンマッチがある
【００４９】
最後に、行１においてパターンマッチを探す。
【００５０】
Liter = Liter - 1 = 0
/* グループ等差級数においてソースデータのグループリーダ位置（ｎ）を見つける */
an = Pt = 158     a0 = 1     d = power (N, Liter) = 50 = 1 
temp = quotient((an - a0)/d) = quotient((158 - 1)/1) = 157;
n = temp + 1 = 158;
/* 「n」がルートグループリーダ級数に含まれるかどうかをチェックする */
bm = n = 158;    b0 = Pp = 2;    z = power(N, Lp) = 5;
r = remainder((bm - b0)/z) = remainder((158-2)/5) = 1;
r ≠ 0 したがって、位置４においてパターンマッチはない
【００５１】
ターゲットパターンが複数の文字から成る場合も、同じアルゴリズムを使用することができる。
【００５２】
算術符号では、文字列は、数直線上の区間によって表される。
区間のサイズは、アルファベットのシンボルの確率によって決まる。
確率が等しい場合、文字列の位置番号
Ｐ＝Ｒｈ／（Ｒｈ−Ｒｌ）                                        方程式（２）
を計算することは簡単な事柄である。
ここで、Ｒｈは区間の最高値であり、Ｒｌは区間の最低値である。
【００５３】
アルファベットの異なる要素が異なる確率を有する場合であっても、位置番号を求めることができる。
ただし、これは、確率が等しい場合ほど簡単ではない。
アルファベット集合の各要素の確率及びソースパターンの長さを考慮して、対象となる区間に対応する位置番号を設定する。
したがって、算術圧縮されたデータに対して操作する場合、符号化された区間の位置番号が計算される。
この位置番号は、ターゲットパターンの位置番号と共に、上記アルゴリズムへの入力となる。
【実施例２】
【００５４】
ソースシーケンスは、そのソースシーケンスの長さを有するアルファベットの要素のすべての可能な組み合わせのリストにおける位置、すなわちソース語彙における位置として表すことができる。
ソースシーケンス自体は、実際には、基数ｎ（ｎはアルファベットの要素数である）で表される場合、アルファベットの要素が基数ｎにおける数字を表す位置である。
【００５５】
ソースシーケンスのすべての部分シーケンスの位置の集合であって、その部分シーケンスの長さを有するアルファベットの要素のすべての可能な組み合わせの語彙内における、位置の集合、を計算することができる。
なお、この位置の集合は、ソースシーケンスの最初の文字の位置を含む。
この集合は、次の要素、すなわち、基数ｎにおけるソースシーケンス位置の長さについて、基数ｎにおけるソースシーケンスの最初の数字、最初の数字及び２番目の数字、最初の数字及び２番目の数字及び３番目の数字等を含む。
【００５６】
ソース語彙内において、ターゲットシーケンスを含む「語（word）」は、ｎをターゲットシーケンスの長さで個別にべき乗したものである。
したがって、ターゲットシーケンスを含む最初の「語」の位置を使用すると、ターゲットシーケンスを含む「語」の位置の級数を定義することができる。
【００５７】
同じ基数及び相関手順で表す必要のある集合及び級数は、可能なターゲットシーケンス位置のいずれかがソース部分シーケンス位置と等しいかどうかを調べるのに実施することができる。
【００５８】
集合が最小の要素から最大の要素へ順序付けられている場合、ターゲット級数にもマッチする当該集合の要素の位置は、ターゲットシーケンスの最も右の要素のソースシーケンスの位置を表す。
【００５９】
もちろん、ソース部分シーケンス位置の集合は、剰余方程式を使用することによって、０（ｎ）で可能なターゲット位置の級数に対してマッチングを行うことができる。
【００６０】
このように、｛Ｘ１…Ｘｍ｝及び｛Ｙ１…Ｙｑ｝が有限順序集合｛Ｚ１…Ｚｏ｝の元である場合にターゲットシーケンス［Ｘ１…Ｘｍ］がソースシーケンス［Ｙ１…Ｙｑ］内に存在するかどうかは、
ｉ．Ｖｋ＝ｊ：Ｙｋ＝Ｚｊである場合に、基数ｏにおけるソース部分シーケンス値の集合｛［Ｖ１］，…［Ｖ１…Ｖｋ］，…［Ｖ１…Ｖｎ］｝を構成すること、及び
ｉｉ．Ｄｋ＝ｈ：Ｘｋ＝Ｚｈとなるようにｐが基数ｏにおける番号［Ｄ１…Ｄｎ］である場合に、上記集合のいずれかの値がターゲット値の級数｛ｐ，…ｐ＋ｋｏｍ，…ｐ＋ｎｏｍ｝に対応するかどうかを判断すること
によって判断することができる。
【００６１】
ステップｉｉにおいて、上記集合のいずれかの値が上記級数に対応するかどうかを判断するには、集合のその値について、以下のアルゴリズム
Ｒ＝ｒｅｍａｉｎｄｅｒ（（Ｎ−ｐ）／ｏｍ）
の結果が０でなければならない。
ここで、Ｎは基数１０の集合の元である、
【００６２】
この方法は、さまざまな標準的なデータ処理デバイスを使用して実施することもできるし、専用グラフィックスオーディオ処理デバイス又はシーケンシングデバイス（sequencing device）を使用して実施することもできる。
例えば、この方法は、ＭＩＣＲＯＳＯＦＴ  ＷＩＮＤＯＷＳ（登録商標）環境下で動作するパーソナルコンピュータに配備することもできるし、ＵＮＩＸ（登録商標）オペレーティングシステム下で動作するサーバマシンに配備することもできる。
【００６３】
この方法は、デバイス上で実行されるソフトウェアで実施することもできるし、専用ハードウェアで実施することもできることが理解されよう。
【００６４】
さらに、この方法は、複数のコンピュータ又はサーバにわたって分散して配備できることも当業者には理解されよう。
【００６５】
本発明は、算術圧縮されたソースデータを伸張することなく、そのデータのパターンマッチングを行うための最初の方法を表すものと考えられる。
また、本発明は、圧縮されたターゲットパターン文字列を使用して動作することもできる。
本発明は、算術デコーダ局で非常に役立つはずである。
この算術デコーダ局では、デコーダは、通常、あらゆる前のデータ列との部分マッチ又は全マッチをチェックすることができる。
本発明は、ソースパターン文字列において、すべてのパターンマッチ、１つのパターンマッチ、又は特定の位置におけるパターンマッチを見つけるのに使用することができる。
また、特定の区間の探索が、他の区間の探索とは独立して実行できるので、本発明は、並列に実行することもできる。
すなわち、本発明は、同時に２つ以上のソース文字列に適用することができる。
また、本発明は、例えば通信ネットワークを介してアクセス可能なサーチエンジンといった分散システムで動作することもできる。
【００６６】
本発明の実施の形態を説明することによって本発明を示し、これらの実施の形態を詳細に説明してきたが、添付の特許請求の範囲をこのような詳細に制限することも、多少なりとも限定することも、本出願人の意図ではない。
別の利点及び変更は、当業者には容易に理解される。
したがって、より広い態様における本発明は、具体的な詳細、代表的な装置及び方法、並びに図示して説明した例示に限定されるものではない。
したがって、本出願人の包括的な発明概念の趣旨又は範囲から逸脱することなく、このような詳細から逸脱することが可能である。
【図面の簡単な説明】
【００６７】
【図１】アルファベット集合が｛０，１｝である場合のターゲットパターン「１」を含む長さ４のソースパターン文字列の位置のチャートである。
【図２】アルファベット集合が｛ａ，ｂ，ｃ，ｄ，ｅ｝である場合のターゲットパターン「ｂ」を含む長さ４のソースパターン文字列のチャートである。
【図３】アルファベット集合が｛ａ，ｂ，ｃ，ｄ，ｅ｝である場合のターゲットパターン「ｂ」を含む長さ４のソースパターン文字列の位置番号のチャートである。
【図４】位置番号が一定の倍率で拡大されるように配置された図３と同様のチャートである。
【図５】パターンマッチングアルゴリズムを示すフローチャートである。
【図１】
2006522401.tif 000006
【図２】
2006522401.tif 000007
【図３】
2006522401.tif 000008
【図４】
2006522401.tif 000009
【図５】
2006522401.tif 000010
【国際調査報告】
2006522401.tif 000011
2006522401.tif 000012
2006522401.tif 000013
2006522401.tif 000014