2

I'd like to match a regex pattern on a stream, but I am not sure what algorithm to use. I certainly don't want to load the entire file into memory.

I tried to figure out how to do this, but I have only very basic ideas. For example I could concat the chunks into some sort of aggregate string as long as I find a match. After that I cut the aggregate at the end of the match and continue. But if there is no match I would end up loading the entire string into memory.

I could give a maximum size to the aggregate, but I might lose matches that way. Another issue that if there is a longer match starting in the same position, then I would miss that. So I guess this algorithm is incompatible with possessive quantifiers too.

Is there a better solution for this problem?

Improve this question
2
  • If you want to apply arbitrary regexps to strings which are so huge they fill up all the available memory, I am pretty sure you will run into trouble with any available Javascript regexp engine. Or do you want to implement your own engine? – Doc Brown Mar 19 '20 at 9:01
  • The typical way to do this is to know the longest possible match (a URL is probably less than 10K in length for example) And read the data by chunks into a circular buffer of at least double the max match length and after each load try to match the buffer. This works as long as the thing you are trying to match has a way to find the start and the end so that you know you are matching a complete item - in the case of JSON it is a starting :" and ending [^\\]" – Jerry Jeremiah Mar 19 '20 at 23:34
2

This is a hard problem. Regular expression engines come on twp flavors: NFA and DFA.

  1. DFA (deterministic finite-state automata) run efficiently and in limited space, but they cannot do the sort of thing you presumably want, such as capturing and backreferencing substrings of the input. If you only need to know whether the input matches, not where, they're the way to go.

  2. NFA (nondeterministic finite automata) fundamentally rely on being able to backtrack, i.e. to try something else with input that they have already consumed. And the problem is not limited to possessive quantifiers, but to most constructs: even (A|B) requires backtracking.

If there is any way you can limit the possible length of your matches, then it is almost certainly your best option to apply a normal match on overlapping chunks of size 2 * L than to change the way your regex engine works.

If you do have to change it, though, it would involve analyzing the regex or monitoring the progress of the engine to prove when previous input can no longer be part of any match, i.e. when the top-level backtracking has exhausted its alternatives. At that point you can discard characters and so limit the amount of memory required for the entire operation. But be aware that that would be a fascinating project, i.e. almost certainly outside the budget if you're just trying to get some random work task done.

Improve this answer
11
  • 6
    Actually, that is wrong. A pure Regex can be implemented without need for backtracking using either a Finite State Automata, or a Pushdown Finite State Automata. Take a look here at a good write-up by Russ Cox. – Kain0_0 Mar 19 '20 at 8:03
  • @Kain0_0 Sure they can, but typically you then lose the interesting functionality that you actually want while programming, such as capturing and backreferencing. I assume that OP wants to capture information, not just Booleans. – Kilian Foth Mar 19 '20 at 9:07
  • @KilianFoth Thanks! For my current case 14GB memory is not enough. I have a massive JSON and I want to extract URLs from it. I have the right constraints to be able to use what I wrote in my question, I was just curious if there is a general solution. According to your answer a non-backtracking regex engine would solve this. It is interesting, because I was looking for a way to solve the redos issue too. I did not realize there are engines without backtracking. github.com/uhop/node-re2 – inf3rno Mar 19 '20 at 10:27
  • @KilianFoth Warning sour ppl arrived to downvote. :D – inf3rno Mar 19 '20 at 10:30
  • 1
    @KilianFoth Again incorrect. Push down automata can stow position information in the stack, you can even stow the relevant pieces of information captured from the text and apply relevant transformations. Run these automata in parallel, sharing portions of the stack between instances. These can support look around, back reference, and CF Grammars. Need only provide group level operations such as branch, anchor, cut, join, token, and production-rule, that work on the group of automata branching from the same shared base stack. – Kain0_0 Mar 20 '20 at 0:02
6

In general, it is not a good idea to apply a regex to such a huge file at whole. In most real-world cases, files of that size have some kind of structure which can be used to split it into smaller strings in a streaming manner. Applying the regexes only for these "building blocks" will usually result in a way more performant and memory efficient solution.

For example, in a comment, you wrote

I have a massive JSON and I want to extract URLs from it.

Even without knowing the precise structure of that JSON file, I assume URLs can only occur in string literals. Hence, what you can do here is to

  • utilize a JSON streaming library like Oboe.js

  • implement a callback which is called for each string literal where an URL might be contained in the JSON. In that callback, use a regex to detect the URLs within the strings.

But this is just an example, you can probably apply this approach to many comparable use cases.

Improve this answer
4
  • I don't know the structure of the json and I don't want to care about that. I guess you missed the " I was just curious if there is a general solution" part... – inf3rno Mar 19 '20 at 13:47
  • You need to know the structure to be able to parse JSON. Or would you just traverse the whole thing and check every property if it is an URL? For me handling it as plain text is much simpler. – inf3rno Mar 20 '20 at 5:52
  • Another thing that I did not claim I need a solution for JSON files only. If I want to have a specific solution for my problem I write to stackoverflow not here, but I am perfectly capable of solving the problem on my own, I don't need proposed solutions for that. My question was about how to do this in general on plain texts, and I got an answer for that. Yours is just a comment and afaik posting comments as answer here should not be possible, so I'll flag this answer and let others decide about it. – inf3rno Mar 20 '20 at 6:06
  • Much better now, thanks! – inf3rno Mar 20 '20 at 12:24
1

I'm jumping the gun by posting here already since my code isn't published as a package yet (it will be @iter-tools/regex), but hey I'm bored and I'm working on my OSS projects full time so a v0.1.0 will be up soon.

I've implemented what I understand to be the (roughly) optimal strategy -- non-backtracking matching with NFAs and captures. In some of the materials here it seems to be referred to as Thompson NFA, though I came to my solution independently starting from simple boolean NFAs. Anyone who is interested can take a look at the code.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.