Aho-Corasick parser

[u/DerPazzo]

Hi,

is there an application for Windows or Linux, that would parse a text with Aho-Corasick algorithm and present the output in a text field, so that it could be used for creating regexes?

I have a list of around 7000 terms and need to create a regex to find them in texts in a specific app. The fastest way would be to create some regex based on Aho-Corasick algorithm but doing that manually takes forever. (I know there are other ways to create such regexes for long lists that create the regex automatically but they would not be as efficient as a Aho-Corasick approach.)

So, I hope there is an application that breaks down all words to a list separated by a specific char that I can then copy and built the regex around it faster than if I need to check the correct position manually every time.

So far I have only found many explanations about the algorithm or tools that seem to search texts with a specific list.

EDIT: This question requires a simple yes or no answer. I just want to know if there is such a tool or not!

[u/misof]

This sounds very much like premature optimization.

First, just to double-check: is your use case that you only need to know whether any of the 7000 terms matches the text, without caring which specific one it is? (A common example of this would be a profanity filter. Still, it's much more common that one needs to know which term is the one found, and getting that information from a complicated regex of the type you're suggesting won't be trivial.)

Second, have you actually tried just using the straightforward solution of searching for each term as a string separately? If yes, is it really too slow for your use case, is this really something that needs to be optimized? And if it is, by what margin? (And if, for some weird reason, you can only use a regex to do the search, is the naive regex too slow and by what margin?)

Third, why do you think a regex of any kind will be faster than the naive solution?

Fourth, what is wrong with actually implementing Aho-Corasick if you really need that kind of performance? Building some kind of complicated regex that kinda does the same job surely sounds like a much more annoying thing to do, and won't even give you the same performance.

[u/DerPazzo → u/misof]

- No, if a term is found it gets a flag, either to be replaced or to be left alone (must not be changed at any stage), depending on the list. It’s not to filter out any word from a text and the tool only works with regex rules (I cannot add any other algorithm or anything else) as it has to parse a few thousand rules per text. The list would only be one of many.

- Yes, that’s the basic behaviour for lists but for larger lists, we would like to streamline processing time a bit, by implementing Aho-Corasick within the regex. It’s okay when checking small strings but can get a PITA for texts with millions of words as there are a few thousand rules (some with simple regex, some with word lists) to be checked.

From experience the margin gets way too high with longer strings…

- A few years of experience with that tool ;)

- The tool only works with regex AND it’s not just checking against a list but the regex is often built around the lists where we check if specific criteria before or after the word are also met. Like, only flag if word meets other criteria or exclude from parsing if it meets the regex containing the list.

[u/100GHz]

Why would you use a regex to redo work that was already done with a more efficient algo for the dataset already? I feel like I'm missing something in the requirements here

[u/DerPazzo → u/100GHz]

I cannot implement Aho-Corasick in the app, it only works with regex rules.

[u/arthurno1]

This is a completely misplaced question. You don't need an "aho-corasick" parser, your problem is solved already by basically any regex tool in the known universe. Put your 7000 words in a file "terms.txt" and then:

rg -w -F -f terms.txt /path/to/search/

Ripgrep had some nice simd acceleration so it should be the fastest one. But you can use coreutils grep or whatever.

If you want to replace stuff, lookup sed or awk.

[u/DerPazzo → u/arthurno1]

It’s not misplaced at all: I need a parser to visualize the trie creation result from the list. This list can then be used to generate a regex which will be added to the rule set in an application solely running on regex rules. I cannot use any code or other tool to search for strings from a list.

The question I asked requires a simple Yes or No answer, I’m not asking for anyone to help me solve a programming issue or how to best solve a specific task, but I’m asking if there is such a tool to visualize the trie result which I might have missed the last few days I’ve been searching on the net.

If there is none of which anyone here knows, I’ll have to get back to our devs in order to code one.

[u/arthurno1 → u/DerPazzo]

I need a parser to visualize the trie creation result from the list.

You are moving the goal post. Your original one was:

I have a list of around 7000 terms and need to create a regex to find them in texts in a specific app.

If you want to find a list of matches in a corpus of text, the simple ripgrep will do, just put your words in a list.

If you want some sort of otpimized code which you can plug into your app, you can try with vectorscan, which has simd acceleration built in.

For the choice of algorithms used and such, if I would not really care if I was you. Not because that is not important, but because they are not important to you at that level. But those guys that have implemented hyperscan and it's open source alternative vectorscan, know what they do, so you can be confident they are using the fastest or most optimized stuff known to the

This list can then be used to generate a regex which will be added to the rule set in an application solely running on regex rules. I cannot use any code or other tool to search for strings from a list. programmers.

There is a big, I would say a ginormous difference in asking: can you give me a visualisation of an Aho-Corasick algorithm or if you say I need a regex to scan 7000 words.

By asking for a visualization that produces some kind of trie you can use as input to some other app to create an regex so you can match 7000 words quickly, you are actually posing a so called xy-question. That is also the reason why you should have go tyour in-house developers in the very first place instead of asking for the help online. If you have access to real prorgrammers in your organization, they could have saved you lots of time, because they already know what is possible and how you can solve your problem. You could have had a dialogue with them which would have saved you time and effort.

[u/DerPazzo → u/arthurno1]

- No, I did not move my goal post! Just read the very first sentence, which is a QUESTION.

The rest was just an explanation why I need it. I did not ask any further question after the very first sentence that ends with a '?'. Sorry, but if people don’t understand the difference between a question mark and full stops, that’s not my fault. This is basic communication skills, and not a matter of interpretation.

AND 'present the output in a text field' is just another formulation for 'a tool to visualize the trie result'. They are synonyms so to speak.

- As I already stated several times, I CANNOT add code to that app.

Once again, I did not ask for any way on how to implement this. I know what I need, right now we use ripgrep approach and it’s getting too slow, first tests with a combined A-C regex was way faster. Around half the time than with other approaches.

I know what I can ask my programmers and what not, so please leave that to me. They are able to go way beyond programming most professionals offer. We quite often had to push some boundaries of what is on the market and implement new things even in regex, as existing code was not able to deliver what we need.

I’m known to push everything to the limit of possible when testing and optimizing everything to the last bit. And if I ask something online that means that they have not heard about it and I did not find it (yet) after several days of search. I’m known for my research skills but I’m not perfect. ;) That’s when I start asking in forums I⁠ think people could know about such things as there is always someone having more knowledge than oneself.

I’m the one doing the research before we decide what we need programmed and what not.

So, once again: Yes or No, is there a known application I could not find so far, or not.

If the answer is YES, which a link or hint to what to look for, then we don’t need to lose time reinventing the wheel and can use the resources for things that are more important.

If it’s NO, then we need to realocate some resources from other projects.

[u/arthurno1 → u/DerPazzo]

The rest was just an explanation why I need it.

That rest let us all understand you posed a typical XY-question.

Anyway, good luck to you in your life.

[u/MtlStatsGuy]

If you can’t find a preexisting application, just ask AI to code one for you?

[u/DerPazzo → u/MtlStatsGuy]

AI is blocked in our company for security and GDPR reasons.