(57)【特許請求の範囲】
【請求項１】
メモリバッファ内に格納されたデータシーケンスを表すサフィックスアレイを生成するステップであって、前記サフィックスアレイは、前記メモリバッファ内のバッファ位置として生成され、前記バッファ位置は、個々のバッファ位置でデータシーケンスを開始するデータ文字列に従って並べられる、ステップと、
前記サフィックスアレイをトライ構造に変換するステップであって、前記サフィックスアレイの代わりに当該トライ構造が生成されるように前記メモリバッファ内の前記サフィックスアレイを上書きするトライ構造に変換するステップと、
前記トライ構造のノードによってそれぞれ表される少なくとも２つのデータシーケンスに共通するサブ文字列を列挙するステップと、
を含む、方法。
【請求項２】
前記サフィックスアレイは、前記トライ構造を前記サフィックスアレイの連続するサフィックスから徐々に更新することによって、前記トライ構造に変換される、請求項１に記載の方法。
【請求項３】
前記トライ構造は、各ノードが前記サフィックスアレイの１つまたは複数のサフィックスを表す複数のノードを備え、各連続するサフィックスは、前記トライ構造内の既存のノードでグループ化されるか、前記トライ構造の新たなノードとして追加される、請求項１に記載の方法。
【請求項４】
前記サフィックスアレイのサフィックスは、当該サフィックスが前記トライ構造内の既存のノードとしてデータシーケンスの共通一致長を有するとき、前記既存のノードでグループ化される、請求項３に記載の方法。
【請求項５】
前記トライ構造は、各ノードが、親ノードへの参照と、派生ノードのデータシーケンスの共通一致長と、最も最近トラバースされた派生ノードのデータ位置とを含む、複数のノードを備える、請求項１に記載の方法。
【請求項６】
前記派生ノードは、あるノードの直近の子ノードを含み、前記トライ構造は、
当該トライ構造が、少なくとも２つの直近の子ノードを各々有する１つまたは複数の非リーフノードを含むことと、
前記派生ノードのデータシーケンスの前記共通一致長が最大であることと、
前記トライ構造内のノードの合計数が最小であることと
に基づいて生成される、請求項５に記載の方法。
【請求項７】
前記トライ構造の生成が完了した後に、前記データシーケンスの一致を列挙するのに前記トライ構造を検索するステップをさらに含む、請求項１に記載の方法。
【請求項８】
最も最近トラバースされたノードのノードフィールドを現在の位置で更新して、前記最も最近トラバースされたノードを将来のデータシーケンスの一致に指定するステップをさらに含む、請求項１に記載の方法。
【請求項９】
少なくともメモリと、列挙サービスを実装するプロセッサと
を備えたコンピューティングデバイスであって、
前記列挙サービスは、
メモリバッファ内に格納されたデータシーケンスを表すサフィックスアレイを生成することと、
前記サフィックスアレイをトライ構造に変換することであって、前記トライ構造は、当該トライ構造が前記サフィックスアレイの代わりに生成されるように前記メモリバッファ内の前記サフィックスアレイを上書きし、前記トライ構造は、各ノードが前記サフィックスアレイの１つまたは複数のサフィックスを表す複数のノードを含み、各連続するサフィックスが前記トライ構造内の既存のノードでグループ化されるか、前記トライ構造の新たなノードとして追加される、前記トライ構造に変換することと、
前記トライ構造のノードによってそれぞれ表される少なくとも２つのデータシーケンスに共通するサブ文字列を列挙することと、
を行うように構成される、コンピューティングデバイス。
【請求項１０】
コンピューティングデバイスによって実行されると、該コンピューティングデバイスに、
メモリバッファ内に格納されたデータシーケンスを表すサフィックスアレイを生成させ、
前記サフィックスアレイをトライ構造に変換させることであって、前記トライ構造は、当該トライ構造が前記サフィックスアレイの代わりに生成されるように前記メモリバッファ内の前記サフィックスアレイを上書きし、前記トライ構造は、各ノードが前記サフィックスアレイの１つまたは複数のサフィックスを表す複数のノードを含み、各連続するサフィックスが前記トライ構造内の既存のノードでグループ化されるか、前記トライ構造の新たなノードとして追加される、前記トライ構造に変換させ、
前記トライ構造を検索して、前記トライ構造のノードによってそれぞれ表される少なくとも２つのデータシーケンスに共通するサブ文字列を列挙させる、
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、圧縮一致列挙に関する。
【背景技術】
【０００２】
コンピューティングデバイスは、データ圧縮の様々な技術を実行してデータバイトを圧縮し、それにより、より少ないメモリおよび他のコンピューティングデバイスリソースを用いて、データを格納し、処理し、保持し、および／または通信する。従来のデータ圧縮技術は、処理リソースの観点から非効率的であり、および／またはデータの一致（例えば、繰り返しのデータシーケンス）を見つけてそのデータを圧縮することにおいて信頼できないことがある。例えば、ＬＺＸおよびＬＺＭＡなどのいずれかのＬＺ７７圧縮実装の主要な課題は、効率的かつ信頼できるように、最小に圧縮されたデータを生成するデータ一致を見つけることである。
【０００３】
様々なＬＺ７７圧縮のアルゴリズムは、繰り返しのバイトシーケンスを決定し、一致を（距離，長さ）のペアを用いてエンコードすることを試みる。圧縮アルゴリズムは、各位置においてバッファを最初から最後まで処理し、可能性のある一致は、バッファの前方からのバイトシーケンスであり、このバイトシーケンスはバッファの現在の位置におけるバイトと同じである。バッファに戻る距離がより短いと、より少ないビットでエンコードされ、より長い距離はより多くのデータを網羅する。距離は、バッファ内のデータ一致の間の距離をバイトで示し、長さは、一致するデータバイトの数を示す。良い圧縮比を得るために、アルゴリズムは、バッファ内の各位置について、可能性のある各長さの最短の距離を列挙すべきである。高速にするためには、アルゴリズムは、長さに対する距離が最短の距離ではない一致を列挙するのに時間をかけるべきではない。例えば、バッファ内のある位置において、可能性のある一致の全てのセットが、（距離＝５０，長さ＝３）、（１００，４）、（１２０，３）、（１５０，４）、（２００，５）であるとする。アルゴリズムは、（５０，３）、（１００，４）、および（２００，５）のみを列挙するであろう。なぜなら、他の２つ（１２０，３）および（１５０，４）は、少なくとも同じ長さ（例えば、長さ３または４）であるが、距離がより近い一致に取って代わられるためである。最適化の観点から、アルゴリズムは素早く、パレートフロンティアの一致を列挙すべきであるが、この場合、２つの最適化基準は、より長い長さとより短い距離である。
【０００４】
ＬＺＸアルゴリズムは、スプレーツリーを使用して圧縮の一致を決定し、問題を解決する。スプレーツリーは二分木であり、新しい要素はルートに追加される。これは、当該アルゴリズムがツリーを検索して一致を決定するとき、最初に、最も最近の、したがって最短の距離の一致に遭遇する、という特性を提供する。このアルゴリズムは、文字列がアルファベット順で挿入される場合など、ツリーがアンバランスになる場合は実行が難しく、実際、ＬＺＸアルゴリズムは、大きな一致履歴に対してスケーリングしにくい。
【０００５】
ＬＺＭＡアルゴリズムは、ハッシュチェーン、二分木、およびパトリシアトライの変形を使用して、圧縮一致を決定し、問題を解決することができる。また、ツリーの各ノードにおいて最も最近挿入されたデータ文字列の何らかの概念を用いて、ツリー実装が修正される場合、問題を解決することができる空間効率的なツリー実装の技術がいくつか存在する。しかしながら、これらの技術は、ツリー構造を、当該ツリーのルートから下位レベルのノードまで階層を下の方にトラバースするように実装され、最近の一致が長い長さであるときにも次善的なものである。
【発明の概要】
【０００６】
この発明の概要は、圧縮一致列挙の概念を簡略化した形で紹介し、この概念は、以下の発明の詳細な説明でさらに説明され、および／または図面に示される。この発明の概要は、特許請求される主題の本質的特徴を説明するものと解釈されるべきではなく、特許請求される主題の範囲を決定または限定するのに用いられるべきでもない。
【０００７】
圧縮一致列挙は、リーフからルートへの（ｌｅａｆ−ｔｏ−ｒｏｏｔ）トライ構造を用いて、格納されたデータシーケンスにおけるデータ一致の可能性の全てを列挙するのに実装される。諸実施形態において、メモリバッファ内に格納されたデータシーケンスを表すサフィックスアレイを生成することができる。次いで、サフィックスアレイをトライ構造に変換することができる。トライ構造は、当該トライ構造がサフィックスアレイの代わりに生成されるように、メモリバッファ内のサフィックスアレイを上書きする。トライ構造は、各ノードがサフィックスアレイの１つまたは複数のサフィックスを表す複数のノードを含み、各連続したサフィックスは、トライ構造内の既存のノードでグループ化されるか、トライ構造の新たなノードとして追加される。サフィックスアレイのサフィックスが既存のノードとしてデータシーケンスの共通の一致長を有するとき、当該サフィックスをトライ構造のその既存のノードでグループ化することができる。その後、トライ構造から決定されるように、データシーケンスを列挙することができる。
【０００８】
他の実施形態において、サフィックスアレイは、メモリバッファ内のバッファ位置のアレイであり、バッファ位置は、個々のバッファ位置でデータシーケンスを開始するデータ文字列によって、アルファベット順にソートされる。サフィックスアレイは、サフィックスアレイの連続するサフィックスから徐々にトライ構造を更新することによって、トライ構造に変換することができる。トライ構造のノードはそれぞれ、親ノードへの参照、派生ノード（例えば、あるノードの直近の子ノードを含む）のデータシーケンスの共通の一致長、および最も最近トラバースされた派生ノードのバッファ位置を含む。トライ構造を以下に基づいて生成することができる。すなわち、トライ構造が、各々が少なくとも２つの直近の子ノードを有する、１つまたは複数の非リーフノードを含むことと、派生ノードのデータシーケンスの共通の一致長が最大であることと、トライ構造内のノードの合計数が最小であることとに基づいて、トライ構造を生成することができる。
【０００９】
圧縮一致列挙の諸実施形態を、図面を参照して説明する。図面を通して同じ符号を用いて図面内に示される同様の特徴および構成要素を指す。
【図面の簡単な説明】
【００１０】
【図１】圧縮一致列挙の諸実施形態を実装することができる例示的システムを示す図である。
【図２】１つまたは複数の実施形態にかかる、トライ構造および圧縮一致列挙の例を示す図である。
【図３】１つまたは複数の実施形態にかかる、圧縮一致列挙の例示的方法を示す図である。
【図４】圧縮一致列挙の諸実施形態を実装することができる例示的なデバイスの様々な構成要素を示す図である。
【発明を実施するための形態】
【００１１】
格納されたデータシーケンスにおけるデータ一致の可能性の全てを列挙する、圧縮一致列挙の諸実施形態を説明し、実装する。ＬＺ７７圧縮アルゴリズムなどにおいて用いられるような圧縮一致列挙は、リーフからルートへのトライ構造を用いてデータ一致を列挙する。諸実施形態において、メモリバッファに格納されるデータシーケンスを表すサフィックスアレイが生成される。サフィックスアレイは次いで、トライ構造に変換される。トライ構造は、当該トライ構造がサフィックスアレイの代わりに生成されるように、メモリバッファ内のサフィックスアレイを上書きする。ノードが可変の数の子ノードを有する可能性があるために、トライ構造内のノードの子ノードへの参照を格納することは一般に複雑であるので、トライ構造内のノードの子ノードへの参照を格納するのではなく、トライ構造のノードはそれぞれ、親ノードへの参照と、派生ノードのデータシーケンスの共通の一致長と、最も最近トラバースされた派生ノードのバッファ位置とを含む。派生ノードは、あるノードの直近の子ノード、または任意の他の子ノード、孫ノード、もしくは派生ノードを含む可能性がある。
【００１２】
圧縮一致列挙の特徴および概念を、任意の数の異なるデバイス、システム、環境、ネットワーク、および／または構成において実装することができ、圧縮一致列挙の諸実施形態は、以下の例示のデバイス、システム、および方法のコンテキストで説明される。
【００１３】
図１は、圧縮一致列挙の様々な実施形態を実装することができる例示的なシステム１００を図示している。例示的なシステムは、コンピューティングデバイス１０２を含む。コンピューティングデバイス１０２は、列挙された圧縮データマッチングを実行する任意のタイプのサーバ、コンピュータ、またはデバイスとすることができる。本明細書で参照されるコンピューティングデバイスのいずれも、１つまたは複数のプロセッサおよびメモリデバイスだけでなく、図４に示される例示的デバイスを参照してさらに説明されるような任意の数の種々の構成要素およびそれらの構成要素の組み合わせなど、様々な構成要素を用いて実装することができる。
【００１４】
例示的システム１００において、コンピューティングデバイス１０２は、格納されたデータシーケンス１０６を格納または保持するメモリバッファ１０４を含む。メモリバッファは、任意のタイプのメモリ、記憶媒体、および／または適切な電子的データ記憶などのデータ記憶を可能にする、任意のタイプのコンピュータ読取可能記憶媒体として実装することができる。格納されたデータシーケンス１０６は、メモリ内に格納されたバイトであり、メモリは、データのより小さい表現へと認識して圧縮することができる、反復的なバイトシーケンスを有することがある。
【００１５】
圧縮一致列挙の諸実施形態は、格納されたデータシーケンスにおけるデータ一致の可能性の全てを列挙するように実装される。例えば、「ａｂａｃｄｅ」というデータ文字列は、第１のバッファ位置でデータシーケンスを開始する。「ａｂａｃｆｄ」という第１の可能性のある一致が、第２のバッファ位置において決定され、この一致を、「ａｂａｃ」という４バイトの一致と、第１のバッファ位置と第２のバッファ位置との間の距離が１，０００バイトであることについて、（長さ＝４、距離＝１，０００）によって表すことができる。第２の可能な一致「ａｂａｃｄｆ」が第３のバッファ位置において決定され、この一致は、「ａｂａｃｄ」という５バイトの一致と、第１のバッファ位置と第３のバッファ位置との間の距離が１０，０００バイトであることについて、（長さ＝５、距離＝１０，０００）と表すことができる。
【００１６】
コンピューティングデバイス１０２は、本明細書で説明される圧縮一致列挙の諸実施形態を実装する列挙サービス１０８も含むことができる。列挙サービスを、ソフトウェアアプリケーションおよび／またはアルゴリズムなどのコンピュータ実行可能命令として実装し、コンピューティングデバイスの１つまたは複数のプロセッサによって実行することができる。この例において、列挙サービスは、コンピューティングデバイスの構成要素として実装されるように示される。あるいは、列挙サービスは、圧縮一致列挙の諸実施形態を実装する独立のソフトウェアアプリケーション、アルゴリズム、ネットワークベースのサービスとして構成することもできる。
【００１７】
諸実施形態において、列挙サービス１０８は、格納されたデータシーケンス１０６を表すサフィックスアレイ１１０を生成するように実装される。データシーケンス１０６は、メモリバッファ１０４に格納される。サフィックスアレイは、メモリバッファ内の全てのバッファ位置（例えば、サフィックス）のアレイであり、バッファ位置を、個々のバッファ位置の各々においてデータシーケンスを開始するデータ文字列によって、アルファベット順にソートすることができる。サフィックスアレイを生成する技術は公知であり、様々な技術のいずれかを列挙サービスにより実装して、サフィックスアレイを生成することができる。
【００１８】
列挙サービス１０８は次いで、サフィックスアレイ１１０をトライ構造１１２に変換するように実装される。トライ構造１１２は、当該トライ構造１１２がサフィックスアレイの代わりに生成されるように、メモリバッファ１０４内のサフィックスアレイを上書きする。これは、サフィックスアレイからトライ構造を生成または構築するのに追加のメモリを必要としないので、メモリが節約される。サフィックスアレイは、当該サフィックスアレイの連続するサフィックスから徐々にトライ構造を更新することによって、トライ構造に変換される。トライ構造は、ルートノードから開始して次第に下位レベルの階層に広がっていくのではなく、リーフからルートへと生成される。リーフノードをトライ構造に追加して、トライ構造のルートノードに向かって次第に縮小する、すなわちルートノードを決定する。列挙サービスは次いで、トライ構造が生成または構築された後、トライ構造の検索を開始して、トライ構造から決定されたデータシーケンスの一致１１４を列挙する。
【００１９】
トライ構造１１２の例１１６が、サフィックスアレイ１１０のサフィックスから生成される幾つかのトライノード１１８とともに示されている。トライ構造は、例示のリーフノード１２０などのリーフノードを含み、このリーフノードはそれぞれ、サフィックスアレイ１１０の１つのサフィックスに対応する。トライ構造は、例示の非リーフノード１２２などの非リーフノードも含む。リーフノード１２０は、トライ構造内における親ノードに対する子ノードとすることもでき、一方、非リーフノード１２２は、トライ構造内における子ノードと親ノードの双方とすることができる。
【００２０】
トライ構図１１２の例１１６は、大きなデータ文字列からのサフィックスを幾つかアルファベット順に図示しているにすぎない。メモリバッファ１０４内の格納されたデータシーケンス１０６は、圧縮一致列挙が適用される、非常に大きなデータセットとすることができる。矢印は、親ノード参照ポインタを表し、数字は、直近の子ノードを含め、特定のノードの派生ノードの全てのデータシーケンスについての共通一致長を表す。例えば、データシーケンス「ａｂｃｅｂ」を有するデータノード１２０は、非リーフノード１２２への親ノード参照を含んでおり、この場合、４という共通一致長は、２つの子ノードのデータシーケンスを表している。
【００２１】
トライ構造は、サフィックスアレイから効率的に構築することができる。なぜなら、幾何学的に言うと、トライ構造が生成されるときに、親ノードポインタの線が相互に交わることのない、平面図であるからである。それぞれの後続リーフノード１２０がトライ構造１１２内で接続されると（および、非リーフエントリが、後のエントリによって参照不可能となると）、新たなリーフノードが接続されるノードのセットは、この平面的特性のために小さくなり、これにより、圧縮一致列挙の諸実施形態における効率的かつ簡単なアルゴリズムが得られる。
【００２２】
トライ構造は基本的にツリー構造であり、このツリー構造では、一致するサブ文字列が共通ノードの下にグループ化され、これらのノードが、より短い一致を効率的にグループ化する他のノードの下でグループ化される。ノードから子ノードへの情報は必要とされず、格納されない。むしろ、トライ構造のトライノード１１８は、親ノード参照と、派生ノード（例えば、直近の子ノードを含む）のデータシーケンスの共通一致長と、最も最近トラバースされた派生ノードのノードバッファ位置とについてのノードフィールドを含む。親ノード参照のフィールドと共通一致長のフィールドとの双方を、例えば、親ノード参照インデックスに２６ビットを使用し、共通データシーケンス長に６ビットを使用して、１つの３２ビット値に格納することができる。より長い長さを、３２ビット値に格納可能な最大の長さにキャップすることができる。
【００２３】
列挙サービス１０８がトライ構造１１２を構築すると、列挙サービスの３つのアルゴリズムの不変条件が保持される。第１に、全ての非リーフノード１２２が、少なくとも２つの直近の子ノードを有する。第２に、あるノードの派生ノードの共通一致長は最大である（例えば、１０の文字列位置が長さＬを有し、この文字列位置のうちの２つが、共通する長さＬ＋１を有する場合、これら２つの文字列位置がこれら自身のノードの下にグループ化される）。第３に、これらの制約内において、トライ構造内のノードの合計を最小にする（例えば、２つの文字列位置またはサブノードを共通ノードの下でグループ化することができる場合、これらを、その共通ノードの下でグループ化する必要がある）。
【００２４】
列挙サービス１０８は、サフィックスアレイ１１０のサフィックス（例えば、バッファ位置）を、当該サフィックスがサフィックスアレイ内で発生する順序で処理し、このサフィックスアレイとともに計算される、最長の共通のプレフィックスフィールドに基づいて決定を行う。最長の共通プレフィックスフィールドは、どれほど多くのサフィックスが辞書学的に最も近いサフィックスに一致するかの長さを示す。一致長を増大する小さなスタックが保持され、トライノード１１８は、プレフィックス長が減少するとき、そのスタックを展開することによって構築される。ある実装において、スタックは、一致長が６ビット数としてキャップされるので小さい。スタックのエントリが、将来のノードが接続され得る全ての既存のノードのセットを表すか、あるいは、トライ構造が生成されるとき、新たなリーフノード１２０を作成することができる。サフィックスアレイの各サフィックスに関して、サフィックスを、適切な長さの既存のノードでグループ化することができ、あるいはサフィックスを使用してトライ構造の新たなリーフノードを生成することができる。非リーフノードは、適切な長さのノードに対する検索の間にスタックが展開されるように、親ノードを割り当てられる。これらのグループ化の決定は、上述の３つのアルゴリズムの不変条件に基づいている。
【００２５】
トライ構造１１２内の非リーフノード１２２の空間は、サフィックスアレイ自体から割り当てられ、そして、割り当てられる非リーフノードの数は、処理されるサフィックスの数よりも少ないことが容易に実証されるので、これは、サフィックスアレイ１１０を新たなトライ構造で徐々に上書きする、「インプレース」方法である。上述のように、このことにより、２つの大きなデータ構造（例えば、サフィックスアレイ１１０とトライ構造１１２）の双方が同時に格納されることがないので、メモリが節約される。各リーフノード１２０は、サフィックス（例えば、バッファ位置）に対応し、各リーフノードの親ノードは、反対のサフィックスアレイを上書きすることによって格納される。
【００２６】
列挙サービス１０８は、一致列挙検索方法も実装し、各バッファ位置について順に、トライ構造内においてリーフノードからルートノードへと親ノードのポインタをたどる。各非リーフノード１２２（トライノード１１８によっても表される）は、親ノード参照と、共通一致長と、直近の子ノードを含め、最も最近トラバースされた非リーフノードからの派生ノードの派生ノードバッファ位置（例えば、この処理の間に、非リーフノードを最も最近「訪問した」派生ノードのバッファ位置）とを格納または保持する。他のノードからの後続のトラバースに関して、これらのノードフィールドは、リーフノードからルートノードへのリーフ・ルート経路に沿った各長さについて、最短距離のデータシーケンスの後方一致を提供する。その後、検索段階におけるトライ構造に関して変化するノードフィールドのみが、各非リーフノードに関連付けられた、最も最近トラバースされた派生ノードについての派生ノードバッファ位置フィールドである。
【００２７】
データシーケンスの最新の一致が長い一致でもあり、トライ構造１１２内に表された、異なる長さの多くの短い一致が存在する場合、次いで、トライ構造が徐々にトラバースされると、同じデータ一致が何度も発生する。例えば、長さ１０の最短距離の一致は、長さ９、８、７などの最短距離の一致とすることもできる。簡単な解決策は、トライ構造内の各非リーフノードに対して、８バイトのメモリを用いること、例えば、親ノード参照に約４バイト、派生ノードのバッファ位置（例えば、最も最近見た位置）に概ね約４バイト、および共通一致長に何バイトかを用いることである。しかしながら、トライ構造内の非リーフノード毎に８バイト使用し、リーフノード毎に４バイト使用すると、合計メモリ使用量はノード数の１２倍（１２ｎ）になる。トライ構造内の非リーフノードに４バイトのみを使用することによって、この合計メモリ使用量をノード数の８倍（８ｎ）まで減少することができる。
【００２８】
メモリを節約するために、列挙サービスは、リーフから親への参照のみを順に使用し、位置に関するデータ一致が見つかると、その位置のデータリーフはもはや必要とされない、ということに利点がある。メモリバッファは前方に向かってトラバースされるので、メモリ空間は、以前は反対のサフィックスアレイであり、トライ構造１１２の構築中に上書きされたものから利用可能になり、この利用可能なメモリ空間を使用して、情報の全てを格納することができる。ある実装において、フィールドは、親自体をルックアップする「親ノード空間」に格納されるが、これは、この利用可能なメモリ空間が、ノードの親の記憶に隣接する可能性が低いからである。リーフから親へのアレイを追加のメモリとして使用するとき、最も最近見たノードフィールドは、ちょうどそのようなフィールドに近い。したがって、（例えば、サフィックスアレイとなるように使用される）トライ構造の非リーフ部分において、親ノード参照は、最も最近見た位置で置換され、元の親ノード参照は次いで、最も最近見た位置のリーフ親ノードに以前に使用されたメモリ内に格納され、ここには、そのノードから最も最近見た位置を知ることによって到達することができる。したがって、検索方法がトラバースまたは訪問する各ノードについて、親ノード参照と、最も最近トラバースされた派生ノードと、派生ノードの共通一致長の３つのノードフィールドを決定することができる。
【００２９】
このことはメモリ使用を節約するだけでなく、長くかつすぐ近くのデータ一致が決定されるとき、トラバースする必要のないトライ構造内のノードをスキップすることもできる。これは、最近の位置の全体が、実際には、１つの親ノード参照のみに対するメモリ空間を有する、リーフからルートへの経路における各ノードについて最も最近トラバースされた（例えば、最も最近見た）位置であるためである。最初は、ＮＵＬＬ参照を格納して、親ノードがトライ構造のルートノードであることを示すことができる。次いで、次のノード位置を処理すると、次のノード位置が、ルートノードにおいて見られるような、最も最近トラバースされた位置となり、以前の最も最近トラバースされた位置の親参照は、双方の位置に共通するノード（便宜上、トラバースの「現在」のノードである）を参照するように更新される。これは、ルートノードだけでなく、トライ構造の全てのノードにおいて行われ、古い位置は段々とトライ構造の下の方にいく。トライ構造を継続的に変更および更新するこの技術は、同じ一致長を複数回繰り返すことや、明らかに次善的な一致を列挙することなど、トライ構造をトラバースするときに不必要なステップをスキップすることにおいて効率的である。
【００３０】
図２は、トライ構造２００の例、および本発明で説明される圧縮一致列挙の実施形態にしたがって、図１を参照して説明した列挙サービス１０８がどのように実装され、トライ構造を検索して更新するかを図示している。２０２において、サフィックスアレイから変換されるときに、任意の一致列挙に先行して構築されるようなトライ構造を示している。トライ構造のノードはノード２０４から２２０として識別され、リーフノードのボトムレイヤは、リーフノードが列挙サービスによって処理される順序を示す、Ｐ１からＰ４としても識別される。一致列挙を実行するのに２つの基本的な原則に従う。第１に、以前にトラバースされた非リーフノードは、最も最近トラバースされた非リーフノードからリーフノードへポイントする。第２に、リーフノードおよび未だトラバースされていないノードは、何らかの非リーフノード（大まかに、親ノードと称され、一部の場合においてルートノートとすることができる）をポイントする。
【００３１】
２０２に示されるトライ構造から、２２４に示されるトライ構造への第１の遷移２２２において、列挙サービス１０８は、リーフノード２０４（例えば、１番目に処理されるリーフノードＰ１）に関連付けられたサフィックス（例えば、データバッファ）のデータ一致を列挙しようと試みる。この例において、処理される第１のリーフノードに合う一致はないが、トライ構造は更新され、これのよりリーフノード２０４からルートノード２２０への経路の各ノードは、自身の個々のリーフノード（例えば、これらのノードの最も最近の「訪問者」）を参照するようになる。例えば、リーフノード２０４からルートノード２２０への経路は、ノード２０１、２１６、および２１８を通る。これらのノードの各々がトラバースされると、派生ノードバッファ位置に関する個々のノードのフィールドは、リーフノードを参照するように更新される。加えて、リーフノード２０４の親ノード参照フィールドは、ルートノード２２０を参照するように更新される。
【００３２】
２２４に示されるトライ構造から、２２８に示されるトライ構造への第２の遷移２２６において、列挙サービス１０８は、リーフノード２０８からの検索経路をたどり、リーフノード（例えば、２番目に処理されるリーフノードＰ２）に関連付けられたサフィックスに対する一致を列挙する。この例において、（図では指定されていない）ある長さの一致が、（例えば、非リーフノード２１４がトラバースされた後に）トラバースされる第２の非リーフノード２１６において列挙される。ノード２１６から、一致するリーフノード２０４の位置が決定される（例えば、ノード２１６は、２２４に示されるようにリーフノード２０４を参照する）。次にトラバースすべき親ノード（この例ではルート２２０である）は、リーフノード２０４の親ノード参照フィールドから決定される（例えば、ノード２０４は、２２４に示されるようにルートノード２２０を参照する）。リーフノード２０８の元のリーフ・ルート経路内にあった非リーフノード２１８は、この例ではスキップされ、以下にさらに述べるように取り扱われることとなる。さらに、リーフノード２０８の親ノード参照フィールドは、ルートノード２２０を参照するように更新される。
【００３３】
２２８に示されるトライ構造から、２３２に示されるトライ構造への第３の遷移２３０において、列挙サービス１０８は、リーフノード２０６からの検索経路をたどり、リーフノード（例えば、３番目に処理されるリーフノードＰ３）に関連付けられたサフィックスに関する一致を列挙する。この例では、リーフノード２０４とリーフノード２０８において２つの一致が列挙される。リーフノード２０８における親ノード参照フィールドは、ノード２１６を参照するように更新され、検索経路内の非リーフノード２１２および２１６は、非リーフノード２０１と２１６をトラバースする最近のノードであるリーフノード２０６を参照するように更新される。加えて、リーフノード２０６の親ノード参照フィールドは、ルートノード２２０を参照するように更新される。
【００３４】
２３３に示されるトライ構造から、２３６に示されるトライ構造への最後の遷移２３４において、列挙サービス１０８は、リーフノード２１０（例えば、４番目に処理されるリーフノードＰ４）からの検索経路にたどる。上記においてリーフノード２０８の元のリーフ・ルート経路内のスキップされたノードである、非リーフノード２１８に遭遇する。非リーフノード２１８はまだ、トライ構造内で非リーフ構造２１８の下にある親ノード２１６を参照する第１のリーフノード２０４を参照している。検索経路はトライ構造内の高い方をトラバースすべきであるため、これは問題であるように見えることがある。しかしながら、これは、リーフノード２０４の親ノード２１６が現在の非リーフノード２１８よりも長い長さを有することを検出することによって、容易に対処される。列挙サービスは次いで、現在の非リーフノード２１８よりも短い長さのノード（この場合、ルートノード２２０である）に遭遇し、その短い長さが派生ノードではなく上位ノードを示すまで、ノード２１６からノード２０６を介して検索経路をたどり続ける。したがって、リーフノード２０６の親ノード参照フィールドは、非リーフノード２１８を参照するように更新され、リーフノード２０８の親ノード参照フィールドは、ルートノード２２０を参照するように更新される。各リーフノードの検索経路をたどってトライ構造をトラバースするアルゴリズムの動的な性質は、非常に少ない処理負荷で正確に、列挙された一致を提供する。
【００３５】
圧縮一致列挙の１つまたは複数の実施形態にかかる例示の方法３００を、図３を参照して説明する。一般に、本明細書で説明されるサービス、関数、方法、プロシージャ、構成要素、およびモジュールはいずれも、ソフトウェア、ファームウェア、ハードウェア（例えば、固定の論理回路）、マニュアル処理、およびこれらの任意の組み合わせを用いて実装することができる。ソフトウェア実装は、コンピュータプロセッサによって実行されると、指定されたタスクを実行するプログラムコードを表す。例示的な方法を、コンピュータ実行可能命令の一般的なコンテキストで説明することができ、コンピュータ実行可能命令には、ソフトウェア、アプリケーション、ルーチン、プログラム、オブジェクト、構成要素、データ構造、プロシージャ、モジュール、関数などが含まれ得る。プログラムコードを、コンピュータプロセッサに対してローカルおよび／またはリモート双方の１つまたは複数のコンピュータ読取可能記憶媒体装置に格納することができる。本方法を、分散コンピューティング環境において複数のコンピュータデバイスによって実施することもできる。さらに、本明細書で説明される特徴は、プラットフォームに独立であり、様々なプロセッサを有する様々なコンピューティングプラットフォームにおいて実装されうる。
【００３６】
図３は、圧縮一致列挙の例示的方法３００を図示している。方法のブロックを説明する順序は、限定として解釈されるようには意図されておらず、任意の数の説明される方法のブロックを任意の順序で組み合わせて、方法または代替的方法を実装することができる。
【００３７】
ブロック３０２において、メモリバッファに格納されたデータシーケンスを表すサフィックスアレイが生成される。例えば、コンピューティングデバイス１０２（図１）における列挙サービス１０８は、メモリバッファ１０４内に格納される、格納済みデータシーケンス１０６を表すサフィックスアレイ１１０を生成する。サフィックスアレイは、メモリバッファ内のバッファ位置のアレイであり、そのバッファ位置は、個々のバッファ位置でデータシーケンスを開始するデータ文字列によってアルファベット順にソートされる。
【００３８】
ブロック３０４において、サフィックスアレイは、サフィックスアレイの代わりに生成されるようにメモリバッファ内のサフィックスアレイを上書きする、トライ構造に変換される。例えば、列挙サービス１０８は、サフィックスアレイ１１０をトライ構造１１２に変換し、トライ構造がサフィックスアレイの代わりに生成されるようにメモリバッファ内のサフィックスアレイを上書きする。サフィックスアレイは、サフィックスアレイの連続するサフィックスからトライ構造を徐々に更新することによって、トライ構造に変換される。トライ構造は、各ノードがサフィックスアレイの１つまたは複数のサフィックスを表す複数のノードを含み、連続するサフィックスのそれぞれは、トライ構造内の既存のノードでグループ化されるか、トライ構造の新たなノードとして追加される。サフィックスアレイのサフィックスは、当該サフィックスが既存のノードとしてデータシーケンスの共通一致長を有するとき、トライ構造内のその既存のノードでグループ化することができる。さらにトライ構造は、次の事項に基づいて生成される。すなわち、トライ構造は、当該トライ構造が、各非リーフノードが少なくとも２つの直近の子ノードを有する、１つまたは複数のリーフノードを含むことと、派生ノードのデータシーケンスの共通一致長が最大であることと、トライ構造内のノードの合計数が最小であること、に基づいて生成される。
【００３９】
ブロック３０６において、トライ構造は、各リーフノードからルートノードまで検索され、ブロック３０８において、データシーケンスの一致が、トライ構造から決定されるように列挙される。例えば、列挙サービス１０８は、各リーフノード２０４（図２）から始まるトライ構造１１２を検索し、ルートノード２２０への親ノード参照の経路をたどって、トライ構造１１２から決定されるデータシーケンスの一致１１４を列挙する。
【００４０】
ブロック３１０において、最も最近トラバースされたノードのノードフィールドを現在の位置で更新して、将来のデータシーケンスの一致のために、その最も最近トラバースされたノードを指定する。例えば、列挙サービス１０８は、最も最近トラバースされたノードのノードフィールドを現在の位置で更新して、将来のデータシーケンスの一致のために、その最も最近トラバースされたノードを指定する。最も最近トラバースされたノードのノードフィールドは、親ノードへの参照、派生ノード（例えば、ノードの直近の子ノードを含む）のデータシーケンスの共通一致長、および最も最近トラバースされた派生ノードのバッファ位置を含む。
【００４１】
図４は、図１〜３を参照して前述した、デバイス、またはデバイスによって実装されるサービスのいずれかとして実装することができる例示のデバイス４００の様々な構成要素を図示している。諸実施形態において、このデバイスを、固定のデバイスまたはモバイルデバイスのいずれか、またはその組み合わせとして、家庭用デバイス、コンピュータデバイス、ポータブルデバイス、ユーザデバイス、通信デバイス、電話デバイス、ナビゲーションデバイス、テレビジョンデバイス、家電デバイス、ゲームでアイス、メディア再生デバイス、および／または電子デバイスなどの形式で実装することができる。デバイスは、ユーザ（すなわち、人間）、および／またはデバイスを操作するエンティティに関連付けることができ、その結果、デバイスは、ユーザ、ソフトウェア、ファームウェア、ハードウェア、および／またはデバイスの組み合わせを含む論理デバイスを記述する。
【００４２】
デバイス４００は、受信したデータ、受信中のデータ、ブロードキャスト用にスケジュールされたデータ、データのデータパケットなど、デバイスデータ４０４の有線および／または無線通信を可能にする、通信デバイス４０２を含む。デバイスデータまたは他のデバイスコンテンツは、デバイスの構成設定、デバイスに格納されたメディアコンテンツ、および／またはデバイスのユーザに関連付けられた情報を含むことができる。デバイスに格納されたメディアコンテンツは、任意のタイプのオーディオ、ビデオ、および／またはイメージデータを含むことができる。デバイスは、１つまたは複数のデータ入力部４０６を含み、当該データ入力部４０６を介して、ユーザ選択可能な入力、および任意の他のタイプのオーディオ、ビデオ、および／または任意のコンテンツおよび／またはデータソースから受信したイメージデータなどの、任意のタイプのデータ、メディアコンテンツ、および／または入力を受信することができる。
【００４３】
デバイス４００は通信インタフェース４０８も含む。通信インタフェース４０８は、例えば、シリアルインタフェース、パラレルインタフェース、ネットワークインタフェース、または無線インタフェースのうちのいずれか１つまたは複数などである。通信インタフェースは、デバイスと通信ネットワークとの間の接続および／または通信リンクを提供し、この通信ネットワークにより、他の電子デバイス、コンピューティングデバイス、および通信デバイスは、上記デバイスにデータを通信する。
【００４４】
デバイス４００は、１つまたは複数のプロセッサ４１０（例えば、マイクロプロセッサ、コントローラなどのいずれか）を含み、１つまたは複数のプロセッサ４１０は、様々なコンピュータ実行可能命令を処理してデバイスの動作を制御する。あるいはまた、デバイスを、ソフトウェア、ハードウェア、ファームウェア、あるいは、４１２において全体として特定される処理および制御回路との関連で実装される固定の論理回路のうちのいずれか１つ、またはその組み合わせで実装することができる。図示されていないが、デバイスは、当該デバイス内の様々な構成要素を結合するシステムバスまたはデータ転送システムを含むことができる。システムバスは、メモリバスもしくはメモリコントローラ、周辺バス、ユニバーサルシリアルバス、および／または様々なバスアーキテクチャのいずれかを用いるプロセッサもしくはローカルバスなどの、異なるバス構造のいずれか１つまたはその組み合わせを含むことができる。
【００４５】
デバイス４００は、１つまたは複数のメモリデバイス４１６（例えば、コンピュータ読取可能記憶媒体）も含み、１つまたは複数のメモリデバイス４１６は、ランダムアクセスメモリ（ＲＡＭ）、非揮発性メモリ（例えば、読み取り専用メモリ（ＲＯＭ）、フラッシュメモリなど）、およびディスク記憶装置などのデータ記憶を可能にする。ディスク記憶デバイスを、ハードディスクドライブ、記録可能および／または書き換え可能ディスクなど、任意のタイプの磁気もしくは光記憶デバイスとして実装することができる。デバイスは、大容量記憶媒体デバイスを含むこともできる。
【００４６】
コンピュータ読取可能媒体は、コンピューティングデバイスによってアクセスされる任意の利用可能な媒体とすることができる。限定ではなく例として、コンピュータ読取可能媒体は、記憶媒体と通信媒体を備えることがある。記憶媒体は、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータなどの情報の記憶のための任意の方法または技術で実装される、揮発性および非揮発性、取り外し可能および取り外し不可能な媒体を含む。記憶媒体には、これらに限定されないが、ＲＡＭ，ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光記憶、磁気カセット、磁気テープ、磁気ディスク記憶もしくは他の磁気記憶デバイス、または情報を格納するのに使用でき、コンピュータによってアクセス可能な任意の他の媒体が含まれる。
【００４７】
通信媒体は典型的に、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータを、搬送波または他の伝送機構などの変調データ信号に具現化する。通信媒体は、任意の情報配信媒体も含む。変調データ信号は、情報を信号内にエンコードする手法で設定または変更された特性の１つまたは複数を有する。限定ではなく例として、通信媒体は、有線ネットワークまたは直接有線接続などの有線媒体と、音響、ＲＦ、赤外線、または他の無線媒体などの無線媒体とを含む。
【００４８】
メモリデバイス４１４は、データ記憶機構を提供し、デバイスデータ４０４、他のタイプの情報および／またはデータ、ならびに様々なデバイスアプリケーション４１６を格納する。例えば、オペレーティングシステム４１８を、メモリデバイスによりソフトウェアアプリケーションとして保持し、プロセッサ上で実行することができる。デバイスアプリケーションは、デバイスマネジャを、コントロールアプリケーション、ソフトウェアアプリケーション、信号処理および制御モジュール、特定のデバイスに固有のコード、特定のデバイスのハードウェア抽出層など任意の形式で含むこともできる。この例において、デバイスアプリケーション４１６は、本明細書で説明される圧縮一致列挙の諸実施形態を実装する列挙サービス４２０を含む。
【００４９】
デバイス４００は、オーディオシステム４２４のオーディオデータを生成し、および／またはディスプレイシステム４２６のディスプレイデータを生成する、オーディオおよび／またはビデオ処理システム４２２も含む。オーディオシステムおよび／またはディスプレイシステムは、オーディオ、ビデオ、ディスプレイ、および／またはイメージデータを処理、表示、および／またはそうでなくともレンダリングする任意のデバイスを含むことができる。ディスプレイデータおよびオーディオ信号を、オーディオデバイスおよび／またはディスプレイデバイスに、ＲＦ（ラジオ周波数）リンク、Ｓ−ビデオリンク、構成ビデオリンク、構成要素ビデオリンク、ＤＶＩ（デジタルビデオインタフェース）リンク、アナログオーディオ接続、または他の同様の通信リンクを介して通信することができる。諸実装において、オーディオシステムおよび／またはディスプレイシステムは、デバイスに対する外部構成要素である。あるいは、オーディシステムおよび／またはディスプレイシステムは、統合タッチスクリーンディスプレイなど、例示のデバイスの構成要素に統合される。
【００５０】
圧縮合致列挙の諸実施形態を、特徴および／または方法に特有の言葉で説明してきたが、添付の特許請求の範囲の主題は、必ずしも説明した特有の特徴または方法に限定されない。むしろ、そのような特有の特徴または方法は、圧縮一致列挙の例示的な実装として開示される。
【図１】
0005873925.tif 000002
【図２】
0005873925.tif 000003
【図３】
0005873925.tif 000004
【図４】
0005873925.tif 000005