接尾辞木

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
テキストの接尾辞木BANANA各部分文字列は特殊文字で終了します$ルートからリーフまでの6つのパス(ボックスで表示)は、6つのサフィックス、、、、、およびA$対応ます葉の数字は、対応する接尾辞の開始位置を示します。破線で描かれた接尾辞リンクは、建設中に使用されます。NA$ANA$NANA$ANANA$BANANA$

コンピュータサイエンスでは接尾辞木( PATツリーまたは以前の形式では位置ツリーとも呼ばれます)は、指定されたテキストのすべての接尾辞をキーとして、テキスト内の位置を値として含む圧縮されたトライです。接尾辞木は、多くの重要な文字列操作の特に高速な実装を可能にします。

文字列のためのそのような木の建設の長さで線形の時間と空間がかかります構築されると、いくつかの操作をすばやく実行できます。たとえば、特定の数の間違いが許容される場合の部分文字列の検索、正規表現パターンの一致の検索など。接尾辞木は、最も長い一般的な部分文字列の問題に対する最初の線形時間ソリューションの1つも提供します。これらの高速化には代償が伴います。文字列の接尾辞木を保存するには、通常、文字列自体を保存するよりもかなり多くのスペースが必要です。

定義

文字列の接尾辞木長さの次のようなツリーとして定義されます。[1]

  • ツリーには、から番号が付けられた正確にn枚の葉があります
  • ルートを除いて、すべての内部ノードには少なくとも2つの子があります。
  • 各エッジには、空でないサブストリングのラベルが付けられます。
  • ノードで始まる2つのエッジに、同じ文字で始まる文字列ラベルを含めることはできません。
  • ルートからリーフへのパスで見つかったすべての文字列ラベルを連結して取得した文字列接尾辞を綴る、 ためにから

このようなツリーはすべての文字列に存在するわけではないため、文字列には表示されない終端記号(通常は$)が埋め込まれます。これにより、サフィックスが別のプレフィックスではなくなり、リーフノード、各ノードに1つの接尾辞すべての内部非ルートノードが分岐しているため、最大でn  − 1個のそのようなノードが存在する可能性があり、合計でn  +(n  − 1)+ 1 = 2 nノード( nリーフ、n  − 1内部非ルートノード、 1ルート)。

接尾辞リンクは、古い線形時間構築アルゴリズムの重要な機能ですが、 Farachのアルゴリズムに基づくほとんどの新しいアルゴリズムでは、接尾辞リンクが不要です。完全なサフィックスツリーでは、すべての内部非ルートノードに別の内部ノードへのサフィックスリンクがあります。ルートからノードへのパスが文字列を綴っている場合、 どこ単一の文字であり、文字列(おそらく空)であり、内部ノードへのサフィックスリンクがあります。たとえば、上の図のノードからノードへの接尾辞リンクを参照してANAくださいNAサフィックスリンクは、ツリーで実行されている一部のアルゴリズムでも使用されます。

一般化された接尾辞木は、単一の文字列ではなく、文字列のセット用に作成された接尾辞木です。これは、この文字列セットのすべてのサフィックスを表します。各文字列は、異なる終了記号で終了する必要があります。

歴史

この概念は、Weiner(1973)によって最初に導入されました。接尾辞S [ i .. n ]ではなく、Weinerはトライ[2]に各位置の接頭辞識別子、つまりiで始まり、 Sで1回だけ出現する最短の文字列を格納しました彼のアルゴリズムDは、 S [ k +1 .. n ]の非圧縮[3]トライを取り、それをS [ k..n ]のトライに拡張しますこのように、 S [ n ..の些細なトライから始めます。n ]、 S [1 .. n ]のトライは、アルゴリズムDをn -1回連続して呼び出すことで作成できます。ただし、全体の実行時間はOn 2)です。WeinerのアルゴリズムBは、構築されたトライのサイズで線形の実行時間を全体的に達成するために、いくつかの補助データ構造を維持します。後者は、たとえばS = a n b n a n b n $の場合でもOn 2 )ノードにすることができます。WeinerのアルゴリズムCは、最終的に圧縮された試行を使用して、線形の全体的なストレージサイズと実行時間を実現します。[4] ドナルド・クヌースはその後、後者を「1973年のアルゴリズム」として特徴づけました。[要出典] 教科書Aho、Hopcroft&Ullman(1974、Sect.9.5)は、Weinerの結果を簡略化されたよりエレガントな形で再現し、位置ツリーという用語を導入しました。

McCreight(1976)は、 Sのすべての接尾辞の(圧縮された)トライを最初に作成しましたiで始まる接尾辞は通常、プレフィックスIDよりも長くなりますが、圧縮されたトライでのパス表現のサイズに違いはありません。一方、McCreightは、Weinerの補助データ構造のほとんどを省くことができます。サフィックスリンクのみが残りました。

Ukkonen(1995)は、構造をさらに簡素化しました。[5]彼は、当時最速のアルゴリズムと一致する実行時間を備えた、現在Ukkonenのアルゴリズムとして知られている接尾辞木の最初のオンライン構築を提供しました。これらのアルゴリズムはすべて、一定サイズのアルファベットの線形時間であり、最悪の場合の実行時間は一般に。

Farach(1997)は、すべてのアルファベットに最適な最初の接尾辞木構築アルゴリズムを提供しました。特に、これは、多項式範囲の整数のアルファベットから引き出された文字列の最初の線形時間アルゴリズムです。Farachのアルゴリズムは、たとえば、外部メモリ、圧縮、簡潔などで、 接尾辞ツリーと接尾辞配列の両方を構築するための新しいアルゴリズムの基礎になりました。

機能性

文字列の接尾辞木長さの組み込むことができます時間、文字が多項式範囲の整数のアルファベットから来ている場合(特に、これは一定サイズのアルファベットに当てはまります)。[6]大きなアルファベットの場合、実行時間は、最初に文字を並べ替えてサイズの範囲にすること によって支配されます; 一般的に、これには時間。以下の費用は、アルファベットが一定であると仮定して示されています。

文字列の接尾辞木が作成されていると仮定します長さの、または文字列のセットに対して一般化された接尾辞木が構築されていること全長のあなたはできる:

  • 文字列を検索する:
    • 文字列かどうかを確認します長さのの部分文字列です時間。[7]
    • パターンの最初の出現を見つける全長のの部分文字列として時間。
    • すべて検索パターンの発生全長のの部分文字列として時間。[8]
    • で予想される劣線形正規表現 Pを検索します。[9]
    • パターンの各接尾辞を検索します、プレフィックス間の最長一致の長さおよびの部分文字列時間。[10]これはのマッチング統計と呼ばれます
  • 文字列のプロパティを検索します。
    • 文字列の最も長い一般的な部分文字列を検索します時間。[11]
    • ですべての最大ペア、最大リピート、または超最大リピートを検索します時間。[12]
    • Lempel-Ziv分解をで見つける時間。[13]
    • で最も長く繰り返される部分文字列検索します時間。
    • で最も頻繁に発生する最小長の部分文字列を検索します時間。
    • から最短の文字列を検索しますで発生しない、 の時間、もしあればそのような文字列。
    • で1回だけ発生する最短の部分文字列を検索します時間。
    • それぞれについて、見つける、の最短の部分文字列他の場所では発生しません時間。

接尾辞木は、ノード間の一定時間の最小共通祖先検索用に準備できます。時間。[14]次のこともできます。

  • サフィックス間の最長の共通プレフィックスを検索します[15]
  • 最大でk個の不一致がある長さmのパターンPを検索します。時間。ここで、zはヒット数です。[16]
  • すべて検索最大回文[17]または長さのギャップがある場合の時間許可されている、またはもしも不一致は許可されます。[18]
  • すべて検索 タンデムリピート、およびk-不一致タンデムリピート[19]
  • 少なくとも最も長い一般的な部分文字列を見つけるの文字列ために時間。[20]
  • 線形時間で(文字列の一般化された接尾辞木とその逆を使用して)特定の文字列の最長の回文部分文字列を見つけます。[21]

アプリケーション

接尾辞木は、テキスト編集、フリーテキスト検索、計算生物学、およびその他のアプリケーション分野で発生する多数の文字列の問題を解決するために使用できます。[22]主なアプリケーションは次のとおりです。[22]

  • 文字列検索O(m)の複雑さで、mはサブ文字列の長さです(ただし、文字列の接尾辞木を構築するために必要な初期O(n)時間)
  • 繰り返される最長の部分文字列を見つける
  • 最長の共通部分文字列を見つける
  • 文字列内で最長の回文を見つける

接尾辞木は、バイオインフォマティクスアプリケーションでよく使用され、 DNAまたはタンパク質配列(文字の長い文字列として表示できます)のパターンを検索します。不一致を効率的に検索する機能は、彼らの最大の強みと見なされる可能性があります。接尾辞木はデータ圧縮にも使用されます; これらは、繰り返されるデータを見つけるために使用でき、Burrows–Wheeler変換の並べ替え段階に使用できます。LZW圧縮スキームのバリアントは、接尾辞木( LZSS)を使用します。接尾辞木は、一部の検索エンジンで使用されるデータクラスタリングアルゴリズムである接尾辞木クラスタリングも使用されます。[23]

実装

各ノードとエッジをで表すことができる場合スペース、ツリー全体をで表すことができますスペース。ツリーのすべてのエッジにあるすべての文字列の全長は次のとおりです。、ただし、各エッジはSのサブストリングの位置と長さとして格納できるため、合計スペース使用量は次のようになります。コンピューターの言葉。接尾辞木の最悪の場合のスペース使用量は、フィボナッチ列で見られ、完全なノード。

接尾辞木を実装する際の重要な選択は、ノード間の親子関係です。最も一般的なのは、兄弟リストと呼ばれるリンクリストを使用することです。各ノードには、最初の子へのポインターがあり、子リスト内の次のノードへのポインターが含まれています。効率的な実行時間プロパティを備えた他の実装では、ハッシュマップ、並べ替えられた配列または並べ替えられていない配列配列を2倍にする)、またはバランスの取れた検索ツリーを使用します。私たちは興味を持っています:

  • 特定のキャラクターの子供を見つけるためのコスト。
  • 子を挿入するコスト。
  • ノードのすべての子を参加させるためのコスト(下の表の子の数で割った値)。

σをアルファベットのサイズとします。次に、次のコストがかかります。

挿入コストは償却され、ハッシュのコストは完全なハッシュのために与えられます。

各エッジとノードに大量の情報があるため、接尾辞木は非常に高価になり、適切な実装ではソーステキストのメモリサイズの約10〜20倍を消費します。接尾辞配列は、この要件を8分の1に減らします(32ビットアドレス空間と8ビット文字内に構築されたLCP値を含む配列の場合)。この係数はプロパティによって異なり、4バイト幅の文字を使用すると2に達する可能性があります(一部のUNIXのようなシステムではシンボルを含める必要があります。32ビットシステムではwchar_tを参照してください。研究者たちは、より小さなインデックス構造を見つけ続けています。

並列構築

接尾辞木の構築を高速化するためのさまざまな並列アルゴリズムが提案されています。[24] [25] [26] [27] [28] 最近、接尾辞木を構築するための実用的な並列アルゴリズム 仕事(シーケンシャルタイム)と スパンが開発されました。このアルゴリズムは、共有メモリマルチコアマシンで優れた並列スケーラビリティを実現し、40コアマシンを使用して3分以内にヒトゲノム(約3 GB )にインデックスを付けることができます。[29]

外部構造

線形ではありますが、接尾辞木のメモリ使用量は、シーケンスコレクションの実際のサイズよりも大幅に高くなります。大きなテキストの場合、構築には外部メモリアプローチが必要になる場合があります。

外部メモリに接尾辞木を構築するための理論的な結果があります。Farach-Colton、Ferragina&Muthukrishnan(2000)によるアルゴリズム は理論的に最適であり、I/Oの複雑さはソートと同じです。ただし、このアルゴリズムの全体的な複雑さは、これまでのところ、その実用的な実装を妨げてきました。[30]

一方、(数)GB/時間にスケーリングするディスクベースのサフィックスツリーを構築するための実際的な作業があります。最新の手法は、TDD、[31] TRELLIS、[32] DiGeST、[33] 、およびB2STです。[34]

TDDとTRELLISは、ヒトゲノム全体にスケールアップし、数十ギガバイトのサイズのディスクベースのサフィックスツリーを作成します。[31] [32]ただし、これらの方法では、3GBを超えるシーケンスのコレクションを効率的に処理できません。[33] DiGeSTはパフォーマンスが大幅に向上し、約6時間で6GBのオーダーのシーケンスのコレクションを処理できます。[33]これらのメソッドはすべて、ツリーがメインメモリに収まらない場合に接尾辞木を効率的に構築できますが、入力は収まります。最新の方法、B 2 ST、[34]メインメモリに収まらない入力を処理するためのスケール。ERAは、最近の並列接尾辞ツリーの構築方法であり、大幅に高速化されています。ERAは、16GBのRAMを搭載した8コアのデスクトップコンピューターで、19分でヒトゲノム全体のインデックスを作成できます。16ノード(ノードあたり4GB RAM)の単純なLinuxクラスターでは、ERAは9分未満でヒトゲノム全体のインデックスを作成できます。[35]

も参照してください

メモ

  1. ^ http://www.cs.uoi.gr/~kblekas/courses/bioinformatics/Suffix_Trees1.pdf [永久的なデッドリンク]
  2. ^ この用語は、Weinerの先行データ構造を、上記で定義され、 McCreight(1976)以前されていなかった適切な接尾辞木と区別するためにここで使用されます
  3. ^ つまり、各ブランチは1つの文字でラベル付けされています
  4. ^ 非圧縮のサンプルツリーとその圧縮された対応物については、 File :WeinerB aaaabbbbaaaabbbb.gifおよびFile: WeinerCaaaabbbbaaaabbbb.gifを参照してください
  5. ^ Giegerich&Kurtz(1997)
  6. ^ Farach(1997)
  7. ^ ガスフィールド(1999)、p.92。
  8. ^ ガスフィールド(1999)、p.123。
  9. ^ Baeza-Yates&Gonnet(1996)
  10. ^ ガスフィールド(1999)、p.132。
  11. ^ ガスフィールド(1999)、p.125。
  12. ^ ガスフィールド(1999)、p.144。
  13. ^ ガスフィールド(1999)、p.166。
  14. ^ ガスフィールド(1999)、第8章。
  15. ^ ガスフィールド(1999)、p.196。
  16. ^ ガスフィールド(1999)、p.200。
  17. ^ ガスフィールド(1999)、p.198。
  18. ^ ガスフィールド(1999)、p.201。
  19. ^ ガスフィールド(1999)、p.204。
  20. ^ ガスフィールド(1999)、p.205。
  21. ^ ガスフィールド(1999)、pp.197–199。
  22. ^ a b Allison、L. 「接尾辞木」2008-10-13にオリジナルからアーカイブされました。2008年10月14日取得
  23. ^ Zamir&Etzioni(1998)によって最初に導入されました
  24. ^ Apostolicoetal。(1988)
  25. ^ ハリハラン(1994)
  26. ^ Sahinalp&Vishkin(1994)
  27. ^ Farach&Muthukrishnan(1996)
  28. ^ Iliopoulos&Rytter(2004)
  29. ^ Shun&Blelloch(2014)
  30. ^ Smyth(2003)
  31. ^ a b Tata、Hankins&Patel(2003)
  32. ^ a b Phoophakdee&Zaki(2007)
  33. ^ a b c Barskyetal。(2008)
  34. ^ a b Barskyetal。(2009)
  35. ^ Mansouretal。(2011)

参照

外部リンク