はじめに
今回は Ruby の例題として、いろいろなコレクションクラスを作ってみましょう。
●双方向リスト
双方向リストは、直後のセルだけでなく直前のセルへの参照を持たせたデータ構造です。双方向リストは「重連結リスト (doubly-linked list)」と呼ばれることもあります。双方向リストを使う場合、ヘッダセルを用意してリストを環状に構成することが多いです。
図 : 双方向リスト
連結リストは後ろ方向にしかセルをたどることができませんが、双方向リストでは前後どちらの方向へもセルをたどることができます。セルを削除する場合も、前後のセルがわかるので簡単に削除することができます。詳しい説明は拙作のページ Algorithms with Python: 連結リストとキュー をお読みください。
●仕様
- クラス名: DList
- インクルードするモジュール: Enumerable
- コンストラクタ: DList.new(...)
- at(n), n 番目の要素を求める
- insert(n, x), n 番目に x を挿入する
- delete_at(n), n 番目の要素を削除する
- delete_if {|x| ...}, ブロックが真を返す要素をすべて削除する
- delete(x), x と等しい (==) 要素をすべて削除する
- empty?(), 空リストならば真を返す
- each {|x| ...}, 要素 x にブロックを適用する
- to_s, 文字列に変換
添字 n が負の場合は後ろから数える。演算子 [ ] による参照と代入もサポートする。
●使用例
irb> load "dlist.rb"
=> true
irb> d = DList.new
=> #<DList: ...>
irb> d.empty?
=> true
irb> d.insert(0, 1)
=> 1
irb> d.empty?
=> false
irb> d.at(0)
=> 1
irb> d.at(-1)
=> 1
irb> d.delete_at(0)
=> 1
irb> d.empty?
=> true
irb> d = DList.new(10, 20, 30, 40, 50)
=> #<DList: ...>
irb> 5.times {|i| print d[i], " "}
10 20 30 40 50 => 5
irb> d.each {|x| print x, " "}
10 20 30 40 50 => #<DList: ...>
irb> d.insert(0, 0)
=> 0
irb> d.to_s
=> "(0,10,20,30,40,50)"
irb> d.to_a
=> [0, 10, 20, 30, 40, 50]
irb> d.insert(3, 1)
=> 1
irb> d.to_a
=> [0, 10, 20, 1, 30, 40, 50]
irb> d.insert(-1, 2)
=> 2
irb> d.to_a
=> [0, 10, 20, 1, 30, 40, 50, 2]
irb> d.delete_at(0)
=> 0
irb> d.to_a
=> [10, 20, 1, 30, 40, 50, 2]
irb> d.delete_at(2)
=> 1
irb> d.to_a
=> [10, 20, 30, 40, 50, 2]
irb> d.delete_at(-1)
=> 2
irb> d.to_a
=> [10, 20, 30, 40, 50]
irb> d1 = DList.new(1,2,3,4,5,6,7,8)
=> #<DList:0x104<
irb(main):004:0> d1.delete_if{|x| x % 2 == 0}
=> #<DList:0x104<
irb> d1.to_a
=> [1, 3, 5, 7]
irb> d1 = DList.new(1,2,3,4,1,2,3,1,2,1)
=> #<DList:0x118<
irb> d1.to_a
=> [1, 2, 3, 4, 1, 2, 3, 1, 2, 1]
irb> d1.delete(1)
=> 1
irb> d1.to_a
=> [2, 3, 4, 2, 3, 2]
irb> d.to_a
=> [10, 20, 30, 40, 50]
irb> d.member? 30
=> true
irb> d.member? 33
=> false
irb> d.map {|x| x * 10}
=> [100, 200, 300, 400, 500]
irb> d.filter {|x| (x / 10) % 2 == 1}
=> [10, 30, 50]
irb> d.reduce(0){|a, x| a + x}
=> 150
●プログラム
リスト : 双方向リスト (dlist.rb)
class DList
include Enumerable
# 双方向リスト用セル
class Cell2
attr_accessor :data, :link, :prev
def initialize(data, link = nil, prev = nil)
@data = data
@link = link
@prev = prev
end
end
def initialize(*args)
@head = Cell2.new(nil) # Header Cell
@head.link = @head
@head.prev = @head
args.each do |x| insert(-1, x) end
end
private
# n 番目のセルを求める
def _at(n)
if n >= 0
cp = @head.link
while cp != @head
return cp if n == 0
n -= 1
cp = cp.link
end
else
cp = @head.prev
while cp != @head
n += 1
return cp if n == 0
cp = cp.prev
end
end
end
public
# n 番目の要素を求める
def at(n)
cp = _at(n)
cp.data if cp
end
# n 番目のデータを削除
def delete_at(n)
cp = _at(n)
if cp
# p <--> cp <--> q
p = cp.prev
q = cp.link
p.link = q
q.prev = p
cp.data
end
end
# ブロックが真を返す要素を削除する
def delete_if
cp = @head.link
while cp != @head
if yield cp.data
p = cp.prev
q = cp.link
p.link = q
q.prev = p
end
cp = cp.link
end
self
end
# 引数 value と等しい要素を削除する
def delete(value)
data = nil
delete_if {|x|
if x == value
data = value
true
else
false
end
}
data
end
# n 番目にデータを挿入する
def insert(n, data)
q = @head
if n >= 0
begin
if n == 0
# q <--> cp <--> p
p = q.link
cp = Cell2.new(data, p, q)
q.link = cp
p.prev = cp
return data
end
n -= 1
q = q.link
end while q != @head
else
begin
n += 1
if n == 0
# p <--> cp <--> q
p = q.prev
cp = Cell2.new(data, q, p)
q.prev = cp
p.link = cp
return data
end
q = q.prev
end while q != @head
end
end
# 空リストか？
def empty?
@head.link == @head
end
# Enumerable 用
def each
cp = @head.link
while cp != @head
yield cp.data
cp = cp.link
end
self
end
# 演算子 [] の定義
# 参照
def [](n)
at(n)
end
# 代入
def []=(n, value)
cp = _at(n)
cp.data = value if cp
end
# 文字列に変換
def to_s
if @head.link != @head
str = "("
each do |x|
str << x.to_s
str << ","
end
str[-1] = ")"
else
str = "()"
end
str
end
def inspect
sprintf("#<DList:%#x>", self.object_id)
end
end
●ディキュー (deque)
deque は「両端キュー」のことで、「デック」とか「ディーキュー」と呼ばれています。キューの場合、データの追加は最後尾に、データの取り出しは先頭に対してのみ行えます。これに対しディーキューは、先頭および最後尾のどちらでもデータの追加と取り出しが行えるデータ構造です。ディーキューは双方向リストを使うと簡単に実現できます。
●仕様
- クラス名: Deque
- コンストラクタ: Deque.new()
- push(x), 最後尾にデータを追加する
- pop(), 最後尾からデータを削除する
- unshift(x), 先頭にデータを追加する
- shift(), 先頭からデータを削除する
- first(), 先頭要素を参照する
- last(), 末尾要素を参照する
- size, 要素数を返す
- empty?(), ディキューが空ならば真を返す
- to_s, 文字列に変換する
- ro_a, 配列に変換する
●使用例
irb> load "dlist.rb"
=> true
irb> d = Deque.new
=> #<Deque: ...>
irb> d.empty?
=> true
irb> d.size
=> 0
irb> d.push 1
=> 1
irb> d.push 2
=> 2
irb> d.unshift 3
=> 3
irb> d.unshift 4
=> 4
irb> d.to_a
=> [4, 3, 1, 2]
irb> d.empty?
=> false
irb> d.size
=> 4
irb> d.pop
=> 2
irb> d.pop
=> 1
irb> d.shift
=> 4
irb> d.shift
=> 3
irb> d.empty?
=> true
irb> 8.times {|x| d.push x}
=> 8
irb> while not d.empty?
irb> print d.pop, " "
irb> end
7 6 5 4 3 2 1 0 => nil
irb> 8.times {|x| d.push x}
=> 8
irb> while not d.empty?
irb> print d.shift, " "
irb> end
0 1 2 3 4 5 6 7 => nil
●プログラム
リスト : ディキュー (dlist.rb)
class Deque
attr_reader :size
def initialize
@size = 0
@buff = DList.new
end
# Array の仕様に合わせる
# 最後尾にデータを追加
def push(data)
@size += 1
@buff.insert(-1, data)
end
# 最後尾からデータを削除
def pop
if @size > 0
@size -= 1
@buff.delete_at(-1)
end
end
# 先頭にデータを追加
def unshift(data)
@size += 1
@buff.insert(0, data)
end
# 先頭からデータを削除
def shift
if @size > 0
@size -= 1
@buff.delete_at(0)
end
end
# 先頭データの取得
def first
@buff.at(0) if @size > 0
end
# 末尾データの取得
def last
@buff.at(-1) if @size > 0
end
# デキューは空か？
def empty?
@size == 0
end
# 配列に変換
def to_a
@buff.to_a
end
# 文字列に変換
def to_s
@buff.to_s
end
def inspect
sprintf("#<Deque:%#x>", self.object_id)
end
end
●ヒープ
「ヒープ (heap)」は「半順序木 (partial ordered tree)」を配列で実現したデータ構造です。一般的な二分木では、親よりも左側の子のほうが小さく、親よりも右側の子が大きい、という関係を満たすように作ります。「半順序木」の場合、親は子より小さいか等しい、という関係を満たすように作ります。したがって、木の根（配列の添字 0）には、必ず最小値のデータが格納されます。下図にヒープと配列の関係を示します。
図 : ヒープと配列の対応関係
ヒープを利用すると、最小値をすぐに見つけることができ、新しくデータを挿入する場合も、高々要素の個数 (N) の対数 (log2 N) に比例する程度の時間で済みます。詳しい説明は拙作のページ Algorithms with Python: 二分木とヒープ をお読みくださいませ。
●優先度つき待ち行列
それでは、ヒープを使って「優先度つき待ち行列 (priority queue)」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。
- クラス名: PQueue
- コンストラクタ: PQueue.new(ary = [])
- first(), 最小値を参照する
- delete_min(), 最小値を取り出す
- insert(x), データ x を挿入する
- empty?(), キューが空ならば真を返す
- size(), 要素数を求める
●使用例
irb> load "heap.rb" => true irb> pq = PQueue.new => #<PQueue: ...> irb> pq.empty? => true irb> pq.size => 0 irb> pq.insert(5) => nil irb> pq.insert(3) => nil irb> pq.insert(7) => nil irb> pq.insert(1) => nil irb> pq.insert(9) => nil irb> pq.empty? => false irb> pq.size => 5 irb> while not pq.empty? irb> print pq.delete_min, " " irb> end 1 3 5 7 9 => nil irb> a = (1..20).to_a.shuffle => [19, 17, 14, 12, 8, 20, 2, 18, 4, 11, 6, 1, 10, 5, 3, 16, 15, 13, 7, 9] irb> pq = PQueue.new(a) => #<PQueue: ...> irb> while not pq.empty? irb> print pq.delete_min, " " irb> end 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 => nil
●プログラム
リスト : プライオリティキュー (heap.rb)
class PQueue
def initialize(ary = [])
@buff = ary.dup
(@buff.size / 2 - 1).downto(0) do |n|
reheap_to_leaf(@buff, n)
end
end
private
def reheap_to_leaf(ary, n)
loop do
c = 2 * n + 1
break if c >= ary.size
if c + 1 < ary.size
c += 1 if ary[c] > ary[c + 1]
end
break if ary[n] <= ary[c]
temp = ary[n]
ary[n] = ary[c]
ary[c] = temp
n = c
end
end
def reheap_to_root(ary, n)
loop do
p = (n - 1) / 2
break if p < 0 || ary[p] <= ary[n]
temp = ary[n]
ary[n] = ary[p]
ary[p] = temp
n = p
end
end
public
# 最小値を取り出す
def delete_min
return nil if @buff.empty?
value = @buff[0]
last = @buff.pop
if @buff.size > 0
@buff[0] = last
reheap_to_leaf(@buff, 0)
end
value
end
# 最小値を参照
def first
return nil if @buff.empty?
@buff[0]
end
# データの挿入
def insert(data)
@buff.push data
reheap_to_root(@buff, @buff.size - 1)
end
# キューは空か？
def empty?
@buff.empty?
end
# 要素の個数
def size
@buff.size
end
def inspect
sprintf("#<PQueue:%#x>", self.object_id)
end
end
●トライ
トライは文字列の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval)」という言葉の真ん中 (trie) に由来しています。トライは木構造の一種であり、根から葉までの経路がひとつの単語に対応します。次の図を見てください。
図 : 文字列の集合を表したトライ
上図は文字列の集合をトライで表現したものです。ここでは葉を $ で表しています。たとえば、葉 $7 までたどると、それは "THEN" という文字列を表しています。また、文字列 "THE" をトライから探す場合は、節を順番にたどっていって、葉 $6 に達した時点で "THE" を見つけることができます。もし、節 E の子に葉 $6 がなければ、THE はトライに存在しないことになります。詳しい説明は拙作のページ Algorithms with Python: トライとパトリシア をお読みくださいませ。
●仕様
- クラス名: Trie
- コンストラクタ: Trie.new()
- member?(seq), トライに seq があれば真を返す
- insert(seq), トライに seq を挿入する
- delete(seq), トライから seq を削除する
- empty?(), トライが空ならば真を返す
- size, トライの要素数を求める
- each {|x| ...}, トライの要素にブロックを適用する
- common_prefix(seq){|x| ...}, 共通接頭辞 seq の要素を求めてブロックを適用する
●使用例
irb> load "trie.rb"
=> true
irb> a = Trie.new
=> #<Trie: ...>
irb> a.empty?
=> true
irb> a.size
=> 0
irb> a.insert("hello")
=> "hello"
irb> a.empty?
=> false
irb> a.size
=> 1
irb> a.insert("world")
=> "world"
irb> a.size
=> 2
irb> a.member?("hello")
=> true
irb> a.member?("hello,")
=> false
irb> a.member?("hell")
=> false
irb> a.member?("world")
=> true
irb> a.member?("world ")
=> false
irb> a.member?("worl")
=> false
irb> a.delete("hello")
=> true
irb> a.delete("hello")
=> false
irb> a.member?("hello")
=> false
irb> a.delete("world")
=> true
irb> a.delete("world")
=> false
irb> a.member?("world")
=> false
irb> a.empty?
=> true
irb> a.size
=> 0
irb> s = "abcabbca"
irb> for i in 0 ... s.size
irb> a.insert(s[i..-1])
irb> end
=> 0...8
irb> a.each{|xs| print xs, "\n"}
["a", "b", "c", "a", "b", "b", "c", "a"]
["a", "b", "b", "c", "a"]
["a"]
["b", "c", "a", "b", "b", "c", "a"]
["b", "c", "a"]
["b", "b", "c", "a"]
["c", "a", "b", "b", "c", "a"]
["c", "a"]
=> #<Trie: ...>
irb> a.common_prefix("ab"){|xs| print xs.join, "\n"}
abcabbca
abbca
=> #<Trie: ...>
irb> a.common_prefix("bc"){|xs| print xs.join, "\n"}
bcabbca
bca
=> #<Trie: ...>
irb> a.common_prefix("ca"){|xs| print xs.join, "\n"}
cabbca
ca
=> #<Trie: ...>
●プログラム
リスト : トライ (trie.rb)
class Trie
attr_reader :size
# トライ用節の定義
class Node
attr_accessor :data, :child
def initialize(data)
@data = data
@child = [] # 子は配列に格納する
end
end
def initialize
@root = Node.new(nil)
@leaf = Node.new(nil)
@size = 0
end
private
def search_child(node, x)
node.child.find do |n|
n.data == x
end
end
# 巡回
def _traverse(node, buff, &block)
if node == @leaf
yield buff
else
b = buff + [node.data]
for x in node.child
_traverse(x, b, &block)
end
end
end
public
# 探索
def member?(seq)
node = @root
for x in 0 ... seq.size
node = search_child(node, seq[x])
return false unless node
end
node.child.member?(@leaf)
end
# 挿入
def insert(seq)
node = @root
for x in 0 ... seq.size
child = search_child(node, seq[x])
unless child
child = Node.new(seq[x])
node.child.push child
end
node = child
end
unless node.child.member?(@leaf)
node.child.push @leaf
@size += 1
seq
end
end
# 削除 (葉を削除するだけ)
def delete(seq)
node = @root
for x in 0 ... seq.size
node = search_child(node, seq[x])
return nil unless node
end
if node.child.delete(@leaf)
@size -= 1
true
else
false
end
end
# 共通接頭辞を持つデータを求める
def common_prefix(seq, &block)
node = @root
buff = []
for x in 0 ... seq.size
buff.push seq[x]
node = search_child(node, seq[x])
return nil unless node
end
for cnode in node.child
_traverse(cnode, buff, &block)
end
self
end
# トライは空か？
def empty?
@size == 0
end
# Enumberable 用
def each(&block)
for x in @root.child
_traverse(x, [], &block)
end
self
end
def inspect
sprintf("#<Trie:%#x>", self.object_id)
end
end
●パトリシア
トライはとても便利なデータ構造ですが、節にはひとつの文字しか格納できないため、文字列の種類が多くなるとメモリを大量に消費してしまいます。このため、文字ではなく文字列を節に格納する方法があります。次の図を見てください。
図 : 文字列の集合を表したパトリシア
"TAIL" をトライで表すと T - A - I - L となりますが、I の子は L しかありませんね。この部分は "IL" とまとめることができます。つまり、節には部分文字列を格納するわけです。このように、トライにおいて分岐していない節をひとつにまとめたものをパトリシア (Patricia Tree) と呼びます。
パトリシアの場合、データの探索は節の部分文字列を比較していくだけなので、簡単に実現できます。ところが、データの挿入はちょっとだけ複雑になります。たとえば、パトリシアが "ab" - "cdef" という状態で、ここに文字列 "abcdgh" を挿入してみましょう。
挿入する文字列の先頭 2 文字と最初の節 "ab" は一致するので、次の節 "cdef" と残りの文字列 "cdgh" を比較します。"cd" は一致しますが、それ以降で不一致になりますね。この場合、節 "cdef" を不一致の位置で分割します。つまり、節 "cdef" を "cd" - "ef" と分割し、節 "cd" に新しい節 "gh" を追加するのです。このあと、終端を表す葉を追加すれば、パトリシアに "abcdgh" を挿入することができます。
このように、パトリシアにデータを挿入する場合、節の分割が必要になるためプログラムは複雑になります。そのかわり、パトリシアはトライに比べて節の個数を少なくすることができるので、トライよりも少ないメモリで文字列の集合を表すことができます。詳しい説明は拙作のページ Algorithms with Python: トライとパトリシア をお読みくださいませ。
●仕様
- クラス名: Patricia
- コンストラクタ: Patricia.new()
- member?(seq), パトリシアに seq があれば真を返す
- insert(seq), パトリシアに seq を挿入する
- delete(seq), パトリシアから seq を削除する
- empty?(), パトリシアが空ならば真を返す
- size, パトリシアの要素数を求める
- each {|x| ...}, パトリシアの要素にブロックを適用する
- common_prefix(seq){|x| ...}, 共通接頭辞 seq の要素を求めてブロックを適用する
●使用例
irb> load "patricia.rb"
=> true
irb> a = Patricia.new
=> #<Patricia: ...>
irb> a.empty?
=> true
irb> a.size
=> 0
irb> ["hello", "world", "hello, world"].each{|s| a.insert(s)}
=> ["hello", "world", "hello, world"]
irb> a.empty?
=> false
irb> a.size
=> 3
irb> a.member? "hello"
=> true
irb> a.member? "hello,"
=> false
irb> a.member? "world"
=> true
irb> a.member? " world"
=> false
irb> a.member? "hello, world"
=> true
irb> a.member? "hello, world!"
=> false
irb> a.delete "hello"
=> true
irb> a.delete "hello"
=> false
irb> a.member? "hello"
=> false
irb> a.delete "world"
=> true
irb> a.delete "world"
=> false
irb> a.member? "world"
=> false
irb> a.delete "hello, world"
=> true
irb> a.delete "hello, world"
=> false
irb> a.member? "hello, world"
=> false
irb> a.size
=> 0
irb> a.empty?
=> true
irb> s = "abcabbca"
=> "abcabbca"
irb> for i in 0 ... s.size
irb> a.insert(s[i .. -1])
irb> end
=> 0...8
irb> a.size
=> 8
irb> a.each{|xs| print xs, "\n"}
["a", "b", "cabbca"]
["a", "b", "bca"]
["a"]
["b", "ca", "bbca"]
["b", "ca"]
["b", "bca"]
["ca", "bbca"]
["ca"]
=> #<Patricia: ...>
irb> a.common_prefix("a"){|xs| print xs, "\n"}
["a", "b", "cabbca"]
["a", "b", "bca"]
["a"]
=> #<Patricia: ...>
irb> a.common_prefix("ab"){|xs| print xs, "\n"}
["ab", "cabbca"]
["ab", "bca"]
=> #<Patricia: ...>
irb> a.common_prefix("abc"){|xs| print xs, "\n"}
["abc", "abbca"]
=> #<Patricia: ...>
irb> a.common_prefix("bc"){|xs| print xs, "\n"}
["bc", "a", "bbca"]
["bc", "a"]
=> #<Patricia: ...>
irb> a.common_prefix("bca"){|xs| print xs, "\n"}
["bca", "bbca"]
["bca"]
=> #<Patricia: ...>
●プログラム
リスト : パトリシア (patricia.rb)
class Patricia
attr_reader :size
# 節の定義
class Node
attr_accessor :data, :child
def initialize(data, child = [])
@data = data
@child = child
end
end
def initialize
@root = Node.new(nil)
@leaf = Node.new(nil)
@size = 0
end
private
# 子を探す
def search_child(n, c)
n.child.find do |x|
x.data && x.data[0] == c
end
end
# 最長一致を求める
def longest_match(seq)
node = @root
i = 0
while i < seq.size
child = search_child(node, seq[i])
break unless child
j = 1
while j < child.data.size
if i + j == seq.size || seq[i + j] != child.data[j]
return child, j, i + j
end
j += 1
end
i += j
node = child
end
return node, 0, i
end
# 巡回
def traverse(node, buff, &block)
for x in node.child
if x == @leaf
yield buff
else
buff.push x.data
traverse(x, buff, &block)
buff.pop
end
end
end
public
# 探索
def member?(seq)
node, len, match_len = longest_match(seq)
match_len == seq.size && len == 0 && node.child.member?(@leaf)
end
# 削除
def delete(seq)
node, len, match_len = longest_match(seq)
if match_len == seq.size && len == 0 && node.child.delete(@leaf)
@size -= 1
true
else
false
end
end
# 挿入
def insert(seq)
node, len, match_len = longest_match(seq)
if len == 0
if match_len == seq.size
return false if node.child.member?(@leaf)
node.child.push @leaf
else
# @node に残りの節を追加する
new_node = Node.new(seq[match_len .. -1], [@leaf])
node.child.push new_node
end
else
# @node を分割する
node1 = Node.new(node.data[len .. -1], node.child)
node.data = node.data[0 ... len]
if match_len < seq.size
new_node = Node.new(seq[match_len .. -1], [@leaf])
node.child = [node1, new_node]
else
node.child = [node1, @leaf]
end
end
@size +=1
true
end
# 共通接頭辞を持つデータを求める
def common_prefix(seq, &block)
node, len, match_len = longest_match(seq)
if match_len == seq.size
buff = [seq]
buff.push node.data[len .. -1] if len > 0
traverse(node, buff, &block)
end
self
end
# パトリシアは空か？
def empty?
@size == 0
end
def each(&block)
traverse(@root, [], &block)
self
end
def inspect
sprintf("#<Patricia:%#x>", self.object_id)
end
end
●Ternary Search Tree
Ternary Search Tree (TST) は三分木を使った探索木で、トライと同様に文字列の集合を表すのに都合のよいデータ構造です。TST の動作はとても簡単で、節に格納されているデータを基準にして、それよりも小さいデータは左の木、等しいデータは中央の木、大きなデータは右の木をたどることで文字列を探索します。簡単な例を示します。次の図を見てください。
図：文字列の集合を表した TST
TST の場合、トライのように「葉」で終端を表すことはできません。このため、終端を表すデータ（たとえば 0）を TST に挿入します。上図では、0 の節を $ で表しています。
たとえば、上図の 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 の節が追加されます。TST の場合、終端を表す節は「葉」になるとは限りません。詳しい説明は拙作のページ Algorithms with Python: Ternary Search Tree をお読みくださいませ。
●仕様
- クラス名: Tss
- コンストラクタ: Tst.new(x = "\0"), x は終端を表す値
- member?(seq), TST に seq があれば真を返す
- insert(seq), TST に seq を挿入する
- delete(seq), TST から seq を削除する
- empty?(), TST が空ならば真を返す
- size, TST の要素数を求める
- each {|x| ...}, TST の要素にブロックを適用する
- common_prefix(seq){|x| ...}, 共通接頭辞 seq の要素を求めてブロックを適用する
●使用例
irb> load "tst.rb"
=> true
irb> a = Tst.new
=> #<Tst: ...>
irb> a.empty?
=> true
irb> a.size
=> 0
irb> a.insert "hello"
=> true
irb> a.insert "world"
=> true
irb> a.insert "hello, world"
=> true
irb> a.size
=> 3
irb> a.empty?
=> false
irb> a.member? "hello"
=> true
irb> a.member? "hello,"
=> false
irb> a.member? "world"
=> true
irb> a.member? " world"
=> false
irb> a.member? "hello, world"
=> true
irb> a.member? "hello, world!"
=> false
irb> a.delete "hello"
=> true
irb> a.delete "hello"
=> false
irb> a.member? "hello"
=> false
irb> a.size
=> 2
irb> a.delete "world"
=> true
irb> a.delete "world"
=> false
irb> a.member? "world"
=> false
irb> a.delete "hello, world"
=> true
irb> a.delete "hello, world"
=> false
irb> a.member? "hello, world"
=> false
irb> a.size
=> 0
irb> a.empty?
=> true
irb> s = "abcabbca"
=> "abcabbca"
irb> for i in 0 ... s.size
irb> a.insert(s[i..-1])
irb> end
=> 0...8
irb> a.size
=> 8
irb> a.each{|x| print x, "\n"}
["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"]
=> #<Tst: ...>
irb> a.common_prefix("a"){|x| print x, "\n"}
["a"]
["a", "b", "b", "c", "a"]
["a", "b", "c", "a", "b", "b", "c", "a"]
=> #<Tst: ...>
irb> a.common_prefix("ab"){|x| print x, "\n"}
["a", "b", "b", "c", "a"]
["a", "b", "c", "a", "b", "b", "c", "a"]
=> #<Tst: ...>
irb> a.common_prefix("abc"){|x| print x, "\n"}
["a", "b", "c", "a", "b", "b", "c", "a"]
=> #<Tst: ...>
irb> a.common_prefix("b"){|x| print x, "\n"}
["b", "b", "c", "a"]
["b", "c", "a"]
["b", "c", "a", "b", "b", "c", "a"]
=> #<Tst: ...>
irb> a.common_prefix("bc"){|x| print x, "\n"}
["b", "c", "a"]
["b", "c", "a", "b", "b", "c", "a"]
=> #<Tst: ...>
irb> a.common_prefix("c"){|x| print x, "\n"}
["c", "a"]
["c", "a", "b", "b", "c", "a"]
=> #<Tst: ...>
●プログラム
リスト : Ternary Search Tree (tst.rb)
class Tst
attr_reader :size
# TST 用節の定義
class Node
attr_accessor :data, :left, :mid, :right
def initialize(x)
@data = x
@left = nil
@mid = nil
@right = nil
end
end
def initialize(x = '\0')
@root = Node.new(nil) # header
@leaf = x
@size = 0
end
# 木の操作関数
private
# 探索
def search_node(node, x)
while node
return node if node.data == x
if x < node.data
node = node.left
else
node = node.right
end
end
end
# 挿入
# x は節
def insert_node(node, x)
if not node
return x
elsif x.data == node.data
return node
elsif x.data < node.data
node.left = insert_node(node.left, x)
else
node.right = insert_node(node.right, x)
end
node
end
# 最小値を探す
def search_min_node(node)
if node.left
search_min_node(node.left)
else
node.data
end
end
# 最小値を削除する
def delete_min_node(node)
if node.left
node.left = delete_min_node(node.left)
node
else
node.right
end
end
# 削除
def delete_node(node, x)
if node
if x == node.data
if not node.left
return node.right
elsif not node.right
return node.left
else
node.data = search_min_node(node.right)
node.right = delete_min_node(node.right)
end
elsif x < node.data
node.left = delete_node(node.left, x)
else
node.right = delete_node(node.right, x)
end
end
node
end
# 巡回
def traverse_node(node, buff, leaf, &block)
if node
traverse_node(node.left, buff, leaf, &block)
if node.data == leaf
yield buff
else
buff.push node.data
traverse_node(node.mid, buff, leaf, &block)
buff.pop
end
traverse_node(node.right, buff, leaf, &block)
end
end
# TSTの操作
public
# 探索
def member?(seq)
node = @root
for i in 0 ... seq.size
node = search_node(node.mid, seq[i])
return false unless node
end
# check leaf
search_node(node.mid, @leaf) ? true : false
end
# 挿入
def insert(seq)
node = @root
for i in 0 ... seq.size
x = seq[i]
child = search_node(node.mid, x)
if not child
child = Node.new(x)
node.mid = insert_node(node.mid, child)
end
node = child
end
# check leaf
if search_node(node.mid, @leaf)
false
else
node.mid = insert_node(node.mid, Node.new(@leaf))
@size += 1
true
end
end
# 削除
def delete(seq)
node = @root
for i in 0 ... seq.size
node = search_node(node.mid, seq[i])
return false unless node
end
# delete leaf
if search_node(node.mid, @leaf)
node.mid = delete_node(node.mid, @leaf)
@size -= 1
true
else
false
end
end
# 巡回
def each(&block)
traverse_node(@root.mid, [], @leaf, &block)
self
end
# 共通接頭辞を持つデータを求める
def common_prefix(seq, &block)
node = @root
buff = []
for i in 0 ... seq.size
x = seq[i]
buff.push x
node = search_node(node.mid, x)
return self unless node
end
traverse_node(node.mid, buff, @leaf, &block)
self
end
def empty?
@size == 0
end
def inspect
sprintf("#<Tst:%#x>", self.object_id)
end
end