Skip to content
This repository has been archived by the owner on Jan 11, 2022. It is now read-only.
/ go-trie Public archive

A trie-tree string-matching in golang, fatster than trie 2 regex.

License

Notifications You must be signed in to change notification settings

ledyba/go-trie

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

19 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

go-trie

A trie tree implementation in golang.

It runs faster than trie to regex approach more than 100 times (vs golang's regex engine; Please see the benchmark below).

Performance

Please see rival directory to benchmarks in other languages.

 % make bench
 - php's trie2regex: 742.64 us/op (10000 times)
 - v8's trie2regex: 4.29 us/op (100000 times)
 - golang's trie2regex: 2438.09 us / op (1000 times)
 - go-trie: 24.28 us/op (x 100.40) (100000 times)

how to use?

package test

import (
  "testing"
  "github.com/ledyba/go-trie/matchers/trie"
)

func TestSlimReadme(t *testing.T) {
	tr := trie.New() // Animes.
	// kirara
	tr.Add("NewGame!")
	tr.Add("School Live!")
	tr.Add("Urara Meirocho")
	tr.Add("Anne Happy")
	tr.Add("Kiniro Mosaic")
	tr.Add("Hanayamata")
	tr.Add("Is the order a rabbit?")
	tr.Add("Is the order a rabbit??")
	tr.Add("The Demon Girl Next Door")
	tr.Add("Hidamari Sketch")
	tr.Add("Blend S")
	tr.Add("Dōjin Work")
	tr.Add("Magic of Stella")
	// semi-kirara
	tr.Add("Yuki Yuna Is a Hero")
	tr.Add("Non Non Biyori")
	tr.Pack()

	// Match method 
	if tr.Match("NewGame!") == false {
		t.Error("NewGame! is a first season of the series.")
	}
	if tr.Match("NewGame!!") == false {
		t.Error("NewGame!! is a second season of the series.")
	}
	if tr.Match("NewGame") == true {
		t.Error("Not NewGame. NewGame\"!\"")
	}
	if tr.Match("Dojin Work") == true {
		t.Error("Not Dojin Work. \"Dōjin Work\"")
	}

	// Contains method
	if tr.Contains("I would like to eat udon with Fuu Inubozaki, a hero in \"Yuki Yuna Is a Hero\".") == false {
		t.Error("What????? Why????")
	}
	if tr.Contains("Alas, Ikaruga is going...") == true {
		t.Error("Ikaruga is a game. Not an animation.")
	}
}

You can see other examples in the unit test file.

About

A trie-tree string-matching in golang, fatster than trie 2 regex.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published