Обновление дерева Aho-Corasick перед лицом вставок и удалений

Question

Вся литература и реализации, которые я нашел в Aho-Corasick, посвящены предварительному построению всего три из набора фраз.Однако мне интересны способы работы с ней как с изменяемой структурой данных, где она может обрабатывать случайные добавления и удаления без необходимости перестроения всего дерева (представьте, что в нем содержится 1 миллион записей).Это нормально, если худший случай ужасен, если средний случай близок к логарифмическому.

Насколько я понимаю, состояние отказа для каждого узла - это другой узел, который использует тот же символ.Поэтому, если у нас есть хэш-карта из каждого символа в список узлов, которые используют этот символ, у нас есть кандидаты, для которых необходимо обновить состояние отказа.

Удалить - просто.Вы найдете все другие узлы, которые используют удаленный узел в качестве состояния сбоя, и повторно вычислите их состояние сбоя.Идите от конца строки назад, и дерево должно все еще быть в хорошей форме.

Добавить немного сложнее.Любой узел, который потерпел неудачу с этим символом, может иметь новый узел в качестве лучшего кандидата.Однако, опять же, кажется достаточным для прохождения каждого другого узла с этим символом и полного пересчета его состояния отказа.

Другими словами, если мы добавляем или удаляем узел с символом«A», нам нужно посетить любой другой узел «A» в любом месте дерева и пересчитать состояние сбоя (найдите его ближайшего предка с «A» в качестве дочернего или корневого элемента).Это потребовало бы посещения каждого узла для символа «A», но в моем случае это было бы на несколько порядков меньше, чем посещение каждого узла в дереве.

Будет ли этот алгоритм работать или я упустил что-то очевидное

Answer 1

Я пошел дальше и реализовал его, и он кажется работает. Несколько более приятное описание алгоритма, включая картинки: https://burningmime.gitlab.io/setmatch/implementation-overview.html#supporting-add-remove-in-an-aho-corasick-trie

Для потомков (и согласно политике StackOverflow) я скопировал его здесь:

Он поддерживает модификацию (добавление / удаление) вместо того, чтобы создавать все в один раз из предустановленного словаря. Это не упоминается ни в одной литературе об этом, и все реализации с открытым исходным кодом, которые я видел, имеют последовал в этом отношении. Оказывается, что поддержка добавить и удалить Операции с автоматом переменного тока довольно тривиальны. Для глубоких попыток над маленький алфавит, это было бы не очень эффективно, но, к счастью, мы мелкий шрифт над большим алфавитом.

Мы сохраняем хэш-карту каждого токена для каждого узла, который его использует маркер. Когда мы удаляем фразу, мы начинаем с последней (самой нижней) узел. Мы удаляем указатель на фразу из этого самого нижнего узла. Тогда, если у него есть дети, мы не можем больше удалять. В противном случае, иди через каждый другой узел, который использует этот узел в качестве состояния сбоя и пересчитать его состояние сбоя. Наконец, удалите узел, затем перейдите к родительский узел и сделать тот же процесс. В конечном итоге мы достигнем узел с выходом другой фразы, дочерний или корневой узел.

Это довольно сложно изобразить, так что подумайте об этом из статьи в Википедии). Мы собираемся удалить строку CAA (светло-серый цвет), который потребует, чтобы состояние отказа было желтым обновляться:

Результат:

Обратите внимание, что в некоторых случаях состояние сбоя узла может быть обновлено 2 или больше раз в той же операции удаления, но в конечном итоге будет правильный. Этого можно избежать, сначала удалив все, затем возвращаясь через токены, но код достаточно сложен, так как есть, и это только обеспечит выигрыш в производительности в определенных неуклюжие обстоятельства, будучи ударом производительности в среднем дело. Мы просто предполагаем, что строки, содержащие один и тот же токен больше, чем один раз редки.

Добавление узла немного сложнее, но может использовать тот же хэш многокарточной структуры. Каждый раз, когда добавляется узел, каждый второй узел в дереве, которое использует тот же токен и находится на более низкой глубине, чем добавленному узлу может потребоваться обновить его состояние отказа до нового узла.

Чтобы представить это, представьте, что вы переходите от второй диаграммы к первая диаграмма. Те же два состояния неудачи - это те, кто должны быть обновлены, если добавить строку CAA обратно в этот три, и поскольку мы пересчитываем каждый c и узел, это не проблема.

Мы могли бы отслеживать глубину узла, чтобы пропустить около половины, но сейчас это просто пересчет состояния отказа для каждого узла, который делится токеном для сохранения памяти. Это означает, что пытается где токены, которые появляются много раз, будут медленно добавляться, но опять же, это считается достаточно редкой ситуацией. Было бы беспокойство, если бы вы были пытаясь адаптировать эту технику к чему-то вроде последовательности ДНК или антивирусная база, где есть маленький алфавит.

Сложность времени зависит от того, сколько узлов совместно используют символы и как глубоко, это означает, что это наихудший O (N), но на практике довольно небольшое число (средний случай - примерно O (log ^ 2 N)).

Невероятно грязный и в основном некомментированный код, но если вам интересно, вот заголовок , тело и некоторые тесты