トライ
トライは文字列の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval) 」という言葉の真ん中 (trie) に由来しています。トライは木構造の一種であり、根から葉までの経路がひとつの単語に対応します。次の図を見てください。
図 : 文字列の集合を表したトライ
上図は文字列の集合をトライで表現したものです。ここでは葉を $ で表しています。たとえば、葉 $7 までたどると、それは "THEN" という文字列を表しています。また、文字列 "THE" をトライから探す場合は、節を順番にたどっていって、葉 $6 に達した時点で "THE" を見つけることができます。もし、節 E の子に葉 $6 がなければ、THE はトライに存在しないことになります。
●参考文献
- A.V. Aho, J.E. Hopcroft, J.D. Ullman, 『データ構造とアルゴリズム』, 培風館, 1987
- 近藤嘉雪, 『Ｃプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998
●プログラム
#
# trie.rb : トライ
#
# Copyright (C) 2006 Makoto Hiroi
#
# 節の定義
class Node
attr_accessor :data, :child
def initialize(data)
@data = data
@child = [] # 子は配列に格納する
end
end
# トライ
class Trie
include Enumerable
def initialize
@root = Node.new(nil)
@leaf = Node.new(nil)
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 search(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 << child
end
node = child
end
unless node.child.member?(@leaf)
node.child << @leaf
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
seq if node.child.delete(@leaf)
end
# Enumberable 用
def each(&block)
for x in @root.child
_traverse(x, [], &block)
end
end
end
# テスト
if __FILE__ == $0
a = Trie.new
10.times do
p a.insert(sprintf("%s", rand(10000)))
end
a.each do |x| p x.pack("c*") end
for x in a.to_a
p a.delete(x)
p a.search(x)
end
end
●実行例
"4649" "3507" "9673" "7942" "5876" "4805" "5373" "4274" "136" "5486" "4649" "4805" "4274" "3507" "9673" "7942" "5876" "5373" "5486" "136" [52, 54, 52, 57] false [52, 56, 48, 53] false [52, 50, 55, 52] false [51, 53, 48, 55] false [57, 54, 55, 51] false [55, 57, 52, 50] false [53, 56, 55, 54] false [53, 51, 55, 51] false [53, 52, 56, 54] false [49, 51, 54] false
Ternary Search Tree
Ternary Search Tree (TST) は三分木を使った探索木で、トライと同様に文字列の集合を表すのに都合のよいデータ構造です。Ternary Search Tree の動作はとても簡単で、節に格納されているデータを基準にして、それよりも小さいデータは左の木、等しいデータは中央の木、大きなデータは右の木をたどることで文字列を探索します。簡単な例を示します。次の図を見てください。
図：文字列の集合を表した 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 の場合、終端を表す節は「葉」になるとは限りません。ご注意ください。
●参考文献
- Jon Bentley, Robert Sedgewick, "Fast Algorithms for Sorting and Searching Strings", Sorting and Searching Strings, 1997
●プログラム
#
# ternary.rb : Ternary Search Tree
#
# Copyright (C) 2006 Makoto Hiroi
#
require "bintree"
class Tnode < Node
attr_accessor :middle
def initialize(data)
super(data)
@middle = nil
end
end
class TernaryTree < BinTree
def initialize(leaf)
@root = Tnode.new(nil)
@leaf = leaf
end
private
# 巡回
def _traverse(node, buff = [], &block)
if node
_traverse(node.left, buff, &block)
if node.data == @leaf
yield buff
_traverse(node.middle, buff, &block)
else
_traverse(node.middle, buff + [node.data], &block)
end
_traverse(node.right, buff, &block)
end
end
public
# 探索
def search(seq)
node = @root
for x in 0 ... seq.size
child = _search(node.middle, seq[x])
return false unless child
node = child
end
# 葉をチェック
if _search(node.middle, @leaf)
true
else
false
end
end
# 挿入
def insert(seq)
node = @root
for x in 0 ... seq.size
child = _search(node.middle, seq[x])
unless child
child = Tnode.new(seq[x])
node.middle = _insert(node.middle, child)
end
node = child
end
# 葉をチェック
child = _search(node.middle, @leaf)
unless child
child = Tnode.new(@leaf)
node.middle = _insert(node.middle, child)
end
end
# 削除（とりあえず葉を削除するだけ）
def delete(seq)
node = @root
for x in 0 ... seq.size
child = _search(node.middle, seq[x])
return unless child
node = child
end
# 葉を削除
node.middle = _delete(node.middle, @leaf)
end
# Enumerable 用
def each(&block)
_traverse(@root.middle, [], &block)
end
# 文字列
def to_s
str ="("
_traverse(@root.middle) do |x|
str << x.pack("c*")
str << ","
end
if str[-1] == ?,
str[-1] = ?)
else
str << ")"
end
str
end
end
# テスト
if __FILE__ == $0
a = TernaryTree.new(257)
puts a
for x in ["abc", "abcd", "abcde"]
a.insert(x)
puts a
end
for x in ["ab", "abc", "abcd", "abcde", "ac"]
print x, ":", a.search(x), "\n"
end
for x in ["abc", "abcd", "abcde"]
a.delete(x)
puts a
end
for x in ["ab", "abc", "abcd", "abcde", "ac"]
print x, ":", a.search(x), "\n"
end
10.times do
a.insert(sprintf("%04d", rand(10000)))
puts a
end
end
●実行例
() (abc) (abcd,abc) (abcde,abcd,abc) ab:false abc:true abcd:true abcde:true ac:false (abcde,abcd) (abcde) () ab:false abc:false abcd:false abcde:false ac:false (3897) (3897,6925) (1618,3897,6925) (1618,3897,4884,6925) (1058,1618,3897,4884,6925) (1058,1618,3897,4884,6925,7997) (1058,1618,3897,4884,6388,6925,7997) (1058,1618,3897,4884,6388,6925,7997,9682) (0348,1058,1618,3897,4884,6388,6925,7997,9682) (0348,1058,1618,3897,4884,6388,6925,7173,7997,9682)
パトリシア
トライはとても便利なデータ構造ですが、節にはひとつの文字しか格納できないため、文字列の種類が多くなるとメモリを大量に消費してしまいます。このため、文字ではなく文字列を節に格納する方法があります。次の図を見てください。
図：文字列の集合を表したパトリシア
"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" を挿入することができます。
このように、パトリシアにデータを挿入する場合、節の分割が必要になるためプログラムは複雑になります。そのかわり、パトリシアはトライに比べて節の個数を少なくすることができるので、トライよりも少ないメモリで文字列の集合を表すことができます。
●プログラム
#
# patricia.rb : パトリシア
#
# Copyright (C) 2006 Makoto Hiroi
#
# 節の定義
class Node
attr_accessor :data, :child
def initialize(data, child = [])
@data = data
@child = child
end
end
class Patricia
include Enumerable
def initialize
@root = Node.new(nil)
@leaf = Node.new(nil)
# longest_match
@node = nil # 最後に一致した節
@len = 0 # node.data との一致長
@match_len = 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 seq[i + j] != child.data[j]
@node = child
@len = j
@match_len = i + j
return false
end
j += 1
end
i += j
node = child
end
@node = node
@len = 0 # node.data とすべて一致
@match_len = i
seq.size == i
end
# 巡回
def traverse(node, buff, &block)
for x in node.child
if x == @leaf
yield buff.join
else
buff << x.data
traverse(x, buff, &block)
buff.pop
end
end
end
public
# 探索
def search(seq)
if longest_match(seq)
# 葉があるか
@node.child.member?(@leaf)
end
end
# 削除
def delete(seq)
if longest_match(seq)
return true if @node.child.delete(@leaf)
end
end
# 挿入
def insert(seq)
if longest_match(seq)
return false if @node.child.member?(@leaf)
@node.child << @leaf
elsif @len == 0
# @node に残りの節を追加する
new_node = Node.new(seq[@match_len .. -1], [@leaf])
@node.child << new_node
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
true
end
# Enumerable 用
def each(&block)
traverse(@root, [], &block)
end
end
if __FILE__ == $0
a = Patricia.new
b = "ababcabcdabcdef"
for x in 0 ... b.size
a.insert(b[x .. -1])
end
a.each do |x| print x, "\n" end
for x in a.to_a
p a.search(x)
p a.delete(x)
p a.search(x)
end
end
●実行例
ababcabcdabcdef abcabcdabcdef abcdabcdef abcdef babcabcdabcdef bcabcdabcdef bcdabcdef bcdef cabcdabcdef cdabcdef cdef dabcdef def ef f true true false true true false true true false true true false true true false true true false true true false true true false true true false true true false true true false true true false true true false true true false true true false
経路の探索
図 : 経路の探索
スタート (A) からゴール (F) までの経路を求めるプログラムです。
●プログラム
#
# keiro.rb : 経路の探索
#
# Copyright (C) 2006 Makoto Hiroi
#
# 隣接リスト
$adjacent = [
[1, 2], # A
[0, 2, 3], # B
[0, 1, 4], # C
[1, 4, 5], # D
[2, 3, 6], # E
[3], # F
[4]] # G
# 経路の表示
def print_path(path)
path.each do |x| print x, " " end
print "\n"
end
# 深さ優先探索
def depth_search(goal, path)
if goal == path[-1]
print_path(path)
else
for n in $adjacent[path[-1]]
unless path.member?(n)
path << n
depth_search(goal, path)
path.pop
end
end
end
end
# 幅優先探索
def breadth_search(start, goal)
queue = [[start]]
while queue.size > 0
path = queue.shift
if goal == path[-1]
print_path(path)
else
for n in $adjacent[path[-1]]
unless path.member?(n)
queue << (path.dup << n)
end
end
end
end
end
# 反復深化
def id_search(limit, goal, path)
if path.size == limit
print_path(path) if goal == path[-1]
else
for n in $adjacent[path[-1]]
unless path.member?(n)
path << n
id_search(limit, goal, path)
path.pop
end
end
end
end
print "-- 深さ優先探索 --\n"
depth_search(5, [0])
print "-- 幅優先探索 --\n"
breadth_search(0, 5)
print "-- 反復深化 --\n"
for x in 1 .. 7
print x, " moves\n"
id_search(x, 5, [0])
end
●実行結果
-- 深さ優先探索 -- 0 1 2 4 3 5 0 1 3 5 0 2 1 3 5 0 2 4 3 5 -- 幅優先探索 -- 0 1 3 5 0 2 1 3 5 0 2 4 3 5 0 1 2 4 3 5 -- 反復深化 -- 1 moves 2 moves 3 moves 4 moves 0 1 3 5 5 moves 0 2 1 3 5 0 2 4 3 5 6 moves 0 1 2 4 3 5 7 moves