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

Question

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

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

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

---

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

5b4e5ff55b4e5ff55b4e5ff55b4e5ff55b4e5ff55bee5b5e5b555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555 5

, который в соответствии с числом излучений появляется в файле 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.