Patricia Trie as a Ruby Standard Library

Detlef_R · December 18, 2013, 12:19am

Hi there,
I have written a Radix Trie or Patricia Trie for this kata:
http://codekata.pragprog.com/2007/01/kata_eight_conf.html
Although I have called my implementation a “Generic one” I will be
polishing it and providing all features that a Patricia Trie should do.

Here is the kata: GitHub - acnalesso/pragprog_kata08
I would like you guys to have a look, if possible, and let me know
whether this would get merged or not.
I think Ruby should provide a standard such standard library, as it
can help, speed up, people to build many programs with it.
Please bear in mind that this is still a work-in-progress, so far I
just want to hear your feedback, ideas, suggestions etc…

I am looking forward to hearing from you all.
Merry Christmas everyone and a lovely new’s year.

Nalesso Moreira

nalesso · December 18, 2013, 11:09pm

Hi!

On 18/12/13 00:19, nalesso moreira wrote:

Hi there, I have written a Radix Trie or Patricia Trie for this
kata: http://codekata.pragprog.com/2007/01/kata_eight_conf.html
Although I have called my implementation a “Generic one” I will be
polishing it and providing all features that a Patricia Trie should
do.

There is a Trie implementation as rubygem and a public git repository
is available [1].
There was google summer of code project called “algorithms” a while ago.

The most current version should be:

[1]

github.com

kanwei/algorithms/blob/master/lib/containers/trie.rb

=begin rdoc
    A Trie is a data structure that stores key value pairs in a tree-like fashion. It allows
    O(m) lookup speed, where m is the length of the key searched, and has no chance of collisions,
    unlike hash tables. Because of its nature, search misses are quickly detected.
    
    Tries are often used for longest prefix algorithms, wildcard matching, and can be used to
    implement a radix sort.

    This implemention is based on a Ternary Search Tree.
=end
class Containers::Trie  
  # Create a new, empty Trie.
  #
  #   t = Containers::Trie.new
  #   t["hello"] = "world"
  #   t["hello"] #=> "world"
  def initialize
    @root = nil
  end

This file has been truncated. show original

nalesso · December 24, 2013, 9:19pm

Hi there!
I am aware of this gem.
I have benchmarks showing that my implementation is faster.
Thanks any way

“Sandor Szücs” [email protected] wrote in post #1131020:

Hi!

On 18/12/13 00:19, nalesso moreira wrote:

Hi there, I have written a Radix Trie or Patricia Trie for this
kata: http://codekata.pragprog.com/2007/01/kata_eight_conf.html
Although I have called my implementation a “Generic one” I will be
polishing it and providing all features that a Patricia Trie should
do.

There is a Trie implementation as rubygem and a public git repository
is available [1].
There was google summer of code project called “algorithms” a while ago.

The most current version should be:
GitHub - kanwei/algorithms: Ruby algorithms and data structures. C extensions

[1]
algorithms/lib/containers/trie.rb at master · kanwei/algorithms · GitHub