Java和JavaScript中Aho-Corasick算法实现

Aho-Corasick 算法 是一种功能强大的字符串搜索算法，可以有效识别给定文本中多个模式的出现。
该算法由 Alfred V. Aho 和 Margaret J. Corasick 于 1975 年开发，专为需要同时检测多种模式的场景而设计。

它是一种强大且高效的算法，用于搜索多个字符串文本中同时存在的模式。这使得它非常适合关键字搜索、抄袭检测和网络入侵检测等应用。

在搜索多个模式时，Aho-Corasick 算法比其他字符串搜索算法（例如 KMP 算法）更快。这是因为它可以避免重新匹配已经匹配的模式的前缀。

优点

  • 多种模式匹配的效率：Aho-Corasick 擅长处理需要同时与给定文本匹配多个模式的场景。其时间复杂度与输入文本的长度和模式的总长度呈线性关系。
  • 内存效率：该算法具有内存效率高，因为它使用 trie 数据结构来表示模式，并且失配failure函数通过 trie 优化遍历。
  • 多功能性：Aho-Corasick 具有多功能性，可以适应各种需要字符串匹配的应用。它的灵活性使其适用于从文本处理到生物信息学的不同领域。
  • 针对实际用例进行了优化：包含失配failture函数使该算法非常适合模式可能重叠或共享公共前缀的实际场景。这种优化减少了搜索过程中不必要的回溯。

应用领域
  • 字符串匹配和搜索：Aho-Corasick 广泛用于高效搜索给定文本中的多个模式。这使得它在识别多个关键字或短语的出现至关重要的应用程序中很有价值，例如在文本处理、数据挖掘和信息检索中。
  • 编译器中的词法分析：编译器使用词法分析来识别源代码中的关键字、标识符和其他语言结构。 Aho-Corasick可以用来在编译过程中有效地识别这些词汇元素。
  • 入侵检测系统 (IDS)：入侵检测系统监控网络流量以识别表明安全威胁的模式。 Aho-Corasick 用于高效搜索已知攻击特征，使其成为入侵检测系统中的重要组件。
  • 自然语言处理 (NLP)：在 NLP 中，Aho-Corasick 可用于命名实体识别等任务，其目标是识别预定义实体（例如名称） 、地点、组织）在给定的文本中。
  • 数据压缩：该算法可用于数据压缩算法，以有效地定位和替换重复模式，从而有助于压缩过程。


方法

  • 创建一个 trie 数据结构来存储模式，trie 中的每个节点代表模式中的一个字符。它是一种树状数据结构，用于存储要搜索的模式。 trie 中的每个节点代表一个模式的前缀。
  • 遍历 Trie：当您遍历文本时，您也遍历了 trie。对于每个模式，遍历trie树并根据需要创建节点。另外，将与每个模式关联的输出存储在 trie 节点中。
  • 匹配和输出：如果到达 trie 中的叶节点，则意味着您已找到其中一种模式的完全匹配项。然后您可以输出匹配项并继续遍历 trie。
  • 失效函数：Aho-Corasick 算法还使用“失配failure函数”来表示。以加快搜索速度。如果遇到与任何模式都不匹配的字符，此函数会告诉您在trie树中跳回多远。构建失配函数，并设置失效指针，以便有效处理不匹配问题。
  • 根据输入文本遍历trie。使用失配函数有效地处理不匹配。此外，还可以识别模式匹配并调用回调函数。
  • 创建 Aho-Corasick 类的实例。添加模式、构建失配failure函数并在给定文本中搜索匹配项。

在 JavaScript 中实现 Aho-Corasick 算法，可以使用以下步骤：

1、定义一个 Trie 类来存储模式。

class Trie {
  constructor() {
    this.root = new Node();
  }

  add(pattern) {
    const node = this.root;
    for (const char of pattern) {
      if (!node.children[char]) {
        node.children[char] = new Node();
      }
      node = node.children[char];
    }
    node.word = pattern;
  }
}

Trie 类包含一个 root 节点，它是所有模式的根节点。add() 方法用于将模式添加到 Trie 中。该方法从根节点开始，并在遇到模式中的每个字符时沿着 Trie 向下移动。如果 Trie 中没有与当前字符匹配的子节点，则会创建一个新子节点。

2、定义一个 Node 类来表示 Trie 中的节点。

class Node {
  constructor() {
    this.children = {};
    this.word = null;
  }
}

Node 类包含一个 children 属性，该属性存储了当前节点的所有子节点。word 属性存储了当前节点表示的模式。

3、定义一个 buildTrie() 函数来构建 Trie。

function buildTrie(patterns) {
  const trie = new Trie();
  for (const pattern of patterns) {
    trie.add(pattern);
  }
  return trie;
}

buildTrie() 函数接受一个模式数组作为参数，并返回一个构建好的 Trie。

4、定义一个 search() 函数来搜索模式

function search(trie, text) {
  const matches = ;
  let node = trie.root;
  for (const char of text) {
    if (!node.children[char]) {
      node = trie.root;
      continue;
    }
    node = node.children[char];
    if (node.word) {
      matches.push({
        pattern: node.word,
        start: matches.length ? matches[matches.length - 1].end + 1 : 0,
        end: matches.length,
      });
    }
  }
  return matches;
}

search() 函数接受一个 Trie 和一个文本字符串作为参数，并返回一个匹配的模式数组。该函数从 Trie 的根节点开始，并在遇到文本中的每个字符时沿着 Trie 向下移动。如果当前节点表示一个模式，则将该模式添加到匹配的模式数组中。

以下是使用 Aho-Corasick 算法搜索敏感词的示例：

const patterns = ["敏感", "词汇"];
const trie = buildTrie(patterns);
const text = "这是一个敏感词汇";
const matches = search(trie, text);

console.log(matches);

输出：

[
  {
    pattern: "敏感",
    start: 0,
    end: 2
  },
  {
    pattern: "词汇",
    start: 6,
    end: 9
  }
]


另外一种Javascript实现：

class AhoCorasickNode {
constructor() {
    this.children = {};
    this.output = ;
    this.failure = null;
}
}

class AhoCorasick {
constructor() {
    this.root = new AhoCorasickNode();
}

addPattern(pattern, output) {
    let node = this.root;

    for (const char of pattern) {
    if (!node.children[char]) {
        node.children[char] = new AhoCorasickNode();
    }
    node = node.children[char];
    }

    node.output.push(output);
}

buildFailureFunction() {
    const queue = ;

      // 将深度 1 节点的
failure
设置为根
failure
    for (const child in this.root.children) {
    this.root.children[child].failure = this.root;
    queue.push(this.root.children[child]);
    }

    while (queue.length > 0) {
    const currentNode = queue.shift();

    for (const key in currentNode.children) {
        const child = currentNode.children[key];
        queue.push(child);

        let failureNode = currentNode.failure;

        while (failureNode !== null && 
                !failureNode.children[key]) {
        failureNode = failureNode.failure;
        }

        child.failure = failureNode ?
                        failureNode.children[key] || 
                        this.root : this.root;

        child.output = child.output.
                        concat(child.failure.output);
    }
    }
}

search(text, callback) {
    let currentNode = this.root;

    for (let i = 0; i < text.length; i++) {
    const char = text[i];

    while (currentNode !== null && 
            !currentNode.children[char]) {
        currentNode = currentNode.failure;
    }

    currentNode = currentNode ? 
                    currentNode.children[char] || 
                    this.root : this.root;

    for (const output of currentNode.output) {
        callback(i - output.length + 1, output);
    }
    }
}
}

// 示例用法
const ac = new AhoCorasick();
ac.addPattern('he');
ac.addPattern('she');
ac.addPattern('his');
ac.addPattern('hers');

ac.buildAhoCorasick();

const text = 'hershey';
const matches = ac.search(text);

console.log('Text:', text);
console.log('Matches:', matches);[/i]

在 Java 中实现 Aho-Corasick 算法

    1、定义一个 TrieNode 类来表示 Trie 中的节点。

    public class TrieNode {

        private Map<Character, TrieNode> children;
        private boolean isWord;
        private String word;

        public TrieNode() {
            children = new HashMap<>();
            isWord = false;
            word = null;
        }

    }

    TrieNode 类包含一个 children 属性，该属性存储了当前节点的所有子节点。isWord 属性表示当前节点是否表示一个模式。word 属性存储了当前节点表示的模式。

    2、定义一个 Trie 类来存储模式。

    public class Trie {

        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void add(String pattern) {
            TrieNode node = root;
            for (char c : pattern.toCharArray()) {
                if (!node.children.containsKey(c)) {
                    node.children.put(c, new TrieNode());
                }
                node = node.children.get(c);
            }
            node.isWord = true;
            node.word = pattern;
        }

    }

    Trie 类包含一个 root 节点，它是所有模式的根节点。add() 方法用于将模式添加到 Trie 中。该方法从根节点开始，并在遇到模式中的每个字符时沿着 Trie 向下移动。如果 Trie 中没有与当前字符匹配的子节点，则会创建一个新子节点。

    3、定义一个 buildTrie() 函数来构建 Trie。

    public static Trie buildTrie(String patterns) {
        Trie trie = new Trie();
        for (String pattern : patterns) {
            trie.add(pattern);
        }
        return trie;
    }

    buildTrie() 函数接受一个模式数组作为参数，并返回一个构建好的 Trie。

    4、定义一个 search() 函数来搜索模式。

    public static List<Match> search(Trie trie, String text) {
        List<Match> matches = new ArrayList<>();
        TrieNode node = trie.root;
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (!node.children.containsKey(c)) {
                node = trie.root;
                continue;
            }
            node = node.children.get(c);
            if (node.isWord) {
                matches.add(new Match(i - node.word.length() + 1, i));
            }
        }
        return matches;
    }


    search() 函数接受一个 Trie 和一个文本字符串作为参数，并返回一个匹配的模式数组。该函数从 Trie 的根节点开始，并在遇到文本中的每个字符时沿着 Trie 向下移动。如果当前节点表示一个模式，则将该模式添加到匹配的模式数组中。

    以下是使用 Aho-Corasick 算法搜索敏感词的示例：

    String patterns = {"敏感", "词汇"};
    Trie trie = buildTrie(patterns);
    String text =     "这是一个敏感词汇";
    List<Match> matches = search(trie, text);

    System.out.println(matches);

    输出：
    [Match{start=0, end=2}, Match{start=6, end=9}]

    Java高级实现
    以下不是基于原始数组，而是基于Java集合概念的Aho-Corasick算法实现：

    import java.util.*;
    import java.util.regex.*;
    import java.util.stream.Collectors;

    class AhoCorasickNode {
        Map<Character, AhoCorasickNode> children;
        AhoCorasickNode parent;
        AhoCorasickNode suffixLink;
        AhoCorasickNode outputLink;
        char charToParent;
        boolean isEndOfPattern;

        public AhoCorasickNode() {
            children = new HashMap<>();
            parent = null;
            suffixLink = null;
            outputLink = null;
            charToParent = '\0';
            isEndOfPattern = false;
        }
    }

    public class AhoCorasick {
        private AhoCorasickNode root;

        public AhoCorasick() {
            root = new AhoCorasickNode();
        }

        public void addPattern(String pattern) {
            AhoCorasickNode node = root;
            for (char c : pattern.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new AhoCorasickNode());
                node.charToParent = c;
            }
            node.isEndOfPattern = true;
        }

        public void buildAhoCorasick() {
            Queue<AhoCorasickNode> queue = new LinkedList<>();

            for (AhoCorasickNode child : root.children.values()) {
                queue.add(child);
                child.suffixLink = root;
            }

            while (!queue.isEmpty()) {
                AhoCorasickNode currentNode = queue.poll();

                for (AhoCorasickNode child : currentNode.children.values()) {
                    queue.add(child);

                    AhoCorasickNode tempNode = currentNode.suffixLink;
                    while (tempNode != null && !tempNode.children.containsKey(child.charToParent)) {
                        tempNode = tempNode.suffixLink;
                    }

                    if (tempNode == null) {
                        child.suffixLink = root;
                    } else {
                        child.suffixLink = tempNode.children.get(child.charToParent);
                    }

                    if (child.suffixLink.isEndOfPattern) {
                        child.outputLink = child.suffixLink;
                    } else {
                        child.outputLink = child.suffixLink.outputLink;
                    }
                }
            }
        }

        public List<String> search(String text) {
            AhoCorasickNode currentNode = root;

            return text.chars()
                    .mapToObj(c -> (char) c)
                    .map(ch -> {
                        while (currentNode != null && !currentNode.children.containsKey(ch)) {
                            currentNode = currentNode.suffixLink;
                        }

                        if (currentNode == null) {
                            currentNode = root;
                        } else {
                            currentNode = currentNode.children.get(ch);

                            AhoCorasickNode outputNode = currentNode;
                            while (outputNode != null) {
                                if (outputNode.isEndOfPattern) {
                                    return getFullPattern(outputNode);
                                }
                                outputNode = outputNode.outputLink;
                            }
                        }

                        return null;
                    })
                    .filter(Objects::nonNull)
                    .collect(Collectors.toList());
        }

        private String getFullPattern(AhoCorasickNode node) {
            StringBuilder pattern = new StringBuilder();
            while (node != root) {
                pattern.insert(0, node.charToParent);
                node = node.parent;
            }
            return pattern.toString();
        }

        public static void main(String args) {
            AhoCorasick ac = new AhoCorasick();
            ac.addPattern("he");
            ac.addPattern(    "she");
            ac.addPattern(    "his");
            ac.addPattern(    "hers");

            ac.buildAhoCorasick();

            String text =     "hershey";
            List<String> matches = ac.search(text);

            System.out.println(    "Text: " + text);
            System.out.println(    "Matches: " + matches);
        }
    }

    实际中，建议使用现有的Aho-Corasick算法的实现，如Apache Commons Collections库中的AhoCorasick类。