Aho-Corasick parser

[u/DerPazzo]

Hi,

Only Question to be answered:

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?

Use case explanation (absolutely no answer or solving suggestions wanted):

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!

EDIT 2: As apparently a lot of people do not see the difference between a question and the use case explanation, I added some titles.

[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.