Skip to content
A bit-alphabet based, space-optimized trie for string storage.
Java
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src/main/java/io/github/saligrama/patricia
.gitignore
LICENSE
README.md
TODO.md
pom.xml

README.md

patricia

Patricia is a bit-alphabet based, space-optimized trie for string storage.

Patricia Trees (also known as Crit-Bit Trees and Compressed Binary Trees) are extremely space-efficient compared to standard tries due to their compression of nodes with only one child. Therefore, no unnecessary nodes and edges are stored, cutting down on both storage and steps needed to traverse the trie.

This trie operates on a bit alphabet and can store any type of ASCII text. It operates similarly to a Radix Tree, with radix r=2.

Usage

Dependency

Add the library as a dependency to your project using Maven.

<dependency>
  <groupId>io.github.saligrama</groupId>
  <artifactId>patricia</artifactId>
  <version>1.0</version>
</dependency>

Example

import io.github.saligrama.patricia.PatriciaTree;

public class PatriciaExample {
    public static void main(String[] args) {
        PatriciaTree tree = new PatriciaTree();
        System.out.println(tree.add("Foo bar baz quux")); // should print true
        System.out.println(tree.contains("Foo")); // should print false
        System.out.println(tree.contains("Foo bar baz quux")); // should print true
        System.out.println(tree.remove("Foo bar baz quux")); // should print true
    }
}
You can’t perform that action at this time.