## Index of all namespaces

# aho-corasick

A Clojure library designed to solve set matching (or multi-string matching) problem by applying the classic aho-corasick algorithm.

## Original Algorithm listing

The following algorithm listing is from the original paper “Efficient String Mathcing: An Aid to Bibliographic Search (1975)” by Alfred V. Aho and Margaret J. Corasick.

### Algorithm 1. Pattern matching machine.

**Input.** A text string x = a1a2…an where each ai is an input symbol and a pattern matching machine M with goto function g, failure function f, and output function output, as described above.

**Output.** Locations at which keywords occur in x.

**Method.** ```
begin
state := 0
for i := 1 until n do
begin
while g(state, ai) == fail do state := f(state)
state := g(state, ai)
if output(state) != empty then
begin
print i
print output(state)
end
end
end
```

### Algorithm 2. Construction of the goto function.

**Input.** Set of keywords K = {y1, y2, …, yk}.

**Output.** Goto function g and a partially computed output function output.

**Method.** We assume output(s) is empty when state s is first created, and g(s, a) == fail if a is undefined or if g(s, a) has not yet been defined. The procedure enter(y) inserts into the goto graph a path that spells out y. ``` begin newstate := 0 for i := 1 until k do enter(yi) for all a such that g(0, a) == fail do g(0, a) := 0 end

procedure enter(a1a2…am): begin state := 0; j := 1 while g(state, aj) != fail do begin state := g(state, aj) j := j + 1 end for p := j until m do begin newstate := newstate + 1 g(state, ap) := newstate state := newstate end output(state) := {a1a2…am} end ```

### Algorithm 3. Construction of the failure function.

**Input.** Goto function g and output function output from Algorithm 2.

**Output.** Failure function f and output function output.

**Method.** ```
begin
queue := empty
for each a such that g(0, a) != 0 do
begin
s := g(0, a)
queue := queue U {s}
f(s) := 0
end
while queue != empty do
begin
let r be the next state in queue
queue := queue - {r}
for each a such that g(r, a) != fail do
begin
s := g(r, a)
queue := queue U {s}
state := f(r)
while g(state, a) == fail do state := f(state)
f(s) := g(state, a)
output(s) := output(s) U output(f(s))
end
end
end
```

FIXME

## License

Copyright © 2016 FIXME

Distributed under the Eclipse Public License either version 1.0 or (at your option) any later version.