hat-trie - C++ implementation of a fast and memory efficient HAT-trie

  •        24

Trie implementation based on the "HAT-trie: A Cache-conscious Trie-based Data Structure for Strings." (Askitis Nikolas and Sinha Ranjan, 2007) paper. For now, only the pure HAT-trie has been implemented, the hybrid version may arrive later. Details regarding the HAT-trie data structure can be found here. The library provides an efficient and compact way to store a set or a map of strings by compressing the common prefixes. It also allows to search for keys that match a prefix. Note though that the default parameters of the structure are geared toward optimizing exact searches, if you do a lot of prefix searches you may want to reduce the burst threshold through the burst_threshold method.

https://github.com/Tessil/hat-trie

Tags
Implementation
License
Platform

   




Related Projects

gse - Go efficient text segmentation; support english, chinese, japanese and other. Go 语言高性能分词

  •    Go

Go efficient text segmentation; support english, chinese, japanese and other. Dictionary with double array trie (Double-Array Trie) to achieve, Sender algorithm is the shortest path based on word frequency plus dynamic programming.

marisa-trie

  •    C++

Static memory-efficient Trie-like structures for Python (2.x and 3.x). Uses marisa-trie C++ library.

algorithms_and_data_structures - 180+ Algorithm & Data Structure Problems using C++

  •    C++

Note: Some of the code here is old and was written when I was learning C++. It might be possible that code is not safe or making wrong assumptions. Please use with caution. Pull requests are always welcome. Include contains single header implementation of data structures and some algorithms.

Capsule - The Capsule Hash Trie Collections Library

  •    Java

Capsule aims to become a full-fledged (immutable) collections library for Java 8+ that is solely built around persistent tries. The library is designed for standalone use and for being embedded in domain-specific languages. Capsule still has to undergo some incubation before it can ship as a well-rounded collection library. Nevertheless, the code is stable and performance is solid.


frugally-deep - Header-only library for using Keras models in C++.

  •    C++

Would you like to build/train a model using Keras/Python? And would you like run the prediction (forward pass) on your model in C++ without linking your application against TensorFlow? Then frugally-deep is exactly for you. Layer types typically used in image recognition/generation are supported, making many popular model architectures possible (see Performance section).

ForestDB - A Fast Key-Value Storage Engine Based on Hierarchical B+-Tree Trie

  •    C++

ForestDB is a key-value storage engine developed by Couchbase Caching and Storage Team, and its main index structure is built from Hierarchical B+-Tree based Trie, called HB+-Trie. ForestDB paper has been published in IEEE Transactions on Computers.

FunctionalPlus - Functional Programming Library for C++. Write concise and readable C++ code.

  •    C++

helps you write concise and readable C++ code. Great code should mostly be self-documenting, but while using C++ in reality you can find yourself dealing with low-level stuff like iterators or hand-written loops that distract from the actual essence of your code.

trie - A super fast, efficiently stored Trie for Ruby. Uses libdatrie.

  •    C

A super fast, efficiently stored Trie for Ruby. Uses libdatrie.

php-ext-trie-filter - php extension for spam word filter based on Double-Array Trie tree, it can detect if a spam word exists in a text message

  •    C

php extension for spam word filter based on Double-Array Trie tree, it can detect if a spam word exists in a text message. PHP 5.2 or later.

nanoflann - nanoflann: a C++11 header-only library for Nearest Neighbor (NN) search with KD-trees

  •    C++

nanoflann is a C++11 header-only library for building KD-Trees of datasets with different topologies: R2, R3 (point clouds), SO(2) and SO(3) (2D and 3D rotation groups). No support for approximate NN is provided. nanoflann does not require compiling or installing. You just need to #include <nanoflann.hpp> in your code. This library is a fork of the flann library by Marius Muja and David G. Lowe, and born as a child project of MRPT. Following the original license terms, nanoflann is distributed under the BSD license. Please, for bugs use the issues button or fork and open a pull request.

mux - A high performance and powerful trie based url path router for Go.

  •    Go

A high performance and powerful trie based url path router for Go. This router supports fixed and regex rules in routing pattern, and matches request method. It's optimized by trie structure for faster matching and large scale rules.

wayfarer - :eyeglasses: composable trie based router

  •    Javascript

Composable trie based router. It's faster than traditional, linear, regular expression-matching routers, although insignficantly, and scales with the number of routes. If you're looking for a client-side router check out sheet-router. If you're looking for a server router check out server-router.

doctest - The fastest feature-rich C++11 single-header testing framework for unit tests and TDD

  •    C++

doctest is a new C++ testing framework but is by far the fastest both in compile times (by orders of magnitude) and runtime compared to other feature-rich alternatives. It brings the ability of compiled languages such as D / Rust / Nim to have tests written directly in the production code by providing a fast, transparent and flexible test runner with a clean interface. The framework is and will stay free but needs your support to sustain its development. There are lots of new features and maintenance to do. If you work for a company using doctest or have the means to do so, please consider financial support. Monthly donations via Patreon and one-offs via PayPal.

C-Plus-Plus - All Algorithms implemented in C++

  •    C++

This repository contains some useful algorithms and data structures. How you can contribute? See this small guide.

Trie for C#

  •    

Implementing the Trie structer in C#/.Net

Fit - C++ function utility library

  •    C++

Fit is a header-only C++11/C++14 library that provides utilities for functions and function objects, which can solve many problems with much simpler constructs than whats traditionally been done with metaprogramming. This requires a C++11 compiler. There are no third-party dependencies. This has been tested on clang 3.5-3.8, gcc 4.6-6.2, and Visual Studio 2015. Gcc 5.1 is not supported at all, however, gcc 5.4 is supported.

hof - Higher-order functions for c++

  •    C++

HigherOrderFunctions is a header-only C++11/C++14 library that provides utilities for functions and function objects, which can solve many problems with much simpler constructs than whats traditionally been done with metaprogramming. This requires a C++11 compiler. There are no third-party dependencies. This has been tested on clang 3.5-3.8, gcc 4.6-7, and Visual Studio 2015 and 2017.





We have large collection of open source products. Follow the tags from Tag Cloud >>


Open source products are scattered around the web. Please provide information about the open source projects you own / you use. Add Projects.