前些时候碰到个问题：怎么把短信内容中的联系人找出来？正则表达式是很直接的想法，把所有联系人的姓名拼成一个正则表达式，然后对短信内容做匹配；另外之前听说过AhoCorasick算法，知道这个算法适合做多关键字查找，所以仔细看了一下这个算法，并给出了一个简单的Groovy实现。

关于AhoCorasick算法的介绍和实现很多，感觉还是Wikipedia上的介绍更容易理解一些，Aho–Corasick string matching algorithm?，后面的实现主要是基于Wikipedia上的介绍。

1. 接口

两个过程：构建和查找。

class AhoCorasick {
    AhoCorasick(words) {
        ...
    }

    def matches(text) {
        ...
    }
}

构建过程在构造函数里实现，传入一组关键词words，如果words不能构建有效的结果，抛IllegalArgumentException；查找功能由matches方法实现，输入要搜索的文本text，返回一个列表，列表中对象的结构如下：{start: 10,word: 'hello'}，如果没有匹配，列表为空。

2. 构建

构建过程可以分解为两个步骤：构建Trie，和给节点加额外的链接。

private root

    AhoCorasick(words) {
        buildTrie(words)
        buildLinks()
    }

2.1 构建Trie

以Wikipedia提供的例子，words = ['a','ab','bc','bca','c','caa']，构造的Trie树如下：

这个过程很直观，代码如下：

private buildTrie(words) {
        root = [:]
        words.findAll { it.size() > 0 }.each { addWord(it) }
		
        if (!root) {
            throw new IllegalArgumentException('Invalid words: ' + words)
        }
    }

    private addWord(word) {
        def node = root
        word.each { ch ->
            node[(ch)] = node[(ch)] ?: [:] 
            node = node[(ch)] 
        }
        node.accept = word
    }

出于简化的目的，一个node就是一个HashMap，这个实现里，node可能有4种类型的key：

• 单个字符：指向子节点
• accept：记录该节点匹配的字符串
• fail：fail链接
• dict：dict链接

2.2 添加链接

链接包含蓝色的"suffix"和绿色的"dictionary suffix"，这个链接建立过程是算法的难点。

蓝色的"suffix"链接也叫fail链接，如果节点n的fail链接指向节点f，那么f到root的字符串f->root，就是n到root的字符串n->root的最长后缀。在上面的Trie树上添加fail链接后的结果如下图：

除了根节点，所有的节点都有fail链接，仔细查看这张图，不难发现，f->root，都是n->root的最长后缀；另外，也可以看到，任何节点都可以通过fail链接最终到达root节点，即在节点与root间存在一个fail chain。

怎样通过代码来确定一个节点的fail链接呢？

• 对于深度为1的节点，很容易判断，fail连接都指向root。
• 深度超过1的节点，可以通过它的父节点的fail链接来确定。假如已经知道节点n的fail链接 ，n[ch] = child（即n通过字符ch指向child），那么在n到root形成的fail chain中查找第一个包含字符ch链接的节点ff，那么ff[ch]节点就是n[ch]（child）fail链接指向的节点，这样可以保证ff[ch]->root仍然是n[ch]->root的最长后缀；如果在fail chain中所有的节点都不包含字符ch链接，那么n[ch]的fail链接指向root。

下面的函数在node到root形成的fail chain中查找第一个包含ch链接的节点ff，如果存在返回ff[ch]，否则返回root。

private nextByFailLinks(node,ch) {
        def fail = node.fail
        while (fail) {
            if (fail[(ch)]) {
                return fail[(ch)]
            }
            fail = fail.fail
        }
        return root
    }

绿色的"dictionary suffix"，后面简称为dict，表示查找过程到达一个节点时，存在的成功匹配，比如这个例子里，走到节点ca时，已经可以匹配a了。这个例子加上dict链接后的图如下：
不难发现，dict链接很容易通过fail链接来确定，如果fail链接指向的节点是一个成功匹配，那么dict = fail，否则dict = fail.dict。

确定节点的fail和dict链接需要父节点的链接信息，所以添加链接的过程应该走一个广度优先的遍历，下面是添加链接的实现：

private buildLinks() {
        def nodes = [root] as Queue,node
        while (node = nodes.poll()) {
            node.findAll { it.key.size() == 1 }.each { ch,child ->
                nodes.offer(child)

                child.fail = nextByFailLinks(node,ch)
                child.dict = child.fail.accept ? child.fail : child.fail.dict
            }
        }
    }

3. 查找

搞明白了构建过程，查找过程就很容易理解了，根据输入的字符，选择下一个状态（节点），并根据状态获取可能匹配的所有结果。

def matches(text) {
        def results = [],current = root
        text.eachWithIndex { ch,index ->
            current = current[(ch)] ?: nextByFailLinks(current,ch)
            acceptCurrentMatched(results,current,index)
        }
        return results
    }

当前状态current，读取字符ch，如果current包含ch链接，那么下一个状态是current[ch]；如果不包含，使用前面定义的nextByFailLinks函数，在current到root间的fail chain中查找，这也是为什么把蓝色的"suffix"链接叫做fail链接的原因。

根据状态添加匹配的结果，有两种可能：当前状态是否有accpet属性，dict链上的所有节点。

private acceptCurrentMatched(results,index) {
        current.accept && results << makeResult(current,index) 

        def node = current
        while (node = node.dict) {
            results << makeResult(node,index)
        }
    }

    private makeResult(node,index) {
        def start = index - node.accept.size() + 1
        return [start : start,word : node.accept]
    }

4. 其他

这里的dict链接可以用其他方式来完成同样的功能，在添加完fail链接时，可以把fail chain中所有已匹配的词都追加到accpet属性中，这样在查找过程中，只根据当前节点的accpet属性来生成结果就可以了。

另外accept属性可以不记录word，而记录word的长度，这样会省一点内存。

上面的实现和测试代码，可查看http://git.oschina.net/mononite/aho-corasick。