Aho-Corasick是一种字典匹配算法。该算法用于搜索关键字集中存在的单词。该算法可以快速有效地查找单词及其位置。 Aho-Corasick 算法构建了一个现有系统并采用了TRIE 概念。
树数据结构用于执行该技术。当我们创建树时，它会将其转换或尝试将其转换为自动机，从而使我们能够在线性时间内完成或执行搜索。
Aho-Corasick 算法的时间复杂度
Aho-Corasik 算法在O(X+ Y+ Z) 时间内搜索单词，其中X是文本长度，Y是关键字长度，Z是关键字在文本中出现的次数。
Ahio-Corasick 算法的问题陈述
假设我们有输入文本和一个包含 m 个单词的数组 a[ ]。我们需要搜索输入文本中存在的单词数。
设 x 为文本长度，y 为所有单词中的字符数。这意味着 y = len(a [0]) + len(a [1]) + len(a [2]) + …。 + 长度（a [z - 1]）。这里，z是输入单词的数量。
我们将通过一个示例来理解该算法，在该示例中，我们将采用输入字符串和要在文本字符串中搜索的单词集。
例子：
输入：
文本字符串：txt= “hellotheirshere”
示例单词集： a[ ] = { "he" , "hello" , "she" , "here" , "their" , "the" }
|
输出：
单词“he”位于索引 0 到 1 处。
单词“he”位于索引 6 到 7 处
单词“he”位于索引 11 到 12 处
单词“hello”位于索引 0 到 4 处。
单词“the”位于索引 5 到 7 处
“
|
their”一词位于索引 7 至 11 处。
单词“she”位于索引 10 到 12 处。
单词“here”位于索引 11 到 14 处
|
算法的预处理
Aho-Corasick 算法分为三个不同的阶段：
Go To转到：此阶段使用以模式输入算法的关键字来创建树。它转到主函数，然后设置点，然后转到主根。它跟踪数组 a[ ] 中所有单词的边距。二维数组 gt[ ][ ] 表示 go 函数，我们可以在其中存储字符和状态以用于进一步的下一个状态。Output输出：该阶段搜索以特定状态结尾的单词。这是条件和可用性匹配时的结果。该函数存储以当前状态结尾的单词的索引。一维数组 op[] 表示输出函数，我们可以在其中将单词存储为当前状态的位图。
Failure失败：它搜索向后转换以从集合中找到合适的关键字。如果关键字不匹配，则不会计算在内。当当前字符在 Trie 中缺少边时，该函数记录其后面的每条边。一维数组 fl[ ] 表示我们记录当前状态的下一个状态的失败。
用于模式搜索的 Aho-Corasick 算法在 Python 中的实现
以下是 Aho-Corasick 算法的 Python 实现：
from collections import defaultdict
class Aho_Corasick:
def __init__(self, words):
self.maxStates = sum([len(word) for word in words])
self.maxChar = 22
self.out = [0]*(self.maxStates + 1)
self.fail = [-1]*(self.maxStates + 1)
self.goto = [[-1]*self.maxChar for _ in range(self.maxStates + 1)]
for i in range(len(words)):
words[i] = words[i].lower()
self.words = words
self.states_count = self.__build_matching_machine()
def __build_matching_machine(self):
m = len(self.words)
state = 1
for i in range(m):
word = self.words[i]
currentState = 0
for char in word:
c = ord(char)
if self.goto[currentState][c] == -1:
self.goto[currentState][c] = state
state += 1
currentState = self.goto[currentState][c]
self.out[currentState] |= (1 << i)
for c in range(self.maxChar):
if self.goto[0][c] == -1:
self.goto[0][c] = 0
queue = []
for ch in range(self.maxChar):
if self.goto[0][c] != 0:
self.fail[self.goto[0][c]] = 0
queue.append(self.goto[0][c])
while queue:
states = queue.pop(0)
for c in range(self.maxChar):
if self.goto[states][c] != -1:
failure = self.fail[states]
while self.goto[failure][c] == -1:
failure = self.fail[failure]
failure = self.goto[failure][c]
self.fail[self.goto[states][c]] = failure
self.out[self.goto[states][c]] |= self.out[failure]
queue.append(self.goto[states][ch])
return state
def find_Next_State(self, currentState, next_inp):
ans = currentSate
c = ord(next_inp) - 97
while self.goto[ans][c] == -1:
answer = self.fail[ans]
return self.goto[ans][c]
def search(self, txt):
txt = txt.lower()
currentSate = 0
res = defaultdict(list)
for i in range(len(txt)):
currentState = self.findNextState(currentState, txt[i])
if self.out[currentState] == 0: continue
for j in range(len(self.words)):
if (self.out[currentState] & (1 << j)) > 0:
word = self.words[j]
res[word].append(i-len(word)+1)
return result
if __name__ == "__main__":
words = ["he", "hello", "she", "here", "their", "the"]
txt = "hellotheirshere"
aho_chorasick = Aho_Corasick(words)
res = aho_chorasick.search(txt)
for word in result:
for i in result[word]:
print("The Word", word, "is found at index", i, "to", i + len(word) - 1)
|
解释：
在这里，我们使用默认字典来存储输出。我们设置了字符和状态的最大限制。利用算法的三个阶段，我们对数据进行了预处理。然后，利用循环和队列，我们构建了机器/自动机，然后从文本字符串中搜索单词集。