书中P61提到AC自动机适用于短模式串场景,汉字就是短模式串,但P70和P71在对比DAT和ACDAT时,又说AC自动机的fail机制对短模式串用处不大,且含有短模式串时优先用DAT,请问这两处是否矛盾?
结合上文看,原文的意思是WuManber在短模式串场景中比AC自动机差,但并没有说AC自动机特别适合短模式串。结合书中脚注WuManber的资料来看:
Wu Manber算法理论上复杂度为 O(BN/m)(1 \leq B \leq m = min(strlen(M))),与AC自动机的 O(N) 相比,只有在特定条件下(B \ll m)才能体现出优势。这个特定条件很苛刻,要求模式串不能太短。而在自然语言处理的场景下,经常有单字作为模式串的情况,此时Wu Manber无法跳过多个字符,没有优势。另外,汉语最常见的词语长度为 2 ,也限制了该算法的使用。
注意如果最短模式串非常短,比如长度为 1 ,则算法不可能跳过 2 及以上个字符,效率变低。
当最短长度为 1 时,无论输入什么文本,WuManber一定无法加速,但AC自动机仍然有可能加速,毕竟文本不一定完全由长 1 的模式串构成。