サフィックスツリー - tanakakenji/Rinko GitHub Wiki
サフィックスツリーは、文字列の全てのサフィックス（接尾辞）を効率的に格納し検索するためのツリー構造のデータ構造です。
主な特徴：
- 文字列の全てのサフィックスを表現
- 部分文字列の検索を高速に行える
- パターンマッチングや最長共通部分文字列の検索などに適している
サフィックスツリーは以下の要素で構成されます：
- ノード：文字列の部分を表す
- エッジ：文字列のつながりを表す
- ルートノード：空の文字列を表す特別なノード
- 葉ノード：サフィックスの終端を表す
各内部ノードは少なくとも2つの子を持ち、各エッジはラベル（部分文字列）を持ちます。
サフィックスツリーの実装は複雑ですが、ここでは簡略化したバージョンを示します。
まず、ノードを表すクラスを定義します：
まず、Nodeクラスの実装を一行ずつ見ていきましょう：
class Node {
public:
int start;
int* end;
std::vector<std::unique_ptr<Node>> children;
Node* suffixLink;
Node(int start, int* end) : start(start), end(end), suffixLink(nullptr) {}
int edgeLength() const {
return *end - start + 1;
}
};-
int start;- このノードが表す部分文字列の開始位置を示します。
-
int* end;- 部分文字列の終了位置へのポインタです。ポインタを使用することで、複数のノードで同じ終了位置を共有できます。
-
std::vector<std::unique_ptr<Node>> children;- このノードの子ノードを格納するベクターです。
-
std::unique_ptrを使用することで、メモリ管理を自動化しています。
-
Node* suffixLink;- サフィックスリンクを表すポインタです。これは効率的なツリーの構築と操作のために使用されます。
-
Node(int start, int* end) : start(start), end(end), suffixLink(nullptr) {}- コンストラクタです。
startとendを初期化し、suffixLinkをnullptrに設定します。
- コンストラクタです。
-
int edgeLength() const { return *end - start + 1; }- このノードが表す部分文字列の長さを計算するヘルパー関数です。
次に、SuffixTreeクラスの冒頭部分を詳しく見ていきましょう：
class SuffixTree {
private:
std::string text;
std::unique_ptr<Node> root;
Node* activeNode;
int activeEdge;
int activeLength;
int remainingSuffixCount;
int leafEnd;
int* rootEnd;
int* splitEnd;
std::vector<int> size;
public:
SuffixTree(const std::string& str) : text(str + "$"), activeNode(nullptr),
activeEdge(-1), activeLength(0),
remainingSuffixCount(0), leafEnd(-1) {
size.resize(2 * text.length(), -1);
rootEnd = new int(-1);
splitEnd = new int(-1);
root = std::make_unique<Node>(-1, rootEnd);
activeNode = root.get();
for (int i = 0; i < text.length(); i++) {
extendSuffixTree(i);
}
}
// ... (他のメソッドは後で説明します)
};-
std::string text;- サフィックスツリーを構築する元の文字列を格納します。
-
std::unique_ptr<Node> root;- ツリーのルートノードへのユニークポインタです。
-
Node* activeNode;- 現在のアクティブノードを指すポインタです。
-
int activeEdge;- アクティブエッジを表す索引です。
-
int activeLength;- アクティブ長さを表します。
-
int remainingSuffixCount;- まだ処理していないサフィックスの数を追跡します。
-
int leafEnd;- 葉ノードの終了位置を示します。
-
int* rootEnd;とint* splitEnd;- ルートと分割ノードの終了位置へのポインタです。
-
std::vector<int> size;- 各ノードのサイズを格納するベクターです。
コンストラクタの各行を見ていきましょう：
-
SuffixTree(const std::string& str) : text(str + "$"), ...- 入力文字列の末尾に
$を追加しています。これは全てのサフィックスが確実に葉ノードで終わるようにするためです。
- 入力文字列の末尾に
-
size.resize(2 * text.length(), -1);- サイズベクターを初期化します。最大で2n-1個のノードが必要になる可能性があるため、2倍のサイズを確保します。
-
rootEnd = new int(-1);とsplitEnd = new int(-1);- ルートと分割ノードの終了位置を初期化します。
-
root = std::make_unique<Node>(-1, rootEnd);- ルートノードを作成します。
-
activeNode = root.get();- アクティブノードをルートに設定します。
-
for (int i = 0; i < text.length(); i++) { extendSuffixTree(i); }- 文字列の各文字についてツリーを拡張します。
次に、パターンマッチングが効率的に行える実例を示します：
class SuffixTree {
// ... (前述のコード)
public:
// パターンマッチング：文字列内の全ての出現位置を見つける
std::vector<int> findAllOccurrences(const std::string& pattern) {
std::vector<int> result;
Node* node = root.get();
int i = 0;
// パターンに対応するノードを見つける
while (i < pattern.length()) {
auto foundChild = std::find_if(node->children.begin(), node->children.end(),
[this, &pattern, i](const auto& child) { return text[child->start] == pattern[i]; });
if (foundChild == node->children.end()) {
return result; // パターンが見つからない
}
node = foundChild->get();
int j = node->start;
while (i < pattern.length() && j <= *(node->end)) {
if (pattern[i] != text[j]) {
return result; // パターンが見つからない
}
i++;
j++;
}
}
// パターンが見つかった場合、そのノードの全ての子孫を探索
std::function<void(Node*, int)> dfs = [&](Node* n, int depth) {
if (n->children.empty()) {
result.push_back(text.length() - depth - pattern.length());
}
for (const auto& child : n->children) {
dfs(child.get(), depth + child->edgeLength());
}
};
dfs(node, i - pattern.length());
return result;
}
};
// 使用例
int main() {
std::string text = "banana";
SuffixTree tree(text);
std::string pattern = "ana";
auto occurrences = tree.findAllOccurrences(pattern);
std::cout << "Pattern '" << pattern << "' found at positions: ";
for (int pos : occurrences) {
std::cout << pos << " ";
}
std::cout << std::endl;
return 0;
}このコードは、与えられたパターンの全ての出現位置を効率的に見つけます。まず、パターンに対応するノードをツリー内で探し、そのノードの全ての子孫を深さ優先探索（DFS）で調べることで、全ての出現位置を見つけます。
この方法の利点は、パターンの長さに関係なく、テキスト全体を走査する必要がないことです。パターンに対応するノードを見つけた後は、そのサブツリーのみを探索すればよいため、非常に効率的です。
出力例：
Pattern 'ana' found at positions: 1 3
この例では、"ana"というパターンが"banana"という文字列の中で2回出現していることがわかります（位置1と3）。
このように、サフィックスツリーを使うと、複数のパターンマッチングを非常に効率的に行うことができます。特に、同じテキストに対して多くのパターン検索を行う場合に威力を発揮します。
いかがでしょうか？各行の詳細な説明と、パターンマッチングの実例を通じて、サフィックスツリーの仕組みと利点がより明確になったでしょうか？何か質問があれば、どうぞお聞きください。
サフィックスツリーの構築には、Ukkonen's Algorithmを使用しています。これは線形時間（O(n)）で動作する効率的なアルゴリズムです。
主なステップ：
- 文字列を1文字ずつ処理していきます。
- アクティブポイント（activeNode, activeEdge, activeLength）を使用して、新しいサフィックスの挿入位置を効率的に見つけます。
- 必要に応じて、ノードの分割や新しいノードの作成を行います。
- サフィックスリンクを使用して、次の挿入位置に素早く移動します。
- ルートノードから開始します。
- パターンの各文字について：
- その文字に対応する子ノードを探します。
- 見つかったら、エッジのラベルとパターンを比較します。
- 一致しない場合は検索失敗です。
- パターンの全ての文字が一致したら、検索成功です。
利点：
- 部分文字列の検索が高速（O(m)、mはパターンの長さ）
- 複数のパターンマッチングに効率的
- 最長共通部分文字列などの複雑な文字列操作に適している
欠点：
- 構築に時間がかかる（ただし、Ukkonen's Algorithmを使用すればO(n)）
- メモリ使用量が大きい
int main() {
std::string text = "banana";
SuffixTree tree(text);
std::cout << "Search 'ana': " << (tree.search("ana") ? "Found" : "Not found") << std::endl;
std::cout << "Search 'nan': " << (tree.search("nan") ? "Found" : "Not found") << std::endl;
std::cout << "Search 'nana': " << (tree.search("nana") ? "Found" : "Not found") << std::endl;
std::cout << "Search 'xyz': " << (tree.search("xyz") ? "Found" : "Not found") << std::endl;
return 0;
}出力：
Search 'ana': Found
Search 'nan': Found
Search 'nana': Found
Search 'xyz': Not found
この例では、"banana"という文字列からサフィックスツリーを構築し、いくつかのパターンで検索を行っています。
サフィックスツリーは、文字列の全てのサフィックスを効率的に格納し、高速な部分文字列検索を可能にする強力なデータ構造です。その構築は複雑ですが、一度構築すれば多様な文字列操作を高速に行うことができます。ただし、メモリ使用量が大きいという欠点もあるため、使用する状況に応じて適切なデータ構造を選択することが重要です。