radix_tree

README

Radix Tree Search

Overview

This library implements a reverse pattern search algorithm using a Radix tree data structure. Unlike conventional pattern matching where a string is matched against a pattern, this reverse search identifies patterns that match a given input string.

Use Case Example

Consider a set of patterns:

abc
*cd
*bc
b*d
*

For an input string "abc", the search would yield:

abc
*bc
*

Applications and Implementation

Reverse pattern search is particularly useful for browser database lookups, such as Browscap. The library utilizes a Radix tree as a storage and backtracking to traverse the tree. Since the whole tree structure is stored in memory, it's possible to convert tree into a Directed Acyclic Word Graph (DAWG) which can significantly reduce memory usage.

Installation

go get github.com/eugeniypetrov/radix-tree

Usage

r := radix.NewRadix()
r.Add("abc")
r.Add("*cd")
r.Add("*bc")
r.Add("b*d")
r.Add("*")

for _, v := range r.Find("abc") {
    log.Println(v)
}

To convert into DAWG:

d := r.ToDAWG()
d.Find("abc")

Documentation

Index

• Constants
• type Node
  • func NewRadix() *Node
  • func (n *Node) Add(s string)
  • func (n *Node) Find(s string) []string
  • func (n *Node) Hash() uint64
  • func (n *Node) String() string
  • func (n *Node) ToDAWG() *Node

Constants

const Term rune = -1

Types

type Node

type Node struct {
	// contains filtered or unexported fields
}

func NewRadix

func NewRadix() *Node

func (*Node) Add

func (n *Node) Add(s string)

func (*Node) Find

func (n *Node) Find(s string) []string

func (*Node) Hash

func (n *Node) Hash() uint64

func (*Node) String

func (n *Node) String() string

func (*Node) ToDAWG

func (n *Node) ToDAWG() *Node

ToDAWG converts a radix tree into a DAWG by replacing equivalent subtrees with references