Эта статья была впервые опубликована на:Уокер ИИ
В работе необходимо перехватывать некоторые запрещенные слова, а в практических сценариях применения необходимо обеспечить, чтобы процесс сопоставления давал результаты в пределах сотен миллисекунд. Поэтому, как быстро и точно определить, включены ли эти ключевые слова в текст, становится особенно важным.
Для вышеуказанной задачи мы опишем ее в следующем виде
Учитывая набор ключевых слов P={p1,p2,...,pk}, найдите, какие ключевые слова появляются в целевой строке T[1...m].
Самый простой способ придумать - это сопоставить каждое слово и, наконец, подвести итог, какие слова совпадают успешно.
С учетом алгоритма KMP временная сложность сопоставления одного ключевого слова составляет O(|pk|+m), поэтому временная сложность однократного сопоставления всех ключевых слов составляет O(|p1|+m+|p2|+m+…+| pk| +м). Пусть n=|p1|+…+|pk|, приведенная выше формула упрощается до O(n+km), поэтому, когда количество ключевых слов становится очень большим, этот алгоритм становится невыносимым.
Альфред В.Ахо и Маргарет Дж.Корасик в 1974 году предложили классический алгоритм сопоставления нескольких шаблонов - алгоритм AC, который может гарантировать, что для заданного текста длины n и набора шаблонов P{p1,p2,…pm} находит все целевые шаблоны в тексте с временной сложностью O(n), независимо от размера m набора шаблонов.
1. Подробное объяснение алгоритма AC
Основой автомата AC является Trie-дерево, которое отличается от Trie-дерева тем, что каждый узел в дереве, помимо наличия указателя на потомка, начинает посимвольно сопоставлять листовому узлу по целевому поле, которое ищется. В этом процессе, если есть несоответствие, перейти в соответствии с точкой перехода несоответствия и распечатать, если найдена совпадающая строка шаблона. Алгоритм AC вообще не требует обратного отслеживания при сканировании текста.Если рассматривать только процесс сопоставления, временная сложность алгоритма составляет O (n), что связано только с длиной текста, который необходимо сопоставить.
1.1 Автоматы
Во-первых, давайте объясним, что такое автомат переменного тока? Что такое автомат?
Рис. 1. Диаграмма перехода состояний автомата
Автомат — это математическая модель конечного автомата, что такое состояние? Например: у переключателя два состояния, у решета шесть состояний, как показано на рисунке, есть три состояния А, В и С. Автомат – это машина, способная изменять свое состояние при определенных внешних воздействиях. На рисунке состояние A можно вернуть в исходное состояние с помощью стимулов 0, 3, 6 и 9, а в состояние B можно перейти с помощью стимулов 1, 4 и 7.
AC преобразует сопоставление символов в переходы между состояниями. То есть AC преобразует процесс сопоставления строк в переход состояний между конечными автоматами, создавая автомат для представления процесса сопоставления символов.
1.2 Конкретная реализация
Реализация алгоритма AC может состоять из следующих трех частей:
- таблица перехода: автомат перехода между состояниями, состоящий из всех шаблонов в наборе шаблонов
- таблица отказов: основа для перехода состояния после неудачного совпадения в таблице перехода
- таблица вывода: указывает вывод, также известный как: испускает, что означает, что определенная строка шаблона успешно сопоставляется после достижения определенного состояния
(1) Построить таблицу перехода
Здесь мы берем множество P={"он","она","его","ее"} в качестве примера
Во-первых, построить функцию перехода, которая относится к отношениям перехода между состояниями.Чтобы построить функцию перехода, нам нужно построить диаграмму перехода состояний. В начале этот граф содержит только одно состояние 0, а затем путем добавления пути из начального состояния каждое ключевое слово вводится в граф по очереди, и в граф добавляются новые вершины и ребра, таким образом генерируется путь, который указывает ключевое слово ключевое слово.
Добавление первого ключевого слова «он» приводит к следующему изображению, где путь от состояния 0 до состояния 2 состоит из ключевого слова «он».
Рис. 2. Диаграмма перехода состояний He
Затем мы создаем второе ключевое слово «она».
Рис. 3. Диаграмма переходов между состояниями She
Когда мы добавляем «его», поскольку ребро из состояния 0 в состояние 1 уже существует с входом h, нам не нужно добавлять сюда еще одно такое же ребро.
Рисунок 4. Его диаграмма переходов состояний
Наконец, мы добавляем «hers», чтобы получить следующую ссылку, вывод «hers» связан с состоянием 9, и, наконец, добавляем цикл от состояния 0 до 0 для каждого символа, кроме h и s.
Рисунок 5. Диаграмма переходов ее состояний
На данный момент мы построили диаграмму переходов состояний всего набора шаблонов, то есть функцию перехода.
(2) Построить таблицу отказов
Отказ функции отказа определяет, к какому состоянию следует вернуться, когда следующее состояние, полученное функцией перехода, недопустимо.
При построении функции отказа мы сначала вводим понятие глубины, Глубина (s) состояния s определяется как длина кратчайшего пути от начального состояния 0 до состояния s в таблице перехода. Например, глубина состояний 1 и 3 в таблице перехода равна 1.
Вычислительные идеи
Сначала вычислите значение функции отказа для всех состояний с глубиной 1, затем вычислите все состояния с глубиной 2 и так далее, пока не будет вычислено значение функции отказа для всех состояний (кроме состояния 0, поскольку его функция отказа не определена). .
метод расчета
Алгоритм вычисления значения функции отказа состояния концептуально очень прост. Во-первых, пусть значение функции всех состояний s глубины 1 равно f(s) = 0. Предполагая, что f-значения всех состояний с глубиной меньше d были рассчитаны, значение функции отказа состояния с глубиной d будет вычислено из значения функции отказа состояния с глубиной меньше d.
процесс расчета
- Для всех символов a, если goto(r,a) = fail, то ничего не делать (это тот случай, когда r является конечным узлом дерева дерева, которое мы построили выше)
- Если goto(r,a) == s, мы пишем state = fail® и выполняем state = f(state) ноль или более раз, пока goto(state,a) != fail, потому что goto(0,a) != fail , поэтому это состояние должно существовать
- Помните, что fail(s) = goto(state,a)
Взяв в качестве примера диаграмму состояний, которую мы построили выше, таблица отказов, которую мы построили, выглядит следующим образом:
| государство | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| значение ошибки | None | 0 | 0 | 0 | 1 | 2 | 0 | 3 | 0 | 3 |
(3) Построить выходную таблицу
вывод означает вывод, что означает, что определенная строка шаблона успешно сопоставляется после достижения определенного состояния. Процесс построения этой таблицы интегрирован в процесс построения таблицы перехода и таблицы отказов.
-
При построении таблицы перехода конечное состояние каждой строки шаблона добавляется в выходную таблицу, то есть черный полужирный кружок в таблице перехода. получить:
i output(i) 2 {he} 5 {she} 7 {his} 9 {hers} -
При построении таблицы отказов, если f(s) = s', выходные наборы, соответствующие s и s', объединяются. Если f(5) = 2, окончательная выходная таблица будет следующей:
i output(i) 2 {he} 5 {she, he} 7 {his} 9 {hers}
2. Конкретная реализация алгоритма AC
Возьмем питон в качестве примера
class ac_automation(object):
def __init__(self):
self.root = node()
def add(self, word):
temp_root = self.root
for char in word:
if char not in temp_root.next:
temp_root.next[char] = node()
temp_root = temp_root.next[char]
temp_root.isWord = True
temp_root.word = word
def make_fail(self):
temp_que = []
temp_que.append(self.root)
while len(temp_que) != 0:
temp = temp_que.pop(0)
p = None
for key,value in temp.next.item():
if temp == self.root:
temp.next[key].fail = self.root
else:
p = temp.fail
while p is not None:
if key in p.next:
temp.next[key].fail = p.fail
break
p = p.fail
if p is None:
temp.next[key].fail = self.root
temp_que.append(temp.next[key])
def search(self, content):
p = self.root
result = []
currentposition = 0
while currentposition < len(content):
word = content[currentposition]
while word in p.next == False and p != self.root:
p = p.fail
if word in p.next:
p = p.next[word]
else:
p = self.root
if p.isWord:
result.append(p.word)
currentposition += 1
return result
PS: Для получения дополнительной технической галантереи, пожалуйста, обратите внимание на [Публичный аккаунт | xingzhe_ai] и обсудите с ходоками!