`
itace
  • 浏览: 181583 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

AC自动机

 
阅读更多

 

Usage

Setting up the Trie is a piece of cake:

    Trie trie = Trie.builder()
        .addKeyword("hers")
        .addKeyword("his")
        .addKeyword("she")
        .addKeyword("he")
        .build();
    Collection<Emit> emits = trie.parseText("ushers");

You can now read the set. In this case it will find the following:

  • "she" starting at position 1, ending at position 3
  • "he" starting at position 2, ending at position 3
  • "hers" starting at position 2, ending at position 5

In normal situations you probably want to remove overlapping instances, retaining the longest and left-most matches.

    Trie trie = Trie.builder()
        .removeOverlaps()
        .addKeyword("hot")
        .addKeyword("hot chocolate")
        .build();
    Collection<Emit> emits = trie.parseText("hot chocolate");

The removeOverlaps method tells the Trie to remove all overlapping matches. For this it relies on the following conflict resolution rules: 1) longer matches prevail over shorter matches, 2) left-most prevails over right-most. There is only one result now:

  • "hot chocolate" starting at position 0, ending at position 12

If you want the algorithm to only check for whole words, you can tell the Trie to do so:

    Trie trie = Trie.builder()
        .onlyWholeWords()
        .addKeyword("sugar")
        .build();
    Collection<Emit> emits = trie.parseText("sugarcane sugarcane sugar canesugar");

In this case, it will only find one match, whereas it would normally find four. The sugarcane/canesugar words are discarded because they are partial matches.

Some text is WrItTeN in a combination of lowercase and uppercase and therefore hard to identify. You can instruct the Trie to lowercase the entire searchtext to ease the matching process. The lower-casing extends to keywords as well.

    Trie trie = Trie.builder()
        .caseInsensitive()
        .addKeyword("casing")
        .build();
    Collection<Emit> emits = trie.parseText("CaSiNg");

Normally, this match would not be found. With the caseInsensitive settings the entire search text is lowercased before the matching begins. Therefore it will find exactly one match. Since you still have control of the original search text and you will know exactly where the match was, you can still utilize the original casing.

It is also possible to just ask whether the text matches any of the keywords, or just to return the first match it finds.

    Trie trie = Trie.builder().removeOverlaps()
            .addKeyword("ab")
            .addKeyword("cba")
            .addKeyword("ababc")
            .build();
    Emit firstMatch = trie.firstMatch("ababcbab");

The firstMatch will now be "ababc" found at position 0. containsMatch just checks if there is a firstMatch and returns true if that is the case.

If you just want the barebones Aho-Corasick algorithm (ie, no dealing with case insensitivity, overlaps and whole words) and you prefer to add your own handler to the mix, that is also possible.

    Trie trie = Trie.builder()
            .addKeyword("hers")
            .addKeyword("his")
            .addKeyword("she")
            .addKeyword("he")
            .build();

    final List<Emit> emits = new ArrayList<>();
    EmitHandler emitHandler = new EmitHandler() {

        @Override
        public void emit(Emit emit) {
            emits.add(emit);
        }
    };

In many cases you may want to do useful stuff with both the non-matching and the matching text. In this case, you might be better served by using the Trie.tokenize(). It allows you to loop over the entire text and deal with matches as soon as you encounter them. Let's look at an example where we want to highlight words from HGttG in HTML:

    String speech = "The Answer to the Great Question... Of Life, " +
            "the Universe and Everything... Is... Forty-two,' said " +
            "Deep Thought, with infinite majesty and calm.";
    Trie trie = Trie.builder().removeOverlaps().onlyWholeWords().caseInsensitive()
        .addKeyword("great question")
        .addKeyword("forty-two")
        .addKeyword("deep thought")
        .build();
    Collection<Token> tokens = trie.tokenize(speech);
    StringBuffer html = new StringBuffer();
    html.append("<html><body><p>");
    for (Token token : tokens) {
        if (token.isMatch()) {
            html.append("<i>");
        }
        html.append(token.getFragment());
        if (token.isMatch()) {
            html.append("</i>");
        }
    }
    html.append("</p></body></html>");
    System.out.println(html);

   转:https://github.com/robert-bor/aho-corasick

 

分享到:
评论

相关推荐

    AC自动机_AC自动机模板_

    AC自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于信息学奥林匹克竞赛、数据结构与算法竞赛以及文本处理等领域。它的主要功能是高效地在一个字符串集合中进行多模式匹配,即同时查找多个模式串...

    中文高性能AC自动机代码

    **AC自动机(Aho-Corasick算法)**是一种在字符串搜索中用于高效查找多个模式串的算法。在中文文本处理中,AC自动机尤其适用,因为它能够一次性处理大量关键词,避免了对文本的多次扫描。这个算法由Aho和Corasick在...

    36丨AC自动机:如何用多模式串匹配实现敏感词过滤功能?1

    AC自动机是一种高效的多模式串匹配算法,主要应用于文本处理中的敏感词过滤、关键词搜索等功能。它的全称为Aho-Corasick算法,由Aho和Corasick在1975年提出。AC自动机在Trie树的基础上进行了扩展,增加了失败指针,...

    支持多线程AC自动机

    **支持多线程AC自动机** 在网络安全领域,Snort是一款广泛应用的开源网络入侵检测系统(IDS)。它能够实时分析网络流量,识别潜在的攻击行为。然而,原版的Snort可能在处理大量数据时面临性能瓶颈,因为它通常是单...

    ac自动机.pptx

    要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难) 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话...

    AC自动机.pdf

    ### AC自动机详解 #### 一、AC自动机概述 AC自动机(Aho-Corasick Automaton)是一种经典的字符串匹配算法,特别适用于处理多个模式串的匹配问题。它结合了KMP算法的思想以及字典树(Trie)的结构特点,能够有效地在...

    AC自动机实现多模式串匹配,支持中文

    AC自动机,全称为Aho-Corasick自动机,是一种在文本中高效地进行多模式串匹配的算法。它的核心思想是构建一个自动机结构,该结构能够在一次遍历文本的过程中,同时匹配多个模式串,大大提高了搜索效率,避免了对每一...

    AC自动机算法(Aho-Corasick 多模式匹配算法)

    AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现

    AC自动机最全数据,欢迎下载

    AC自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于文本处理、生物信息学、搜索引擎等领域。这个压缩包包含了多个以".in"为后缀的文件,很可能是用于AC自动机相关的编程练习或测试数据集。 AC...

    AC自动机详解+例题详解

    ### AC自动机详解 #### 一、AC自动机概述 AC自动机,全称为Aho-Corasick自动机,是一种高效的多模式字符串匹配算法。它由Alfred V. Aho和Margaret J. Corasick在1975年提出,并在贝尔实验室首次发布。AC自动机主要...

    高效Java敏感词过滤系统AC自动机算法源码,支持独立部署与集成注册中心

    本项目是一款高效的Java敏感词过滤系统,基于AC自动机算法实现。系统支持独立部署,同时可便捷集成至注册中心,为各类项目提供敏感词过滤服务。包含文件共117个,其中主要构成如下: - Java源文件:49个 - Class...

    AC自动机模板

    **AC自动机(Aho-Corasick Algorithm)模板** AC自动机是一种字符串搜索算法,它在文本中查找多个模式串的出现情况。该算法由艾伦·科拉斯和戈登·科拉斯在1975年提出,是KMP算法和后缀自动机的结合,具有高效性和...

    AC自动机 C语言 ACM 字符串匹配|AC自动机C语言.rar

    AC自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于文本处理、数据挖掘等领域。它在ACM(国际大学生程序设计竞赛)中也是一项重要的算法技能,因为它能高效地解决字符串匹配问题,特别是面对...

    AC自动机pdf

    ### AC自动机详解及其在生物序列算法中的应用 #### 一、引言 AC自动机,也称为Aho-Corasick算法,是一种经典的字符串搜索算法,由Alfred V. Aho与Margaret J. Corasick于1975年提出。该算法主要用于在一个文本串中...

    自己写的ac自动机,STL实现

    相当给力,头文件中附带了简单的使用方法,使用istream当接口,因此你可以传入stringstream或fstream,甚至可以自己派生istream再传入,支持全文查找和增量查找两种模式,有问题可以联系我

    ac自动机java版

    AC自动机,全称为Aho-Corasick算法,是一种在字符串搜索中用于高效查找多个模式的算法。在Java编程环境中,AC自动机被广泛应用于文本处理、数据分析、搜索引擎等领域,尤其是处理大规模数据时,它的效率尤为突出。这...

    AC自动机AC自动机。。。。

    AC自动机AC自动机AC自动机AC自动机

    文学研究助手(AC自动机版本)

    文学研究助手,AC自动机版本,数据结构 利用AC自动机只对文件进行一次扫描,统计要查询的单词在文档出现的次数及所在行

    AC自动机程序资料合集

    AC自动机,全称为Aho-Corasick自动机,是一种在字符串匹配中高效查找多个模式的算法。这个程序资料合集包含AC自动机的实现代码和相关教程,旨在帮助学习者深入理解和应用这一技术。 AC自动机的核心思想是将所有待...

Global site tag (gtag.js) - Google Analytics