# 4-1 入侵检测系统2026(1).pptx：逐页可提取文字

> [原课件](../../../4-1 入侵检测系统2026(1).pptx)；共83页。以下是文字提取，**未经逐句纠错**；图中文字、截图代码、公式对象及动画关系可能无法完整提取。阅读主题笔记后，可按页码回原文件查看。

## 第 1 页

````text
计算机安全
@
入侵检测系统
````

### 备注区文字

````text
大家好。本节课我们介绍对称密钥加密算法。
````

## 第 2 页

````text
内容提要
入侵检测系统概念
入侵检测系统误报率与贝叶斯定理
入侵检测系统实例
Snort
入侵检测系统检测算法
模式匹配算法
多模式匹配算法
现代方法
2
````

## 第 3 页

````text
入侵检测系统
入侵（Intrusion）定义为未经授权的计算机使用者以及不正当使用(misuse)计算机的合法用户(内部威胁)，危害或试图危害资源的完整性、保密性、可用性的行为
入侵检测（Intrusion Detection，ID）通过监测计算机系统的某些信息，加以分析，检测入侵行为，并作出反应
入侵检测系统（Intrusion Detection System，IDS）是实现入侵检测功能的硬件与软件。入侵检测基于一个观察，即：许多入侵行为与正常行为有显著的不同，因而是可以检测的


预防
Prevent

检测
Detect

恢复
Restore

反应
Response

Protect
````

### 备注区文字

````text
入侵属于对计算机系统的不正当使用。
````

## 第 4 页

````text
入侵检测系统结构 
事件产生器（Event generater， E-box）收集入侵检测事件,并提供给IDS其他部件处理。事件可以是网络活动也可是系统调用序列等系统信息。
事件分析器（Analysis engine, A-box）对输入的事件进行分析并检测入侵。
事件数据库（Event database, D-box）存储和管理E-boxes 和 A-boxes 产生大量数据，用于IDS的训练和证据保存。
事件响应器（Response unit, C-box）对入侵做出响应，包括向管理员发出警告，切断入侵连接，根除入侵者留下的后门以及数据恢复等。					
、
````

## 第 5 页

````text
入侵检测系统分类
检测方法
误用检测(misuse detection)
异常检测(anomaly detection)
混合检测
数据源
来自主机，系统调用序列，存储系统的活动记录，系统日志等
来自网络，网络包
````

## 第 6 页

````text
入侵检测系统检测方法
误用检测
也称为基于特征的检测，
建立已知攻击的知识库
判别当前行为是否符合已知的攻击模式
机制：状态模型、专家系统、正则表达式匹配
异常检测
也称为基于行为的检测
建立用户的正常使用模式知识库
标识出不符合正常模式的行为
机制：统计、机器学习方法
````

## 第 7 页

````text
入侵检测系统的评价
处理高速网络流量的能力
自身抗攻击的能力
误报率和漏报率
协同事件的能力
检测新攻击的能力
````

## 第 8 页

````text
误报率-混淆矩阵





正常
攻击、
不可判定
攻击
报告攻击
正常
报告正常
误报率：误报的数量占所有正常事件的比例
````

## 第 9 页

````text
一个思想实验
一个精确的异常检测系统。检测的准确率为99%。
恶意事件的出现率为1/10000。
问题：当系统报告一个攻击时（A)，正确的概率（是攻击事件T）是多少？
估算：检测的准确率大于多少时，当系统报告一个攻击时（A)，正确的概率接近50%。
2026/11/3
9
````

## 第 10 页

````text
Bayes定律
P(B|A)=P(A|B)P(B)/P(A)
P(A)：事件A的概率
条件概率
P(A|B):在给定事件B发生时发生事件A的概率
P(A|B)=|A∩B|/|B|

2026/11/3
10
      
    A
                    
                 B
A∩B
````

## 第 11 页

````text
计算P(T|A)
攻击的概率
P(T)=1/10000
事件被报警的概率P(A)未知
P(A|T)=99%,
P(A)=P(A|T)P(T)+P(A|!T)P(!T)
=0.99*0.0001+0.01*0.9999=0.10098
根据Bayesian定理
P(T|A)= P(A|T)P(T)/P(A)=0.00098

2026/11/3
11
````

## 第 12 页

````text
IDS误报率




现实中，攻击行为占比很少。导致正确率很高的检测器可能有较高的误报率。
例如设检测器检测正确率为99%，攻击占全部事件的1%，则：
报警的准确度为1%
99%为误报
IDS的核心问题：降低误报率！
````

## 第 13 页

````text
网络入侵检测系统Snort
著名开源NIDS，采用误用检测，包含：网络包的解析器、检测引擎、日志和报警子系统
利用libpcap库作为捕获数据包的工具
特点
设计原则：简单、灵活、高性能
协议分析和模式匹配、正则表达式匹配
特征描述语言：可描述攻击行为
插件子系统：实现系统功能扩展
````

## 第 14 页

````text
网络数据包解析
按照网络协议栈的分层解析包
按照协议层次依次处理各层包头
每一层协议栈都对应一个处理函数
从链路层，到传输层，直到应用层
支持链路层和TCP/IP协议
以太网、令牌网、FDDI
````

## 第 15 页

````text
Snort的规则 pcre
alert tcp any any -> 192.168.1.0/24 111 (content:"|00 01 86 a5|"; msg: "mountd access";)

规则头

规则选项
Snort的规则：
针对已经发现的攻击，编写规则
响应方式(alert)，协议(tcp)，以及IP地址和端口号，
content域指定了在包数据中搜索的内容模式
````

## 第 16 页

````text
规则选项
content 和 pcre
content: 用于匹配固定字符串，适合匹配简单的特征。
pcre: 用于匹配复杂的模式，支持正则表达式，适合匹配灵活多变的攻击 payload。
结合使用: 将 content 和 pcre 结合使用，可以提高检测的准确性。例如，使用 content 匹配关键字，使用 pcre 匹配变量部分。
其他选项
nocase: 忽略大小写。
depth: 指定搜索的最大深度。
offset: 指定搜索的起始位置。
distance: 指定多个匹配内容之间的距离。
fast_pattern: 使用快速模式匹配。
http_uri: 匹配 HTTP URI 部分。
session: 记录指定会话的应用层信息。
规则与性能
先处理匹配几率低的规则选项（如内容匹配），排除后续操作

16
````

## 第 17 页

````text
Snort规则实例
alert tcp $EXTERNAL_NET any -> $HOME_NET any (msg:"SHELLCODE x86 NOOP"; flow:to_server,established; content:"|90 90 90 90 90 90 90 90|"; content:"|90 90 90 90 90 90 90 90|"; content:"|90 90 90 90|"; pcre:"/\\x90{10,}/"; metadata:service http; classtype:shellcode-detect; sid:1390; rev:10;)
alert tcp $EXTERNAL_NET any -> $HTTP_SERVERS $HTTP_PORTS (msg:"WEB-MISC SQL injection attempt"; flow:to_server,established; content:"union"; nocase; http_client_body; content:"select"; nocase; http_client_body; pcre:"/union(\s)+select/i"; content:"from"; nocase; http_client_body; content:"where"; nocase; http_client_body; metadata:service http; classtype:web-application-attack; sid:1000001; rev:1;)

17
````

## 第 18 页

````text
Snort规则数据结构
在Snort的检测引擎中规则被解析为决策树结构
````

## 第 19 页

````text
2026/11/3
19
针对IDS的拒绝服务类攻击
超载攻击 当网络流量超过IDS的处理能力时，IDS的处理能力将急剧下降甚至完全瘫痪。攻击者通过某些手段使网络流量达到饱和，迫使IDS大量丢包。这种攻击还可针对目标IDS系统采用的检测算法进行算法攻击。
资源耗尽攻击 通过发送大量残缺TCP数据段以及IP分片耗尽IDS的存储资源，使IDS不能正常工作。
````

## 第 20 页

````text
加密流量处理
SSL/TLS解密（中间人方式）
元数据分析（Metadata Analysis）
分析HTTPS流量的元数据（例如，SNI、流量模式、连接频率等）
基于行为的异常检测（Anomaly-Based Detection）
对正常流量模式建模，来识别与正常行为偏差较大的活动
恶意软件、数据泄露
EDR（Endpoint Detection and Response，端点检测和响应）
EDR部署在客户端设备上，可以直接查看未加密的流量和活动
20
````

## 第 21 页

````text
2026/11/3
21
IDS性能问题
在高速网络上工作
10Gbps以太网、G比特光纤网 …
DPI处理能力显著下降，发生丢包、漏报
更复杂的攻击模式集合
模式数量巨大,
Snort的模式数量接近10,000
攻击模式的描述手段：从字符串到正则表达式
空间占用和处理速度的两难问题
算法复杂攻击
使DPI算法进入最坏情况，造成拒绝服务。
目前除了通过修改算法还没有其他有效的方法。
````

## 第 22 页

````text
2026/11/3
22
IDS性能问题
DPI = 深度网络数据包检测 
网络入侵检测系统（NIDS）、防火墙系统的核心功能
DPI深入到数据包的载荷处理
高层协议分析、攻击特征码匹配
协议分析。协议分析可以显著地缩小检测模式范围，从而减少内容检查，提高了入侵检测的效率。
内容检查。这是目前大多数网络入侵检测系统最重要的检测手段，内容模式取自攻击数据包的字符串特征。一般在协议分析之后对包内容进行特征串匹配，但相反的顺序可能提高检测效率
内容检查占全部处理时间的1/3
````

## 第 23 页

````text
2026/11/3
23
DPI vs 正则表达式匹配
DPI的中心问题：高效多正则表达式匹配
识别多表达式的DFA
高速度，对输入扫描一次
状态大爆炸
两个DFA的合并，状态数可能为二者之积
88个snort规则占用15G的内存空间
多个有限状态机
空间很小
速度差，需硬件支持
````

## 第 24 页

````text
提高IDS的性能 
提高单机检测性能
采用高效检测算法
多模式匹配/多正则表达式匹配
采用高性能硬件
FPGA、GPU、多核处理器
多机并行 
网络流量的分割
处理任务的分割
````

## 第 25 页

````text
IDS中使用的数据结构&算法
(组合)模式匹配算法
单模式匹配 kmp bm Sunday…
多模式匹配 AC WM… 
正则表达式处理、非精确模式匹配
数据结构：AC自动机（TRIE）、后缀树、后缀自动机、后缀数组、紧凑数据结构
应用领域
病毒扫描、入侵检测、搜索引擎、大数据处理
````

## 第 26 页

````text
模式匹配算法
模式匹配算法
Brute Force算法
Knuth-Morris-Pratt (KMP) 算法
Aho-Corasick多模式匹配算法
Boyer-Moore算法
现代技术
后缀树与后缀自动机
基于因子识别的算法
Bit并行算法与非标准模式匹配
Snort IDS中的匹配算法应用
````

## 第 27 页

````text
Notions
字母表 ∑={1,2,…,σ}
String
t = t[1]t[2] ・・・t[n] on ∑
ε：空串
Substring(factor) 子串、因子
t[i.. j] = t[i] t[i + 1] ・・・t[j]
Suffix: t[i.. n] 或 t[i..] 后缀
Prefix: t[1.. j] 或 t[.. j] 前缀
Concatenation: uv
````

## 第 28 页

````text
蛮力算法Brute Force
模式P 长度为m
文本T 长度为n
P在T的位置x处 出现：
T = bacbabababacbb
        P = ababa                       x=4
                   ababa                   x=6
找到P在T中的出现的最直接的方法:
在T的所有位置上检查P的出现
运行时间: 最坏情况 O(nm)
````

## 第 29 页

````text
Brute Force
对一个位置的匹配中已经获得了对于文本的”知识”
例如：

P能出现在x+1, x+2么？
````

## 第 30 页

````text
Brute Force
对一个位置的匹配中已经获得了对于文本的”知识”
例如：

P能出现在x+1, x+2, x+3么？
````

## 第 31 页

````text
观察
假设 P 在T[x…] 处匹配了 k 个字符
P[0..k-1] == T[x..x+k-1],
对于 0<r<k,
如果 T[x+r…x+k-1] 不是 P的前缀,
则 P 不能出现在 x + r 处
````

## 第 32 页

````text
略过位置
当 T[x..] 匹配了P的k个字符,
P[0..k-1] == T[x..x+k-1]
我们可在最左 x+r 处重新匹配
如果T[x+r..x+k-1] 是P的前缀
略过了 r 个位置
````

## 第 33 页

````text
在此例中：
下一个匹配开始于x+3处
````

## 第 34 页

````text
在此例中：
下一个匹配开始于x+3处
````

## 第 35 页

````text
算 可略过的位置数
已匹配的前缀P[0..k-1]，
P[0..k-1]的后缀中最长的前缀为P[r..k-1]
则略过位置数为r
K=3, r=3
K=5, r=3
````

## 第 36 页

````text
模式匹配自动机
字母表 ∑
状态 i 代表前缀p[1,i]。
边
前向边,如果sa是P的前缀,则有边(s, a, sa), 记为 follow(s, a)=sa
后向边,如果sa不是P的前缀,则有边(s, a, s’）, s’是sa后缀中最长的前缀
初始状态0，终止状态|s|
p=ababba 的部分模式匹配自动机，只有前向边
````

## 第 37 页

````text
模式匹配自动机
p=ababba 的(full)模式匹配自动机
goto(i,a)：串 p[1,i]a 后缀中最长的前缀
````

## 第 38 页

````text
fail函数
fail(s, i)  
前缀 p[1, i] 的后缀中最长的前缀

引入状态⊥ (对应长度为-1的串)
follow(⊥, 任意字符)=p0
fail(p0)= p-1=⊥
````

## 第 39 页

````text
通过fail计算goto函数
goto(4,a)=3
````

## 第 40 页

````text
通过fail计算goto函数
goto(5,b)=0
问题：自己动手计算goto(4,c)
````

## 第 41 页

````text
Morris-Pratt (MP)算法
没有Kunth优化的算法
````

## 第 42 页

````text
MP算法
O(m+n) 第一个线性算法！
MP算法对应的有限状态自动机. 模式p, |p|=m
状态集合：模式前缀集合, p为终止状态
follow Function, follow(s, a)
如果sa是s的前缀，则follow(s, a)=sa
否则follow(s, a)未定义
failure Function，后缀链接
fail(s)：s的后缀(不包含s)中最长P的前缀
引入状态⊥ (对应长度为-1的串)
follow(⊥, 任意字符)=p0
fail(p0)= p-1=⊥
````

## 第 43 页

````text
MP算法
goto(s,a) 
{
    while(follow(s,a)==未定义)    
        s=fail(s);
    return  follow(s,a);
}

Match(T)
{
    s= p0;
    for( i=1 to |T|){
        if( s 是终止状态 )
           return 匹配!;
        else  
            s=goto(s,T[i]);
    }
}
````

## 第 44 页

````text
fail函数的构造
fail(s)的定义：
s的后缀(不包含s)中最长P的前缀

分层 递归
fail(p0) = ⊥
fail(pi) =？
看fail(pi-1)有没有字母为P[i]的边
如果有，则fail(pi) 是
    此边指向的状态
如果没有，则沿着失败链向后找…

直到找到P[i]边，这条边指向的状态就是fail(pi) 

Compute_fail()
{
    s = fail(p0) = ⊥;
    for( i =1 to |P| ){
        s = goto(s, P[i]) ;
        fail(pi) = s ;
    }
}

第i次循环中 s=fail(pi-1)
````

## 第 45 页

````text
时间复杂（分摊分析）
对文本扫描一遍，无回头扫描
O(n)
调用了多少次fail函数？
从自动机看
向左的移动距离 >= 向左移动的距离=调用fail的次数
向右的移动距离= 对文本扫描的距离=n
调用fail的次数=O(n)
fail构造复杂度
向左的移动距离>= 向左移动的距离=调用fail的次数
向右的移动距离= 对模式扫描的距离=m
O(m)
O(m+n)
````

## 第 46 页

````text
Knuth-Morris-Pratt (KMP) 算法
KMP算法与MP算法的区别
````

## 第 47 页

````text
多模式匹配问题
在文本 T 中找到模式集合中模式的出现
模式集合： P 
Aho and Corasick，1975
基于有限状态自动机
AC自动机
````

## 第 48 页

````text
Aho-Corasick多模式匹配算法
AC自动机算法是MP算法的多模式扩展

AC自动机包括
Follow Function
failure Function
AC自动机goto函数的实现是用二者的结合
````

## 第 49 页

````text
Aho Corasick 自动机 
follow function: a trie of the patterns
failure function: 对于每个前缀, 其后缀中最长的模式前缀对应的trie节点
MP算法的fail函数的多模式推广
output function: 报告每个前缀的后缀中匹配的模式
````

## 第 50 页

````text
Trie
字符串集合的Trie结构是一颗树，对应于AC自动机的follow函数
模式的每个前缀对应一个状态
s和sa是模式的前缀，则有边(s,a,sa)
前缀压缩（合并）
````

## 第 51 页

````text
Aho Corasick 自动机–trie

h
i
he
ir
is
her
iri
iris
P = {her, iris, he, is}
模式的trie对应着AC自动机的
follow 函数
每个模式前缀对应一个状态
trie的边上的字母是边目标状态的最后一个字母
````

## 第 52 页

````text
AC自动机 - failure link

h
i
he
ir
is
her
iri
iris
P = {her, iris, he, is}
缺省失败链接指向根
s的失败链接指向s的后缀中最长的模式前缀
从状态s起始的失败链接最终到达根，构成了s的失败链
````

## 第 53 页

````text
Aho Corasick 自动机- output

h
i
he
ir
is
her
iri
iris
P = {her, iris, he, is}
如果当前状态的失败链中有状态有模式标志，则要加入匹配标志
对应着模式的状态加上模式标志位
匹配中若当前状态有匹配标志，则需要沿着失败链报告所有模式的匹配
````

## 第 54 页

````text
follow函数的实现方法
跳转表 O(1), O(|P||Σ|log|P|)
数组+二分查找 O(log|Σ|), O(|P|log|P|)
平衡二叉树O(log|Σ|), O(|P|log|P|)
紧凑数据结构O(1), O(|P|(|Σ|+log|P|))

集合数据结构
````

## 第 55 页

````text
Aho Corasick – 分析
AC自动机构造算法时间复杂为 O(|P|)
|P|模式集合中模式的长度之和
模式匹配搜索时间复杂 O(n + occ)
occ为模式出现次数
... 在固定字母表上!
对于整数字母表, Σ=O(nc), 用平衡树等结构
````

### 备注区文字

````text
text length + appearances   O(m+k)
Branching method determines the complexity of the query:




However we can do better than this, like s.t. that are now built in linear time! Indeed our algorithm does better.
````

## 第 56 页

````text
AC算法的模式匹配搜索时间复杂度中为何包含occ？

思考问题
````

## 第 57 页

````text
状态转换函数
引入状态⊥，状态转换简化为：
goto(s,a) 
{
    while(follow(s,a)==未定义)    
        s=fail(s);
    return  follow(s,a);
}
搜索时间复杂 O(n + occ)
````

## 第 58 页

````text
failure链接的构造
按照节点的深度分层
按层由浅到深递增填写fail链接
时间复杂O(|P|)
````

## 第 59 页

````text
模式匹配自动机
模式匹配自动机
取消失败函数
失败链接  边
（s， a， goto(s,a) ）
全部字母都对应跳转边
比AC自动机需要更多的空间
````

## 第 60 页

````text
思考

AC算法是MP算法的多模式扩展，如何将KMP扩展为多模式？
````

## 第 61 页

````text
小结
蛮力算法
KMP模式匹配算法
AC自动机多模式匹配算法
重点和难点
失败链接
均摊分析
Knuth优化
61
````

## 第 62 页

````text
作业
编程实现蛮力算法，KMP算法。比较二者性能。输入包括随机串，模式重复串。考察二者在不同输入的性能差异。
编程实现AC自动机算法，包括AC自动机的构造、匹配算法实现。优化follow函数的实现。分析fail函数的特征，优化fail函数实现。
要求：
给出程序设计描述，结构描述。
给出程序测试，包括正确性测试和性能测试。设计测试实例，展示测试结果。
62
````

## 第 63 页

````text
Boyer-Moore (BM) algorithm
对模式 P 中的字符从右向左匹配：后缀识别
可不用扫描全部输入字符，平均匹配时间c·n, 常量 c <1 (随机或真实文本), 但最坏情况是O(n·m).
可以将BM算法的最坏情况改进到O(n)，记录文本后缀中最长的模式后缀。
````

## 第 64 页

````text
Good-suffix shift
````

## 第 65 页

````text
Good Suffix位移
输入字符在模式x的位置z处失配
当前输入的后缀匹配了从z+1开始的x后缀u
情况1：找到u在z+1之前的最后一次出现位置z’，且x[z’]≠x[z]。重启匹配过程。新匹配窗口的结束向右移动 z - z’ 个字符。
情况2：u在z+1之前没有出现，此时确定u的后缀中最长x的前缀，窗口向右移动。
````

## 第 66 页

````text
Bad-character shift
````

## 第 67 页

````text
Bad-character shift
模式中不包含b
````

## 第 68 页

````text
扩展的Bad-character shift
如果失配字母是x的最后一个字母 b
Bad-character shift 为 0
优化后位移由b的倒数第2次出现决定
一个优化：b 在当前失配位置之前的最后一次出现，窗口位移由这个位置决定
保证了bad-character shift总会向右移动匹配窗口
````

## 第 69 页

````text
BM实例
             7 6 54 3 2 10 
模式x = GCAGAGAG
计算bad char: 输入字符b失配，b在反向第一次出现的反偏移
计算Good suffix：窗口右移长度
bmGS[i]:第i+1后缀匹配，但i处字母失配时，窗口向右移位的距离



特殊情况
bmGS有m个元素
                                            bmGS[-1]=全匹配移位
相当于左结束符不匹配

x的最后一个字母G
bmGS[G] = G的第二次出现
G作为失配输入，则x的匹配数>1，若使用原始Bc定义，导致窗口像左移
````

## 第 70 页

````text
计算Good suffix表
X代表失配
 ???????????X?
GCAGAGAG

   ????????XG?
GCAGAGAG

   ??????XAG?
GCAGAGAG
匹配窗口右移
?????????X???
  GCAGAGAG

????????XG???
                  GCAGAGAG

 ??????XAG???
          GCAGAGAG
````

## 第 71 页

````text
BM匹配实例
````

## 第 72 页

````text
KMP算法与BM算法的比较
KMP算法的实际性能不好，一般实际中不用
BM速度快，但最快的BM类算法不是完整BM算法而是简化的版本
复杂的算法反而比简单的算法实际性能差
````

## 第 73 页

````text
思考题
设计能够识别串s所有子串的数据结构与算法
输入p，能够在O(|p|)时间内判定p是否是s的子串
尽力压缩空间，试试能否达到O(|s|) word
设p=ababb，给出此数据结构实例
````

## 第 74 页

````text
Bit并行算法
非确定性自动机NFA
模式匹配NFA
MP自动机的非确定化
形状极简单：线性，而非树、图
模式匹配NFA的使用
初始状态永远活跃
活动状态集合=当前输入中的后缀中匹配的所有前缀的集合
状态转换
活跃状态集合的转换
````

## 第 75 页

````text
NFA与DFA
NFA需要并行机制的支持
适合硬件实现
空间占用小
DFA只需串行操作
适用于基于存储的系统
空间占用大
````

## 第 76 页

````text
模式匹配NFA的比特并行实现
比特并行
CPU对机器字的多个bit的处理是并行的
常见机器字长 32、64、128、256
算术运算
逻辑运算
假定模式长度小于机器字长！
模式匹配NFA状态与机器字的bit对应
保留顺序
Bit取值
1：对应状态活跃 
0：对应状态未激活
````

## 第 77 页

````text
Shift-And 算法
模式p, |p|=m，输入t, |t|=n
状态向量D = dm…d1. p的每个前缀对应一个bit，
di = 1 代表前缀 i 匹配 （匹配了已处理的输入的一个后缀）
di = 0 代表前缀 i 未匹配
表 B：每个字母对应一个bit向量
B[a]=所有a在p中出现的位置置1，否则置0
状态转换
D ← ((D<<1) | 0m-11) & B [t[i+1]]
````

## 第 78 页

````text
Shift-And 算法
Shift-And (p , t) 
1. Preprocessing 
2. For c ∊ Σ Do B[c] ← 0m 
3. For j ∊ 1 ... m Do B[p[j]] ← B[p[j]] | 0m-j 10j-1 
4. Searching 
5. D ← 0m 
6. For pos from 1 to n Do 
7. D ← ((D << 1) | 0m-1 1) & B[t[pos]] 
8. If D & 10m-1 ≠ 0m then report an occurrence at pos - m + 1 
9. End of for
````

## 第 79 页

````text
Shift-Or 算法
Shift-Or算法
观察：移位后，移入的bit是0
用0代表匹配，则无需 & 0m-11
状态向量D = dm…d1
di = 0 代表前缀 i 匹配 （匹配了已处理的输入的一个后缀）
di = 1 代表前缀 i 未匹配
表 B：每个字母对应一个bit向量
B[a]=所有a在p中出现的位置置0，否则置1
状态转换  
D ← (D<<1) | B [t[i+1]]


79
````

## 第 80 页

````text
Example Shift-Or
字符串是小端顺序比特向量是大端顺序
````

## 第 81 页

````text
通配符匹配
比特并行算法可实现带通配符的模式匹配
通配符 * 匹配任意字符
表 B：每个字母对应一个bit向量
 B[a] = 所有 a 在 p 中出现的位置置1，否则置0
 若 pi 为通配符，则所有 B 元素的第 I 位置置1
比特并行算法可实现字符集合匹配
````

## 第 82 页

````text
AC自动机对应的NFA
用bit对应自动机状态
状态转换
Shift-And不再适用
查表法
同时活跃状态在一条后缀链上
思考题：
如何通过word运算枚举每个活跃状态？
````

## 第 83 页

````text
总结
比特并行模式匹配算法模拟了模式匹配NFA
模式长度不超过机器字长时性能较高
重点
AC多模式匹配
BM算法
bit并行算法
83
````
