cloudflare / cloudflare/ahocorasick

Doesn't support incremental string matching

Open
#14 1 comment 1 reaction 0 assignees View on GitHub
Dominant language
Go
Stars
727
Forks
108
PR merge metrics
No merged PRs in 30d

Description

The algorithm assumes that the dictionary is fixed. I've found that in practical applications it may happen that the user needs to add new strings to the keyword dictionary and have the matching algorithm be able to start matching those on the fly.

This problem has been studied and a modification to the Aho Corasick algorithm to make it support incremental matching has been proposed by Bertrand Meyer in his article ["Incremental string matching"](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.9962&rep=rep1&type=pdf).

I've made several modifications to the implementation in [my fork ](https://github.com/issamemari/ahocorasick), among which is adding the possibility to do incremental string matching as described in Bertrand's article.

I'm happy to submit a PR with only the changes related to this.

Contributor guide

Open the contributing guide

Research direction

Start by reading the repository's existing Aho-Corasick implementation and the linked Bertrand Meyer article. Compare the current fixed-dictionary behavior with the proposed incremental approach and the fork's related changes. Done means newly added dictionary strings can be matched while the algorithm is running, with behavior consistent with the article.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.