はじめに
今回は「接尾辞木 (suffix tree)」というデータ構造について取り上げます。サフィックス (suffix : 接尾辞) とは、文字列のある位置から末尾までの文字列のことです。たとえば、文字列 abcd のサフィックスは abcd, bcd, cd, d の 4 つになります。
全部のサフィックスをトライ (trie) で表したものを suffix trie といい、パトリシア (patricia tree) で表したものを接尾辞木といいます。トライとパトリシアについては、拙作のページ トライとパトリシア をお読みください。
接尾辞木は高速な文字列処理を実現するために用いられるデータ構造です。テキスト長を N とすると、suffix trie は N2 に比例するメモリが必要になりますが、接尾辞木は N に比例するメモリで構築することができます。接尾辞木はナイーブに構築すると N2 に比例する時間がかかりますが、線形時間 (N に比例する時間) で構築するアルゴリズムが考案されています。特に、Ukkonen のアルゴリズム (1995 年) は線形時間かつオンラインで接尾辞木を構築することができます。
なお、接尾辞木よりもコンパクトなデータ構造に「接尾辞配列 (suffix array)」があります。接尾辞配列はデータ圧縮アルゴリズムのブロックソート法にも応用できるため、近年注目を集めているデータ構造の一つです。興味のある方は拙作のページ 接尾辞配列 (suffix array) をお読みくださいませ。
●接尾辞木の簡単な作り方
簡単な例を示しましょう。接尾辞木を構築する最も簡単な方法は、一番長い接尾辞から順番に挿入していくことです。ただし、この方法では接尾辞木の構築に時間がかかることに注意してください。たとえば、文字列 "banana$" の接尾辞木は下図のようになります。
節を [ ] で、葉を ( ) で、終端記号を $ で表しています。挿入処理はパトリシアと同じなので、とくに難しいところはないと思います。
●接尾辞木の特徴
このように、接尾辞木は文字列 s の全接尾辞をパトリシアで表したものです。上図の場合、$ を含めると banana$ の接尾辞は 7 通りあり、ルートから葉までの経路が一つの接尾辞に対応します。文字列長を N とすると、葉の個数は N になり、節の個数は N - 1 以下になります。したがって、接尾辞木の葉と節の総数は 2 * N - 1 以下に収まります。
接尾辞木の場合、ルートから節までの経路に対応する文字列は、ある接尾辞の接頭辞になります。たとえば、root - [a] - [na] とたどると、文字列 ana が得られます。ana は接尾辞 anana$ や ana$ の接頭辞になります。それと同時に、文字列 banana$ や nana$ の部分文字列にもなります。つまり、ルートからある節までの経路は、文字列 s の部分文字列を表しているのです。
したがって、文字列 s とパターン p を照合する場合、s の接尾辞木 st を用いれば、ルートからたどるだけでマッチングを高速に判定することができます。p が出現する位置や回数も、マッチングした節以下の部分木を巡回するだけで求めることができます。また、文字列 s の中で n 回以上現れる部分文字列を探すこと (頻出部分文字列検索) や 2 回以上現れる最長の部分文字列を探すことも、接尾辞木 st を巡回するだけで簡単に実現することができます。
このほかにも、接尾辞木は多種多様の文字列処理に応用することができます。接尾辞木・接尾辞配列の説明とその応用については、渋谷哲朗先生 の 講義資料 (スライド [pdf]) がとても参考になります。
●使用メモリの低減
ところで、上図のように部分文字列を節と葉に格納すると、メモリの使用量は文字列長の 2 乗に比例することになるので、次のように部分文字列を区間で表すことにします。
これで文字列長 N に比例するメモリ量で接尾辞木を構築することができます。なお、葉の場合、部分文字列の終端は文字列の最後尾になるので、部分文字列の開始位置だけ格納しておきます。こうしておくと、オンラインで接尾辞木を構築するときに便利です。
接尾辞木を構築するときはこれで十分なのですが、接尾辞木を使って文字列を検索するとき、区間だけでは処理がちょっと面倒になる場合があります。そこで、終了位置のかわりに、ルートから親節までの経路長 (親節までの接頭辞の長さ) を使うことにします。次の図を見てください。
開始位置を start、接頭辞の長さを depth で表します。たとえば、root - [a] - [na] - (na$) の場合、[a] の start は 1 で、depth は 0 になります。[na] の start は 2 で、depth は [a] の長さ 1 になります。(na$) の場合、start は 5 で、depth は [a] - [na] の長さ 3 になります。兄弟節の depth はすべて同じ値になるので、節 node の長さは子の depth から自分の depth を引き算することで求めることができます。
●節の定義
説明だけでは面白くないので、とりあえずナイーブな方法で接尾辞木を作ってみましょう。今回はトライと同様に、節の兄弟関係を連結リストで表すことにします。次の図を見てください。
縦に親子関係が伸びていき、横に兄弟の関係が伸びていくと考えてください。この方法は木をたどるときに連結リストを線形探索するため、時間がかかるのが欠点です。節の親子関係はハッシュ法を使って表した方が高速になりますが、接尾辞木を巡回する処理には適していません。
節を表すクラス Node の定義は次のようになります。
リスト : 節の定義
class Node:
# 初期化
def __init__(self, start, depth):
self.start = start # 開始位置
self.depth = depth # 木の深さ (接頭辞の長さ)
self.child = None # 子のリンク
self.bros = None # 兄弟のリンク
# 子を探す
def search_child(self, buff, size, x):
child = self.child
while child is not None:
if child.start < size and buff[child.start] == x:
return child
child = child.bros
return None
# 子を挿入する
def insert_child(self, child):
child.bros = self.child
self.child = child
# 子を削除する
def delete_child(self, child):
if self.child is child:
self.child = child.bros
else:
# リンクをたどる
node = self.child
while node.bros is not None:
if node.bros is child:
node.bros = node.bros.bros
break
node = node.bros
# 節の長さを求める
def len(self):
if self.start == ROOT: return 0
if self.child is None: return MAX_LEN # 葉
return self.child.depth - self.depth
# 葉を巡回する
def traverse_leaf(self):
if self.child is None:
yield self
else:
node = self.child
while node is not None:
for x in node.traverse_leaf():
yield x
node = node.bros
start と depth で部分文字列の区間を表します。ルートの場合、start にダミー値 ROOT (-1) を格納します。基本的な操作はパトリシアと同様なので、とくに難しいところはないと思います。
節の長さを求めるメソッド len() の場合、節がルートであれば 0 を返し、葉であれば MAX_LEN (0x7fffffff) を返します。それ以外の場合は、depth を使って節の長さを計算して返します。メソッド traverse_leaf() は部分木を巡回して葉を返します。これは文字列の検索処理で使用します。
●単純な実装方法
次は接尾辞木を表すクラス SuffixTree を定義します。次のリストを見てください。
リスト : Suffix Tree の構築
class SuffixTree:
def __init__(self, buff):
self.buff = buff
self.size = len(buff)
self.root = Node(ROOT, 0)
#
i = 0
while i < self.size:
# 最長一致を求める
p, q, end, sub_match = self.longest_match(self.root, i, self.size)
self.insert_node(p, q, end, sub_match)
i += 1
root に接尾辞木のルートをセットします。start の値は ROOT に、depth の値は 0 に設定します。あとは longest_match() で i 番目から始まる接尾辞との最長一致を求め、不一致の位置で節を分割して葉を挿入します。この処理を insert_node() で行います。
次はメソッド longest_match() を作ります。
リスト : node の次の子からの最長一致を求める
def longest_match(self, node, i, size):
buff = self.buff
prev = node
while i < size:
child = node.search_child(buff, size, buff[i])
if child is None: break
j = 1
k = child.len()
while j < k:
if i + j == size or buff[i + j] != buff[child.start + j]:
return node, child, i + j, j
j += 1
i += j
prev = node
node = child
return prev, node, i, 0
これもパトリシアの探索処理とほぼ同じです。節の途中で不一致になった場合、親節 node と子 child と、不一致になった buff の位置 i + j と、節の部分文字列を分割する位置 j を返します。child が見つからない場合は、node の部分文字列がすべて一致したことになります。この場合は node に葉を挿入するだけです。親節 prev, 子 node, 不一致になった buff の位置 i と node の部分文字列が全て一致したことを表す値 0 を返します。
なお、longest_match() は文字列 buff の終端でも節を分割するように作られています。今回のプログラムは、文字列に終端記号を付加しなくても接尾辞木を構築することが可能です。
次は節の分割と葉の挿入を行うメソッド insert_node() を作ります。
リスト : 節の分割と葉の挿入
def insert_node(self, parent, node, match, sub_match):
if sub_match > 0:
# node を new_node - node に分割する
new_node = Node(node.start, node.depth)
node.depth += sub_match
node.start += sub_match
# 子の付け替え
parent.delete_child(node)
parent.insert_child(new_node)
new_node.insert_child(node)
# new_node に葉を追加する
leaf = Node(match, node.depth)
new_node.insert_child(leaf)
else:
# node に葉を追加する
leaf = Node(match, node.depth + node.len())
node.insert_child(leaf)
引数 parent が親節、node が分割する節、match が buff で不一致になった位置、sub_match が node を分割する位置です。sub_match が 0 でない場合、node を sub_match の位置で分割します。新しい節を new_node とすると、prev と node の間に new_node を挿入します。したがって、new_node の区間は (node.start, node.depth) になり、node の区間は (node.start + sub_match, node.depth + sub_match) になります。
あとは、prev の子から node を削除して new_node を挿入し、new_node の子に node を挿入します。そして、新しい葉 leaf を作って、new_node に挿入します。sub_match が 0 の場合は、新しい葉 leaf を作って node に挿入するだけです。これでプログラムは完成です。
●簡単な実行例
それでは簡単なテストを行ってみましょう。次のリストを見てください。
リスト : 簡単なテスト
# デバッグ用表示ルーチン
def print_node(node, buff):
if node.child is None:
print(' ' * node.depth + buff[node.start:])
else:
if node.start != ROOT:
print(' ' * node.depth + buff[node.start:node.start + node.len()])
x = node.child
while x is not None:
print_node(x, buff)
x = x.bros
# 子の個数を数える
def count_child(node):
a = 0
x = node.child
while x is not None:
a += 1
x = x.bros
return a
# 同じ文字から始まる兄弟がないかチェックする
def check_same_child(node, buff):
if node.child:
x = buff[node.start]
node = node.bros
while node is not None:
if node.start < len(buff) and buff[node.start] == x:
raise SuffixTreeError('error2')
node = node.bros
# suffix tree のチェック
def check_node(node, buff):
if node.child is None:
return 1
else:
# 節
if node.start != ROOT and count_child(node) < 2:
print(id(node))
raise SuffixTreeError('error1')
x = node.child
a = 0
while x is not None:
check_same_child(x, buff)
a += check_node(x, buff)
x = x.bros
return a
# テスト
def test(buff):
st = SuffixTree(buff)
print_node(st.root, buff)
if check_node(st.root, buff) != len(buff):
raise SuffixTreeError('error3')
if __name__ == '__main__':
# suffix tree
test("banana$")
test("abcabbca$")
test("aaaaaaaa$")
test("mississippi$")
test("aabbaaab$")
関数 print_node() は接尾辞木を表示します。関数 check_node() は接尾辞木の条件を満たしているかチェックします。接尾辞木の場合、ルートと葉を除いた節には必ず 2 つ以上の子が存在します。子が 2 個未満の場合はエラーを送出します。それから、同じ文字で始まる子は存在しません。同じ文字で始まる子が見つかった場合はエラーを送出します。この処理を関数 check_same_child() で行っています。check_node() は葉の個数を返すので、それが文字列の長さと一致しない場合もエラーを送出します。
実行結果は次のようになります。
$
a
$
na
$
na$
na
$
na$
banana$
-----
$
a
$
b
bca$
cabbca$
ca
$
bbca$
b
ca
$
bbca$
bca$
-----
$
a
$
a
$
a
$
a
$
a
$
a
$
a
$
a$
-----
$
p
i$
pi$
i
$
ppi$
ssi
ppi$
ssippi$
s
i
ppi$
ssippi$
si
ppi$
ssippi$
mississippi$
-----
$
b
$
aaab$
baaab$
a
b
$
baaab$
a
b
$
baaab$
ab$
-----
正常に動作していますね。ちなみに、最後に $ を付けなくても接尾辞木を構築することができます。興味のある方はいろいろ試してみてください。
●簡単な応用例
それでは、実際に接尾辞木を使ってみましょう。最初にパターンを検索するメソッド search_pattern() を作ります。
リスト : パターンの検索
def search_pattern_sub(self, seq):
size = len(seq)
node = self.root
i = 0
while i < size:
child = node.search_child(self.buff, self.size, seq[i])
if child is None: return None
j = 1
k = child.len()
while j < k:
if i + j == size: return child
if i + j == self.size or seq[i + j] != self.buff[child.start + j]:
return None
j += 1
i += j
node = child
return node
def search_pattern(self, seq):
node = self.search_pattern_sub(seq)
return node is not None
def search_pattern_all(self, seq):
node = self.search_pattern_sub(seq)
if node is None: return
for x in node.traverse_leaf():
yield x.start - x.depth
メソッド search_pattern_sub() の処理は longest_match() とほとんど同じです。引数 seq に検索するパターンを渡します。そして、接尾辞木をルートからたどり、seq と一致した節を返します。見つからない場合は None を返します。search_pattern() は search_pattern_sub() を呼び出して、結果を True または Flase で返します。
search_pattern_all() は traverse_leaf() を呼び出して、node 以下の部分木に存在する葉をすべて求めます。つまり、seq が接頭辞となる接尾辞を求めているわけです。そして、その接尾辞の開始位置を計算して返します。これは葉の開始位置 start から depth を引き算するだけで求めることができます。
簡単な実行例を示します。
>>> from sufftree import *
>>> st = SuffixTree("banana banana$")
>>> st.search_pattern("banana")
True
>>> for x in st.search_pattern_all("banana"): print(x, end=' ')
...
7 0
>>> st.search_pattern("ana")
True
>>> for x in st.search_pattern_all("ana"): print(x, end=' ')
...
10 8 1 3
>>> st.search_pattern("bananas")
False
次は入力文字列の中で 2 回以上現れる最長の部分文字列を求めてみましょう。たとえば、sakurasaku$ で 2 回以上現れている部分文字列は次のようになります。
s, a, k, u, sa, ak, ku, sak, aku, saku
この場合、最長部分文字列は saku になります。接尾辞木の場合、葉を含む部分文字列は接尾辞になるので、入力文字列の中で一度しか現れていません。節の場合は 2 つ以上の子を持つので、それを含む部分文字列は入力文字列の中で必ず 2 回以上現れています。したがって、節を巡回して見つけた一番長い部分文字列が、条件を満たしていることになるのです。プログラムは次のようになります。
リスト : 2 回以上出現する最長の部分文字列を求める
def search_longest_repeated_substring(self, node):
if node.child is None:
# 葉は該当しない
return None
else:
max_node = node
x = node.child
while x is not None:
y = self.search_longest_repeated_substring(x)
if y is not None and max_node.child.depth < y.child.depth:
max_node = y
x = x.bros
return max_node
def longest_repeated_substring(self):
node = self.search_longest_repeated_substring(self.root)
return node.start - node.depth, node.start + node.len()
実際の処理は search_longest_repeated_substring() で行います。考え方は二分木の高さを求める処理と同じです。節 node の文字列長は node.child.depth で求めることができます。最初に node を max_node にセットして、メソッドを再帰呼び出しします。返り値 y が None でなければ、max_node と長さを比較します。y が長ければ max_node の値を y に書き換えます。全ての子をチェックしたら max_node を返します。
簡単な実行例を示しましょう。
>>> st = SuffixTree("sakurasaku$")
>>> st.longest_repeated_substring()
(0, 4)
>>> st = SuffixTree("bananasbanana$")
>>> st.longest_repeated_substring()
(0, 6)
最後に頻出部分文字列と出現回数を求めるプログラムを作りましょう。これも接尾辞木を巡回するだけで求めることができます。プログラムは次のようになります。
リスト : n 文字以上で m 回以上出現している部分文字列を求める
def search_repeated_substring(self, node, n, m, a):
if node.child is None:
c = 1
l = self.size - node.start
else:
# 葉の数を求める
x = node.child
c = 0
while x is not None:
c += self.search_repeated_substring(x, n, m, a)
x = x.bros
l = node.len()
# 節の長さと回数をチェック
if l > 0 and c >= m:
for k in range(l, 0, -1):
if node.depth + k < n: break
a.append((node.start - node.depth, node.start + k, c))
return c
def repeated_substring(self, n, m):
a = []
self.search_repeated_substring(self.root, n, m, a)
return a
一般に、部分文字列の最小単位は文字になりますが、メソッド repeated_substring() は文字数 m と頻度 n を指定することにしました。つまり、n 文字以上で m 回以上出現している部分文字列とその回数を求めます。
実際の処理は search_repeated_substring() で行います。このメソッドは接尾辞木を巡回して葉の個数を返します。まず node 以下の部分木にある葉の個数を求めます。次に、部分文字列長と出現回数をチェックします。それらが条件を満たしていたら、引数 a のリストに (開始位置, 終了位置, 回数) を追加します。最後に葉の個数を返します。
接尾辞木の場合、節 node の長さは 1 より大きくなることがあるので、節の部分文字列の途中から条件を満たす場合もあります。これをチェックするため、for 文で節の長さ k を一つずつ減らしながら、条件を満たす部分文字列を求めています。ただし、この処理を行うと条件によっては時間がかかる場合があります。
たとえば、n = 1, m = 1 とすると、全ての部分文字列の出現回数を求めることになります。文字列長を N とすると、部分文字列の総数は N2 に比例するので、N が大きくなると時間がかかるようになると思われます。もし、節の部分文字列をそのまま出力するだけでよければ、N に比例する時間で処理することが可能になります。この処理のほうが簡単なので、興味のある方はプログラムを改造してみてください。
簡単な実行例を示しましょう。
>>> a = "sakurasaku$" >>> st = SuffixTree(a) >>> for s, e, c in st.repeated_substring(1, 2): print(a[s:e], c) ... u 2 ku 2 k 2 saku 2 sak 2 sa 2 s 2 aku 2 ak 2 a 3
今回はここまでです。次回は Ukkonen のアルゴリズムを使って接尾辞木を作ってみましょう。
●追記
今回のプログラムは葉を節と同じクラス Node で表しているため、インスタンス変数 child, bros が無駄になっています。そこで、節をクラス Node で、葉をクラス Leaf で表すようにプログラムを作り直しました。興味のある方はお読みくださいませ。
●プログラムリスト
#
# sufftree.py : 接尾辞木 (Suffix Tree)
# (一番長い接尾辞から挿入していく方法)
#
# Copyright (C) 2009-2022 Makoto Hiroi
#
# 定数
ROOT = -1
MAX_LEN = 0x7fffffff
# 節の定義
class Node:
# 初期化
def __init__(self, start, depth):
self.start = start # 開始位置
self.depth = depth # 木の深さ
self.child = None # 子のリンク
self.bros = None # 兄弟のリンク
# 子を探す
def search_child(self, buff, size, x):
child = self.child
while child is not None:
if child.start < size and buff[child.start] == x:
return child
child = child.bros
return None
# 子を挿入する
def insert_child(self, child):
child.bros = self.child
self.child = child
# 子を削除する
def delete_child(self, child):
if self.child is child:
self.child = child.bros
else:
# リンクをたどる
node = self.child
while node.bros is not None:
if node.bros is child:
node.bros = node.bros.bros
break
node = node.bros
# 節の長さを求める
def len(self):
if self.start == ROOT: return 0
if self.child is None: return MAX_LEN # 葉
return self.child.depth - self.depth
# 葉を巡回する
def traverse_leaf(self):
if self.child is None:
yield self
else:
node = self.child
while node is not None:
for x in node.traverse_leaf():
yield x
node = node.bros
# Suffix Tree
class SuffixTreeError(Exception): pass
class SuffixTree:
def __init__(self, buff):
self.buff = buff
self.size = len(buff)
self.root = Node(ROOT, 0)
#
i = 0
while i < self.size:
# 最長一致を求める
p, q, end, sub_match = self.longest_match(self.root, i, self.size)
self.insert_node(p, q, end, sub_match)
i += 1
# node の次の子からの最長一致を求める
def longest_match(self, node, i, size):
buff = self.buff
prev = node
while i < size:
child = node.search_child(buff, size, buff[i])
if child is None: break
j = 1
k = child.len()
while j < k:
if i + j == size or buff[i + j] != buff[child.start + j]:
return node, child, i + j, j
j += 1
i += j
prev = node
node = child
return prev, node, i, 0
# 節の挿入
def insert_node(self, parent, node, match, sub_match):
if sub_match > 0:
# node を new_node - node に分割する
new_node = Node(node.start, node.depth)
node.depth += sub_match
node.start += sub_match
# 子の付け替え
parent.delete_child(node)
parent.insert_child(new_node)
new_node.insert_child(node)
# new_node に葉を追加する
leaf = Node(match, node.depth)
new_node.insert_child(leaf)
else:
# node に葉を追加する
leaf = Node(match, node.depth + node.len())
node.insert_child(leaf)
# 共通接頭辞の検索
def search_pattern_sub(self, seq):
size = len(seq)
node = self.root
i = 0
while i < size:
child = node.search_child(self.buff, self.size, seq[i])
if child is None: return None
j = 1
k = child.len()
while j < k:
if i + j == size: return child
if i + j == self.size or seq[i + j] != self.buff[child.start + j]:
return None
j += 1
i += j
node = child
return node
def search_pattern(self, seq):
node = self.search_pattern_sub(seq)
return node is not None
def search_pattern_all(self, seq):
node = self.search_pattern_sub(seq)
if node is None: return
for x in node.traverse_leaf():
yield x.start - x.depth
# n 文字以上 m 回以上出現している文字列を求める
def search_repeated_substring(self, node, n, m, a):
if node.child is None:
c = 1
l = self.size - node.start
else:
# 葉の数を求める
x = node.child
c = 0
while x is not None:
c += self.search_repeated_substring(x, n, m, a)
x = x.bros
l = node.len()
# 節の長さと回数をチェック
if l > 0 and c >= m:
for k in range(l, 0, -1):
if node.depth + k < n: break
a.append((node.start - node.depth, node.start + k, c))
return c
def repeated_substring(self, n, m):
a = []
self.search_repeated_substring(self.root, n, m, a)
return a
# 2 回以上繰り返しのある最長の文字列を求める
def search_longest_repeated_substring(self, node):
if node.child is None:
# 葉は該当しない
return None
else:
max_node = node
x = node.child
while x is not None:
y = self.search_longest_repeated_substring(x)
if y is not None and max_node.child.depth < y.child.depth:
max_node = y
x = x.bros
return max_node
def longest_repeated_substring(self):
node = self.search_longest_repeated_substring(self.root)
return node.start - node.depth, node.start + node.len()
# デバッグ用表示ルーチン
def print_node(node, buff):
if node.child is None:
print(' ' * node.depth + buff[node.start:])
else:
if node.start != ROOT:
print(' ' * node.depth + buff[node.start:node.start + node.len()])
x = node.child
while x is not None:
print_node(x, buff)
x = x.bros
# 子の個数を数える
def count_child(node):
a = 0
x = node.child
while x is not None:
a += 1
x = x.bros
return a
# 同じ文字から始まる兄弟がないかチェックする
def check_same_child(node, buff):
if node.child:
x = buff[node.start]
node = node.bros
while node is not None:
if node.start < len(buff) and buff[node.start] == x:
raise SuffixTreeError('error2')
node = node.bros
# suffix tree のチェック
def check_node(node, buff):
if node.child is None:
return 1
else:
# 節
if node.start != ROOT and count_child(node) < 2:
print(id(node))
raise SuffixTreeError('error1')
x = node.child
a = 0
while x is not None:
check_same_child(x, buff)
a += check_node(x, buff)
x = x.bros
return a
# テスト
def test(buff):
st = SuffixTree(buff)
print_node(st.root, buff)
if check_node(st.root, buff) != len(buff):
raise SuffixTreeError('error3')
print('-----')
for x in range(0, len(buff)):
a = buff[x:]
print(a, st.search_pattern(a), end=' ')
for y in st.search_pattern_all(a):
print(y, end=' ')
print()
print('-----')
s, e = st.longest_repeated_substring()
print(s, e, buff[s:e])
print('-----')
for s, e, c in st.repeated_substring(2, 2):
print(s, e, c, buff[s:e])
print('-----')
if __name__ == '__main__':
# suffix tree
test("banana$")
test("abcabbca$")
test("aaaaaaaa$")
test("mississippi$")
test("aabbaaab$")
test("banana")
test("abcabbca")
test("aaaaaaaa")
test("mississippi")
test("aabbaaab")
●プログラムリスト２
#
# sufftree.py : 接尾辞木 (Suffix Tree)
# (一番長い接尾辞から挿入していく方法)
#
# Copyright (C) 2009-2022 Makoto Hiroi
#
# 定数
ROOT = -1
MAX_LEN = 0x7fffffff
count = 0
def print_count(): print(count)
# 基本クラス
class BaseNode:
def __init__(self, start, depth):
self.start = start # 開始位置
self.depth = depth # 木の深さ
# 葉の定義
class Leaf(BaseNode):
def __init__(self, start, depth):
BaseNode.__init__(self, start, depth)
# 葉の長さ
def len(self): return MAX_LEN
# 葉の巡回
def traverse_leaf(self): yield self
# 節の定義
class Node(BaseNode):
# 初期化
def __init__(self, start, depth):
BaseNode.__init__(self, start, depth)
self.child = None # 子のリンク
self.bros = None # 兄弟のリンク
# 子を探す
def search_child(self, buff, size, x):
global count
count += 1
child = self.child
while child is not None:
if child.start < size and buff[child.start] == x:
return child
child = child.bros
return None
# 子を挿入する
def insert_child(self, child):
child.bros = self.child
self.child = child
# 子を削除する
def delete_child(self, child):
if self.child is child:
self.child = child.bros
else:
# リンクをたどる
node = self.child
while node.bros is not None:
if node.bros is child:
node.bros = node.bros.bros
break
node = node.bros
# 節の長さを求める
def len(self):
if self.start == ROOT: return 0
return self.child.depth - self.depth
# 葉を巡回する
def traverse_leaf(self):
node = self.child
while node is not None:
for x in node.traverse_leaf():
yield x
node = node.bros
# Suffix Tree
class SuffixTree:
def __init__(self, buff):
self.buff = buff
self.size = len(buff)
self.root = Node(ROOT, 0)
#
i = 0
while i < self.size:
# 最長一致を求める
p, q, end, sub_match = self.longest_match(self.root, i, self.size)
self.insert_node(p, q, end, sub_match)
i += 1
# node の次の子からの最長一致を求める
def longest_match(self, node, i, size):
buff = self.buff
prev = node
while i < size:
child = node.search_child(buff, size, buff[i])
if child is None: break
j = 1
k = child.len()
while j < k:
if i + j == size or buff[i + j] != buff[child.start + j]:
return node, child, i + j, j
j += 1
i += j
prev = node
node = child
return prev, node, i, 0
# 節の挿入
def insert_node(self, parent, node, match, sub_match):
if sub_match > 0:
# node を new_node - node に分割する
new_node = Node(node.start, node.depth)
node.depth += sub_match
node.start += sub_match
# 子の付け替え
parent.delete_child(node)
parent.insert_child(new_node)
new_node.insert_child(node)
# new_node に葉を追加する
leaf = Leaf(match, node.depth)
new_node.insert_child(leaf)
else:
# node に葉を追加する
leaf = Leaf(match, node.depth + node.len())
node.insert_child(leaf)
# 共通接頭辞の検索
def search_pattern_sub(self, seq):
size = len(seq)
node = self.root
i = 0
while i < size:
child = node.search_child(self.buff, self.size, seq[i])
if child is None: return None
j = 1
k = child.len()
while j < k:
if i + j == size: return child
if i + j == self.size or seq[i + j] != self.buff[child.start + j]:
return None
j += 1
i += j
node = child
return node
def search_pattern(self, seq):
node = self.search_pattern_sub(seq)
return node is not None
def search_pattern_all(self, seq):
node = self.search_pattern_sub(seq)
if node is None: return
for x in node.traverse_leaf():
yield x.start - x.depth
# n 文字以上 m 回以上出現している文字列を求める
def search_repeated_substring(self, node, n, m, a):
if isinstance(node, Leaf):
c = 1
l = self.size - node.start
else:
# 葉の数を求める
x = node.child
c = 0
while x is not None:
c += self.search_repeated_substring(x, n, m, a)
x = x.bros
# 節の長さをチェック
l = node.len()
if l > 0 and c >= m:
for k in range(l, 0, -1):
if node.depth + k < n: break
a.append((node.start - node.depth, node.start + k, c))
return c
def repeated_substring(self, n, m):
a = []
self.search_repeated_substring(self.root, n, m, a)
return a
# 2 回以上繰り返しのある最長の文字列を求める
def search_longest_repeated_substring(self, node):
if isinstance(node, Leaf):
# 葉は該当しない
return None
else:
max_node = node
x = node.child
while x is not None:
y = self.search_longest_repeated_substring(x)
if y is not None and max_node.child.depth < y.child.depth:
max_node = y
x = x.bros
return max_node
def longest_repeated_substring(self):
node = self.search_longest_repeated_substring(self.root)
return node.start - node.depth, node.start + node.len()
# デバッグ用表示ルーチン
def print_node(node, buff):
if isinstance(node, Leaf):
print(' ' * node.depth + buff[node.start:])
else:
if node.start != ROOT:
print(' ' * node.depth + buff[node.start:node.start + node.len()])
x = node.child
while x is not None:
print_node(x, buff)
x = x.bros
# 子の個数を数える
def count_child(node):
a = 0
if isinstance(node, Node):
x = node.child
while x is not None:
a += 1
x = x.bros
return a
# 同じ文字から始まる兄弟がないかチェックする
def check_same_child(node, buff):
if isinstance(node, Node):
x = buff[node.start]
node = node.bros
while node is not None:
if node.start < len(buff) and buff[node.start] == x:
raise SuffixTreeError('error2')
node = node.bros
# suffix tree のチェック
def check_node(node, buff):
if isinstance(node, Leaf):
return 1
else:
# 節
if node.start != ROOT and count_child(node) < 2:
print(id(node))
raise SuffixTreeError('error1')
x = node.child
a = 0
while x is not None:
check_same_child(x, buff)
a += check_node(x, buff)
x = x.bros
return a
# テスト
def test(buff):
st = SuffixTree(buff)
print_node(st.root, buff)
if check_node(st.root, buff) != len(buff):
raise SuffixTreeError('error3')
print('-----')
for x in range(0, len(buff)):
a = buff[x:]
print(a, st.search_pattern(a), end=' ')
for y in st.search_pattern_all(a):
print(y, end=' ')
print()
print('-----')
s, e = st.longest_repeated_substring()
print(s, e, buff[s:e])
print('-----')
for s, e, c in st.repeated_substring(2, 2):
print(s, e, c, buff[s:e])
print('-----')
if __name__ == '__main__':
# suffix tree
test("banana$")
test("abcabbca$")
test("aaaaaaaa$")
test("mississippi$")
test("aabbaaab$")
test("banana")
test("abcabbca")
test("aaaaaaaa")
test("mississippi")
test("aabbaaab")
改訂 2022 年 10 月 1 日