今回は Ternary Search Tree というデータ構造を紹介します。Ternary Search Tree (TST) は、1997 年に Jon Bentley と Robert Sedgewick が論文 "Fast Algorithms for Sorting and Searching Strings" で提案したデータ構造です。TST は「三分木」を使った探索木 (Search Tree) で、文字列の集合を表すのに都合のよいデータ構造です。その仕組みは同じ論文で提案された マルチキークイックソート とよく似ています。
文字列の集合を表す場合、前回説明した「トライ (trie) 」がよく使われます。トライの実装にはいくつかの方法がありますが、文字の種類が多い場合はトライを二分木で表す方法が一般的です。この方法で多数の文字列を登録すると、探索速度はどうしても遅くなってしまいます。TST の場合、文字の種類が多くなっても探索速度は高速です。ただし、TST は三分木なので、メモリの使用量はトライよりも多くなります。
今回は Ternary Search Tree について簡単に説明し、実際にプログラムを作ってみましょう。なお、TST の詳しい説明は、Robert Sedgewick の Sorting and Searching Strings で公開されている論文 "Fast Algorithms for Sorting and Searching Strings" をお読みくださいませ。
Ternary Search Tree は名前が示すように、三分木を使った探索木です。Ternary Search Tree の動作はとても簡単です。節に格納されているデータを基準にして、それよりも小さいデータは左部分木、等しいデータは中央の部分木、大きなデータは右部分木をたどることで文字列を探索します。
具体的に、文字列の n 番目の文字 Sn を探索する場合を考えてみましょう。まず最初に、文字 Sn と節のデータを比較します。値が等しい場合は n 番目の文字が一致したので、中央の木をたどって n + 1 番目の文字を探します。Sn が節のデータよりも小さい場合は、左の木をたどって Sn と等しいデータを探します。Sn が節のデータよりも大きい場合は、右の木をたどって Sn と等しいデータを探します。
ようするに、節のデータと一致したら中央の木をたどって次の文字と比較する、そうでなければ、左右の部分木の中から一致するデータを探す、というわけです。このように、TST の基本的な考え方は マルチキークイックソート とほとんど同じです。
マルチキークイックソートをご存知ない方は、次のように考えるといいでしょう。トライを二分木で表す場合、兄弟関係を連結リストで表しています。この関係を二分木で表したものが Ternary Search Tree だと考えてください。兄弟関係の探索処理を二分木で行い、等しいデータを見つけたならば、もうひとつの木（中央の木）をたどって次の文字の探索処理を行います。したがって、連結リストを線形探索するトライよりも Ternary Search Tree の方が高速に文字列を探索できる、というわけです。
簡単な例を示しましょう。次の図を見てください。
Ｔ
│
Ａ
│＼
│ ＼
│ ＼
│ ＼
│ ＼
│ ＼
│ ＼
Ｋ ＼
／│＼ Ｈ
／ │ ＼ │
Ｉ Ｅ Ｌ Ｅ
│ │ │ ／│＼
Ｌ $2 Ｌ ／ │ ＼
│ ／│ ／ $6 ＼
$1 Ｋ $4 Ａ ＼ Ｉ
│ │ Ｎ │
$3 Ｔ │ Ｓ
│ $7 │
$5 $8
{TAIL,TAKE,TALK,TALL,THAT,THE,THEN,THIS}
図：文字列の集合を表した TST
TST の場合、終端を表すデータ（たとえばヌル文字 '\x00'）を三分木に挿入します。上図では、ヌル文字の節を $ で表しています。
たとえば、上図の TST から文字列 "THAT" を探してみましょう。最初の文字は T で、これは最初の節と一致しますね。中央の木をたどって、次の文字 H と比較します。節のデータは A なので、文字 H の方が大きいですね。右側の木をたどって次の節のデータと比較します。文字 H はこの節と一致するので、中央の木をたどって次の節へ進み、次の文字 A と比較します。
今度は E > A なので、左側の木をたどって次の節へ進みます。この節で文字 A と一致するので、中央の木をたどって次の節へ進み、次の文字 T と比較します。この節で文字 T と一致するので、中央の木をたどり終端を表す節 $5 に到達します。ここで、文字列 "THAT" を見つけたことになります。たどった経路は T - A - H - E - A - T - $5 ですが、この経路で表される文字列は "TAHEAT" ではなく "THAT" になることに注意してください。
このように、TST は一致する文字がないか左右の部分木をたどって探索し、一致したら中央の部分木をたどって次の文字へ進むことで文字列の探索を行います。それから、終端を表す節にもデータが追加されることがあります。たとえば、文字列 "THE" のあとに "THEN" を挿入すると、節 $6 の右側の木に文字 N の節が追加されます。
一般に、木構造では子を持たない節を「葉 (leaf) 」といいます。TST の場合、終端を表す節に左右の子を挿入することがあるので、厳密に言うと終端を表す節は「葉」ではありません。ただし、終端を表す節に中央の子が挿入されることはないので、本ページでは中央の子がない節を便宜上「葉」と呼ぶことにします。通常、終端を表す節が「葉」になるので、本ページでは終端を表す節も「葉」と表記しています。ご注意ください。
それではプログラムを作りましょう。最初に節を表すデータ構造と子を操作する関数を定義します。次のリストを見てください。
リスト : 節の定義
# 節の定義
class Node3:
def __init__(self, x):
self.data = x
self.left = None
self.mid = None
self.right = None
節を表すクラスは Node3 としました。データを格納するインスタンス変数 data と、左、中央、右の部分木を格納するインスタンス変数 left, mid, right を用意します。
次に、TST で使用する子の操作関数を作ります。これは二分木の操作関数とほとんど同じです。二分木の詳しい説明は拙作のページ 二分木とヒープ をお読みください。
リスト : 子の操作関数
# 探索
def _search(node, x):
while node:
if node.data == x: return node
if x < node.data:
node = node.left
else:
node = node.right
return None
# 挿入
def _insert(node, x):
if node is None: return x
elif x.data == node.data: return node
elif x.data < node.data:
node.left = _insert(node.left, x)
else:
node.right = _insert(node.right, x)
return node
# 最小値を探す
def _search_min(node):
if node.left is None: return node.data
return _search_min(node.left)
# 最小値を削除する
def _delete_min(node):
if node.left is None: return node.right
node.left = _delete_min(node.left)
return node
# 削除
def _delete(node, x):
if node:
if x == node.data:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
node.data = _search_min(node.right)
node.right = _delete_min(node.right)
elif x < node.data:
node.left = _delete(node.left, x)
else:
node.right = _delete(node.right, x)
return node
関数 _search は x と等しいデータを持つ子を探します。見つけた場合は子 (node) を返します。関数 _insert は子 x を挿入します。引数 x には Node3 のインスタンスを渡します。関数 _delete は x と等しいデータを持つ子を削除します。このほかに、TST を巡回する関数 _traverse を作りますが、これはあとで説明します。
それでは、TST の操作メソッドを作りましょう。クラス名は Tst とします。最初に Tst を初期化するメソッド __init__ を作ります。
リスト : Ternary Search Tree
class Tst:
def __init__(self, x = None):
self.root = Node3(None) # header
self.leaf = x
Tst のインスタンス変数 root にはヘッダを表す節を格納します。この節の data はダミーです。実際のデータは root の子に追加していきます。インスタンス変数 leaf は終端を表すデータを格納します。leaf は Tst を呼び出すときに引数として渡します。省略した場合は None になります。
Python の場合、型の異なるオブジェクトを演算子で比較してもエラーにはなりません。たとえば、None と数値や文字列を比較した場合、Python 2.4.2 では None の方が小さいと判定されます。終端を表すデータが None のままでもプログラムは動作しますが、終端には適切なデータを設定したほうがよいかもしれません。ご注意ください。
次はデータを探索するメソッド search を作成します。次のリストを見てください。
リスト : データの探索
def search(self, seq):
node = self.root
for x in seq:
node = _search(node.mid, x)
if not node: return False
# check leaf
return _search(node.mid, self.leaf) is not None
引数 seq が探索するデータ (列 : sequence) です。for ループで seq の要素を一つずつ取り出して、TST をたどっていきます。最初に、ヘッダの節 self.root の値を変数 node にセットします。そして for ループの中で、節 node にデータ x を持つ子があるか関数 _search で調べます。このとき、_search の引数には中央の木 (node.mid) を渡すことに注意してください。
TST の場合、節 node の子は中央の木 (node.mid) にあります。そして、node の兄弟は左部分木 (node.left) と右部分木 (node.right) で二分木を構成しています。つまり、node.mid が節 node の子を表わす二分木のルートになるのです。これが TST の特徴です。
子が見つからない場合は探索失敗です。return で False を返します。見つかった場合は探索を続行します。最後に node の子に葉 (leaf) があるかチェックします。葉が見つからない場合は探索失敗となります。
次はデータを挿入するメソッド insert を作成します。次のリストを見てください。
リスト : データの挿入
def insert(self, seq):
node = self.root
for x in seq:
child = _search(node.mid, x)
if not child:
child = Node3(x)
node.mid = _insert(node.mid, child)
node = child
# check leaf
if not _search(node.mid, self.leaf):
node.mid = _insert(node.mid, Node3(self.leaf))
TST をたどる処理はデータの探索処理と同じです。_search で子が見つからない場合は、Node3(x) で新しい子 child を生成し、それを関数 _insert で挿入します。このときも、_insert には中央の木 (node.mid) を渡すことに注意してください。最後に、関数 _search で葉をチェックます。葉が見つからない場合は、新しい葉を _insert で挿入します。
次はデータを削除するメソッド delete を作ります。次のリストを見てください。
リスト : データの削除
def delete(self, seq):
node = self.root
for x in seq:
node = _search(node.mid, x)
if not node: return False
# delete leaf
if _search(node.mid, self.leaf):
node.mid = _delete(node.mid, self.leaf)
return True
return False
データの削除は対応する葉を削除するだけです。この場合、不要になった節 (node) が残ったままになるので、メモリを余分に消費する欠点があります。今回はこの対策を行っていません。ご注意くださいませ。
TST をたどる処理は今までと同じです。TST をたどれない場合は、削除するデータがないので False を返します。あとは、最後に関数 _search で葉があるかチェックして、関数 _delete で葉を削除するだけです。
次は TST を巡回するメソッド traverse を作ります。実際の処理は関数 _traverse で行います。次のリストを見てください。
リスト : TST の巡回
def _traverse(node, leaf):
if node:
for x in _traverse(node.left, leaf):
yield x
if node.data == leaf:
yield []
else:
for x in _traverse(node.mid, leaf):
yield [node.data] + x
for x in _traverse(node.right, leaf):
yield x
関数 _traverse はジェネレータとして実装しています。二分木と同様に通りがけ順で TST を巡回すると、文字列を昇順に出力することができます。データは配列に格納して返します。最初に左部分木 (node.left) を _traverse で巡回します。この場合、_traverse の返り値 x を yield でそのまま返すだけです。
次に中央の部分木 (node.mid) を巡回します。ここで、node が葉の場合は、yield で空の配列 [] を返します。葉の後ろにはデータがないので、中央の木 (node.mid) をたどる必要はありません。葉でない場合は、中央の木を _traverse で巡回し、その返り値 x と節のデータ node.data を連結し、その値を yield で返します。最後に、右部分木 (node.right) を _traverse でたどります。
Tst のメソッド traverse は次のようになります。
リスト : TST の巡回
def traverse(self):
for x in _traverse(self.root.mid, self.leaf):
yield x
Tst の巡回は操作関数 _traverse を呼び出すだけです。ヘッダのデータはダミーで、実際のデータは中央の木 (node.mid) に格納されます。_traverse を呼び出すときは引数に self.root.mid を渡します。あとは返り値 x を yield で返すだけです。
最後に common prefix を持つデータを求めるメソッド common_prefix を作ります。
リスト : 共通接頭辞を持つデータを求める
def common_prefix(self, seq):
node = self.root
buff = []
for x in seq:
buff.append(x)
node = _search(node.mid, x)
if not node: return
for x in _traverse(node.mid, self.leaf):
yield buff + x
引数 seq に接頭辞 (prefix) を渡します。そして、同じ接頭辞を持つデータを求めます。最初に、接頭辞 seq を探索します。接頭辞が見つからない場合は return で処理を終了します。common_prefix はジェネレータとして実装するので、return に引数を与えてはいけません。あとは、接頭辞から下の中央の木 (node.mid) にあるデータを関数 _traverse で求めるだけです。接頭辞 buff と _traverse の返り値を連結して yield で返します。
それでは、簡単な実行例として suffix trie を TST で作成してみましょう。suffix trie は、サフィックスを順番にトライに追加していくだけで作成できます。次のリストを見てください。
# 簡単なテスト
if __name__ == '__main__':
# suffix trie
def make_suffix_trie(seq):
a = Tst()
for x in xrange(len(seq)):
a.insert(seq[x:])
return a
s = make_suffix_trie('abcabbca')
for x in s.traverse():
print x
for x in ['a', 'bc']:
print x
for y in s.common_prefix(x):
print y
print s.delete('a')
print s.delete('ca')
print s.delete('bca')
for x in s.traverse():
print x
関数 make_suffix_trie は引数 seq の suffix trie を生成します。seq[x:] で seq の接尾辞を作り、メソッド insert でトライに追加します。とても簡単な方法ですが、データが多くなると時間がかかるのが欠点です。データ数を N とすると、実行時間は N2 に比例します。ご注意くださいませ。
それでは実行例を示します。
['a'] ['a', 'b', 'b', 'c', 'a'] ['a', 'b', 'c', 'a', 'b', 'b', 'c', 'a'] ['b', 'b', 'c', 'a'] ['b', 'c', 'a'] ['b', 'c', 'a', 'b', 'b', 'c', 'a'] ['c', 'a'] ['c', 'a', 'b', 'b', 'c', 'a'] a ['a'] ['a', 'b', 'b', 'c', 'a'] ['a', 'b', 'c', 'a', 'b', 'b', 'c', 'a'] bc ['b', 'c', 'a'] ['b', 'c', 'a', 'b', 'b', 'c', 'a'] True True True ['a', 'b', 'b', 'c', 'a'] ['a', 'b', 'c', 'a', 'b', 'b', 'c', 'a'] ['b', 'b', 'c', 'a'] ['b', 'c', 'a', 'b', 'b', 'c', 'a'] ['c', 'a', 'b', 'b', 'c', 'a']
ところで、Ternary Search Tree (TST) は前回説明したパトリシア (patricia tree) にも応用することができます。この場合、節に格納されるデータは列 (sequence) になるので、その先頭の要素を比較して二分木を操作するように関数を修正します。二分木の操作関数は簡単に修正できるので、説明は割愛いたします。詳細は プログラムリスト２ をお読みください。
次は、パトリシア (TST 版) のメソッドを作ります。クラス定義と最長一致を求めるメソッド longest_match は次のようになります。
リスト : Patricia3 の定義
# クラス定義
class Patricia3:
def __init__(self, x = None):
self.root = Node3(None) # header
self.leaf = x
self.leaf_data = [x]
# 最長一致を求める
def longest_match(self, seq):
node = self.root
k = len(seq)
i = 0
while i < k:
child = _search(node.mid, seq[i])
if not child: break
j = 1
k1 = len(child.data)
while j < k1:
if i + j == k or seq[i + j] != child.data[j]:
return child, i + j, j
j += 1
i += j
node = child
return node, i, 0
クラス名は三分木 (TST) を使ったパトリシアということで Patricia3 としました。メソッド __init__ はパトリシアとほぼ同じです。節は Node3() で生成して、インスタンス変数 root にはヘッダをセットします。メソッド longest_match もパトリシアと同じですが、子を求めるときは関数 _search を呼び出すように修正します。
次はデータを挿入するメソッド insert を作ります。
リスト : データの挿入
def insert(self, seq):
# 子を挿入する
def insert_child(node, x):
child = Node3(x)
node.mid = _insert(node.mid, child)
return child
#
node, match, sub_match = self.longest_match(seq)
if sub_match > 0:
# node を node - node1 に分割する
node1 = Node3(node.data[sub_match:])
node1.mid = node.mid
node.data = node.data[:sub_match]
node.mid = node1
if match < len(seq):
# node に残りのデータを追加する
new_node = insert_child(node, seq[match:])
insert_child(new_node, self.leaf_data)
else:
# 葉を追加するだけ
insert_child(node, self.leaf_data)
else:
# node にデータを追加
if match == len(seq):
# 葉を追加するだけ
if not _search(node, self.leaf):
insert_child(node, self.leaf_data)
else:
# node に残りのデータを追加する
new_node = insert_child(node, seq[match:])
insert_child(new_node, self.leaf_data)
最初に、子を挿入する内部関数 insert_child を定義しています。新しい子を Node3() で生成して、それを _insert で node の子に挿入します。最後に、return で新しい子 child を返します。
子を挿入するときは関数 insert_child を呼び出すように修正します。あと注意する点は節を分割する処理です。TST の場合、node の兄弟関係の節は左右の部分木に、子は中央の木に格納されています。したがって、node を node - node1 に分割する場合、node.left と node.right はそのままで、node の子 (node.mid) は node1 だけになります。また、node1 は node の子を引き継ぐので、node1.mid の値は node.mid になります。あとはパトリシアのプログラムとほとんど同じです。
あとは、とくに難しいところはないので、説明は割愛いたします。詳細は プログラムリスト２ をお読みください。
それでは、簡単な実行例として suffix tree を Patricia3 で作成してみましょう。suffix tree は、サフィックスを順番にパトリシアに追加していくだけで作成できます。次のリストを見てください。
# 簡単なテスト
if __name__ == '__main__':
# suffix tree
def make_suffix_tree(seq):
a = Patricia3()
for x in xrange(len(seq)):
a.insert(seq[x:])
return a
s = make_suffix_tree('abcabbca')
for x in s.traverse():
print x
for x in ['a', 'bc']:
print x
for y in s.common_prefix(x):
print y
print s.delete('a')
print s.delete('ca')
print s.delete('bca')
for x in s.traverse():
print x
実行結果を示します。
['a'] ['a', 'b', 'bca'] ['a', 'b', 'cabbca'] ['b', 'bca'] ['b', 'ca'] ['b', 'ca', 'bbca'] ['ca'] ['ca', 'bbca'] a ['a'] ['a', 'b', 'bca'] ['a', 'b', 'cabbca'] bc ['bc', 'a'] ['bc', 'a', 'bbca'] True True True ['a', 'b', 'bca'] ['a', 'b', 'cabbca'] ['b', 'bca'] ['b', 'ca', 'bbca'] ['ca', 'bbca']
最後に、今まで作成した Trie, Patricia, Tst, Patricia3 の実行速度を比較してみましょう。テストデータは 整列 [3] で使用したものと同じで、文字 (アルファベットと数字) をランダムで選んで作成しました。1 行 8 文字で、1000, 2000, 4000, 8000 行の 4 種類のデータを用意しました。これらのデータをトライに挿入します。テストプログラムは次のようになります。
# テストプログラム
from trie import *
from patricia import *
from tst import *
from patricia3 import *
import time
def test(trie, buff):
a = trie()
s = time.clock()
for x in buff:
if not a.search(x): a.insert(x)
e = time.clock()
return e - s
for name in ['s1.dat','s2.dat','s4.dat','s8.dat']:
f = open(name, 'r')
buff = f.readlines()
f.close()
print name,
for trie in [Trie, Patricia, Tst, Patricia3]:
print '%.3f' % test(trie, buff),
print
それでは実行結果を示します。
表 : 実行結果 (単位 : 秒) 個数 : Trie Pat Tst Pat3 ----------------------------------- 1000 : 0.288 0.256 0.127 0.108 2000 : 0.653 0.598 0.252 0.206 4000 : 1.539 1.390 0.596 0.484 8000 : 3.357 3.139 1.230 1.031 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
Patricia3 が最も速くなりました。パトリシアと Ternary Search Tree を組み合わせた効果は十分に出ていると思います。単純なトライよりもパトリシアの方が少し速くなり、メモリの使用量も効率的です。そして、Teranary Search Tree の方が単純なトライやパトリシアよりも高速になります。
ただし、Ternary Search Tree の場合、兄弟関係のリンクに二分木を使っているため、二分木のバランスが崩れると性能が劣化することに注意してください。たとえば、ソート済みのデータを挿入すると、次のような結果になります。
表 : ソート済みデータの実行結果 (単位 : 秒) 個数 : Trie Pat Tst Pat3 ----------------------------------- 1000 : 0.116 0.081 0.314 0.302 2000 : 0.261 0.203 0.738 0.713 4000 : 0.625 0.477 1.727 1.650 8000 : 1.196 0.962 3.825 3.748 実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2
このように、Ternary Search Tree の実行速度は 3 倍以上も遅くなってしまいました。ご注意くださいませ。
# coding: utf-8
#
# tst.py : Ternary Search Tree (三分木)
#
# Copyright (C) 2007 Makoto Hiroi
#
# 節の定義
class Node3:
def __init__(self, x):
self.data = x
self.left = None
self.mid = None
self.right = None
#
# 木の操作関数
#
# 探索
def _search(node, x):
while node:
if node.data == x: return node
if x < node.data:
node = node.left
else:
node = node.right
return None
# 挿入
def _insert(node, x):
if node is None: return x
elif x.data == node.data: return node
elif x.data < node.data:
node.left = _insert(node.left, x)
else:
node.right = _insert(node.right, x)
return node
# 最小値を探す
def _search_min(node):
if node.left is None: return node.data
return _search_min(node.left)
# 最小値を削除する
def _delete_min(node):
if node.left is None: return node.right
node.left = _delete_min(node.left)
return node
# 削除
def _delete(node, x):
if node:
if x == node.data:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
node.data = _search_min(node.right)
node.right = _delete_min(node.right)
elif x < node.data:
node.left = _delete(node.left, x)
else:
node.right = _delete(node.right, x)
return node
# 巡回
def _traverse(node, leaf):
if node:
for x in _traverse(node.left, leaf):
yield x
if node.data == leaf:
yield []
else:
for x in _traverse(node.mid, leaf):
yield [node.data] + x
for x in _traverse(node.right, leaf):
yield x
##### Ternary Search Tree #####
class Tst:
def __init__(self, x = None):
self.root = Node3(None) # header
self.leaf = x
# 探索
def search(self, seq):
node = self.root
for x in seq:
node = _search(node.mid, x)
if not node: return False
# check leaf
return _search(node.mid, self.leaf) is not None
# 挿入
def insert(self, seq):
node = self.root
for x in seq:
child = _search(node.mid, x)
if not child:
child = Node3(x)
node.mid = _insert(node.mid, child)
node = child
# check leaf
if not _search(node.mid, self.leaf):
node.mid = _insert(node.mid, Node3(self.leaf))
# 削除
def delete(self, seq):
node = self.root
for x in seq:
node = _search(node.mid, x)
if not node: return False
# delete leaf
if _search(node.mid, self.leaf):
node.mid = _delete(node.mid, self.leaf)
return True
return False
# 巡回
def traverse(self):
for x in _traverse(self.root.mid, self.leaf):
yield x
# 共通接頭辞を持つデータを求める
def common_prefix(self, seq):
node = self.root
buff = []
for x in seq:
buff.append(x)
node = _search(node.mid, x)
if not node: return
for x in _traverse(node.mid, self.leaf):
yield buff + x
# 簡単なテスト
if __name__ == '__main__':
# suffix trie
def make_suffix_trie(seq):
a = Tst()
for x in xrange(len(seq)):
a.insert(seq[x:])
return a
s = make_suffix_trie('abcabbca')
for x in s.traverse():
print x
for x in ['a', 'bc']:
print x
for y in s.common_prefix(x):
print y
print s.delete('a')
print s.delete('ca')
print s.delete('bca')
for x in s.traverse():
print x
s = make_suffix_trie([0,1,2,0,1,1,2,0])
for x in s.traverse():
print x
# coding: utf-8
#
# patricia3.py : パトリシア (patricia tree, TST バージョン)
#
# Copyright (C) 2007 Makoto Hiroi
#
# 節の定義
class Node3:
def __init__(self, x):
self.data = x
self.left = None
self.mid = None
self.right = None
#
# 木の操作関数
#
# 探索
def _search(node, x):
while node:
if node.data[0] == x: return node
if x < node.data[0]:
node = node.left
else:
node = node.right
return None
# 挿入
def _insert(node, x):
if node is None: return x
elif x.data[0] == node.data[0]: return node
elif x.data[0] < node.data[0]:
node.left = _insert(node.left, x)
else:
node.right = _insert(node.right, x)
return node
# 最小値を探す
def _search_min(node):
if node.left is None: return node.data
return _search_min(node.left)
# 最小値を削除する
def _delete_min(node):
if node.left is None: return node.right
node.left = _delete_min(node.left)
return node
# 削除
def _delete(node, x):
if node:
if x == node.data[0]:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
node.data = _search_min(node.right)
node.right = _delete_min(node.right)
elif x < node.data[0]:
node.left = _delete(node.left, x)
else:
node.right = _delete(node.right, x)
return node
# 巡回
def _traverse(node, leaf):
if node:
for x in _traverse(node.left, leaf):
yield x
if node.data[0] == leaf:
yield []
else:
for x in _traverse(node.mid, leaf):
yield [node.data] + x
for x in _traverse(node.right, leaf):
yield x
class Patricia3:
def __init__(self, x = None):
self.root = Node3(None) # header
self.leaf = x
self.leaf_data = [x]
#
# 最長一致を求める
# 返り値 (node, match, sub_match)
# sub_match = 0, node のデータと全て一致
#
def longest_match(self, seq):
node = self.root
k = len(seq)
i = 0
while i < k:
child = _search(node.mid, seq[i])
if not child: break
j = 1
k1 = len(child.data)
while j < k1:
if i + j == k or seq[i + j] != child.data[j]:
return child, i + j, j
j += 1
i += j
node = child
return node, i, 0
# 探索
def search(self, seq):
node, match, sub_match = self.longest_match(seq)
if len(seq) == match and sub_match == 0:
# 葉をチェックする
return _search(node.mid, self.leaf) is not None
return False
# 挿入
def insert(self, seq):
# 子を挿入する
def insert_child(node, x):
child = Node3(x)
node.mid = _insert(node.mid, child)
return child
#
node, match, sub_match = self.longest_match(seq)
if sub_match > 0:
# node を node - node1 に分割する
node1 = Node3(node.data[sub_match:])
node1.mid = node.mid
node.data = node.data[:sub_match]
node.mid = node1
if match < len(seq):
# node に残りのデータを追加する
new_node = insert_child(node, seq[match:])
insert_child(new_node, self.leaf_data)
else:
# 葉を追加するだけ
insert_child(node, self.leaf_data)
else:
# node にデータを追加
if match == len(seq):
# 葉を追加するだけ
if not _search(node, self.leaf):
insert_child(node, self.leaf_data)
else:
# node に残りのデータを追加する
new_node = insert_child(node, seq[match:])
insert_child(new_node, self.leaf_data)
# 削除
def delete(self, seq):
node, match, sub_match = self.longest_match(seq)
if match == len(seq) and sub_match == 0:
# delete leaf
if _search(node.mid, self.leaf):
node.mid = _delete(node.mid, self.leaf)
return True
return False
# 巡回
def traverse(self):
for x in _traverse(self.root.mid, self.leaf):
yield x
# 共通接頭辞を持つデータを求める
def common_prefix(self, seq):
node, match, sub_match = self.longest_match(seq)
if len(seq) == match:
buff = [seq]
if sub_match > 0: buff.append(node.data[sub_match:])
for x in _traverse(node.mid, self.leaf):
yield buff + x
# 簡単なテスト
if __name__ == '__main__':
# suffix tree
def make_suffix_tree(seq):
a = Patricia3()
for x in xrange(len(seq)):
a.insert(seq[x:])
return a
s = make_suffix_tree('abcabbca')
for x in s.traverse():
print x
for x in ['a', 'bc']:
print x
for y in s.common_prefix(x):
print y
print s.delete('a')
print s.delete('ca')
print s.delete('bca')
for x in s.traverse():
print x