aho-corasick-automaton

Stream Aho-Corasick automata

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 !== ) {
    console.log("matches at position", i, ":")
    for(var cur = state; cur.value !== ; 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")

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

Returns A new Aho-Corasick automata

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

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

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