接尾辞木の続きです。今回は 1995 年に Ukkonen が考案した線形時間でかつオンラインで接尾辞木を構築するアルゴリズムを説明します。
Ukkonen のアルゴリズムの基本的な考え方は、文字を読み込みながら接尾辞木を構築していくところです。次の図を見てください。
(1) b, a, n を読み込む
┌ (an)
│
root ┼ (ban)
│
└ (n)
(2) a, n, a を読み込む
...
┌ (anana) : (anana) の ana まで一致
│
root ┼ (banana)
│
└ (nana)
(3) $ を読み込む
┌ [ana] ┬ (na$) : ana まで一致、n で不一致、そこで分割する
│ └ ($) : 葉 ($) を挿入する
│
root ┼ (banana$)
│
└ (nana$)
(4) na$ を挿入
┌ [ana] ┬ (na$)
│ └ ($)
│
root ┼ (banana$)
│
└ [na] ┬ (na$) : na まで一致、n で不一致、そこで分割する
└ ($) : 葉を挿入する
(5) a$ を挿入
┌ [a] ┬ [na] ┬ (na$) : ana を [a] - [na] に分割
│ │ └ ($)
│ └ ($) : 葉を挿入する
│
root ┼ (banana$)
│
└ [na] ┬ (na$)
└ ($)
(6) $ を挿入
┌ [a] ┬ [na] ┬ (na$) : anana$
│ │ │
│ │ └ ($) : ana$
│ │
│ └ ($) : a$
│
root ┼ (banana$) : banana$
│
├ [na] ┬ (na$) : nana$
│ │
│ └ ($) : na$
│
└ ($) : $
図 : banana$ の接尾辞木 (Ukkonen のアルゴリズム)
(1) で b, a, n を読み込むとき、接尾辞木をたどることができないので、ルートに葉 (ban), (an), (n) が挿入されます。葉の区間は開始位置から文字列の終わりまでであることに注意してください。つまり、文字を読み込むたびに葉の区間は長くなっていきます。そして、この時点で ban までの接尾辞木ができていることにも注意してください。
(2) で a, n, a を読み込みますが、これは接尾辞木をたどることができます。葉 (anana) の ana まで一致します。次に (3) で $ を読み込みます。この時点で、接尾辞木 には banana$, anana$, nana$ が挿入されています。あとは、ana$ の接尾辞を挿入すればいいのです。
葉の次の文字は n なので不一致になります。ここで、葉を [ana] - (na$) に分割して、節 [ana] に葉 ($) を挿入します。次に na$ を挿入します (4)。接尾辞木をたどり、葉 (nana$) を [na] - (na$) に分割して葉 ($) を挿入します。その次に a$ を挿入します (5)。節 [ana] を [a] - [na] に分割して葉 ($) を挿入します。最後にルートに葉 ($) を挿入して、banana$ の接尾辞木が完成します (6)。
簡単にまとめると、次のようになります。接尾辞木をたどって一致した区間が (s, e) とします。このとき、(0, e), (1, e), ..., (s - 1, e) までの接尾辞は接尾辞木に挿入されている、つまり区間 (0, s - 1) の接尾辞木は完成しています。あとは区間 (s, e) の接尾辞 (s, e), (s + 1, e), ..., (e - 1, e) を挿入すればいいわけです。
ただし、これらの接尾辞を挿入するとき、ルートから接尾辞木をたどっていくと時間がかかってしまい、線形時間で接尾辞木を構築することができません。そこで、節にサフィックスリンク (suffix links) というデータを持たせることにします。
サフィックスリンク (suffix links) は、節 p から一つ短い接尾辞を持つ節 q へのリンクのことです。接尾辞木を構築するとき、葉のサフィックスリンクは不要です。次の図を見てください。
A B
┌ [a] ┬ [na] ┬ (na$) : anana$
│ │ │
│ │ └ ($) : ana$
│ │
│ └ ($) : a$
│
root ┼ (banana$) : banana$
│
│ C
├ [na] ┬ (na$) : nana$
│ │
│ └ ($) : na$
│
└ ($) : $
suffix links : B -> C -> A -> root
図 : banana$ のサフィックスリンク
接尾辞 ana$ より一つ短い接尾辞は na$ になります。節 B は ana$ を持っていて、節 C は na$ を持っています。この場合、B のリンク先は C になります。na$ より一つ短い接尾辞は a$ で、これは節 A が持っています。よって、C のリンク先は A になります。同様に、接尾辞 $ を持っているのは root なので、A のリンク先は root になります。
サフィックスリンクは接頭辞で考えた方がわかりやすいと思います。節 B までたどって得られる接頭辞は ana です。これより一つ少ない接頭辞は na で、これは節 C になります。na より一つ少ない接頭辞は a で、これは節 A になります。a より一つ少ない接頭辞は空文字列で、これは root になります。よって、サフィックスリンクは B -> C -> A -> root になります。
簡単な例を示します。文字列 bananasanan$ の接尾辞木を作ってみましょう。bananas までの接尾辞木は banana$ と同じです。
(1) a, n, a, n, $ を読み込む
. .. .
┌ [a] ┬ [na] ┬ [n] ┬ (asanan$) : anan まで一致
│ A │ B │ D └ ($) : (nasanan$) を分割して ($) を挿入
│ │ └ (sanan$)
│ │
│ └ (sanan$)
│
root ┼ (bananasanan$)
│
├ [na] ┬ (nasanan$)
│ C │
│ └ (sanan$)
│
└ (sanan$)
(2) n, a, n, $ を挿入
┌ [a] ┬ [na] ┬ [n] ┬ (asanan$)
│ A │ B │ D └ ($)
│ │ └ (sanan$)
│ │
│ └ (sanan$)
│
root ┼ (bananasanan$)
│
├ [na] ┬ [n] ┬ (asanan$) : B のリンクをたどり C へ移動
│ C │ E └ ($) : (nasanan$) を分割して ($) を挿入
│ └ (sanan$) : suffix links : D -> E
│
└ (sanan$)
(3) a, n, $ を挿入
┌ [a] ┬ [n] ┬ [a] ┬ [n] ┬ (asanan$) : C のリンクをたどり A へ移動
│ A │ F │ B │ D └ ($) : [na] を分割して ($) を挿入
│ │ │ └ (sanan$) : suffix links : E -> F
│ │ └ ($)
│ └ (sanan$)
│
root ┼ (bananasanan$)
│
├ [na] ┬ [n] ┬ (asanan$)
│ C │ E └ ($)
│ └ (sanan$)
│
└ (sanan$)
(3) n, $ を挿入
┌ [a] ┬ [n] ┬ [a] ┬ [n] ┬ (asanan$)
│ A │ F │ B │ D └ ($)
│ │ │ └ (sanan$)
│ │ └ ($)
│ └ (sanan$)
│
root ┼ (bananasanan$)
│
├ [n] ┬ [a] ┬ [n] ┬ (asanan$) : A のリンク先は root
│ G │ C │ E └ ($) : [na] を分割して ($) を挿入
│ │ └ (sanan$) : suffix links : F -> G
│ └ ($)
└ (sanan$)
(4) $ を挿入
┌ [a] ┬ [n] ┬ [a] ┬ [n] ┬ (asanan$)
│ A │ F │ B │ D └ ($)
│ │ │ └ (sanan$)
│ │ └ ($)
│ └ (sanan$)
│
root ┼ (bananasanan$)
│
├ [n] ┬ [a] ┬ [n] ┬ (asanan$)
│ G │ C │ E └ ($)
│ │ └ (sanan$)
│ └ ($)
├ (sanan$)
└ ($) : suffix links : G -> root
suffix links : B -> C -> A -> root
: D -> E -> F -> G -> root
図 : bananasnana$ のサフィックスリンク
a, n, a, n と読み込み、接尾辞木をたどります。経路は [a] - [na] - (nasanan) となり、葉 (nasanan) の先頭文字 n まで一致します。次に、$ を読み込むと次の文字 a と不一致になるので、葉 (nasanan$) を [n] - (asanan$) に分割し、節 D に葉 ($) を挿入します (1)。
次は分割前の親節 B のサフィックスリンクをたどって節 C へ移動し、nan$ 挿入します (2)。節 C から不一致となる節 (葉) (nasanan$) を求め、[n] - (asanan$) に分割します。そして、節 E に葉 ($) を挿入します。ここで、節 D のサフィックスリンクが節 E に定まります。
次は節 C のサフィックスリンクをたどり節 A に移動し、an$ を挿入します (3)。節 A から不一致となる節 [na] を求め、[n] - [a] に分割します。そして、節 F に葉 ($) を挿入します。ここで、節 E のサフィックスリンクが節 F に定まります。
次は n$ を挿入します。節 A のサフィックスリンクは root なので、root から不一致となる節を探索し、節 C の [na] を [n] - [a] に分割して、節 G に葉 ($) を挿入します (3)。節 F のサフィックスリンクは G に定まります。最後に root に葉 ($) を挿入します。G のサフィックスリンクは root になります (4)。これで bananasanan$ の接尾辞木が完成します。
もう一つ簡単な例を示しましょう。bananasana$ の接尾辞木を作ります。$ の前の n が 1 文字少ないことに注意してください。bananas までの接尾辞木は banana$ と同じです。
(1) a, n, a, $ を読み込む
. ..
┌ [a] ┬ [na] ┬ (asana$) : ana まで一致
│ A │ B │
│ │ ├ (sana$)
│ │ └ ($) : 葉を挿入する
│ └ (sana$)
│
root ┼ (bananasana$)
│
├ [na] ┬ (nasana$)
│ C │
│ └ (sana$)
│
└ (sana$)
(2) n, a, $ を挿入
┌ [a] ┬ [na] ┬ (asana$)
│ A │ B │
│ │ ├ (sana$)
│ │ └ ($)
│ └ (sana$)
│
root ┼ (bananasana$)
│
├ [na] ┬ (nasana$) ; 節 B のサフィックスリンクをたどり
│ C │ ; 節 C へ移動する
│ ├ (sana$)
│ └ ($) : 葉を挿入する
└ (sana$)
(3) a, $ を挿入
┌ [a] ┬ [na] ┬ (asana$)
│ A │ B │
│ │ ├ (sana$)
│ │ └ ($) : 節 C のサフィックスリンクをたどり
│ ├ (sana$) : 節 A へ移動する
│ └ ($) : 葉を挿入する
root ┼ (bananasana$)
│
├ [na] ┬ (nasana$)
│ C │
│ ├ (sana$)
│ └ ($)
└ (sana$)
(4) $ を挿入
┌ [a] ┬ [na] ┬ (asana$)
│ A │ B │
│ │ ├ (sana$)
│ │ └ ($)
│ ├ (sana$)
│ └ ($)
root ┼ (bananasana$)
│
├ [na] ┬ (nasana$)
│ C │
│ ├ (sana$)
│ └ ($)
├ (sana$)
└ ($)
suffix links : B -> C -> A -> root
図 : bananasnan$ のサフィックスリンク
(1) で a, n, a, $ と読み込むと、節 B の終わりまで一致します。節 B の子に $ で始まる子がないので、B に葉を ($) を挿入します。次は節 B のサフィックスリンクをたどり、節 C へ移動して na$ を挿入します。この場合も、節 C の終わりまで一致して、C に $ で始まる子がないので、C に葉 ($) を挿入するだけです (2)。同様に (3) で節 A に葉 ($) を挿入します。最後に葉 ($) を root に挿入して bananasana$ の接尾辞木が完成します (4)。
このように、節を分割しないで葉を挿入するだけの場合、サフィックスリンク先の節も葉を挿入するだけでよいのです。そして、そのサフィックスリンクは必ず存在します。
たとえば、接頭辞が abcde で、e を格納している節 p に葉を挿入することにしましょう。節 p の最後の文字が e の場合、abcde - f や abcde - g など abcde を接頭辞に持つ部分文字列が必ず複数存在します。ということは、bcde, cde, de, e を接頭辞に持つ部分文字列も必ず複数存在することなります。つまり、それらの接頭辞を持つ節は文字 e で必ず終わっているのです。
したがって、p のサフィックスリンクをたどれば、bcde を接頭辞として持つ節 q へ移動することができ、q のサフィックススリンクをたどれば、cde を接頭辞として持つ節へ移動することができます。あとはそれらの節に葉を挿入していけばいいのです。
ところで、Ukkonen のアルゴリズムを適用するとき、注意する点がひとつあります。簡単な例として、文字列 aabbaaab$ の接尾辞木を作成してみましょう。次の図を見てください。
(1) a, a を読み込む
.
root ─ (aa) : 葉 (aa) の a まで一致
(2) b を読み込む
root ┬ [a] ┬ (ab) : 節 A のサフィックスリンクは root
│ A │
│ └ (b)
│
└ (b)
(3) b を読み込む
root ┬ [a] ┬ (abb)
│ A │
│ └ (bb)
│ .
└ (bb) : 葉 (bb) の b まで一致
(4) a を読み込む
.
root ┬ [a] ┬ (abba) : [a] の a まで一致
│ A │
│ └ (bba)
│
└ [b] ┬ (ba) : [b] - (ba) に分割
B │ : 節 B のサフィックスリンクは root
└ (a) : (a) を挿入
(5) a を読み込む
. .
root ┬ [a] ┬ (abbaa) : (abbaa) の a まで一致
│ A │
│ └ (bbaa)
│
└ [b] ┬ (baa)
B │
└ (aa)
(6) a を読み込む (aaa を挿入)
root ┬ [a] ┬ [a] ┬ (bbaaa) : [a] - (bbaaa) に分割
│ A │ C │
│ │ └ (a) : a を挿入
│ │
│ └ (bbaaa)
│
└ [b] ┬ (baaa)
B │
└ (aaa)
(7) aa を挿入
. .
root ┬ [a] ┬ [a] ┬ (bbaaa) : 節 A に a から始まる子 C があるので
│ A │ C │ : 節 A に葉 (a) は挿入しない
│ │ └ (a) : 節 C のサフィックスリンクは節 A になる
│ │
│ └ (bbaaa)
│
└ [b] ┬ (baaa)
B │
└ (aaa)
図 : aabbaaab$ の接尾辞木 (1)
a, a, b, b, a, a と読み込むと、(1) から (5) のように接尾辞木が構築されます。このとき、接尾辞木と一致している文字列は aa です。次に a を読み込むと、葉 (abbaaa) の b と比較するので不一致になります。葉 (abbaaa) を [a] - (bbaaa) に分割して、節 [a] に葉 (a) を挿入します。
次は aa を挿入します。今までの例では、最初の a で一致する節が必ず見つかり、次の a で不一致になる節が見つかります。ところが (7) のように、最初の a は節 A で一致しますが、次の a は節 C で一致します。この場合、節 A に葉 (a) を挿入してはいけません。節 C のサフィックスリンクは節 A になり、ここで挿入処理を終了します。
一般に、Si, ..., Sj, ..., Sk の文字列を挿入するとき、区間 (j, k) の文字列が既に接尾辞木に存在するのであれば、それより短い区間 (j + 1, k), (j + 2, k), ..., (k - 1, k), (k, k) の文字列は (j, k) の接尾辞になるので、Ukkonen のアルゴリズムで接尾辞木を構築すれば必ず存在するはずです。したがって、ここで文字列の挿入処理を中断してよいのです。
あとは、区間 (j, k) まで接尾辞木と一致したわけですから、それ以降の文字を読み込んで接尾辞木をたどっていきます。そして、l 番目で不一致になったならば、接尾辞木に区間 (j, l) の文字列とその接尾辞を挿入すればよいわけです。たとえば aabbaaab$ の場合、(7) では aabba まで接尾辞が出来上がり、その次の a, a まで読み込み、接尾辞木の節 C までたどっている、という状態にします。あとの処理は次のようになります。
(8) b を読み込む
. . .
root ┬ [a] ┬ [a] ┬ (bbaaab) : (bbaaab) の b まで一致
│ A │ C │
│ │ └ (ab)
│ │
│ └ (bbaaab)
│
└ [b] ┬ (baaab)
B │
└ (aaab)
(9) $ を読み込む (aab$ を挿入)
. . .
root ┬ [a] ┬ [a] ┬ [b] ┬ (baaab$)
│ A │ C │ D │ .
│ │ │ └ ($)
│ │ │
│ │ └ (ab$)
│ │
│ └ (bbaaab$)
│
└ [b] ┬ (baaab$)
B │
└ (aaab$)
(10) ab$ を挿入
root ┬ [a] ┬ [a] ┬ [b] ┬ (baaab$)
│ A │ C │ D │
│ │ │ └ ($)
│ │ │
│ │ └ (ab$)
│ │
│ └ [b] ┬ (baaab$) : 節 D のサフィックスリンクは節 E
│ E │
│ └ ($)
│
└ [b] ┬ (baaab$)
B │
└ (aaab$)
(11) b$ を挿入
root ┬ [a] ┬ [a] ┬ [b] ┬ (baaab$)
│ A │ C │ D │
│ │ │ └ ($)
│ │ │
│ │ └ (ab$)
│ │
│ └ [b] ┬ (baaab$)
│ E │
│ └ ($)
│
└ [b] ┬ (baaab$) : 節 D のサフィックスリンクは節 B
B │
├ (aaab$)
│
└ ($)
(12) $ を挿入
root ┬ [a] ┬ [a] ┬ [b] ┬ (baaab$)
│ A │ B │ C │
│ │ │ └ ($)
│ │ │
│ │ └ (ab$)
│ │
│ └ [b] ┬ (baaab$)
│ D │
│ └ ($)
│
├ [b] ┬ (baaab$)
│ E │
│ ├ (aaab$)
│ │
│ └ ($)
│
└ ($)
suffix link : B -> A -> root
C -> D -> E -> root
図 : aabbaaab$ の接尾辞木 (2)
(8) で b を読み込むと葉 (bbaaab) の先頭文字 b と一致します。次に、(9) で $ を読み込むと、葉の次の文字 b で不一致になるので、葉を [b] - (baaab$) に分割します。次に節 C のリンクをたどり節 A に移動します (10)。ab$ を挿入するので、節 A から b$ を挿入すると、葉 (bbaaab$) の先頭文字 b まで一致して、次の文字 b で不一致になります。葉を [b] - (baaab$) に分割します。節 D のサフィックスリンクは節 E になります。
次に、節 A のリンクをたどると root になります。root から b$ を挿入すると、節 B に葉 ($) を挿入することになります。この場合、節 D のサフィックスリンクは B になります (11)。最後に root に葉 ($) を挿入して接尾辞木が完成します (12)。
それではプログラムを作りましょう。節を表すクラス Node はサフィックスリンクを格納する変数 link を追加するだけで、あとはそのまま利用することができます。接尾辞木を表すクラス SuffixTree は次のようになります。
リスト : 接尾辞木の構築 (Ukkonen のアルゴリズム)
class SuffixTree:
def __init__(self, buff):
self.buff = buff
self.size = len(buff)
self.root = Node(ROOT, 0)
self.root.link = self.root
#
bi = 0 # buff の位置
ni = 0 # node 内の位置
si = 0 # 照合開始位置
node = self.root # 照合中の節
prev = node # node の親節
nlen = 0 # node の長さ
while bi < self.size:
if ni == nlen:
# 次の子を探す
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is None:
if si == bi:
# ルートに挿入
self.root.insert_child(Node(bi, 0))
si += 1
bi += 1
else:
# 葉を挿入する
prev, node, nlen, ni, si, bi = self.insert_leaf(node, bi, si)
else:
prev = node
node = child
nlen = child.len()
ni = 1
bi += 1
else:
if buff[bi] != buff[node.start + ni]:
# 節を分割して葉を挿入する
prev, node, nlen, ni, si, bi = self.divide_node(prev, node, ni, bi, si)
else:
ni += 1
bi += 1
#
if si < bi:
if nlen == ni:
self.insert_leaf(node, bi, si)
else:
self.divide_node(prev, node, ni, bi, si)
root のサフィックスリンク root.link は root 自身に初期化します。局所変数 node が探索中の節、nlen が節の長さ、prev が node の親節を表します。そして、bi が buff の検索位置、ni が節内の検索位置、si が接尾辞木と照合を開始した位置を表します。探索中の状態を保持する変数が多く必要になるため、プログラムはかなり複雑になります。
while ループの中で最初に ni と nlen を比較します。等しい場合、node の部分文字列と一致したので、search_child で次の子を探します。見つからない場合、その節に葉を挿入します。si と bi が等しい場合は、root に葉を挿入するだけです。葉の場合、サフィックスリンクの設定は不要です。そうでなければメソッド insert_leaf を呼び出し、その中でサフィックスリンクをたどって節に葉を挿入します。子が見つかった場合は、照合中の状態を表す局所変数の値を更新します。
ni < nlen の場合は node の ni 番目の文字と buff の bi 番目の文字を比較します。異なる場合はメソッド divide_node を呼び出し、サフィックスリンクをたどりながら節を分割して葉を挿入します。そうでなければ、ni と bi の値を +1 して次の文字を比較します。
while ループが終了したあと si < bi であれば、insert_leaf または divide_node を呼び出して区間 (si, bi) の接尾辞を挿入します。
次はメソッド insert_leaf を作ります。
リスト : サフィックスリンクをたどり葉を挿入していく
def insert_leaf(self, node, bi, si):
node.insert_child(Node(bi, node.depth + node.len()))
node = node.link
si += 1
while si < bi:
if bi < self.size:
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is not None:
return node, child, child.len(), 1, si, bi + 1
node.insert_child(Node(bi, node.depth + node.len()))
node = node.link
si += 1
return self.root, self.root, 0, 0, si, bi
引数 node が葉を挿入する節、bi は buff の検索位置、si は接尾辞木と照合を開始した位置です。最初に、insert_child を呼び出して node に葉を挿入します。そして、サフィックスリンクをたどって葉を挿入していきます。
葉を挿入する前に、buff[bi] の文字から始まる子がないか search_child で調べます。子が見つかった場合は処理を終了します。このとき、探索中のデータとして親節 node、探索中の節 child、節の長さ child.len()、節の探索位置 1、接尾辞木との照合開始位置 si、buff の検索位置 bi + 1 を返します。これで接尾辞木との照合を継続することができます。
次は節を分割して葉を挿入するメソッド divide_node を作ります。
リスト : サフィックスリンクをたどり節を分割して葉を挿入していく
def divide_node(self, prev, node, ni, bi, si):
link_node = self.insert_node(prev, node, bi, ni)
si += 1
while si < bi:
prev, node, match = self.search_next_node(prev.link, si, bi)
if match == 0:
if bi < self.size:
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is not None:
link_node.link = node
return node, child, child.len(), 1, si, bi + 1
link_node.link = node
return self.insert_leaf(node, bi, si)
#
link_node.link = self.insert_node(prev, node, bi, match)
link_node = link_node.link
si += 1
#
link_node.link = self.root
return self.root, self.root, 0, 0, si, bi
引数 prev が親節、node が分割または葉を挿入する節、ni は節を分割する位置、bi は buff の検索位置、si は接尾辞木と照合を開始した位置です。最初に、insert_node を呼び出して節を分割して葉を挿入します。insert_node は新しく挿入した節を返します。これを変数 link_node にセットします。この link_node を使ってサフィックスリンクを設定します。
次に while ループで親節 prev のサフィックスリンクをたどって、区間 (si, bi) の文字列を挿入します。親節 prev のサフィックスリンクをたどり、そこから分割する節をメソッド search_next_node で探索します。search_next_node は分割する節 (または葉を挿入する節) node とその親節 prev と分割する位置 match を返します。
match が 0 の場合、buff[bi] の文字から始まる子がないか search_child で調べます。子が見つかった場合、link_node.link に node をセットして処理を終了します。この処理は insert_leaf と同じです。子が見つからない場合、節を分割する必要がなくなったので、link_node.link に node をセットして insert_leaf を呼び出します。
match が 0 でない場合、分割位置の次の文字が buff[bi] と同じか調べる必要はありません。接尾辞木のルートから節 p までの接頭辞は、接尾辞木の中でそれ一つしかありません。たとえば、ab ... xy の接頭辞が存在し、y の位置で不一致になったとします。一つ短い接頭辞 b ... xy は必ず存在し、xy が一つの節にある場合、それ以外の接頭辞は存在しないのです。もし、b ... xz という接頭辞が存在するのであれば、x と y の間で節は既に分割されていて、親節の最後の文字が x で、y から始まる子と z から始まる子がないと接尾辞木は成立しません。
分割する節と位置を求めたら、insert_node で節を分割して葉を挿入します。そして、その返り値が link_node のサフィックスリンク先になります。最後には接頭辞が 1 文字の節が生成されて、それが root に挿入されます。あとは、その節の link に root をセットして、接尾辞木のルートから照合を再開します。
次は節の分割位置を求める search_next_node を作ります。
リスト : 分割位置を求める
def search_next_node(self, node, i, end):
prev = node
if node is not self.root:
i += node.child.depth
while i < end:
child = node.search_child(self.buff, self.size, self.buff[i])
j = child.len()
if i + j > end:
return node, child, end - i
i += j
prev = node
node = child
return prev, node, 0
引数 node から分割する節を求めます。引数 i が buff の検索開始位置、end が buff で不一致になった位置を表します。ルートから node までの接頭辞は buff[i] からの部分文字列と一致しているので、node が root でなければ i に接頭辞の長さを加算します。そして、while ループで接尾辞木をたどり、分割する節を求めます。
最初に node の子 child を求めます。child は必ず見つかります。child の長さを j にセットし、i + j が end よりも大きい場合は child が求める節です。親節が node で、分割する節が child、分割する位置が end - i になります。そうでなければ、i に j を加算して、次の子を調べます。
i が end と等しくなると while ループを終了します。この場合、節 node までの接頭辞とちょうど一致したことになります。親節 prev と一致した節 node、node の部分文字列と一致したことを表す値 0 を返します。あとは節を分割する必要はなく、葉を挿入していくだけになります。
節を挿入するメソッド insert_node は前回のプログラムとほぼ同じなので、説明は割愛いたします。詳細は プログラムリスト をお読みくださいませ。
それでは、簡単な実行例を示しましょう。
リスト : 簡単なテスト
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),
for y in st.search_pattern_all(a):
print y,
print
print '-----'
s, e = st.longest_repeated_substring()
print s, e, buff[s:e]
print '-----'
for s, e, c in st.repeated_substring(1, 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("sakurasaku$")
接尾辞木を表示する print_node は節とサフィックスリンク先の節を関数 id で表示します。また、check_node ではサフィックスリンクで一つ短い接頭辞になるかチェックする関数 check_suffix_link を呼び出して確認しています。
テストの実行結果は次のようになります。
root 12214960
$
a 12215280 12214960
$
na 12215120 12215200
$
na$
na 12215200 12215280
$
na$
banana$
-----
banana$ True 0
anana$ True 1
nana$ True 2
ana$ True 3
na$ True 4
a$ True 5
$ True 6
-----
1 4 ana
-----
1 4 2 ana
1 3 2 an
1 2 3 a
2 4 2 na
2 3 2 n
-----
root 12215560
$
a 12216040 12215560
$
b 12215720 12215800
bca$
cabbca$
ca 12215960 12216040
$
bbca$
b 12215800 12215560
ca 12215880 12215960
$
bbca$
bca$
-----
abcabbca$ True 0
bcabbca$ True 1
cabbca$ True 2
abbca$ True 3
bbca$ True 4
bca$ True 5
ca$ True 6
a$ True 7
$ True 8
-----
1 4 bca
-----
0 2 2 ab
0 1 3 a
2 4 2 ca
2 3 2 c
1 4 2 bca
1 3 2 bc
1 2 3 b
-----
root 12216240
$
a 12216800 12216240
$
a 12216720 12216800
$
a 12216640 12216720
$
a 12216560 12216640
$
a 12216480 12216560
$
a 12216400 12216480
$
a 12216320 12216400
$
a$
-----
aaaaaaaa$ True 0
aaaaaaa$ True 1
aaaaaa$ True 2
aaaaa$ True 3
aaaa$ True 4
aaa$ True 5
aa$ True 6
a$ True 7
$ True 8
-----
0 7 aaaaaaa
-----
0 7 2 aaaaaaa
0 6 3 aaaaaa
0 5 4 aaaaa
0 4 5 aaaa
0 3 6 aaa
0 2 7 aa
0 1 8 a
-----
root 12216920
$
p 12217520 12216920
i$
pi$
i 12217400 12216920
$
ppi$
ssi 12217160 12217240
ppi$
ssippi$
s 12217080 12216920
i 12217320 12217400
ppi$
ssippi$
si 12217240 12217320
ppi$
ssippi$
mississippi$
-----
mississippi$ True 0
ississippi$ True 1
ssissippi$ True 2
sissippi$ True 3
issippi$ True 4
ssippi$ True 5
sippi$ True 6
ippi$ True 7
ppi$ True 8
pi$ True 9
i$ True 10
$ True 11
-----
1 5 issi
-----
8 9 2 p
1 5 2 issi
1 4 2 iss
1 3 2 is
1 2 4 i
3 5 2 si
2 5 2 ssi
2 4 2 ss
2 3 4 s
-----
root 12217760
$
b 12217960 12217760
$
aaab$
baaab$
a 12217840 12217760
b 12218200 12217960
$
baaab$
a 12218040 12217840
b 12218120 12218200
$
baaab$
ab$
-----
aabbaaab$ True 0
abbaaab$ True 1
bbaaab$ True 2
baaab$ True 3
aaab$ True 4
aab$ True 5
ab$ True 6
b$ True 7
$ True 8
-----
0 3 aab
-----
2 3 3 b
1 3 2 ab
0 3 2 aab
0 2 3 aa
0 1 5 a
-----
root 12226608
$
u 12227168 12226608
$
rasaku$
ku 12227088 12227168
$
rasaku$
saku 12226928 12227008
$
rasaku$
a 12226848 12226608
ku 12227008 12227088
$
rasaku$
saku$
rasaku$
-----
sakurasaku$ True 0
akurasaku$ True 1
kurasaku$ True 2
urasaku$ True 3
rasaku$ True 4
asaku$ True 5
saku$ True 6
aku$ True 7
ku$ True 8
u$ True 9
$ True 10
-----
0 4 saku
-----
3 4 2 u
2 4 2 ku
2 3 2 k
0 4 2 saku
0 3 2 sak
0 2 2 sa
0 1 2 s
1 4 2 aku
1 3 2 ak
1 2 3 a
-----
正常に動作しています。興味のある方はいろいろな文字列で試してみてください。
最後に、ナイーブな方法と Ukkonen のアルゴリズムの実行速度を比較してみましょう。Canterbury Corpus で配布されているテストデータ The Large Corpus の中の bible.txt と e.coli を使って実行速度を計測してみました。ファイルの先頭から 50 k, 100 k, 200 k, 400 k バイト読み込んで接尾辞木を構築します。実行結果は次のようになりました。
表 : 接尾辞木の構築時間 (単位 : 秒) bible.txt: 50 k : 100 k : 200 k : 400 k ---------+-------+-------+-------+------ ナイーブ : 4.40 : 10.54 : 25.29 : 67.21 Ukkonen : 1.27 : 3.18 : 8.05 : 25.18 e.coli : 50 k : 100 k : 200 k : 400 k ---------+-------+-------+-------+------ ナイーブ : 2.44 : 5.84 : 14.92 : 40.13 Ukkonen : 1.26 : 3.20 : 9.07 : 26.34 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.6.2
bible.txt は英文テキスト、e.coli は文字が 4 種類 (a, c, g, t) のデータです。どちらの場合も Ukkonen のアルゴリズムのほうが速くなりました。今回のプログラムは子を連結リストに格納しているので、Ukkonen のアルゴリズムでも驚くほど速くはならないようです。親子関係をハッシュ法で表すと、もっと速くなると思われます。また、M.Hiroi のプログラムよりも高速な実装方法もあるでしょう。興味のある方はいろいろ試してみてください。
今回のプログラムは葉を節と同じクラス Node で表しているため、インスタンス変数 child, bros, link が無駄になっています。そこで、節をクラス Node で、葉をクラス Leaf で表すようにプログラムを作り直しました。興味のある方はお読みくださいませ。
# coding: utf-8
#
# sufftree.py : 接尾辞木 (Suffix Tree)
# (Ukkonen のアルゴリズム)
#
# Copyright (C) 2009 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 # 兄弟のリンク
self.link = 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)
self.root.link = self.root
#
bi = 0 # buff の位置
ni = 0 # node 内の位置
si = 0 # 照合開始位置
node = self.root # 照合中の節
prev = node # node の親節
nlen = 0 # node の長さ
while bi < self.size:
if ni == nlen:
# 次の子を探す
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is None:
if si == bi:
# ルートに挿入
self.root.insert_child(Node(bi, 0))
si += 1
bi += 1
else:
# 葉を挿入する
prev, node, nlen, ni, si, bi = self.insert_leaf(node, bi, si)
else:
prev = node
node = child
nlen = child.len()
ni = 1
bi += 1
else:
if buff[bi] != buff[node.start + ni]:
# 節を分割して葉を挿入する
prev, node, nlen, ni, si, bi = self.divide_node(prev, node, ni, bi, si)
else:
ni += 1
bi += 1
#
if si < bi:
if nlen == ni:
self.insert_leaf(node, bi, si)
else:
self.divide_node(prev, node, ni, bi, si)
# サフィックスリンクをたどり葉を挿入していく
def insert_leaf(self, node, bi, si):
node.insert_child(Node(bi, node.depth + node.len()))
node = node.link
si += 1
while si < bi:
if bi < self.size:
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is not None:
return node, child, child.len(), 1, si, bi + 1
node.insert_child(Node(bi, node.depth + node.len()))
node = node.link
si += 1
return self.root, self.root, 0, 0, si, bi
# リンクをたどり節を分割して葉を挿入していく
def divide_node(self, prev, node, ni, bi, si):
link_node = self.insert_node(prev, node, bi, ni)
si += 1
while si < bi:
prev, node, match = self.search_next_node(prev.link, si, bi)
if match == 0:
if bi < self.size:
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is not None:
link_node.link = node
return node, child, child.len(), 1, si, bi + 1
link_node.link = node
return self.insert_leaf(node, bi, si)
#
link_node.link = self.insert_node(prev, node, bi, match)
link_node = link_node.link
si += 1
#
link_node.link = self.root
return self.root, self.root, 0, 0, si, bi
# 分割位置を求める
def search_next_node(self, node, i, end):
prev = node
if node is not self.root:
i += node.child.depth
while i < end:
child = node.search_child(self.buff, self.size, self.buff[i])
j = child.len()
if i + j > end:
return node, child, end - i
i += j
prev = node
node = child
return prev, node, 0
# 節の挿入
def insert_node(self, parent, node, match, sub_match):
# 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)
return new_node
# 共通接頭辞の検索
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 xrange(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 "root", id(node)
else:
print ' ' * node.depth + buff[node.start:node.start + node.len()], \
id(node), id(node.link)
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 link のチェック
def check_suffix_link(node, buff):
len1 = node.len()
len2 = node.link.len()
depth1 = node.depth
depth2 = node.link.depth
if depth1 + len1 != depth2 + len2 + 1:
raise SuffixTreeError, "suffix link error1"
str1 = buff[node.start - depth1 + 1:node.start + len1]
str2 = buff[node.link.start - depth2:node.link.start + len2]
if str1 != str2:
raise SuffixTreeError, "suffix link error2"
# print "OK", id(node), str1, str2
# suffix tree のチェック
def check_node(node, buff):
if node.child is None:
return 1
else:
# 節
if node.start != ROOT:
check_suffix_link(node, buff)
if node.start != ROOT and count_child(node) < 2:
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),
for y in st.search_pattern_all(a):
print y,
print
print '-----'
s, e = st.longest_repeated_substring()
print s, e, buff[s:e]
print '-----'
for s, e, c in st.repeated_substring(1, 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("sakurasaku$")
# coding: utf-8
#
# sufftree.py : 接尾辞木 (Suffix Tree)
# (Ukkonen のアルゴリズム)
#
# Copyright (C) 2009 Makoto Hiroi
#
# 定数
ROOT = -1
MAX_LEN = 0x7fffffff
# 基本クラスの定義
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 # 兄弟のリンク
self.link = 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
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)
self.root.link = self.root
#
bi = 0 # buff の位置
ni = 0 # node 内の位置
si = 0 # 照合開始位置
node = self.root # 照合中の節
prev = node # node の親節
nlen = 0 # node の長さ
while bi < self.size:
if ni == nlen:
# 次の子を探す
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is None:
if si == bi:
# ルートに挿入
self.root.insert_child(Leaf(bi, 0))
si += 1
bi += 1
else:
# 葉を挿入する
prev, node, nlen, ni, si, bi = self.insert_leaf(node, bi, si)
else:
prev = node
node = child
nlen = child.len()
ni = 1
bi += 1
else:
if buff[bi] != buff[node.start + ni]:
# 節を分割して葉を挿入する
prev, node, nlen, ni, si, bi = self.divide_node(prev, node, ni, bi, si)
else:
ni += 1
bi += 1
#
if si < bi:
if nlen == ni:
self.insert_leaf(node, bi, si)
else:
self.divide_node(prev, node, ni, bi, si)
# サフィックスリンクをたどり葉を挿入していく
def insert_leaf(self, node, bi, si):
node.insert_child(Leaf(bi, node.depth + node.len()))
node = node.link
si += 1
while si < bi:
if bi < self.size:
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is not None:
return node, child, child.len(), 1, si, bi + 1
node.insert_child(Leaf(bi, node.depth + node.len()))
node = node.link
si += 1
return self.root, self.root, 0, 0, si, bi
# リンクをたどり節を分割して葉を挿入していく
def divide_node(self, prev, node, ni, bi, si):
link_node = self.insert_node(prev, node, bi, ni)
si += 1
while si < bi:
prev, node, match = self.search_next_link(prev.link, si, bi)
if match == 0:
if bi < self.size:
child = node.search_child(self.buff, self.size, self.buff[bi])
if child is not None:
link_node.link = node
return node, child, child.len(), 1, si, bi + 1
link_node.link = node
return self.insert_leaf(node, bi, si)
#
link_node.link = self.insert_node(prev, node, bi, match)
link_node = link_node.link
si += 1
#
link_node.link = self.root
return self.root, self.root, 0, 0, si, bi
# 分割位置を求める
def search_next_link(self, node, i, end):
prev = node
if node is not self.root:
i += node.child.depth
while i < end:
child = node.search_child(self.buff, self.size, self.buff[i])
# if child is None: break
j = child.len()
if i + j > end:
return node, child, end - i
i += j
prev = node
node = child
return prev, node, 0
# 節の挿入
def insert_node(self, parent, node, match, sub_match):
# 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)
return new_node
# 共通接頭辞の検索
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 xrange(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()