java - 检查干草堆是否包含一组针的最快方法

Question

我有一个haystack string，我想检查它是否包含任何needle strings。目前我是这样做的:

Set<String> needles = ...;

...

String [] pieces = haystack.split(" ");
for (String piece: pieces) {
  if (needles.contains(piece) {
    return true;
  }
}

return false;

有效，但相对较慢。

问题:有没有更快的方法来完成任务？

示例。

 Haystack: I am a big tasty potato .
 Needles:  big, tasty

 == RUN ==
 I am a big tasty potato .
        |
        [tasty] got a match, we are good!

Answer 1

你应该看看Aho-Corasick算法。这适合您的问题，因为它构建了所有单词(针)的自动机并在构建的自动机上遍历文本(干草堆)以查找所有匹配的单词。它基本上构建了一个类似于 trie 的有限状态机。

时间复杂度为 O(n + m + z) 其中 z 是文本中单词出现的总数，n 是文本的长度，m 是所有单词中的字符总数。

编辑2

这是一个直接的实现，它在发现第一次出现任何针后停止遍历。

import java.util.*;

class AhoCorasick {

  static final int ALPHABET_SIZE = 256;

  Node[] nodes;
  int nodeCount;

  public static class Node {
    int parent;
    char charFromParent;
    int suffLink = -1;
    int[] children = new int[ALPHABET_SIZE];
    int[] transitions = new int[ALPHABET_SIZE];
    boolean leaf;

    {
      Arrays.fill(children, -1);
      Arrays.fill(transitions, -1);
    }
  }

  public AhoCorasick(int maxNodes) {
    nodes = new Node[maxNodes];
    // create root
    nodes[0] = new Node();
    nodes[0].suffLink = 0;
    nodes[0].parent = -1;
    nodeCount = 1;
  }

  public void addString(String s) {
    int cur = 0;
    for (char ch : s.toCharArray()) {
      int c = ch;
      if (nodes[cur].children[c] == -1) {
        nodes[nodeCount] = new Node();
        nodes[nodeCount].parent = cur;
        nodes[nodeCount].charFromParent = ch;
        nodes[cur].children[c] = nodeCount++;
      }
      cur = nodes[cur].children[c];
    }
    nodes[cur].leaf = true;
  }

  public int suffLink(int nodeIndex) {
    Node node = nodes[nodeIndex];
    if (node.suffLink == -1)
      node.suffLink = node.parent == 0 ? 0 : transition(suffLink(node.parent), node.charFromParent);
    return node.suffLink;
  }

  public int transition(int nodeIndex, char ch) {
    int c = ch;
    Node node = nodes[nodeIndex];
    if (node.transitions[c] == -1)
      node.transitions[c] = node.children[c] != -1 ? node.children[c] : (nodeIndex == 0 ? 0 : transition(suffLink(nodeIndex), ch));
    return node.transitions[c];
  }

  // Usage example
  public static void main(String[] args) {
    AhoCorasick ahoCorasick = new AhoCorasick(1000);
    ahoCorasick.addString("big");
    ahoCorasick.addString("tasty");

    String s = "I am a big tasty potato";
    int node = 0;
    for (int i = 0; i < s.length(); i++) {
      node = ahoCorasick.transition(node, s.charAt(i));
      if (ahoCorasick.nodes[node].leaf) {
        System.out.println("A match found! Needle ends at: " + i); // A match found! Needle ends at: 9
        break;
      }
    }
  }
}

但是目前这段代码会找到文本中任何出现的结束位置。如果需要起始位置和/或针，可以从结束位置回溯，直到找到一个空格来得到匹配的词。

这并不能保证最坏情况下的速度，但在平均情况和最佳情况下应该会表现得更好。