"メモリバッファ内に格納されたデータシーケンスを表すサフィックスアレイを生成するステップと、前記サフィックスアレイをトライ構造に変換するステップであって、前記サフィックスアレイの代わりに当該トライ構造が生成されるように前記メモリバッファ内の前記サフィックスアレイを上書きする、トライ構造に変換するステップと、前記トライ構造から決定されるデータシーケンスの一致を列挙するステップと、を含む、方法。前記サフィックスアレイは、前記メモリバッファ内のバッファ位置のアレイであり、前記バッファ位置は、個々のバッファ位置におけるデータシーケンスを開始するデータ文字列によってアルファベット順にソートされる、請求項1に記載の方法。前記サフィックスアレイは、前記トライ構造を前記サフィックスアレイの連続するサフィックスから徐々に更新することによって、前記トライ構造に変換される、請求項1に記載の方法。前記トライ構造は複数のノードを備え、各ノードが前記サフィックスアレイの1つまたは複数のサフィックスを表し、各連続するサフィックスは、前記トライ構造内の既存のノードでグループ化されるか、前記トライ構造の新たなノードとして追加される、請求項1に記載の方法。前記サフィックスアレイのサフィックスは、当該サフィックスが前記トライ構造内の既存のノードとしてデータシーケンスの共通一致長を有するとき、前記既存のノードでグループ化される、請求項4に記載の方法。前記トライ構造は、各ノードが、親ノードへの参照と、派生ノードのデータシーケンスの共通一致長と、最も最近トラバースされた派生ノードのデータ位置とを含む、複数のノードを備える、請求項1に記載の方法。前記派生ノードは、あるノードの直近の子ノードを含み、前記トライ構造は、当該トライ構造が、少なくとも2つの直近の子ノードを各々有する1つまたは複数の非リーフノードを含むことと、前記派生ノードのデータシーケンスの前記共通一致長が最大であることと、前記トライ構造内のノードの合計数が最小であることとに基づいて生成される、請求項6に記載の方法。前記トライ構造の生成が完了した後に、前記データシーケンスの一致を列挙するのに前記トライ構造を検索するステップをさらに含む、請求項1に記載の方法。最も最近トラバースされたノードのノードフィールドを現在の位置で更新して、前記最も最近トラバースされたノードを将来のデータシーケンスの一致に指定するステップをさらに含む、請求項1に記載の方法。少なくともメモリと、列挙サービスを実装するプロセッサとを備えたコンピューティングデバイスであって、前記列挙サービスは、メモリバッファ内に格納されたデータシーケンスを表すサフィックスアレイを生成することと、前記サフィックスアレイをトライ構造に変換することであって、前記トライ構造は、当該トライ構造が前記サフィックスアレイの代わりに生成されるように前記メモリバッファ内の前記サフィックスアレイを上書きし、前記トライ構造は複数のノードを含み、各ノードが前記サフィックスアレイの1つまたは複数のサフィックスを表し、各連続するサフィックスが前記トライ構造内の既存のノードでグループ化されるか、前記トライ構造の新たなノードとして追加される、前記トライ構造に変換することと、前記トライ構造から決定されるデータシーケンスの一致を列挙することと、を行うように構成される、コンピューティングデバイス。格納されたデータシーケンスにおけるデータ一致の可能性の全てを列挙する、圧縮一致列挙の諸実施形態を説明し、実装する。LZ77圧縮アルゴリズムなどにおいて用いられるような圧縮一致列挙は、リーフからルートへのトライ構造を用いてデータ一致を列挙する。諸実施形態において、メモリバッファに格納されるデータシーケンスを表すサフィックスアレイが生成される。サフィックスアレイは次いで、トライ構造に変換される。トライ構造は、当該トライ構造がサフィックスアレイの代わりに生成されるように、メモリバッファ内のサフィックスアレイを上書きする。ノードが可変の数の子ノードを有する可能性があるために、トライ構造内のノードの子ノードへの参照を格納することは一般に複雑であるので、トライ構造内のノードの子ノードへの参照を格納するのではなく、トライ構造のノードはそれぞれ、親ノードへの参照と、派生ノードのデータシーケンスの共通の一致長と、最も最近トラバースされた派生ノードのバッファ位置とを含む。派生ノードは、あるノードの直近の子ノード、または任意の他の子ノード、孫ノード、もしくは派生ノードを含む可能性がある。圧縮一致列挙の特徴および概念を、任意の数の異なるデバイス、システム、環境、ネットワーク、および/または構成において実装することができ、圧縮一致列挙の諸実施形態は、以下の例示のデバイス、システム、および方法のコンテキストで説明される。図1は、圧縮一致列挙の様々な実施形態を実装することができる例示的なシステム100を図示している。例示的なシステムは、コンピューティングデバイス102を含む。コンピューティングデバイス102は、列挙された圧縮データマッチングを実行する任意のタイプのサーバ、コンピュータ、またはデバイスとすることができる。本明細書で参照されるコンピューティングデバイスのいずれも、1つまたは複数のプロセッサおよびメモリデバイスだけでなく、図4に示される例示的デバイスを参照してさらに説明されるような任意の数の種々の構成要素およびそれらの構成要素の組み合わせなど、様々な構成要素を用いて実装することができる。例示的システム100において、コンピューティングデバイス102は、格納されたデータシーケンス106を格納または保持するメモリバッファ104を含む。メモリバッファは、任意のタイプのメモリ、記憶媒体、および/または適切な電子的データ記憶などのデータ記憶を可能にする、任意のタイプのコンピュータ読取可能記憶媒体として実装することができる。格納されたデータシーケンス106は、メモリ内に格納されたバイトであり、メモリは、データのより小さい表現へと認識して圧縮することができる、反復的なバイトシーケンスを有することがある。圧縮一致列挙の諸実施形態は、格納されたデータシーケンスにおけるデータ一致の可能性の全てを列挙するように実装される。例えば、abacdeというデータ文字列は、第1のバッファ位置でデータシーケンスを開始する。abacfdという第1の可能性のある一致が、第2のバッファ位置において決定され、この一致を、abacという4バイトの一致と、第1のバッファ位置と第2のバッファ位置との間の距離が1,000バイトであることについて、長さ=4、距離=1,000によって表すことができる。第2の可能な一致abacdfが第3のバッファ位置において決定され、この一致は、abacdという5バイトの一致と、第1のバッファ位置と第3のバッファ位置との間の距離が10,000バイトであることについて、長さ=5、距離=10,000と表すことができる。コンピューティングデバイス102は、本明細書で説明される圧縮一致列挙の諸実施形態を実装する列挙サービス108も含むことができる。列挙サービスを、ソフトウェアアプリケーションおよび/またはアルゴリズムなどのコンピュータ実行可能命令として実装し、コンピューティングデバイスの1つまたは複数のプロセッサによって実行することができる。この例において、列挙サービスは、コンピューティングデバイスの構成要素として実装されるように示される。あるいは、列挙サービスは、圧縮一致列挙の諸実施形態を実装する独立のソフトウェアアプリケーション、アルゴリズム、ネットワークベースのサービスとして構成することもできる。諸実施形態において、列挙サービス108は、格納されたデータシーケンス106を表すサフィックスアレイ110を生成するように実装される。データシーケンス106は、メモリバッファ104に格納される。サフィックスアレイは、メモリバッファ内の全てのバッファ位置例えば、サフィックスのアレイであり、バッファ位置を、個々のバッファ位置の各々においてデータシーケンスを開始するデータ文字列によって、アルファベット順にソートすることができる。サフィックスアレイを生成する技術は公知であり、様々な技術のいずれかを列挙サービスにより実装して、サフィックスアレイを生成することができる。列挙サービス108は次いで、サフィックスアレイ110をトライ構造112に変換するように実装される。トライ構造112は、当該トライ構造112がサフィックスアレイの代わりに生成されるように、メモリバッファ104内のサフィックスアレイを上書きする。これは、サフィックスアレイからトライ構造を生成または構築するのに追加のメモリを必要としないので、メモリが節約される。サフィックスアレイは、当該サフィックスアレイの連続するサフィックスから徐々にトライ構造を更新することによって、トライ構造に変換される。トライ構造は、ルートノードから開始して次第に下位レベルの階層に広がっていくのではなく、リーフからルートへと生成される。リーフノードをトライ構造に追加して、トライ構造のルートノードに向かって次第に縮小する、すなわちルートノードを決定する。列挙サービスは次いで、トライ構造が生成または構築された後、トライ構造の検索を開始して、トライ構造から決定されたデータシーケンスの一致114を列挙する。トライ構造112の例116が、サフィックスアレイ110のサフィックスから生成される幾つかのトライノード118とともに示されている。トライ構造は、例示のリーフノード120などのリーフノードを含み、このリーフノードはそれぞれ、サフィックスアレイ110の1つのサフィックスに対応する。トライ構造は、例示の非リーフノード122などの非リーフノードも含む。リーフノード120は、トライ構造内における親ノードに対する子ノードとすることもでき、一方、非リーフノード122は、トライ構造内における子ノードと親ノードの双方とすることができる。トライ構図112の例116は、大きなデータ文字列からのサフィックスを幾つかアルファベット順に図示しているにすぎない。メモリバッファ104内の格納されたデータシーケンス106は、圧縮一致列挙が適用される、非常に大きなデータセットとすることができる。矢印は、親ノード参照ポインタを表し、数字は、直近の子ノードを含め、特定のノードの派生ノードの全てのデータシーケンスについての共通一致長を表す。例えば、データシーケンスabcebを有するデータノード120は、非リーフノード122への親ノード参照を含んでおり、この場合、4という共通一致長は、2つの子ノードのデータシーケンスを表している。トライ構造は、サフィックスアレイから効率的に構築することができる。なぜなら、幾何学的に言うと、トライ構造が生成されるときに、親ノードポインタの線が相互に交わることのない、平面図であるからである。それぞれの後続リーフノード120がトライ構造112内で接続されるとおよび、非リーフエントリが、後のエントリによって参照不可能となると、新たなリーフノードが接続されるノードのセットは、この平面的特性のために小さくなり、これにより、圧縮一致列挙の諸実施形態における効率的かつ簡単なアルゴリズムが得られる。トライ構造は基本的にツリー構造であり、このツリー構造では、一致するサブ文字列が共通ノードの下にグループ化され、これらのノードが、より短い一致を効率的にグループ化する他のノードの下でグループ化される。ノードから子ノードへの情報は必要とされず、格納されない。むしろ、トライ構造のトライノード118は、親ノード参照と、派生ノード例えば、直近の子ノードを含むのデータシーケンスの共通一致長と、最も最近トラバースされた派生ノードのノードバッファ位置とについてのノードフィールドを含む。親ノード参照のフィールドと共通一致長のフィールドとの双方を、例えば、親ノード参照インデックスに26ビットを使用し、共通データシーケンス長に6ビットを使用して、1つの32ビット値に格納することができる。より長い長さを、32ビット値に格納可能な最大の長さにキャップすることができる。列挙サービス108がトライ構造112を構築すると、列挙サービスの3つのアルゴリズムの不変条件が保持される。第1に、全ての非リーフノード122が、少なくとも2つの直近の子ノードを有する。第2に、あるノードの派生ノードの共通一致長は最大である例えば、10の文字列位置が長さLを有し、この文字列位置のうちの2つが、共通する長さL1を有する場合、これら2つの文字列位置がこれら自身のノードの下にグループ化される。第3に、これらの制約内において、トライ構造内のノードの合計を最小にする例えば、2つの文字列位置またはサブノードを共通ノードの下でグループ化することができる場合、これらを、その共通ノードの下でグループ化する必要がある。列挙サービス108は、サフィックスアレイ110のサフィックス例えば、バッファ位置を、当該サフィックスがサフィックスアレイ内で発生する順序で処理し、このサフィックスアレイとともに計算される、最長の共通のプレフィックスフィールドに基づいて決定を行う。最長の共通プレフィックスフィールドは、どれほど多くのサフィックスが辞書学的に最も近いサフィックスに一致するかの長さを示す。一致長を増大する小さなスタックが保持され、トライノード118は、プレフィックス長が減少するとき、そのスタックを展開することによって構築される。ある実装において、スタックは、一致長が6ビット数としてキャップされるので小さい。スタックのエントリが、将来のノードが接続され得る全ての既存のノードのセットを表すか、あるいは、トライ構造が生成されるとき、新たなリーフノード120を作成することができる。サフィックスアレイの各サフィックスに関して、サフィックスを、適切な長さの既存のノードでグループ化することができ、あるいはサフィックスを使用してトライ構造の新たなリーフノードを生成することができる。非リーフノードは、適切な長さのノードに対する検索の間にスタックが展開されるように、親ノードを割り当てられる。これらのグループ化の決定は、上述の3つのアルゴリズムの不変条件に基づいている。トライ構造112内の非リーフノード122の空間は、サフィックスアレイ自体から割り当てられ、そして、割り当てられる非リーフノードの数は、処理されるサフィックスの数よりも少ないことが容易に実証されるので、これは、サフィックスアレイ110を新たなトライ構造で徐々に上書きする、インプレース方法である。上述のように、このことにより、2つの大きなデータ構造例えば、サフィックスアレイ110とトライ構造112の双方が同時に格納されることがないので、メモリが節約される。各リーフノード120は、サフィックス例えば、バッファ位置に対応し、各リーフノードの親ノードは、反対のサフィックスアレイを上書きすることによって格納される。列挙サービス108は、一致列挙検索方法も実装し、各バッファ位置について順に、トライ構造内においてリーフノードからルートノードへと親ノードのポインタをたどる。各非リーフノード122トライノード118によっても表されるは、親ノード参照と、共通一致長と、直近の子ノードを含め、最も最近トラバースされた非リーフノードからの派生ノードの派生ノードバッファ位置例えば、この処理の間に、非リーフノードを最も最近訪問した派生ノードのバッファ位置とを格納または保持する。他のノードからの後続のトラバースに関して、これらのノードフィールドは、リーフノードからルートノードへのリーフルート経路に沿った各長さについて、最短距離のデータシーケンスの後方一致を提供する。その後、検索段階におけるトライ構造に関して変化するノードフィールドのみが、各非リーフノードに関連付けられた、最も最近トラバースされた派生ノードについての派生ノードバッファ位置フィールドである。データシーケンスの最新の一致が長い一致でもあり、トライ構造112内に表された、異なる長さの多くの短い一致が存在する場合、次いで、トライ構造が徐々にトラバースされると、同じデータ一致が何度も発生する。例えば、長さ10の最短距離の一致は、長さ9、8、7などの最短距離の一致とすることもできる。簡単な解決策は、トライ構造内の各非リーフノードに対して、8バイトのメモリを用いること、例えば、親ノード参照に約4バイト、派生ノードのバッファ位置例えば、最も最近見た位置に概ね約4バイト、および共通一致長に何バイトかを用いることである。しかしながら、トライ構造内の非リーフノード毎に8バイト使用し、リーフノード毎に4バイト使用すると、合計メモリ使用量はノード数の12倍12nになる。トライ構造内の非リーフノードに4バイトのみを使用することによって、この合計メモリ使用量をノード数の8倍8nまで減少することができる。メモリを節約するために、列挙サービスは、リーフから親への参照のみを順に使用し、位置に関するデータ一致が見つかると、その位置のデータリーフはもはや必要とされない、ということに利点がある。メモリバッファは前方に向かってトラバースされるので、メモリ空間は、以前は反対のサフィックスアレイであり、トライ構造112の構築中に上書きされたものから利用可能になり、この利用可能なメモリ空間を使用して、情報の全てを格納することができる。ある実装において、フィールドは、親自体をルックアップする親ノード空間に格納されるが、これは、この利用可能なメモリ空間が、ノードの親の記憶に隣接する可能性が低いからである。リーフから親へのアレイを追加のメモリとして使用するとき、最も最近見たノードフィールドは、ちょうどそのようなフィールドに近い。したがって、例えば、サフィックスアレイとなるように使用されるトライ構造の非リーフ部分において、親ノード参照は、最も最近見た位置で置換され、元の親ノード参照は次いで、最も最近見た位置のリーフ親ノードに以前に使用されたメモリ内に格納され、ここには、そのノードから最も最近見た位置を知ることによって到達することができる。したがって、検索方法がトラバースまたは訪問する各ノードについて、親ノード参照と、最も最近トラバースされた派生ノードと、派生ノードの共通一致長の3つのノードフィールドを決定することができる。このことはメモリ使用を節約するだけでなく、長くかつすぐ近くのデータ一致が決定されるとき、トラバースする必要のないトライ構造内のノードをスキップすることもできる。これは、最近の位置の全体が、実際には、1つの親ノード参照のみに対するメモリ空間を有する、リーフからルートへの経路における各ノードについて最も最近トラバースされた例えば、最も最近見た位置であるためである。最初は、NULL参照を格納して、親ノードがトライ構造のルートノードであることを示すことができる。次いで、次のノード位置を処理すると、次のノード位置が、ルートノードにおいて見られるような、最も最近トラバースされた位置となり、以前の最も最近トラバースされた位置の親参照は、双方の位置に共通するノード便宜上、トラバースの現在のノードであるを参照するように更新される。これは、ルートノードだけでなく、トライ構造の全てのノードにおいて行われ、古い位置は段々とトライ構造の下の方にいく。トライ構造を継続的に変更および更新するこの技術は、同じ一致長を複数回繰り返すことや、明らかに次善的な一致を列挙することなど、トライ構造をトラバースするときに不必要なステップをスキップすることにおいて効率的である。図2は、トライ構造200の例、および本発明で説明される圧縮一致列挙の実施形態にしたがって、図1を参照して説明した列挙サービス108がどのように実装され、トライ構造を検索して更新するかを図示している。202において、サフィックスアレイから変換されるときに、任意の一致列挙に先行して構築されるようなトライ構造を示している。トライ構造のノードはノード204から220として識別され、リーフノードのボトムレイヤは、リーフノードが列挙サービスによって処理される順序を示す、P1からP4としても識別される。一致列挙を実行するのに2つの基本的な原則に従う。第1に、以前にトラバースされた非リーフノードは、最も最近トラバースされた非リーフノードからリーフノードへポイントする。第2に、リーフノードおよび未だトラバースされていないノードは、何らかの非リーフノード大まかに、親ノードと称され、一部の場合においてルートノートとすることができるをポイントする。202に示されるトライ構造から、224に示されるトライ構造への第1の遷移222において、列挙サービス108は、リーフノード204例えば、1番目に処理されるリーフノードP1に関連付けられたサフィックス例えば、データバッファのデータ一致を列挙しようと試みる。この例において、処理される第1のリーフノードに合う一致はないが、トライ構造は更新され、これのよりリーフノード204からルートノード220への経路の各ノードは、自身の個々のリーフノード例えば、これらのノードの最も最近の訪問者を参照するようになる。例えば、リーフノード204からルートノード220への経路は、ノード201、216、および218を通る。これらのノードの各々がトラバースされると、派生ノードバッファ位置に関する個々のノードのフィールドは、リーフノードを参照するように更新される。加えて、リーフノード204の親ノード参照フィールドは、ルートノード220を参照するように更新される。224に示されるトライ構造から、228に示されるトライ構造への第2の遷移226において、列挙サービス108は、リーフノード208からの検索経路をたどり、リーフノード例えば、2番目に処理されるリーフノードP2に関連付けられたサフィックスに対する一致を列挙する。この例において、図では指定されていないある長さの一致が、例えば、非リーフノード214がトラバースされた後にトラバースされる第2の非リーフノード216において列挙される。ノード216から、一致するリーフノード204の位置が決定される例えば、ノード216は、224に示されるようにリーフノード204を参照する。次にトラバースすべき親ノードこの例ではルート220であるは、リーフノード204の親ノード参照フィールドから決定される例えば、ノード204は、224に示されるようにルートノード220を参照する。リーフノード208の元のリーフルート経路内にあった非リーフノード218は、この例ではスキップされ、以下にさらに述べるように取り扱われることとなる。さらに、リーフノード208の親ノード参照フィールドは、ルートノード220を参照するように更新される。228に示されるトライ構造から、232に示されるトライ構造への第3の遷移230において、列挙サービス108は、リーフノード206からの検索経路をたどり、リーフノード例えば、3番目に処理されるリーフノードP3に関連付けられたサフィックスに関する一致を列挙する。この例では、リーフノード204とリーフノード208において2つの一致が列挙される。リーフノード208における親ノード参照フィールドは、ノード216を参照するように更新され、検索経路内の非リーフノード212および216は、非リーフノード201と216をトラバースする最近のノードであるリーフノード206を参照するように更新される。加えて、リーフノード206の親ノード参照フィールドは、ルートノード220を参照するように更新される。233に示されるトライ構造から、236に示されるトライ構造への最後の遷移234において、列挙サービス108は、リーフノード210例えば、4番目に処理されるリーフノードP4からの検索経路にたどる。上記においてリーフノード208の元のリーフルート経路内のスキップされたノードである、非リーフノード218に遭遇する。非リーフノード218はまだ、トライ構造内で非リーフ構造218の下にある親ノード216を参照する第1のリーフノード204を参照している。検索経路はトライ構造内の高い方をトラバースすべきであるため、これは問題であるように見えることがある。しかしながら、これは、リーフノード204の親ノード216が現在の非リーフノード218よりも長い長さを有することを検出することによって、容易に対処される。列挙サービスは次いで、現在の非リーフノード218よりも短い長さのノードこの場合、ルートノード220であるに遭遇し、その短い長さが派生ノードではなく上位ノードを示すまで、ノード216からノード206を介して検索経路をたどり続ける。したがって、リーフノード206の親ノード参照フィールドは、非リーフノード218を参照するように更新され、リーフノード208の親ノード参照フィールドは、ルートノード220を参照するように更新される。各リーフノードの検索経路をたどってトライ構造をトラバースするアルゴリズムの動的な性質は、非常に少ない処理負荷で正確に、列挙された一致を提供する。圧縮一致列挙の1つまたは複数の実施形態にかかる例示の方法300を、図3を参照して説明する。一般に、本明細書で説明されるサービス、関数、方法、プロシージャ、構成要素、およびモジュールはいずれも、ソフトウェア、ファームウェア、ハードウェア例えば、固定の論理回路、マニュアル処理、およびこれらの任意の組み合わせを用いて実装することができる。ソフトウェア実装は、コンピュータプロセッサによって実行されると、指定されたタスクを実行するプログラムコードを表す。例示的な方法を、コンピュータ実行可能命令の一般的なコンテキストで説明することができ、コンピュータ実行可能命令には、ソフトウェア、アプリケーション、ルーチン、プログラム、オブジェクト、構成要素、データ構造、プロシージャ、モジュール、関数などが含まれ得る。プログラムコードを、コンピュータプロセッサに対してローカルおよび/またはリモート双方の1つまたは複数のコンピュータ読取可能記憶媒体装置に格納することができる。本方法を、分散コンピューティング環境において複数のコンピュータデバイスによって実施することもできる。さらに、本明細書で説明される特徴は、プラットフォームに独立であり、様々なプロセッサを有する様々なコンピューティングプラットフォームにおいて実装されうる。図3は、圧縮一致列挙の例示的方法300を図示している。方法のブロックを説明する順序は、限定として解釈されるようには意図されておらず、任意の数の説明される方法のブロックを任意の順序で組み合わせて、方法または代替的方法を実装することができる。ブロック302において、メモリバッファに格納されたデータシーケンスを表すサフィックスアレイが生成される。例えば、コンピューティングデバイス102図1における列挙サービス108は、メモリバッファ104内に格納される、格納済みデータシーケンス106を表すサフィックスアレイ110を生成する。サフィックスアレイは、メモリバッファ内のバッファ位置のアレイであり、そのバッファ位置は、個々のバッファ位置でデータシーケンスを開始するデータ文字列によってアルファベット順にソートされる。ブロック304において、サフィックスアレイは、サフィックスアレイの代わりに生成されるようにメモリバッファ内のサフィックスアレイを上書きする、トライ構造に変換される。例えば、列挙サービス108は、サフィックスアレイ110をトライ構造112に変換し、トライ構造がサフィックスアレイの代わりに生成されるようにメモリバッファ内のサフィックスアレイを上書きする。サフィックスアレイは、サフィックスアレイの連続するサフィックスからトライ構造を徐々に更新することによって、トライ構造に変換される。トライ構造は、各ノードがサフィックスアレイの1つまたは複数のサフィックスを表す複数のノードを含み、連続するサフィックスのそれぞれは、トライ構造内の既存のノードでグループ化されるか、トライ構造の新たなノードとして追加される。サフィックスアレイのサフィックスは、当該サフィックスが既存のノードとしてデータシーケンスの共通一致長を有するとき、トライ構造内のその既存のノードでグループ化することができる。さらにトライ構造は、次の事項に基づいて生成される。すなわち、トライ構造は、当該トライ構造が、各非リーフノードが少なくとも2つの直近の子ノードを有する、1つまたは複数のリーフノードを含むことと、派生ノードのデータシーケンスの共通一致長が最大であることと、トライ構造内のノードの合計数が最小であること、に基づいて生成される。ブロック306において、トライ構造は、各リーフノードからルートノードまで検索され、ブロック308において、データシーケンスの一致が、トライ構造から決定されるように列挙される。例えば、列挙サービス108は、各リーフノード204図2から始まるトライ構造112を検索し、ルートノード220への親ノード参照の経路をたどって、トライ構造112から決定されるデータシーケンスの一致114を列挙する。ブロック310において、最も最近トラバースされたノードのノードフィールドを現在の位置で更新して、将来のデータシーケンスの一致のために、その最も最近トラバースされたノードを指定する。例えば、列挙サービス108は、最も最近トラバースされたノードのノードフィールドを現在の位置で更新して、将来のデータシーケンスの一致のために、その最も最近トラバースされたノードを指定する。最も最近トラバースされたノードのノードフィールドは、親ノードへの参照、派生ノード例えば、ノードの直近の子ノードを含むのデータシーケンスの共通一致長、および最も最近トラバースされた派生ノードのバッファ位置を含む。図4は、図1~3を参照して前述した、デバイス、またはデバイスによって実装されるサービスのいずれかとして実装することができる例示のデバイス400の様々な構成要素を図示している。諸実施形態において、このデバイスを、固定のデバイスまたはモバイルデバイスのいずれか、またはその組み合わせとして、家庭用デバイス、コンピュータデバイス、ポータブルデバイス、ユーザデバイス、通信デバイス、電話デバイス、ナビゲーションデバイス、テレビジョンデバイス、家電デバイス、ゲームでアイス、メディア再生デバイス、および/または電子デバイスなどの形式で実装することができる。デバイスは、ユーザすなわち、人間、および/またはデバイスを操作するエンティティに関連付けることができ、その結果、デバイスは、ユーザ、ソフトウェア、ファームウェア、ハードウェア、および/またはデバイスの組み合わせを含む論理デバイスを記述する。デバイス400は、受信したデータ、受信中のデータ、ブロードキャスト用にスケジュールされたデータ、データのデータパケットなど、デバイスデータ404の有線および/または無線通信を可能にする、通信デバイス402を含む。デバイスデータまたは他のデバイスコンテンツは、デバイスの構成設定、デバイスに格納されたメディアコンテンツ、および/またはデバイスのユーザに関連付けられた情報を含むことができる。デバイスに格納されたメディアコンテンツは、任意のタイプのオーディオ、ビデオ、および/またはイメージデータを含むことができる。デバイスは、1つまたは複数のデータ入力部406を含み、当該データ入力部406を介して、ユーザ選択可能な入力、および任意の他のタイプのオーディオ、ビデオ、および/または任意のコンテンツおよび/またはデータソースから受信したイメージデータなどの、任意のタイプのデータ、メディアコンテンツ、および/または入力を受信することができる。デバイス400は通信インタフェース408も含む。通信インタフェース408は、例えば、シリアルインタフェース、パラレルインタフェース、ネットワークインタフェース、または無線インタフェースのうちのいずれか1つまたは複数などである。通信インタフェースは、デバイスと通信ネットワークとの間の接続および/または通信リンクを提供し、この通信ネットワークにより、他の電子デバイス、コンピューティングデバイス、および通信デバイスは、上記デバイスにデータを通信する。デバイス400は、1つまたは複数のプロセッサ410例えば、マイクロプロセッサ、コントローラなどのいずれかを含み、1つまたは複数のプロセッサ410は、様々なコンピュータ実行可能命令を処理してデバイスの動作を制御する。あるいはまた、デバイスを、ソフトウェア、ハードウェア、ファームウェア、あるいは、412において全体として特定される処理および制御回路との関連で実装される固定の論理回路のうちのいずれか1つ、またはその組み合わせで実装することができる。図示されていないが、デバイスは、当該デバイス内の様々な構成要素を結合するシステムバスまたはデータ転送システムを含むことができる。システムバスは、メモリバスもしくはメモリコントローラ、周辺バス、ユニバーサルシリアルバス、および/または様々なバスアーキテクチャのいずれかを用いるプロセッサもしくはローカルバスなどの、異なるバス構造のいずれか1つまたはその組み合わせを含むことができる。デバイス400は、1つまたは複数のメモリデバイス416例えば、コンピュータ読取可能記憶媒体も含み、1つまたは複数のメモリデバイス416は、ランダムアクセスメモリRAM、非揮発性メモリ例えば、読み取り専用メモリROM、フラッシュメモリなど、およびディスク記憶装置などのデータ記憶を可能にする。ディスク記憶デバイスを、ハードディスクドライブ、記録可能および/または書き換え可能ディスクなど、任意のタイプの磁気もしくは光記憶デバイスとして実装することができる。デバイスは、大容量記憶媒体デバイスを含むこともできる。コンピュータ読取可能媒体は、コンピューティングデバイスによってアクセスされる任意の利用可能な媒体とすることができる。限定ではなく例として、コンピュータ読取可能媒体は、記憶媒体と通信媒体を備えることがある。記憶媒体は、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータなどの情報の記憶のための任意の方法または技術で実装される、揮発性および非揮発性、取り外し可能および取り外し不可能な媒体を含む。記憶媒体には、これらに限定されないが、RAM,ROM、EEPROM、フラッシュメモリもしくは他のメモリ技術、CD-ROM、デジタル多用途ディスクDVDもしくは他の光記憶、磁気カセット、磁気テープ、磁気ディスク記憶もしくは他の磁気記憶デバイス、または情報を格納するのに使用でき、コンピュータによってアクセス可能な任意の他の媒体が含まれる。通信媒体は典型的に、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータを、搬送波または他の伝送機構などの変調データ信号に具現化する。通信媒体は、任意の情報配信媒体も含む。変調データ信号は、情報を信号内にエンコードする手法で設定または変更された特性の1つまたは複数を有する。限定ではなく例として、通信媒体は、有線ネットワークまたは直接有線接続などの有線媒体と、音響、RF、赤外線、または他の無線媒体などの無線媒体とを含む。メモリデバイス414は、データ記憶機構を提供し、デバイスデータ404、他のタイプの情報および/またはデータ、ならびに様々なデバイスアプリケーション416を格納する。例えば、オペレーティングシステム418を、メモリデバイスによりソフトウェアアプリケーションとして保持し、プロセッサ上で実行することができる。デバイスアプリケーションは、デバイスマネジャを、コントロールアプリケーション、ソフトウェアアプリケーション、信号処理および制御モジュール、特定のデバイスに固有のコード、特定のデバイスのハードウェア抽出層など任意の形式で含むこともできる。この例において、デバイスアプリケーション416は、本明細書で説明される圧縮一致列挙の諸実施形態を実装する列挙サービス420を含む。デバイス400は、オーディオシステム424のオーディオデータを生成し、および/またはディスプレイシステム426のディスプレイデータを生成する、オーディオおよび/またはビデオ処理システム422も含む。オーディオシステムおよび/またはディスプレイシステムは、オーディオ、ビデオ、ディスプレイ、および/またはイメージデータを処理、表示、および/またはそうでなくともレンダリングする任意のデバイスを含むことができる。ディスプレイデータおよびオーディオ信号を、オーディオデバイスおよび/またはディスプレイデバイスに、RFラジオ周波数リンク、S-ビデオリンク、構成ビデオリンク、構成要素ビデオリンク、DVIデジタルビデオインタフェースリンク、アナログオーディオ接続、または他の同様の通信リンクを介して通信することができる。諸実装において、オーディオシステムおよび/またはディスプレイシステムは、デバイスに対する外部構成要素である。あるいは、オーディシステムおよび/またはディスプレイシステムは、統合タッチスクリーンディスプレイなど、例示のデバイスの構成要素に統合される。圧縮合致列挙の諸実施形態を、特徴および/または方法に特有の言葉で説明してきたが、添付の特許請求の範囲の主題は、必ずしも説明した特有の特徴または方法に限定されない。むしろ、そのような特有の特徴または方法は、圧縮一致列挙の例示的な実装として開示される。"