WM算法从零讲起

一、为什么要用WM算法？

在它之前，最简单的方法是拿每个关键词，从头到尾在文章里扫一遍。如果有10个关键词，文章有10000个字，那就得扫10万次，非常慢。

WM算法的聪明之处在于，它一次扫描文章，就能同时匹配所有关键词，大大提升了效率。这在杀毒软件（病毒库有成千上万个特征码）、搜索引擎（同时匹配大量查询词）中非常有用。

二、WM算法的核心思想：跳着查

它模仿我们人眼阅读时的“跳读”。比如找“元宝”这个词，我们不会一个字一个字地看，而是快速扫过，看到“宝”字才停下来仔细看看前面是不是“元”。

WM算法把这种“跳读”做到了极致，它依赖于两张事先准备好的“地图”：

1. SHIFT表（跳跃表）：告诉算法“这次可以安全地跳过多远”。
2. HASH表（哈希表）：当不能跳过时，告诉算法“这里可能匹配到哪些关键词”。

三、WM算法详解（三步走）

第一步：预处理（制作“地图”）

在搜索开始前，算法会先分析所有要查找的关键词，制作两张表。我们假设关键词长度都是m（WM通常处理等长关键词，或取最短长度）。

1. 制作SHIFT表：
   • 想象一个所有可能字符（如a-z）的表格。
   • 规则：对于一个字符，看所有关键词的最后一个字符。计算这个字符到每个关键词末尾的距离（即m - 1 - 位置索引），取最小值。这个值就是可以安全跳跃的步数。
   • 通俗理解：这个表记录了，当我在文章里看到某个字符时，根据所有关键词的“尾巴”来判断，我最少可以往前跳几步，而绝不会错过可能的匹配。

   举例：有关键词 she, her, his（m=3）。

   • 对于字符 e：在 she中，e在最后一位（位置2），距离末尾是 3-1-2=0；在 her中，e在中间（位置1），距离末尾是 3-1-1=1。取最小值 0。所以SHIFT[e] = 0。
   • 对于字符 x：所有关键词末尾都没有x，那么可以安全地跳过几乎整个关键词长度，即 m = 3。所以SHIFT[x] = 3。
2. 制作HASH表：
   • 当SHIFT表告诉我们不能跳了（值为0），我们就需要检查当前位置是否真的匹配了某个关键词。
   • HASH表根据关键词的最后几个字符（比如最后2个）计算一个“指纹”（哈希值），然后把具有相同“指纹”的关键词归类在一起。
   • 通俗理解：这是一本“嫌疑犯名单”。当在某个位置发现“尾巴特征”可疑时，就翻看这本名单，快速找到所有具有这个“尾巴特征”的关键词进行详细比对。

第二步：匹配（使用“地图”扫描文章）

现在开始扫描文章（我们称为“文本”）。

1. 将搜索窗口对准文本末尾，从后往前比较（这是关键！）。
2. 看窗口最后一个字符，查 SHIFT表，得到跳跃值 s。
3. 如果 s > 0，说明当前位置绝不可能匹配，直接将窗口向后（右）移动 s位。
4. 如果 s == 0，说明当前位置“有可能”匹配。这时：
   • 取出窗口的最后几个字符，计算哈希值。
   • 查 HASH表，找到所有具有这个哈希值的关键词。
   • 将这些关键词与窗口内的文本，从后往前逐个字符进行精确比较。
   • 如果完全匹配，就记录下这个位置（找到了！）。
5. 无论是否匹配成功，都将窗口向后移动1位（因为s=0，最小移动量），然后重复步骤2。

第三步：重复

直到搜索窗口移出文本的开头，算法结束。

四、总结与比喻

• 优势：通过SHIFT表实现了“跳跃式”扫描，避免了大量无用的逐字符比较，特别适合关键词数量多、字母表大的情况。
• 局限：对关键词长度敏感，如果长度差异大，效率会下降。现代系统常用其改进版或与其他算法结合。

一个生动的比喻：

WM算法就像一个拿着两份名单的检票员。

• SHIFT表是一份“快速通行名单”：看一眼你票的某个特征（如末尾编号），如果在名单上且距离远，就直接挥手让你快速通过（跳过多位）。
• HASH表是一份“详细核查名单”：如果你需要被检查，检票员根据你票的另一个特征（如最后两位编号），快速从名单里找出所有类似票样，然后仔细核对你的全部信息。

希望这个从零开始的讲解能帮助你理解WM算法！