在大型文本文件中查找出现的模式（目前使用 Aho-Corasick）

Question

我有一个大文本 (5MB-500MB) 文件和一组几千个图案。对于每个模式，我想获取该模式在文件中出现的次数。文本不包含空格，是一个基本的长字母数字字符串。

为此，我尝试使用 Aho-Corasick 算法，特别是 Robert-Bor 的 Java 实现，它确实工作得足够快，但是有一个问题：用模式作为字符串计算发射的结果不等于用文本打开文本文件的结果记事本++等编辑器和统计模式。对我来说重要的是，计数的出现次数将恰好是在文件中找到的模式的次数。因此，我需要找到解决这个问题的办法。

为了实现我的目标，我可以对算法的实现进行更改吗？也许某种 EmitHandler 可以解决我的问题？我也愿意接受其他建议，例如替换 algorithm/solution 方法。然而，如果可能的话，我想继续使用 java，并尽可能快地获得结果（例如，发射指数对我来说并不重要）。

编辑：例如，即使是安装文件的以下小文本： File Link，模式：

5b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff

根据 emits 计数在文件中出现 150 次，但根据 Notepad++/Ctrl-f 在浏览器中的计数功能仅出现 10 次。

关于同一文本的另一个例子：

f34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0

根据发出计数出现99次，但根据文本编辑器计数仅出现10次。

Link算法执行，here。我目前运行基于实现：

  Trie trie = Trie.builder().addKeywords(wordsMap.keySet())
                        .build();
    Collection<Emit> ls2 = trie.parseText(str);``
            for (Emit e: ls2) {
                if (!map.containsKey(e.getKeyword()))
                      map.put(e.getKeyword(),1);
                else {
                    int val = map.get(e.getKeyword());
                    map.replace(e.getKeyword(),val+1);
                }
            }
            return map;

谢谢！

我也尝试过实现中可用的非重叠选项，但它不符合要求，而且对我的使用来说太慢了。

Answer 1

首先，当使用 ignoreOverlaps() 构建 Trie 时，不清楚该算法如何或为什么不满足您对正确性的需求。不过，我相信你的话。当您说在这种情况下对性能有影响时，我也愿意相信您。

所以，与其深入研究算法的实现，不如将其与重叠一起使用，然后手动删除重叠。在这种情况下，我认为您将能够微调哪个发出以跳过。

这是初始化 Trie 的代码：

String text = ... // read the text somewhere

Set<String> keywords = new HashSet<>();
keywords.add("keyword1");
keywords.add("keyword2");

Trie trie = Trie.builder().addKeywords(keywords).build(); // with overlaps!

现在，让我们解析文本：

Collection<Emit> parseResults = trie.parseText(text);

据我所知，解析结果是按文本中出现的顺序返回的，但我还没有对此进行彻底的测试。为了使下面的代码正常工作，我们需要按开始索引对发射进行排序。

鉴于发射是按起始索引排序的，这里是计算每个关键字的非重叠发射的代码：

Map<String, Long> map = parseResults.stream()
    .collect(Collectors.groupingBy(Emit::getKeyword, countingNonOverlaps()));

其中countingNonOverlaps()实用方法如下：

private static Collector<Emit, ?, Long> countingNonOverlaps() {

    class Acc {
        Emit last;
        long count = 0;

        void add(Emit e) {
            if (last == null || !last.overlapsWith(e)) { count++; last = e; }
        }

        Acc merge(Acc another) {
            throw new UnsupportedOperationException("Parallel not supported");
        }
    }
    return Collector.of(Acc::new, Acc::add, Acc::merge, acc -> acc.count);
}

此方法使用自定义收集器来计算每个关键字的非重叠发射次数。还有其他更简单的方法可以在没有自定义收集器的情况下执行此操作，但它们需要保留每个关键字的非重叠发射列表。由于您只需要计数，并且您正在处理 2000 个关键字和大量文本，因此我认为这种方式更好。

收集器基本上跟踪收集的最后一个非重叠发射，并且仅当当前发射不与最后一个非重叠发射重叠时才增加对当前收集的发射的计数。此外，它仅适用于顺序流。

注意：如果计数器递增时需要微调，可以自定义Acc本地class.

的add方法

在大型文本文件中查找出现的模式（目前使用 Aho-Corasick）

Finding Patterns Occurrences In A Large Text File (Currently With Aho-Corasick)

java

search

pattern-matching

trie

aho-corasick