Speeding up “suggest” with python-Levenshtein (DEPRECATED)
sphobjinv uses fuzzywuzzy for fuzzy-match searching of object
names/domains/roles as part of the
Inventory.suggest() functionality,
also implemented as the CLI suggest subcommand.
fuzzywuzzy uses difflib.SequenceMatcher
from the Python standard library for its fuzzy searching.
While earlier versions of sphobjinv were able to make use of
fuzzywuzzy‘s optional link to python-Levenshtein,
a Python C extension providing similar functionality,
due to a licensing conflict this is no longer possible.
sphobjinv now uses a vendored copy of fuzzywuzzy from an
era when it was released under the MIT License.
Formally:
Removed in version 2.2: Acceleration of the sphobjinv “suggest” mode via python-Levenshtein
has been deprecated and is no longer available.
The discussion of performance benchmarks and variations in matching behavior is kept below for historical interest.
Performance Benchmark
The chart below presents one dataset illustrating the performance enhancement
that can be obtained by installing python-Levenshtein.
The timings plotted here are from execution of
timeit.repeat() around a
suggest() call,
searching for the term “function”, for a number of
objects.inv files from different projects (see
here).
The timings were collected using the following code:
import sphobjinv as soi
durations = {}
obj_counts = {}
for fn in os.listdir():
if fn.endswith('.inv'):
inv = soi.Inventory(fn)
# Execute the 'suggest' operation 20 times for each file
timings = timeit.repeat("inv.suggest('function')", repeat=20, number=1, globals=globals())
# Store the average timing for each file
durations.update({fn: sum(timings) / len(timings)})
# Store the number of objects
obj_counts.update({fn: inv.count})
As can be seen, the fifty-two objects.inv files in this dataset contain widely varying numbers of objects \(n\):
Unsurprisingly, larger inventories require more time to search.
Also relatively unsurprisingly, the time required appears to be
roughly \(O(n)\), since the fuzzy search must be performed once on the
as_rst representation of each object.
For this specific search, using python-Levenshtein instead of
difflib decreases the time required from 0.90 seconds per thousand objects
down to 0.15 seconds per thousand objects,
representing a performance improvement of almost exactly six-fold.
Other searches will likely exhibit somewhat better or worse
improvement from the use of python-Levenshtein,
depending on the average length of the reST-like representations
of the objects in an objects.inv
and the length of the search term.
Variations in Matching Behavior
Note that the matching scores calculated by
difflib and python-Levenshtein can often
differ appreciably. (This is illustrated in
issue #128
of the fuzzywuzzy GitHub repo.)
This difference in behavior doesn’t have much practical significance,
save for the potential of causing some confusion between users with/without
python-Levenshtein installed.
As an example, the following shows an excerpt of the results of a representative
CLI suggest call without
python-Levenshtein:
$ sphobjinv suggest objects_scipy.inv surface -asit 40
Name Score Index
------------------------------------------------------ ------- -------
:py:function:`scipy.misc.face` 64 1018
:py:function:`scipy.misc.source` 64 1032
:std:doc:`generated/scipy.misc.face` 64 4042
:std:doc:`generated/scipy.misc.source` 64 4056
:py:data:`scipy.stats.rice` 56 2688
:std:label:`continuous-rice` 56 2896
:py:method:`scipy.integrate.complex_ode.successful` 51 156
:py:method:`scipy.integrate.ode.successful` 51 171
:py:function:`scipy.linalg.lu_factor` 51 967
... more with score 51 ...
:py:attribute:`scipy.LowLevelCallable.signature` 50 5
:py:function:`scipy.constants.convert_temperature` 50 53
:py:function:`scipy.integrate.quadrature` 50 176
... more with score 50 and below ...
This is a similar excerpt with python-Levenshtein:
Name Score Index
------------------------------------------------------ ------- -------
:py:function:`scipy.misc.face` 64 1018
:py:function:`scipy.misc.source` 64 1032
:std:doc:`generated/scipy.misc.face` 64 4042
:std:doc:`generated/scipy.misc.source` 64 4056
:py:method:`scipy.integrate.ode.successful` 51 171
:py:function:`scipy.linalg.lu_factor` 51 967
:py:function:`scipy.linalg.subspace_angles` 51 1003
... more with score 51 ...
:py:function:`scipy.cluster.hierarchy.fcluster` 49 23
:py:function:`scipy.cluster.hierarchy.fclusterdata` 49 24
:py:method:`scipy.integrate.complex_ode.successful` 49 156
... more with score 49 and below ...