Speed up the detection process

[sasi143]

First of all, really appreciate your work and time.

With small input data patterns, it is doing a good job, but when input data patterns crossing more than 1 lakh, it is taking too much time. Is there any possibility which can speed up the process (maybe using on GPU)

[gandersen101]

Hi @sasi143, thanks for your interest in Spaczz. I am very interested in improving the speed of the fuzzy matching process, however, for reasons I'll outline below, I unfortunately do not think this will happen in the near future without additional contributor(s).

I believe the performance bottleneck(s) in spaczz's fuzzy matching come from the amount of time the code spends in pure Python iterating through and processing text and potential matches. I do not believe the fuzzy comparisons themselves are a bottleneck because they are done with RapidFuzz which is already written in C++. I do need to do some profiling to confirm this though.

The pattern that spaCy proper uses to achieve it's rapid speed is dropping most of it's internal text processing code to C, and that is the pattern I would eventually like to follow. Unfortunately, I have almost no experience with C/C++, so without help from additional contributor(s) with C/C++ experience, my progress will be quite slow. That being said, I do intend to work on it myself, I just can't make any promises about timelines. Also, while I think incorporating GPU support is an interesting idea, to be honest I have even less of an idea about how to implement that than dropping portions of the code down to C/C++.

In the shorter term here are some possible actions:

1. Raise the min_r1 threshold from the current value of 25 for your patterns. min_r1 is essentially a trade-off between speed and accuracy. Raising it will mean some potential matches will be missed because they won't be passed to further match optimization, but raising it should result in modest speed increases. Look at the documentation for the FuzzySearcher for details on min_r1 and the documentation for the FuzzyMatcher and SpaczzRuler for how to incorporate this into your patterns or change the default value for all patterns in an instance of those classes.
2. Think about rewriting some of your fuzzy patterns as fuzzy regex patterns, look at the "Approximate “fuzzy” matching" section in the Regex package documentation. spaczz supports these kind of patterns and they will likely run faster as Regex is mostly implemented in lower-level code.
3. I can run some profiling on spaczz to confirm my hypothesis of where the bottleneck(s) are. In addition I may discover some "easy-wins" where I have written something inefficiently even for Python.
4. I can try to rethink/redesign aspect of the fuzzy matching algorithm to potentially reduce the number of comparisons it currently does.

I'm sorry I can't give you a more definite solution or timeline right now. Hopefully as people continue to discover/use spaczz some more experienced programmers may become interested in contributing. As things stand, I will slowly be working on accomplishing these speed improvements myself.

I'll use this issue as a place to keep track of these updates as they come.

[sasi143]

@gandersen101 Really thankfull to your well explaination and appreciate for your time. Keep doing good work and stay safe.

[gandersen101]

Issue #41 has turned into a performance discussion and I am planning to make some performance improvements very soon. I will provide a summary of those changes on this thread soon.

[kwhumphreys]

@gandersen101 Thanks for the inspiration. I started a low-level integration of rapidfuzz into spaCy, to attempt to improve performance explosion/spaCy#11359
Any thoughts/ideas welcome there.

[gandersen101]

@kwhumphreys very cool. Best of luck! Obviously I have not put much time into spaczz over the past couple years but the functionality is something people have been looking for. Hopefully you can get an official implementation into spaCy proper.

I'm going to add an announcement to the README - essentially I intend to address some issues/ add some functionality with spaczz going forward but I don't know if I'll ever have the time to "Cythonize" this library to extent that it's fast-enough for many use-cases.