Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Generates an Aho-Corasick automata for matching multiple patterns in a stream
JavaScript
Branch: master

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
test
.gitignore
LICENSE
README.md
aho-corasick.js
package.json

README.md

aho-corasick-automaton

A streaming Aho-Corasick automata for matching strings. This module is a low level interface, but can be used to construct more complex algorithms.

Example

var createTrie = require("array-trie")
var createAC = require("aho-corasick-automaton")

var trie = createTrie()

//First build the trie data structure
trie.set([1,2,3], 1)
trie.set([2,3,4], 2)
trie.set([6,7,8], 3)
trie.set([1,2], 4)
trie.set([2,3], 5)

//Next construct the automata and use it to 
var automata = createAC(trie)

//Now run it on some data
var data = [1,2,3,4,5,6,7,8,9]
for(var state=automata, i=0; i<data.length; ) {

  //Process next symbol
  state=state.push(data[i++])

  //Print out all matches at position i
  if(state.value !== undefined) {
    console.log("matches at position", i, ":")
    for(var cur = state; cur.value !== undefined; cur = cur.next) {
      console.log(cur.value)  
    }
  }
}

Here is some example output from the above program:

matches at position 2 :
4
matches at position 3 :
1
5
matches at position 4 :
2
matches at position 8 :
3

Install

npm install aho-corasick-automata

API

var createAC = require("aho-corasick-automata")

Constructor

var root = createAC(trie)

Creates an Aho-Corasick automata from the trie encoded as an array-trie

Returns A new Aho-Corasick automata

Methods

automata.push(symbol)

Returns the next state of the automata after processing symbol

  • symbol is the next character in the stream to process

Returns The next state of the automata

automata.value

A value representing the terminal of the automata. undefined if there is no trie entry at this point

automata.next

A pointer to the next entry in the linked list of values at this automata state. If the value is undefined, then this is the last node in this list.

Credits

(c) 2013 Mikola Lysenko. MIT License

Something went wrong with that request. Please try again.