Skip to content
Multi-String Pattern Matching Algorithm Using TrieHashNode
Branch: master
Clone or download
Latest commit 2e8956b May 19, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
ds/trie Fixed golint issue with trie package and modified mspm accordingly May 18, 2018
search Fixed golint issue with trie package and modified mspm accordingly May 18, 2018
LICENSE Initial commit with project setup. May 17, 2018
README.md Update README.md May 19, 2018

README.md

Multi-String Pattern Matching algorithm.

Go Report Card GoDoc

This implementation is inspired from Aho-Corasick algorithm

Getting Started

modelA = mspm.NewModel("mspm_model_A")
patternsToSearch = strings.NewReader(words) // words is newline seperated list of words/keywords

// build mspm model with patterns
modelA.Build(patternsToSearch)

inputString := "input document where the above pattern is searched for."
document := strings.NewReader(inputString)
output, err := modelA.MultiTermMatch(document)

// output ~= [{matched_word: n_count}, ..]

Test Coverage

TrieNode vs TrieHashNode benchmark

$ cd github.com/BlackRabbitt/mspm/ds/trie
$ go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/BlackRabbitt/mspm/ds/trie
BenchmarkTrieNodeInsert-4             500000          2582 ns/op
BenchmarkTrieNodeSearch-4           10000000           205 ns/op
BenchmarkTrieHashNodeInsert-4        1000000          1491 ns/op
BenchmarkTrieHashNodeSearch-4       10000000           206 ns/op
PASS
ok      github.com/BlackRabbitt/mspm/ds/trie	8.795s

Resources

  1. Trie
  2. mspm - Multi-String Pattern Matching algorithm. Generally used for Information Retrieval.
  3. Aho-Corasick algorithm
You can’t perform that action at this time.