Dependency Matcher execution time

[DavidGerva]

I am heavily using spacy Dependency Matcher (https://spacy.io/api/dependencymatcher) to extract information from long texts. Some executions take very long time, sometimes the execution does not even come to an end.

Is there a way to set a maximum execution time?
How can one interrupt the matcher?

[polm]

There is no way to set a timeout on the Matcher.

Usually the DependencyMatcher shouldn't be very slow. There are some exceptions that we've seen before - in the worst case, it is possible to get into an infinite loop if your dependencies have cycles. But spaCy's parser won't create Docs like that, so it should only happen if you're reading in dependencies from other sources.

Can you share more information about your data? Are you processing individual sentences or multi-page documents or ...? Are your sentences very long, like in a legal document or something? More info about your data (or, even better, a specific example) would help us figure out if this is a design limitation or a bug of some kind.

[DavidGerva]

I tried to reduce the problem at the minimum set-up. I hope this helps.
This is the pattern:

[
                {
                  "RIGHT_ID": "anchor_verb",
                  "RIGHT_ATTRS": {"POS": "VERB"}
                },
                {
                    "LEFT_ID": "anchor_verb",
                    "REL_OP": "$--",
                    "RIGHT_ID": "verb_subj",
                    "RIGHT_ATTRS": {"DEP": "nsubj"},
                },
                {
                    "LEFT_ID": "anchor_verb",
                    "REL_OP": ">",
                    "RIGHT_ID": "verb_conj",
                    "RIGHT_ATTRS": {"DEP": "conj"},
                },
                {
                    "LEFT_ID": "verb_conj",
                    "REL_OP": ">",
                    "RIGHT_ID": "conj_obj",
                    "RIGHT_ATTRS": {"DEP":  {"IN": ["pobj", "dobj"]}},
                },

            ]

I paste the text I am working on outside the forum, here: https://pastebin.com/SxKvaqTD. Too long to paste it here just for visual intent.
The text is quite long. But I don't think this is the problem because a slightly different pattern performs really well.

Thank you!

[polm]

So your input text is a single sentence that's like a thousand tokens. It looks like something from a patent application. For the record, we don't test on sentences like this.

The way the dependency matcher works is internally it uses a normal matcher to get candidate tokens using only the RIGHT_ATTRS. Then for each combination of those it checks whether the dependency relations are valid. For a normal sentence this is fine, but for a monster sentence like your sample I believe you are triggering a combinatorial explosion due to the number of tokens involved. I would need to look more closely to figure out all the details, but I think the issue is the cartesian product of matches here. (#6678 looks kind of similar, but I think that was a bug about checking across sentence boundaries.) I am not sure if it is possible to improve this, but we can look at it.

As for what you can do immediately, I would suggest changing your approach a little. I would start by either treating semicolons as sentence boundaries if you keep using the dependency matcher, or maybe instead walking the dependency tree manually, since for your sample pattern above the relations you want are pretty simple, and by using the tree directly you can avoid an explosion of complexity.

[DavidGerva]

Ok, thank you @polm I'll try to work on this as you suggested

[DavidGerva]

@polm I have a question for you. I have to work with a lot of long texts. And I posted here just one of the patterns I'm using in the matcher, the one giving the problem. I generally use 8/10 patterns. Probably simple, like the one above.
Would you suggest to work with the dependency matcher or with a navigation through the tree like you said above? I really don't know how to discriminate between this two way. Thank you, as always.

[polm]

Whether the DependencyMatcher will be slow with a long sentence or not depends on the details of the pattern and the sentence, so it's hard to give general advice. However looking at your example document and assuming it's typical, it looks like you have a lot of repetitive structures, which may mean the DependencyMatcher needs to sift through a lot of potential matches (= more work = slow).

If you already have working Matcher patterns, I would check if they work well enough or not, and only rewrite them if you run into speed issues.