3

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

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

为了实现我的目标，我可以在算法的实现中做出改变吗？也许某种 EmitHandler 可以解决我的问题？我也愿意接受其他建议，例如替换算法/解决方案方法。但是，如果可能的话，我想继续使用 java，并尽可能快地获得结果（例如，发出索引对我来说并不重要）。

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

5b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff

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

以及同一文本的另一个示例：

f34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0ff34a6e0

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

链接到算法的实现，在这里。我目前基于实现运行的内容：

  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;

谢谢！

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

4

1 回答 1

2

首先，当Trie使用ignoreOverlaps(). 不过，我相信你的话。当您说在这种情况下对性能有影响时，我也愿意相信您。

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

这是初始化的代码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 个关键字和大量文本，因此我认为这种方式更好。

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

注意：如果需要在计数器递增时进行微调，可以自定义本地类的add方法。Acc

于 2018-09-26T20:03:09.103 回答