模式匹配：查字符串中是否存在某个（些）⼦字符串
在NLP任务中，经常会遇到判断某些关键词是否在⽂本中以及在⽂本中的位置，还有些类似分词的应⽤场景，这时就可以利⽤模式匹配这种⼩⽽美的⽅式。本⽂主要涉及KMP算法、Trie树、双数组Trie树以及AC⾃动机四种算法的原理与实现。不同的语⾔都有类似成熟的实现，在实际应⽤中，⼤家可以直接调⽤包。⽂本代码都是由Python实现，完整代码还未开源（会尽快开源），因为没有经过严格测试，所以代码仅供参考。查看有道云格式，请点击这⾥。
KMP算法
Trie树
双数组Trie树
index与match举例讲解图中，上⾯表⽰⽂本，下⾯表⽰匹配的关键词。假设我们匹配到⽂本6的位置，此时判断关键词5的位置与其是否⼀致，如果⼀致，则继续往下匹配，如果不⼀致，朴素的想法则是像下图⼀样。
我们将关键词的头移⾄⽂本3的位置，开始重新匹配。事实上，我们有更好的选择。我们不需要再匹配⽂本2-5的位置，因为⽂本2-5的位置与关键词1-4是⼀样的，这样我们在匹配前，通过对关键词⾃⾝的匹配，就可以知道形如关键词1-4的字符串可以被匹配成什么样，如下图所⽰：
此时假设关键词1-4的后缀中（不包含1-4，只有2-4，3-4，4），是关键词的前缀且最长的是3-4（2-4不是前缀，4不管是不是前缀都⽐3-4短），此时就相当于⽂本4-5被关键词1-2匹配了，只需要判断关键词3与⽂本6是否⼀致。也就是关键词5的位置不匹配时，可以直接再判断关键词3是否与当前匹配。此时的状态与第⼀个图的状态⼀致，后续的匹配过程依次循环，直⾄匹配结束。
当然，如果关键词1-4的后缀中不存在关键词的前缀，那么直接重⽂本6开始重新匹配，如下图所⽰：
根据上⾯的分析，我们可以知道，在查的过程中，不需要回退查，只要扫⼀遍⽂本就可以了。其中关键点在于，当关键词n位置没能匹配时，我们需要跳到m位置进⾏匹配，通常我们⽤next数组表⽰这⼀关系，next[n]=m。其查⽅式如下：
def self_match(self):
if self.length < 2:
return
这样我们就把多个关键词组合成了⼀个树，在搜索⽂本的时候，就可以像匹配⼀个关键词那样匹配这个树，就可以达到⼀次遍历，匹配所有建⽴这个树结构，我们⾸先需要定义节点：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。