M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Ruby Programming

Ruby Junk Scripts

[ PrevPage | R u b y | NextPage ]

トライ

トライは文字列の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval) 」という言葉の真ん中 (trie) に由来しています。トライは木構造の一種であり、根から葉までの経路がひとつの単語に対応します。次の図を見てください。

                      T
                    /  \
                  /      \
                /          \
              /              \
            A                  H
          /│\              /│\
        /  │  \          /  │  \
      /    │    \      /    │    \
    I      K      L  A      E      I
    │      │    /│  │    /│      │
    L      E  K  L  T  $6  N      S
    │      │  │  │  │      │      │
    $1      $2  $3  $4  $5      $7      $8

{ TAIL, TAKE, TALK, TALL, THAT, THE, THEN, THIS }  

  図:文字列の集合を表したトライ

上図は文字列の集合をトライで表現したものです。ここでは葉を $ で表しています。たとえば、葉 $7 までたどると、それは "THEN" という文字列を表しています。また、文字列 "THE" をトライから探す場合は、節を順番にたどっていって、葉 $6 に達した時点で "THE" を見つけることができます。もし、節 E の子に葉 $6 がなければ、THE はトライに存在しないことになります。

●参考文献

  1. A.V. Aho, J.E. Hopcroft, J.D. Ullman, 『データ構造とアルゴリズム』, 培風館, 1987
  2. 近藤嘉雪, 『Cプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 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 の動作はとても簡単で、節に格納されているデータを基準にして、それよりも小さいデータは左の木、等しいデータは中央の木、大きなデータは右の木をたどることで文字列を探索します。簡単な例を示します。次の図を見てください。

         T
         │
         A
         │\
         │  \
         │    \
         │      \
         │        \
         │          \
         │            \
         K              \
       /│\              H
     /  │  \            │
    I   E    L          E
    │   │    │        /│\
    L   $2    L      /  │  \
    │       /│    /    $6    \
    $1      K $4  A        \    I
            │     │          N  │
            $3     T          │  S
                   │          $7  │
                   $5              $8

{TAIL,TAKE,TALK,TALL,THAT,THE,THEN,THIS}  

  図:文字列の集合を表した 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 の場合、終端を表す節は「葉」になるとは限りません。ご注意ください。

●参考文献

  1. 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)

パトリシア

トライはとても便利なデータ構造ですが、節にはひとつの文字しか格納できないため、文字列の種類が多くなるとメモリを大量に消費してしまいます。このため、文字ではなく文字列を節に格納する方法があります。次の図を見てください。

                      T
                    /  \
                  /      \
                /          \
              /              \
            A                  H
          /│\              /│\
        /  │  \          /  │  \
      /    │    \      /    │    \
   "IL"    "KE"     L "AT"     E     "IS"
    │      │    /│  │    /│      │
    $1      $2  K  L  $5  $6  N      $8
                │  │          │
                $3  $4          $7

{ TAIL, TAKE, TALK, TALL, THAT, THE, THEN, THIS }  

       図:文字列の集合を表したパトリシア

"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

経路の探索

    1       3       5
    B───D───F
0 /│      │
A  │      │
  \│      │
    C───E───G
    2       4       6

    図 : 経路の探索

スタート (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

Copyright (C) 2006 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]