предисловие
Часто требуется найти все совпадающие шаблоны в строке, например найти, какие фразы в словаре соответствуют фрагменту текста. На этот раз для эффективной обработки будут рассмотрены автоматы переменного тока, то есть алгоритм автоматов Ахо-Корасика. Его основная идея состоит в том, чтобы умело преобразовывать сравнения символов в переходы между состояниями с помощью конечных автоматов.
Нет необходимости в возврате при сопоставлении через автомат AC, а временная сложность равна O(n), то есть временная сложность не зависит от размера словаря.
жестокий матч
Насильственное сопоставление — это сравнение по одному, сопоставление строки шаблона с основной строкой от начала до конца, как показано на следующем рисунке, строка шаблона «ABCE» сравнивает основную строку. переместитесь назад и начните сравнение снова, пока сравнение не будет завершено.Основная строка, затем вторая строка шаблона продолжает сравнение. Этот метод прост, жесток и легок для понимания, но временная сложность высока, O(mn).
автомат переменного тока
Автомат переменного тока в основном конструирует n строк шаблонов в детерминированный древовидный конечный автомат, а затем использует основную строку в качестве входных данных конечного автомата, чтобы заставить конечный автомат выполнять переходы между состояниями. происходит совпадение.
понять на примереhe、she、his、hersэто строка шаблона,ushersОсновная строка представляет собой следующий конечный автомат.
Внутри конечного автомата вы можете видеть стрелки со сплошными линиями и пунктирными линиями.Сплошная линия предпочтительна для обозначения состояния перехода направления, а переход пунктирной линии используется, когда переход сплошной линии невозможен.
Кроме того, при переключении на положение красного круга на рисунке это означает, что происходит сопоставление с образцом, например, дляhe, от корневого узла к 1, а затем к 2, в это время он соответствуетhe, что указывает на совпадение с образцом.
По картинке выше можно попробоватьushersКакие шаблоны будут сопоставлены, и будет указан процесс перехода к следующему состоянию.
Три функции переменного тока
Автомат AC содержит три основные функции.В принципе, если вы их понимаете, вы поймете AC.
- Функция goto используется для управления переходом состояния, то есть в текущем состоянии, в какое состояние следует перейти после ввода символа, что соответствует части сплошной линии на приведенном выше рисунке.
- Функция сбоя используется для управления переходом состояния, когда совпадение не удается, то есть в текущем состоянии после ввода символа нет возможности преобразовать его в соответствии со сплошной линией.В это время преобразование выполняется в соответствии к пунктирной линии, которая соответствует пунктирной линии на рисунке выше.
- Выходная функция, описывающая, в каких состояниях произошло совпадение и каков шаблон сопоставления.
выполнить
При реализации автомата AC обычно используется древовидная структура TRIE, затем будет определена древовидная структура TRIE.ACTrieNodeКласс, который содержит такие свойства, как дочерние узлы, значения, выходные данные, отказоустойчивые узлы и т. д.
public class ACTrieNode {
private ACTrieNode[] children;
private byte[] value;
private boolean deleted = false;
private int status;
private ACArray[] results = null;
private ACTrieNode failureNode;
private static String encoding = "utf-8";
}
См. github для подробной реализации, https://github.com/sea-boat/TextAnalyzer/blob/master/src/main/java/com/seaboat/text/analyzer/segment/ACTrieTree.java.
------------- Рекомендуем прочитать ------------
Резюме моей статьи за 2017 год — машинное обучение
Краткое изложение моих статей за 2017 год — Java и промежуточное ПО
Резюме моих статей 2017 года — глубокое обучение
Краткое изложение моих статей за 2017 год — исходный код JDK
Резюме моей статьи за 2017 год — обработка естественного языка
Резюме моих статей 2017 года — Java Concurrency
Поговори со мной, задай мне вопросы:
Меню официальной учетной записи было разделено на «Сводка для чтения», «Распределенное», «Машинное обучение», «Глубокое обучение», «НЛП», «Глубина Java», «Ядро параллелизма Java», «Исходный код JDK», "Tomcat Core" "Подождите, может быть, есть тот, который соответствует вашему аппетиту.
Зачем писать «Анализ проектирования ядра Tomcat»
Добро пожаловать, чтобы следовать: