1  
   2  # From: http://www.matasano.com/log/basic-uncommented-crappy-binary-radix-trie/
   3  # Author: Thomas Ptacek
   4  # cf. also http://www.matasano.com/log/1009/aguri-coolest-data-structure-youve-never-heard-of/
   5  
   6  #!/usr/local/bin/ruby -w
   7  
   8  class Fixnum
   9      def to_b(l = 8)
  10          "0'" + self.to_s(2).rjust(l, "0")
  11      end
  12      def set?(i)
  13          if((self & (1 << i)) != 0)
  14              return true
  15          else
  16              return false
  17          end
  18      end
  19  
  20       def bdiff(x)
  21           ret = -1
  22           32.downto(0) do |i|
  23               if(self.set?(i) != x.set?(i))
  24                   ret = i
  25                   break
  26               end
  27           end
  28           ret
  29       end
  30  end
  31  
  32  class String
  33      def to_ip
  34          ip = 0
  35          split(".").each_with_index do |octet, index|
  36              ip |= (octet.to_i << ((3 - index)*8))
  37          end
  38          ip
  39      end
  40  end
  41  
  42  class SimpleTrie
  43      def initialize(width=32)
  44          @@node ||= Struct.new(:right, :left, :pos, :key, :value, :color)
  45          @root = @@node.new(nil, nil, width, 0, nil)
  46          @root.right = @root
  47          @root.left = @root
  48          @width = width
  49          @sz = 0
  50      end
  51  
  52      private
  53  
  54      def srch(key, limit=nil)
  55          cur = @root
  56          prev = nil
  57  
  58          while(((not prev) or (cur.pos < prev.pos)) and ((not limit) or cur.pos > limit))
  59              prev = cur
  60              if(key.set? cur.pos)
  61                  cur = cur.right
  62              else
  63                  cur = cur.left
  64              end
  65          end
  66  
  67          return cur, prev
  68      end
  69  
  70      public
  71  
  72      def []=(key, val)
  73          x, prev = srch(key)
  74          bit = key.bdiff(x.key)
  75          cur, prev = srch(key, bit)
  76  
  77          node = @@node.new(nil, nil, bit, key, val)
  78  
  79          if(key.set? bit)
  80              node.right = node
  81              node.left = cur
  82          else
  83              node.right = cur
  84              node.left = node
  85          end
  86  
  87          if(key.set? prev.pos)
  88              prev.right = node
  89          else
  90              prev.left = node
  91          end
  92  
  93          @sz += 1
  94  
  95          return val
  96      end
  97  
  98      def walk
  99          color = rand
 100          walker = lambda do |x, dir, tab|
 101              if(x.color != color)
 102                  tab.times { print "  " }
 103                  puts "#{ dir } #{ x.key } ( #{ x.key.to_b } ) @ #{ x.pos }"
 104  
 105                  x.color = color
 106  
 107                  walker.call(x.right, "-> ", tab+1)
 108                  walker.call(x.left, "<- ", tab+1)
 109              end
 110          end
 111  
 112          walker.call(@root, ".   ", 0)
 113      end
 114  
 115      def [](key)
 116          res, p = srch(key)
 117          return res.value
 118      end
 119  end
 120  
 121  
 122  require 'pp'
 123  
 124  t = SimpleTrie.new
 125  
 126  t[3] = 3
 127  t[4] = 4
 128  t[2] = 2
 129  
 130  t.walk
 131  pp t
 132  
 133  p t[3]

   1  
   2  # Inspired by http://www.rubyquiz.com/quiz103.html
   3  # cf. also http://en.wikipedia.org/wiki/Trie
   4  
   5  #!/usr/local/bin/ruby -w
   6  
   7  require 'pp'
   8  
   9  class Hash
  10  
  11     def deep_merge!(second)
  12        # cf. http://snippets.dzone.com/posts/show/4146
  13        merger = proc { |key,v1,v2| Hash === v1 && Hash === v2 ? v1.merge(v2, &merger) : v2 }
  14        self.merge!(second, &merger)
  15     end
  16  
  17     def nested_hash(array)
  18        node = self
  19        array.each do |i|
  20           node[i]=Hash.new if node[i].nil?
  21           node = node[i]
  22        end 
  23        self
  24     end
  25  
  26     def merge_nested_hash!(nested_hash)
  27        deep_merge!(nested_hash)
  28     end
  29  
  30     # code basis taken from: "Find every path and it's value in a Hash" by Florian Aßmann,
  31     # http://snippets.dzone.com/posts/show/3565
  32  
  33     def each_trie_path
  34        raise ArgumentError unless block_given?
  35        self.class.each_trie_path(self) { |path, object| yield(path, object) }
  36     end
  37  
  38     protected
  39     def self.each_trie_path(object, path = [], &block)  
  40  
  41        if object.is_a?(Hash)
  42           object.each do |key, value|
  43  
  44              if key == true && value == {}
  45                 if path == [:root]  # special case for empty string: [[:root], {true=>{}}]
  46                    yield(path, {true=>{}})
  47                    next
  48                 end
  49                 yield(path, object)
  50              end
  51  
  52              self.each_trie_path(value, [path , key].flatten, &block)
  53           end
  54        else 
  55           yield(path, object)
  56        end
  57     end 
  58  
  59  end
  60  
  61  
  62  class Trie
  63  
  64     @hash = Hash.new.merge_nested_hash!(Hash.new)
  65     #@hash = Hash.new.merge_nested_hash!({:root=>{}})
  66     #@hash = Hash.new.merge_nested_hash!(Hash.new.nested_hash([:root]))
  67     class << self; attr_accessor :hash; end    # Trie.hash
  68  
  69     def initialize
  70        Trie.hash.merge_nested_hash!({:root=>{}})
  71     end
  72  
  73  
  74     def add_int(int)   # for int >= 0
  75        ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }  # integer array; ex: [4,6,2]
  76        ia.unshift(:root).push(true)
  77        Trie.hash.merge_nested_hash!(Hash.new.nested_hash(ia))
  78     end
  79  
  80     def matchi(int)  # match integer
  81        ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }  
  82        node = Trie.hash.fetch(:root,nil)
  83        ia.each do |digit|
  84           node = node[digit]
  85           #node = node.fetch(digit,nil)
  86           return false unless node
  87        end
  88        node.fetch(true,nil) ? true : false
  89     end
  90  
  91     def mfpi(int)   # match first part of integer
  92        ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }
  93        node = Trie.hash.fetch(:root,nil)
  94        ia.each do |digit|
  95           node = node[digit]
  96           return false unless node
  97        end
  98        return true
  99     end
 100  
 101  
 102     def add_word(word)
 103        ca = word.split(//u)    # UTF-8 aware character array
 104        ca.unshift(:root).push(true)
 105        Trie.hash.merge_nested_hash!(Hash.new.nested_hash(ca))
 106     end
 107  
 108     def match(word)   # match entire word
 109        ca = word.split(//u)    
 110        node = Trie.hash.fetch(:root,nil)
 111        ca.each do |char|
 112           node = node[char]
 113           #node = node.fetch(char,nil)
 114           return false unless node
 115        end
 116        node.fetch(true,nil) ? true : false
 117     end
 118  
 119     def mfpw(word)   # match first part of word
 120        ca = word.split(//u)    
 121        node = Trie.hash.fetch(:root,nil)
 122        ca.each do |char|
 123           node = node[char]
 124           return false unless node
 125        end
 126        return true
 127     end
 128  
 129  end
 130  
 131  
 132  trie = Trie.new
 133  p Trie.hash
 134  
 135  trie.add_word("word")
 136  pp Trie.hash            
 137  p trie.match("word")      
 138  p trie.match("word2")   
 139  trie.add_word("word2")
 140  p trie.match("word2")   
 141  pp Trie.hash            # {:root=>{"w"=>{"o"=>{"r"=>{"d"=>{true=>{}, "2"=>{true=>{}}}}}}}}
 142  
 143  trie.add_word("")
 144  p trie.match("")
 145  pp Trie.hash
 146  
 147  puts
 148  
 149  p trie.match("word")      
 150  p trie.mfpw("wor")     # match first part of word
 151  
 152  puts
 153  
 154  trie.add_int(12345)
 155  p Trie.hash
 156  
 157  trie.add_int(12980345)
 158  pp Trie.hash
 159  
 160  trie.add_int(8512)
 161  pp Trie.hash
 162  p trie.matchi(8512)
 163  p trie.matchi(85)
 164  p trie.mfpi(85)     # match first part of integer
 165  p trie.matchi(51)
 166  
 167  puts
 168  
 169  puts
 170  pp Trie.hash
 171  paths = []
 172  Trie.hash.each_trie_path { |path, value| paths.push([ path ]) }
 173  #Trie.hash.each_trie_path { |path, value| paths.push([ path, value ]) }
 174  #pp paths
 175  puts
 176  paths.each { |x| p x }
 177  puts
 178  
 179  
 180  #------------------------------------------------------
 181  
 182  
 183  require 'pp'
 184  
 185  class Hash
 186     def Hash.new_nested_hash
 187       Hash.new{|h,k| h[k]=Hash.new(&h.default_proc) }
 188     end
 189  end
 190  
 191  
 192  class Trie
 193  
 194     @hash = Hash.new_nested_hash
 195     #@hash = Hash.new_nested_hash.update(true=>{})  # add empty string by default
 196     class << self; attr_accessor :hash; end    # Trie.hash
 197  
 198     def <<(word)
 199        ca = word.split(//u)    # UTF-8 aware character array
 200        wl = ca.size            # word length
 201        str = ""
 202        wl.times { |x| str << "[ca.at(#{x})]" }
 203        str = "Trie.hash" << str << "[true]"
 204        #p str     # example: "Trie.hash[ca.at(0)][ca.at(1)][ca.at(2)][ca.at(3)][true]"
 205        eval(str)
 206     end
 207  
 208  
 209     def match(word)
 210        ca = word.split(//u)    # UTF-8 aware character array
 211        wl = ca.size            # word length
 212        str = ""
 213  
 214        wl.times { |x| str << ".fetch(ca.at(#{x}),nil)" }
 215        str = "Trie.hash" << str << ".fetch(true,nil)"
 216        #p str   # example: "Trie.hash.fetch(ca.at(0),nil).fetch(ca.at(1),nil).fetch(ca.at(2),nil).fetch(true,nil)"
 217        ret = eval(str) rescue nil
 218  
 219  =begin
 220        # alternative
 221        wl.times { |x| str << ".fetch(ca.at(#{x}),{})" }
 222        str = "Trie.hash" << str << ".fetch(true,nil)"
 223        #p str   # example: "Trie.hash.fetch(ca.at(0),{}).fetch(ca.at(1),{}).fetch(ca.at(2),{}).fetch(true,nil)"
 224        ret = eval(str)
 225  =end
 226  
 227        ret == {} ? true : false   # {} is the default value created by Trie.hash or Hash.new_nested_hash respectively
 228     end
 229  
 230  end
 231  
 232  
 233  trie = Trie.new
 234  trie << "word"
 235  pp Trie.hash            
 236  p trie.match("word")      
 237  p trie.match("word2")   
 238  trie << "word2"
 239  p trie.match("word2")   
 240  pp Trie.hash            # {"w"=>{"o"=>{"r"=>{"d"=>{true=>{}, "2"=>{true=>{}}}}}}}
 241  
 242  trie << ""
 243  p trie.match("")
 244  pp Trie.hash
 245  
 246  
 247  #------------------------------------------
 248  
 249  
 250  # alternative with default :root element
 251  
 252  require 'pp'
 253  
 254  class Hash
 255     def Hash.new_nested_hash
 256       Hash.new{|h,k| h[k]=Hash.new(&h.default_proc) }
 257     end
 258  end
 259  
 260  
 261  class Hash
 262  
 263     # code basis taken from: "Find every path and it's value in a Hash" by Florian Aßmann,
 264     # http://snippets.dzone.com/posts/show/3565
 265  
 266     def each_trie_path
 267        raise ArgumentError unless block_given?
 268        self.class.each_trie_path(self) { |path, object| yield(path, object) }
 269     end
 270  
 271     protected
 272     def self.each_trie_path(object, path = [], &block)  
 273  
 274        if object.is_a?(Hash)
 275           object.each do |key, value|
 276  
 277              if key == true && value == {}
 278                 if path == [:root]  # special case for empty string: [[:root], {true=>{}}]
 279                    yield(path, {true=>{}})
 280                    next
 281                 end
 282                 yield(path, object)
 283              end
 284  
 285              self.each_trie_path(value, [path , key].flatten, &block)
 286           end
 287        else 
 288           yield(path, object)
 289        end
 290     end 
 291  
 292  end
 293  
 294  
 295  class Trie
 296  
 297     @hash = Hash.new_nested_hash
 298     class << self; attr_accessor :hash; end    # Trie.hash
 299  
 300     def initialize
 301        Trie.hash[:root]
 302     end
 303  
 304  
 305     def add_int(int)   # for int >= 0
 306        ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }  # integer array; ex: [4,6,2]
 307        ia.unshift(:root)
 308        str = ""
 309        ia.size.times { |x| str << "[ia.at(#{x})]" }
 310        str = "Trie.hash" << str << "[true]"
 311        eval(str)
 312     end
 313  
 314     def matchi(int)  # match integer
 315        ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }  
 316        node = Trie.hash.fetch(:root,nil)
 317        ia.each do |digit|
 318           node = node.fetch(digit,nil)
 319           return false unless node
 320        end
 321        node.fetch(true,nil) ? true : false
 322     end
 323  
 324     def mfpi(int)   # match first part of integer
 325        ia = int.to_s.scan(/[[:digit:]]/).map { |i| i.to_i }
 326        node = Trie.hash.fetch(:root,nil)
 327        ia.each do |digit|
 328           node = node.fetch(digit,nil)
 329           return false unless node
 330        end
 331        return true
 332     end
 333  
 334  
 335     def <<(word)
 336        ca = word.split(//u)    # UTF-8 aware character array
 337        ca.unshift(:root)
 338        #ca = [:root, *word.split(//u)]
 339        #ca = [:root].concat(word.split(//u))
 340        str = ""
 341        ca.size.times { |x| str << "[ca.at(#{x})]" }
 342        str = "Trie.hash" << str << "[true]"
 343        #p str     # example: "Trie.hash[ca.at(0)][ca.at(1)][ca.at(2)][ca.at(3)][true]"
 344        eval(str)
 345     end
 346  
 347     def match(word)
 348        ca = word.split(//u)    
 349        ca.unshift(:root)
 350        #ca = [:root, *word.split(//u)]
 351        #ca = [:root].concat(word.split(//u))
 352        str = ""
 353        ca.size.times { |x| str << ".fetch(ca.at(#{x}),nil)" }
 354        str = "Trie.hash" << str << ".fetch(true,nil)"
 355        #p str   # example: "Trie.hash.fetch(ca.at(0),nil).fetch(ca.at(1),nil).fetch(ca.at(2),nil).fetch(true,nil)"
 356        ret = eval(str) rescue nil
 357  
 358  =begin
 359        # alternative
 360        ca.size.times { |x| str << ".fetch(ca.at(#{x}),{})" }
 361        str = "Trie.hash" << str << ".fetch(true,nil)"
 362        #p str   # example: "Trie.hash.fetch(ca.at(0),{}).fetch(ca.at(1),{}).fetch(ca.at(2),{}).fetch(true,nil)"
 363        ret = eval(str)
 364  =end
 365  
 366        ret == {} ? true : false   # {} is the default value created by Trie.hash or Hash.new_nested_hash respectively
 367     end
 368  
 369     def match2(word)   # match entire word
 370        ca = word.split(//u)    
 371        node = Trie.hash.fetch(:root,nil)
 372        ca.each do |char|
 373           node = node.fetch(char,nil)
 374           return false unless node
 375        end
 376        node.fetch(true,nil) ? true : false
 377     end
 378  
 379     def mfpw(word)   # match first part of word
 380        ca = word.split(//u)    
 381        node = Trie.hash.fetch(:root,nil)
 382        ca.each do |char|
 383           node = node.fetch(char,nil)
 384           return false unless node
 385        end
 386        return true
 387     end
 388  
 389  end
 390  
 391  
 392  trie = Trie.new
 393  trie << "word"
 394  pp Trie.hash            
 395  p trie.match("word")      
 396  p trie.match("word2")   
 397  trie << "word2"
 398  p trie.match("word2")   
 399  pp Trie.hash            # {:root=>{"w"=>{"o"=>{"r"=>{"d"=>{true=>{}, "2"=>{true=>{}}}}}}}}
 400  
 401  trie << ""
 402  p trie.match("")
 403  pp Trie.hash
 404  
 405  puts
 406  
 407  p trie.match2("word")      
 408  p trie.mfpw("wor")     # match first part of word
 409  
 410  puts
 411  
 412  trie.add_int(8512)
 413  pp Trie.hash
 414  p trie.matchi(8512)
 415  p trie.matchi(85)
 416  p trie.mfpi(85)     # match first part of integer
 417  p trie.matchi(51)
 418  
 419  puts
 420  
 421  puts
 422  pp Trie.hash
 423  paths = []
 424  Trie.hash.each_trie_path { |path, value| paths.push([ path ]) }
 425  #Trie.hash.each_trie_path { |path, value| paths.push([ path, value ]) }
 426  #pp paths
 427  puts
 428  paths.each { |x| p x }
 429  puts