Поиск шаблонов в большом текстовом файле (в настоящее время с Aho-Corasick)

Question

У меня большой текстовый файл (5-500 МБ) и набор из нескольких тысяч шаблонов. Для каждого шаблона я хочу получить количество вхождений шаблона в файл. Текст не содержит пробелов и является базовой длинной буквенно-цифровой строкой.

Для этой цели я пытался использовать алгоритм Aho-Corasick, в частности Java-реализацию Robert-Bor, и он действительно работает достаточно быстро, но есть проблема: результат подсчета выбросов с шаблоном, поскольку их строка не равна результат открытия текстового файла с помощью текстового редактора, такого как notepad++, и подсчет шаблона. Для меня важно, что количество подсчитанных вхождений будет точно таким же, сколько раз шаблон найден в файле. Поэтому мне нужно найти решение этой проблемы.

Могу ли я внести изменения в реализацию алгоритма, чтобы достичь своей цели? Может быть, какой-нибудь EmitHandler решит мою проблему? Я также открыт для других предложений, таких как замена алгоритма / метода решения. Тем не менее, я хочу остаться с Java, если это возможно, и получить результаты как можно быстрее (например, индексы выбросов не важны для меня).

---

Редактировать: например, даже небольшой следующий текст установочного файла: ссылка на файл и шаблон:

5b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff

который в соответствии с числом выбросов появляется в файле 150 раз, но появляется только 10 раз в соответствии с функцией подсчета Notepad++/Ctrl-f в браузере.

И еще один пример того же текста:

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;

Спасибо!

Я также попытался использовать неперекрывающуюся опцию, доступную в реализации, но она не соответствует требованиям, а также слишком медленная для моих целей.

Answer 1

Прежде всего, не ясно, как или почему алгоритм не соответствует вашим потребностям в отношении корректности, когда 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 местный класс.