Bug 198100 - New port: devel/p5-Tree-Trie (Data structure optimized for prefix lookup)
Summary: New port: devel/p5-Tree-Trie (Data structure optimized for prefix lookup)
Status: Closed FIXED
Alias: None
Product: Ports & Packages
Classification: Unclassified
Component: Individual Port(s) (show other bugs)
Version: Latest
Hardware: Any Any
: --- Affects Only Me
Assignee: freebsd-ports-bugs (Nobody)
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-02-28 16:46 UTC by gebhart
Modified: 2015-03-08 02:30 UTC (History)
1 user (show)

See Also:


Attachments
shar file of ports files (2.42 KB, application/x-shar)
2015-02-28 16:46 UTC, gebhart
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description gebhart 2015-02-28 16:46:05 UTC
Created attachment 153617 [details]
shar file of ports files

This module implements a trie data structure. The term "trie" comes from the
word retrieval, but is generally pronounced like "try". A trie is a tree
structure (or directed acyclic graph), the nodes of which represent letters
in a word. For example, the final lookup for the word 'bob' would look
something like $ref->{'b'}{'o'}{'b'}{'00'} (the 00 being an end marker).
Only nodes which would represent words in the trie exist, making the structure
slightly smaller than a hash of the same data set.

The advantages of the trie over other data storage methods is that lookup times
are O(1) WRT the size of the index. For sparse data sets, it is probably not as
efficient as performing a binary search on a sorted list, and for small files,
it has a lot of overhead. The main advantage (at least from my perspective) is
that it provides a relatively cheap method for finding a list of words in a
large, dense data set which begin with a certain string.

WWW: http://search.cpan.org/dist/Tree-Trie/
Comment 1 commit-hook freebsd_committer 2015-03-08 02:30:30 UTC
A commit references this bug:

Author: vanilla
Date: Sun Mar  8 02:29:39 UTC 2015
New revision: 380723
URL: https://svnweb.freebsd.org/changeset/ports/380723

Log:
  Add p5-Tree-Trie 1.9, data structure optimized for prefix lookup.

  PR:		198100
  Submitted by:	gebhart@secnetix.de

Changes:
  head/devel/Makefile
  head/devel/p5-Tree-Trie/
  head/devel/p5-Tree-Trie/Makefile
  head/devel/p5-Tree-Trie/distinfo
  head/devel/p5-Tree-Trie/pkg-descr
  head/devel/p5-Tree-Trie/pkg-plist