r/regex • u/DerPazzo • 7d ago
(Resolved) using backreferences for list of words
Hi,
#### not possible as explained by rainshifter ####
#### original flair was .NET ####
I want to create a huge regex to match exact word groups coming from a list of around 7k words.
It’s about chemical names and there are lots of repeated words at the end of the names. The names must always be exact matches and possible variations not on this list are not allowed. I thought about using backreferences wihtin the regex in order not to have to rewrite these words every time.
Will that even work?
Is this a good idea or will it slow down my search?
In the following example list I would like to use the first occurence of EXTRACT as a backreference for all following words within the pipe ending on EXTRACT. It’s mainly about back references for the endings as the start of the word groups is created as efficient as possible with pipes forking at every difference of a word:
\b(A(BIES (ALBA SEED EXTRACT|(BALSAMEA ((BALSAM )?EXTRACT|NEEDLE OIL)|KOREANA LEAF EXTRACT|SIBIRICA (NEEDLE )?OIL))|CACIA CATECHU (BARK POWDER|WOOD EXTRACT)))\b
Using brackets around the first occurence of EXTRACT creates backreference \4 but using it further down the regex does not seem to work. (see regex below)
\b(A(BIES (ALBA SEED (EXTRACT)|(BALSAMEA ((BALSAM )?EXTRACT|NEEDLE OIL)|KOREANA LEAF EXTRACT|SIBIRICA (NEEDLE )?OIL))|CACIA CATECHU (BARK POWDER|WOOD \4)))\b
List:
ABIES ALBA SEED EXTRACT
ABIES BALSAMEA BALSAM EXTRACT
ABIES BALSAMEA EXTRACT
ABIES BALSAMEA NEEDLE OIL
ABIES KOREANA LEAF EXTRACT
ABIES SIBIRICA NEEDLE OIL
ABIES SIBIRICA OIL
ACACIA CATECHU BARK POWDER
ACACIA CATECHU WOOD EXTRACT
3
u/Brilliant-Parsley69 6d ago edited 6d ago
I've a couple of thoughts on this:
Backreferences aren't equal to macro variables! That's why '\4" will never be related to the literal characters "EXTRACT".
If I understood correctly what's the problem you want to solve then I would suggest to take a look at the "Aho-Corasick"-Algorithm.
What brings me to your .Net7 flag. Because this algorithm is implemented internally from .Net8 onwards by using
csharp
SearchValues.Create(IEnumerable<string>)
If you just want to validate a single provided string against 7000 possible variations an in-memory HashSet should be more than enough.
There are concepts like "Prefix Trie Regex" to solve this programmatically if regex is the only possible way to do. But that's way over my head.
1
u/DerPazzo 6d ago edited 6d ago
Well, I can go up to .NET10 (unfortunately .NET7 is the only .NET flair available for this sub) but it must be a regex string. The alternative is a list converted to a piped regex by the software itself. So other variants will not work for this use case.
Regarding the Aho-Corasick algorithm: without knowing this algorithm beforehand (I just looked it up with an example), I used it in my regex so far as this way of backfall seemed the most logic way to handle it. Wanting backreferences to use placeholders would just have been a way more efficient way of handling it, if it would be possible. But according to rainshifter’s explanation, I now know why it cannot work. Sad, but at least I tried it.
2
u/Brilliant-Parsley69 6d ago
Well, that's a big requirement to solve this. The "Aho-Corasick" algorithm would normally be defined as a vector based solution to your problem.
But you found a solution, learned something about new algorithms, also reached the boundaries of this ecosystem while understanding the reasons.
I would call this a win. ✌️
1
2
u/mfb- 6d ago
Don't ask x-y questions: What is the original problem you want to solve? You have 7000 words, you want to match all lines where every word is taken from these 7000? Your regex isn't doing that, however, it looks for specific orders of multiple words.
Do you have 7000 lines in a file and you want to match all lines that match one of these 7000? In other words, you want to find lines in file A that also exist in file B? There are tools for that but regex isn't the right approach. If order doesn't matter, here are some quick ways by sorting the files first.
Do you want to do something else?
If you just want to save on characters, (?(DEFINE) ) can do that: https://regex101.com/r/xabonE/1
1
u/DerPazzo 6d ago edited 6d ago
Hello mfb,
don’t get me wrong, but telling people not to ask questions if they are trying to solve something, where they have an idea but don’t know if it’s possible, and if then how is a bit harsh.
How are we supposed to learn something new then?
When I woke up today, I was thinking about whether it would be possible to define backreferences in a regex beforehand.
The funny thing is, you come up with such a solution but for PCRE. I wonder if DEFINE is also possible with .NET (which was the initial flair, before I set it to solved. Thinking about flair as I changed it, the post no longer shows the flavor, so I’ll have to edit it.). I’ll be looking into this.
Well the problem is that I’m bound to regex with this tool, so other approaches are not possible. Sorting of the file is not possible either as the text to be searched will not contain a list per se but rather contain these terms randomly.
As explained in another answer, I follow an aho-Corasick algorithm approach to solve it, and it works, but it’s a bit difficult to set up within Regex as you easily lose the overview. ^^
2
u/mfb- 6d ago
I'm not saying you shouldn't ask questions. I'm saying you shouldn't ask x-y questions.
Tell people your original problem Y. You think you can solve problem Y with approach X, but you don't know how to do X either, so you ask about X. But what if X was never the right approach to do Y anyway? Then we all waste our time on X, which might not even have a solution, and you make no progress on your original problem.
1
u/DerPazzo 6d ago
Yes, but what if there is a solution the OP did not think of or his approach just contains a minor error? Then they’ll never learn about it.
Just like in this case, the error was that I did not realize that the backreference would never fire as I did not correctly know how these backreferences really work.
Thus with rainshifter’s explanation I realized I could not solve it the way I thought and this kind of solved my problem.
Furthermore Brillian-Parsley69 offered me some other approach on how to solve it. If I would not have it already partly implemented, I’d certainly have gone for it.
2
u/mfb- 6d ago
Yes, but what if there is a solution the OP did not think of or his approach just contains a minor error? Then they’ll never learn about it.
???
That's my point. Write the original problem you want to solve. You can also show what you tried to solve that problem, but the original problem description is by far the most important part.
Thus with rainshifter’s explanation I realized I could not solve it the way I thought and this kind of solved my problem.
Not the one that needed solving...
Furthermore Brillian-Parsley69 offered me some other approach on how to solve it.
Because they made a guess what you might want to do and happened to be right.
1
u/DerPazzo 6d ago
Apparently .NET does not support the DEFINE syntax at least that’s what RegexBuddy coverter shows.
1
u/michaelpaoli 7d ago
Well, somebody ignored rule #3 again, so ... dealer's choice, I'm dealing, I pick ... PCRE ... which also seems likely reasonably consistent with the post (e.g. post includes \b, which I believe was first introduced with PCRE.
So, yeah, in general will work.
$ printf '%s\n' 'one two three four five six four' | perl -ne 'print "\$1>$1 \$2>$2 \$3>$3 \$4>$4 \$5>$5 \$6>$6\n" if /(one) (two) (three) (four) (five) (six) \4/;'
$1>one $2>two $3>three $4>four $5>five $6>six
$
2
u/DerPazzo 6d ago edited 6d ago
Hi Michael,
How am I ignoring rule 3 if I use mandatory flair to point at the flavor? oO Flair clearly stated .NET.
1
1
u/DinTaiFung 6d ago
When I first learned regex (during my perl days long ago), I was infatuated and thought that regex was the solution for many problems -- and it was my first choice.
After years of maturing (I hope) and learning more, I now think of regex as the _last_ choice to solve a problem.
Don't get me wrong: regex are very powerful and can do many things.
No doubt writing a regex to solve your specific task will help you learn more about regex -- and hopefully you'll also discover that eschewing regex altogether and instead writing explicit iterative loops with dynamic lookup maps, etc. will likely be a stronger and better solution for this task.
3
u/rainshifter 6d ago
What you really want is a subroutine (such as
(?4)in PCRE), not a backreference. The .NET flavor does not support this. The reason your\4doesn't match is because the corresponding group(EXTRACT)was never matched in that last string so your backreference text is essentially empty.