Date: Sat, 28 Feb 2015 16:46:05 +0000 From: bugzilla-noreply@freebsd.org To: freebsd-ports-bugs@FreeBSD.org Subject: [Bug 198100] New port: devel/p5-Tree-Trie (Data structure optimized for prefix lookup) Message-ID: <bug-198100-13@https.bugs.freebsd.org/bugzilla/>
next in thread | raw e-mail | index | archive | help
https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=198100 Bug ID: 198100 Summary: New port: devel/p5-Tree-Trie (Data structure optimized for prefix lookup) Product: Ports & Packages Version: Latest Hardware: Any OS: Any Status: New Severity: Affects Only Me Priority: --- Component: Individual Port(s) Assignee: freebsd-ports-bugs@FreeBSD.org Reporter: gebhart@secnetix.de Created attachment 153617 --> https://bugs.freebsd.org/bugzilla/attachment.cgi?id=153617&action=edit 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/ -- You are receiving this mail because: You are the assignee for the bug.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?bug-198100-13>