ChunNote
0%

AC自动机

发表于 分类于

简介

AC 自动机是一种多模式字符串匹配算法，其能在 O(n) 的时间复杂度内完成对多个子字符串的查找，而且其时间复杂度只跟搜索串的长度有关，跟模式串的数量并无关联。是一种高效的字符串匹配算法。

算法过程

AC自动机算法，主要包括预处理过程和查找过程。

预处理

预处理过程主要是构建字典树，同时加入 fail 指针，用于在某个节点匹配失败时进行跳转，避免从根节点重新进行匹配，从而达到快速匹配多个子串的效果。其算法基本过程如下：

  • 根据输入的模式串，构建字典树。在构建字典树的过程中，如果从根节点到某个节点的路径完全匹配上模式串，则将这个模式串的长度加入节点的存储信息中（用于后续搜索匹配时能还原出匹配到的模式串）。
  • 使用广搜算法，依次构建每个节点的失败指针指向。

关于节点的失败指针，可以说是AC自动机算法中的一个难点，也是一个很重要的部分。由于失败指针的加入，在节点匹配失败时，不用重新从根节点出发进行查找，可以直接跳到失败指针指向的节点进行下一步查找，从而减少搜索路径，大大提高搜索效率。

失败指针

对于失败指针，其定义是在发生匹配失败时进行的跳转。假设节点 cur 的失败指针指向的节点为 fail，从根节点到 fail 节点的路径组成的字符串 suffix，从根节点到 cur 节点的路径组成的字符串 string，则必然满足：suffix 是 string 的最长后缀（如果字符串只有一个字符，则最长后缀为空）。

关于节点的失败指针的构建，其算法如下：

  • 根节点的的失败指针为空
  • 对于非根节点 current，获取父亲节点的失败指针指向的节点 temp
    • 如果 temp 为空，则将 current 节点的失败指针指向根节点。
    • 如果 temp 节点和 current 节点的父节点有相同的转移路径（即能够匹配某个相同的字符），则将 current 的失败指针指向 temp 对应的孩子节点上。
    • 如果 temp 节点没有与 current 节点父节点具有相同的转移路径，则继续获取 temp 节点的失败指针指向的节点，将其赋值给 temp，重复上述匹配过程。
  • 在构建节点的失败指针时，如果失败指针指向的节点存在匹配模式串的记录信息（记录了模式串的长度），则将这个信息加入到当前节点中。这个做法是为了方便后续根据搜索串查找相应的匹配串。

现在说明上述算法为什么有效。

假设当前节点是 current，当前节点的父节点是 father，父节点的失败指针指向的节点是 fatherFail。则根据失败指针的定义，可以知道，fatherFail 构成的字符串是 father构成的字符串的最长后缀。

  • 如果 fatherFail 存在一个跳转路径 fp与 father 的跳转路径（从 father 跳转到 current） cp 相同，则说明 fatherFail + fp 构成的字符串是 father + cp 构成的字符串（也是 current 构成的字符串）的最长后缀。即 current 的失败指针指向了 fp 的节点。如下所示

    automation-1

  • 如果上述路径不存在，则查找 fatherFail 的失败指针指向的节点，此时代表的是 fatherFail 路径的最长后缀，同样是 father 的后缀，也是 father 的次最长后缀，如下所示

    automation-2

    同样按照第一点进行匹配，如果仍然匹配不到，则继续第二点依次取出当前的失败指针指向的节点的失败指针指向的节点，逐渐缩小最长后缀的范围直到匹配上或为空（无匹配记录）。

例子

上述描述有点抽象，不好理解，现在举一个例子加以说明，辅助理解。

假设有模式串 he、she、hers、his、shy，则其字典树构建结果如下

automation-3

图中 4、8、9、10、11 五个节点与其他节点颜色不同，主要是想表示这五个节点组成的路径字符串是一个模式串，旁边标识的 wordLength 的数字表示的是模式串的长度。

接下来对每个节点构建失败指针，用虚线表示。 root 节点的失败指针为空，在图中不表示。

2 号节点，其父节点是 root，父节点的失败指针为空，所以 2 号节点的失败指针指向 root 节点

automation-4

3 号节点，其父节点是 root，父节点的失败指针为空，所以 3 号节点的失败指针指向 root 节点

automation-5

4 号节点，其父节点是 2 节点，2 节点的失败指针指向 root，root 没有 e 的跳转路径，所以继续查找父节点 2 的失败指针节点 root 的失败指针，由于其指向空，所以 4 节点的失败指针指向 root 节点

automation-6

5 号节点，其父节点是 2 节点，2 节点的失败指针指向 root，root 没有 i 的跳转路径，所以继续查找父节点 2 的失败指针节点 root 的失败指针，由于其指向空，所以 5 节点的失败指针指向 root 节点

automation-7

6 号节点，其父节点是 3 节点，3 节点的失败指针指向 root，root 节点有 h 的跳转路径到 2 号节点，所以 6 号节点的失败指针指向 2 号节点

automation-8

7 号节点，其父节点是 4 节点，4 节点的失败指针指向 root，root 没有 r 的跳转路径，所以继续查找父节点 4 的失败指针节点 root 的失败指针，由于其指向空，所以 7 节点的失败指针指向 root 节点

automation-9

8 号节点，其父节点是 5 节点，5 节点的失败指针指向 root，root 节点有 s 的跳转路径到 3 号节点，所以 8 号节点的失败指针指向 3 号节点

automation-10

9 号节点，其父节点是 6 节点，6 节点的失败指针指向 2 节点，2 节点有 e 的跳转路径到 4 号节点，所以 9 号节点的失败指针指向 4 号节点。同时，由于 4 号节点存在 wordLength （即 4 号节点组成的路径能够构成某部分模式串），所以将 4 号节点的 wordLength 信息加入到 9 号节点的 wordLength 中

automation-11

10 号节点，其父节点是 6 节点，6 节点 失败指针指向 2 节点，2 节点没有 y 的跳转路径，所以继续寻找 2 的失败指针节点，跳转到 root 节点，root 节点没有 y 的跳转路径，继续寻找 root 的失败指针节点，为空，所以 10 号节点的失败指针指向 root 节点

automation-12

11 号节点，其父节点是 7 节点，7 节点的失败指针指向 root，root 节点有 s 的跳转路径到 3 号节点，所以 11 号节点的失败指针指向 3 号节点

automation-13

至此，节点的失败指针构建完毕。同时也完成了AC自动机的预处理过程。

代码

节点信息

1
2
3
4
5
6
class AcNode
{
    AcNode[] children = new AcNode[128];
    AcNode failNode;
    private List<Integer> wordLengthList = new LinkedList<>();
}

构造字典树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void insert(String word)
{
    AcNode current = root;
    for (int i = 0; i < word.length(); i++)
    {
        AcNode[] children = current.children;
        if (children[word.charAt(i)] == null)
        {
            children[word.charAt(i)] = new AcNode();
        }
        current = children[word.charAt(i)];
    }

    current.wordLengthList.add(word.length());
}

构造失败指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private void buildFailPath()
{
    Queue<AcNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty())
    {
        AcNode current = queue.poll();
        AcNode[] children = current.children;
        for (int i = 0; i < children.length; i++)
        {
            if (children[i] == null)
            {
                continue;
            }

            AcNode temp = current.failNode;
            while (temp != null && temp.children[i] == null)
            {
                temp = temp.failNode;
            }

            if (temp == null)
            {
                children[i].failNode = root;
            }
            else
            {
                children[i].failNode = temp.children[i];
            }


            children[i].wordLengthList.addAll(children[i].failNode.wordLengthList);
            queue.offer(children[i]);
        }
    }
}

搜索查找

搜索过程，先按字典树的查找过程进行匹配，如果在某个节点匹配失败，则运用失败指针跳转到下一个节点继续进行匹配。当搜索到某个节点时，如果该节点存储了模式串的信息（模式串的长度），对进行处理（输出），否则不额外处理。

由于搜索过程中是遍历搜索串的每个字符，能获取到下标信息，根据当前下标和存储的长度就能截取出模式串，所以在预处理的过程中不是存储的模式串，而是存储长度。这样也能节省空间。

例子

假设对上述模式串构建的 AC 自动机对 ahishers 字符串进行搜索，其搜索过程如下，绿色节点表示当前搜索的节点

首先，匹配 a 字符，由于 root 没有 a 的跳转路径，同时其失败指针为空，所以当前节点仍然停留在 root 上

automation-14

搜索匹配 h 字符，由于 root 有 h 的跳转路径，所以当前节点移动到 2 号节点上。由于 2 号节点并没有存储模式串的信息，所以直接进入下一个字符的匹配

automation-15

搜索匹配 i 字符，由于 2 号节点有 i 的跳转路径，所以当前节点移动到 5 号节点上

automation-16

搜索匹配 s 字符，由于 5 号节点有 i 的跳转路径，所以当前节点移动到 8 号节点上。同时，由于 8 号节点存储了模式串的信息，所以在此处进行额外处理，输出模式串 his

automation-17

搜索匹配 h 字符，由于 8 号节点没有跳转路径 h，所以顺着 8 号节点的失败指针转移到节点 3 ，由于节点 3 有跳转路径 h，所以当前节点移动到 6 号节点上

automation-18

automation-19

搜索匹配 e 字符，由于 6 号节点有 e 的跳转路径，所以当前节点移动到 9 号节点上。同时，由于 9 号节点存储了模式串的信息，所以在此处进行额外处理，输出模式串 she、he

automation-20

搜索匹配 r 字符，由于 9 号节点没有跳转路径 r ，所以顺着 9 号节点的失败指针转移到 4 号节点。此处需要注意：虽然 4 号节点存储了模式串的信息，但是访问到 4 号节点并不是“正常”路径访问，是通过失败指针访问的。在构建失败指针的过程中，已经将 4 号节点的相关信息存储在 9 号节点上，因此通过失败指针跳转的，必然经过 9 号节点处理输出模式串，此处不用重复处理。由于 4 号节点有跳转路径 r，所以当前节点移动到 7 号节点上

automation-21

automation-22

搜索匹配 s 字符，由于 7 号节点有 s 跳转路径，所以当前节点移动到 11 号节点上。同时，由于 11 号节点存储了模式串信息，所以在此处进行额外处理，输出模式串 hers

automation-23

至此，搜索结束，总共找到输出四个模式串 his、she、he、hers

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
private void search(String word)
{
    AcNode current = root;
    for (int i = 0; i < word.length(); i++)
    {
        char ch = word.charAt(i);
        AcNode next = current.children[ch];
        if (next != null)
        {
            current = next;
            // 此处是要先判断当前节点是否存储了模式串的信息，如果存储了，才进行操作
            // 此处将这个判断放在函数中
            handleMatchWords(current, word, i);
        }
        else
        {
            next = current.failNode;
            while (next != null && next.children[ch] == null)
            {
                next = next.failNode;
            }

            if (next == null)
            {
                current = root;
            }
            else
            {
                current = next.children[ch];
                // 此处是要先判断当前节点是否存储了模式串的信息，如果存储了，才进行操作
            	// 此处将这个判断放在函数中
                handleMatchWords(current, word, i);
            }
        }
    }
}

代码

整个 AC 自动机的构建和搜索样例代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Automation
{
    class AcNode
    {
        AcNode[] children = new AcNode[128];
        AcNode failNode;
        private List<Integer> wordLengthList = new LinkedList<>();
    }

    private AcNode root = new AcNode();

    public void build(List<String> words)
    {
        for (String word : words)
        {
            insert(word);
        }

        buildFailPath();
    }

    private void insert(String word)
    {
        AcNode current = root;
        for (int i = 0; i < word.length(); i++)
        {
            AcNode[] children = current.children;
            if (children[word.charAt(i)] == null)
            {
                children[word.charAt(i)] = new AcNode();
            }
            current = children[word.charAt(i)];
        }

        current.wordLengthList.add(word.length());
    }

    private void buildFailPath()
    {
        Queue<AcNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty())
        {
            AcNode current = queue.poll();
            AcNode[] children = current.children;
            for (int i = 0; i < children.length; i++)
            {
                if (children[i] == null)
                {
                    continue;
                }

                AcNode temp = current.failNode;
                while (temp != null && temp.children[i] == null)
                {
                    temp = temp.failNode;
                }

                if (temp == null)
                {
                    children[i].failNode = root;
                }
                else
                {
                    children[i].failNode = temp.children[i];
                }


                children[i].wordLengthList.addAll(children[i].failNode.wordLengthList);
                queue.offer(children[i]);
            }
        }
    }

    private void search(String word)
    {
        AcNode current = root;
        for (int i = 0; i < word.length(); i++)
        {
            char ch = word.charAt(i);
            AcNode next = current.children[ch];
            if (next != null)
            {
                current = next;
                // 此处是要先判断当前节点是否存储了模式串的信息，如果存储了，才进行操作
            	// 此处将这个判断放在函数中
                handleMatchWords(current, word, i);
            }
            else
            {
                next = current.failNode;
                while (next != null && next.children[ch] == null)
                {
                    next = next.failNode;
                }

                if (next == null)
                {
                    current = root;
                }
                else
                {
                    current = next.children[ch];
                    // 此处是要先判断当前节点是否存储了模式串的信息，如果存储了，才进行操作
            		// 此处将这个判断放在函数中
                    handleMatchWords(current, word, i);
                }
            }
        }
    }

    private void handleMatchWords(AcNode node, String word, int currentPos)
    {
        for (Integer wordLen : node.wordLengthList)
        {
            int startIndex = currentPos - wordLen + 1;
            String matchWord = word.substring(startIndex, currentPos + 1);
            System.out.println(matchWord);
        }
    }

    public static void main(String[] args)
    {
        List<String> words = new ArrayList<String>() {{
           add("he");
           add("she");
           add("hers");
           add("his");
           add("shy");
        }};

        Automation automation = new Automation();
        automation.build(words);
        automation.search("ahishers");       // his、she、he、hers
        System.out.println("=================");
        automation.search("abcdefg");        // "nothing"
        System.out.println("=================");
        automation.search("ahiskhe");        // his、he
        System.out.println("=================");
        automation.search("ahiskshers");     // his、she、he、hers
        System.out.println("=================");
        automation.search("ahiskabc");       // his
        System.out.println("=================");
        automation.search("sher");           // she、he
        System.out.println("=================");
        automation.search("he");             // he
        System.out.println("=================");
        automation.search("ahishyers");      // his、shy
    }
}

参考资料

https://www.bilibili.com/video/BV1uJ411Y7Eg?p=4

https://www.bilibili.com/video/BV1d7411E7sP?from=search&seid=3361220436715890812