Patricia Trie Ruby Library

7stud2 · 17 December 2013 23:19

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: https://github.com/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

···

--
Posted via http://www.ruby-forum.com/.

Sandor_Szuecs · 18 December 2013 22:08

Hi!

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

···

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

--
All the best, Sandor Szücs

7stud2 · 24 December 2013 20:19

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

"Sandor Szücs" <sandor.szuecs@fu-berlin.de> 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:
https://github.com/kanwei/algorithms/

[1]
https://github.com/kanwei/algorithms/blob/master/lib/containers/trie.rb

--
Posted via http://www.ruby-forum.com/.