January 31, 2023
假设字符串的字符集不是很大，每个字符长度是 1 字节，用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。
如果将上面的过程翻译成代码，就是下面这个样子。其中，变量 b 是模式串，m 是模式串的长度，bc 表示刚刚讲的散列表。
private static final int SIZE = 256; // 全局变量或成员变量
private void generateBC(char[] b, int m, int[] bc) {
for (int i = 0; i < SIZE; ++i) {
bc[i] = -1; // 初始化bc
}
for (int i = 0; i < m; ++i) {
int ascii = (int)b[i]; // 计算b[i]的ASCII值
bc[ascii] = i;
}
}
33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？
January 30, 2023
当模式串滑动到图中的位置的时候，模式串和主串有 2 个字符是匹配的，倒数第 3 个字符发生了不匹配的情况。
把已经匹配的 bc 叫作好后缀，记作{u}。
拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u*}，那就将模式串滑动到子串{u*}与主串中{u}对齐的位置。
下面的例子中，bc 是好后缀，尽管在模式串中没有另外一个相匹配的子串{u*}，但是如果将模式串移动到好后缀的后面，那就会错过模式串和主串可以匹配的情况。
规则一：如果好后缀在模式串中不存在可匹配的子串，那在一步一步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。规则二：当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。
所以，针对这种情况，不仅要看好后缀在模式串中，是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。
所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a，ab。从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到如图所示的位置。
33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？
January 30, 2023
BM 算法的匹配顺序是按照模式串下标从大到小的顺序，倒着匹配的。
从模式串的末尾往前倒着匹配，当发现某个字符没法匹配的时候，把这个没有匹配的字符叫作坏字符（主串中的字符）。
拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符时，可以将模式串直接往后滑动三位，从模式串的末尾字符开始比较。
这个时候，坏字符 a 在模式串中是存在的，模式串中的 a 的下标是 0。此时，不能滑动三位，模式串应往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。
第一次不匹配的时候，滑动了三位，第二次不匹配的时候，将模式串后移两位，那具体滑动多少位，到底有没有规律呢？
当发生不匹配的时候，把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作 xi。如果不存在，把
xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，这里说的下标，都是字符在模式串的下标）。
如果坏字符在模式串里多处出现，那在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。
利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。比如，主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。
不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。
33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？
January 30, 2023
在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。把主串的长度记作 n，模式串的长度记作 m。因为是在主串中查找模式串，所以 n>m。
算法的思路：通过哈希算法对主串中的起始位置分别是 0、1、2….n-m 且长度为 m 的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
假设要匹配的字符串的字符集中只包含 K 个字符，可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。
比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。
相邻两个子串 s[i-1]和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，也就是说，我们可以使用 s[i-1]的哈希值很快的计算出 s[i]的哈希值。
\[h[i-1]=26^{m-1}\times (S[i-1]-‘a’)+26^{m-2}\times (s[i]-‘a’)+\cdots + 26^0\times (S[i+m-2]-‘a’)\] \[h[i]=26^{m-1}\times (S[i]-‘a’)++\cdots +26^1\times (s[i+m-2]-‘a’) + 26^0\times(S[i+m-1]-‘a’)\] 由此可知： \[h[i]=(h[i-1]-26^{m-1} \times (s[i-1] - ‘a’)) \times 26 + 26^0 \times (s[i+m-1]-‘a’)\]
...
January 29, 2023
#include<cstring>中的memset是按字节填充的。例如，int占4字节，因此memset(a,0x3f,sizeof(a))按字节填充相当于将0x3f3f3f3f赋值给数组 a[]的每个元素。memset经常用来初始化一个int型数组为0、-1，或者最大值、最小值，也可以初始化一个bool型数组为true(1)或false(0)。
不可以用memset初始化一个int型数组为1，因为memset(a,1,sizeof(a))相当于将每个元素都赋值为0000 0001 0000 0001 0000 0001 0000 0001，即将0000 0001分别填充到4字节中。布尔数组可以赋值为true，是因为布尔数组中的每个元素都只占1字节。
memset(a,0,sizeof(a)); //初始化为0
memset(a,-1,sizeof(a));//初始化为-1
memset(a,0x3f,sizeof(a));//初始化为最大值0x3f3f3f3f
memset(a,0xcf,sizeof(a));//初始化为最小值0xcfcfcfcf
需要注意的是，动态数组或数组作为函数参数时，不可以用sizeof(a)测量数组空间，因为这样只能测量到首地址的空间。可以用 memset(a,0x3f,n×sizeof(int))的方法处理，或者用fill函数填充。
如果用memset(a,0x3f,sizeof(a))填充double类型的数组，则经常会得到一个连 1都不到的小数。double类型的数组填充极值时需要用fill(a,a+n,0x3f3f3f3f)。
尽管0x7fffffff是32-bit int的最大值，但是一般不使用该值初始化最大值，因为0x7fffffff不能满足“无穷大加一个有穷的数依然是无穷大”，它会变成一个很小的负数。0x3f3f3f3f的十进制是1061109567，也就是10^9级别的（和 0x7fffffff在一个数量级），而一般情况下的数据都是小于10^9的，所以它可以作为无穷大使用而不至于出现数据大于无穷大的情形。另一方面，由于一般的数据都不会大于10^9，所以当把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”）。事实上， 0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了“无穷大加无穷大还是无穷大”的需求。
January 28, 2023
January 28, 2023
朴素贝叶斯分类器受训练数据集规模的限制，某些属性的取值在训练集中可能从未与某个类同时出现，这就可能导致属性条件概率为 0，此时直接使用朴素贝叶斯分类就会导致错误的结论。
还是以贷款申请为例，如果在训练集中没有样本同时具有“年龄大于 60”的属性和“发放贷款”的标签，那么当一个退休人员申请贷款时，即使他是坐拥百亿身家的李嘉诚，朴素贝叶斯分类器也会因为后验概率等于零而将他无情拒绝。
因为训练集样本的不充分导致分类错误，显然不是理想的结果。为了避免属性携带的信息被训练集中未曾出现过的属性值所干扰，在计算属性条件概率时需要添加一个称为“拉普拉斯平滑”的步骤。
所谓拉普拉斯平滑就是在计算类先验概率和属性条件概率时，在分子上添加一个较小的修正量，在分母上则添加这个修正量与分类数目的乘积。这就可以保证在满足概率基本性质的条件下，避免了零概率对分类结果的影响。当训练集的数据量较大时，修正量对先验概率的影响也就可以忽略不计了。
January 27, 2023
观察 /proc/softirqs 文件的内容，就能知道各种软中断类型的次数。
不过，这里的各类软中断次数，是系统运行以来的累积中断次数。所以我们直接查看文件内容，得到的只是累积中断次数。
那什么工具可以观察命令输出的变化情况呢？就是watch 命令，就可以定期运行一个命令来查看输出；如果再加上 -d 参数，还可以高亮出变化的部分，从高亮部分我们就可以直观看出，哪些内容变化得更快。
$ watch -d cat /proc/softirqs
CPU0 CPU1
HI: 0 0
TIMER: 1083906 2368646
NET_TX: 53 9
NET_RX: 1550643 1916776
BLOCK: 0 0
IRQ_POLL: 0 0
TASKLET: 333637 3930
SCHED: 963675 2293171
HRTIMER: 0 0
RCU: 1542111 1590625
通过 /proc/softirqs 文件内容的变化情况，可以发现， TIMER（定时中断）、 NET_RX（网络接收）、SCHED（内核调度）、RCU（RCU 锁）等这几个软中断都在不停变化。
其中，NET_RX，也就是网络数据包接收软中断的变化速率最快。而其他几种类型的软中断，是保证 Linux 调度、时钟和临界区保护这些正常工作所必需的，所以它们有一定的变化倒是正常的。
10 | 案例篇：系统的软中断CPU使用率升高，我该怎么办？
January 27, 2023
sar可以用来查看系统的网络收发情况，还有一个好处是，不仅可以观察网络收发的吞吐量（BPS，每秒收发的字节数），还可以观察网络收发的 PPS，即每秒收发的网络帧数。
我们在第一个终端中运行 sar 命令，并添加 -n DEV 参数显示网络收发的报告：
# -n DEV 表示显示网络收发的报告，间隔1秒输出一组数据
$ sar -n DEV 1
15:03:46 IFACE rxpck/s txpck/s rxkB/s txkB/s
15:03:47 eth0 12607.00 6304.00 664.86 358.11
15:03:47 docker0 6302.00 12604.00 270.79 664.66
15:03:47 lo 0.00 0.00 0.00 0.00
15:03:47 veth9f6bbcd 6302.00 12604.00 356.95 664.66
对于 sar 的输出界面，我先来简单介绍一下，从左往右依次是：
我们具体来看输出的内容，你可以发现：
重点来看 eth0 ：接收的 PPS 比较大，达到 12607，而接收的 BPS 却很小，只有 664 KB。直观来看网络帧应该都是比较小的，我们稍微计算一下， 664*1024/12607 = 54 字节，说明平均每个网络帧只有 54 字节，这显然是很小的网络帧，也就是我们通常所说的小包问题。
...
January 27, 2023
# -S参数表示设置TCP协议的SYN（同步序列号），-p表示目的端口为80
# -i u100表示每隔100微秒发送一个网络帧
# 注：如果你在实践过程中现象不明显，可以尝试把100调小，比如调成10甚至1
$ hping3 -S -p 80 -i u100 192.168.0.30
这是一个 SYN FLOOD 攻击。
10 | 案例篇：系统的软中断CPU使用率升高，我该怎么办？