Use string length diff heuristic to skip Levenshtein Algo (#369)
authorKenneth Finnegan <kennethfinnegan2007@gmail.com>
Thu, 15 Sep 2022 17:12:02 +0000 (10:12 -0700)
committerGitHub <noreply@github.com>
Thu, 15 Sep 2022 17:12:02 +0000 (10:12 -0700)
commit8fe8cfd60af417f5467f7723075f5ad050b806c8
tree2b10155ae2f61267def7831ca33c29b4614510bd
parent7a2dbf717794655a3fd82439fdb1e3d8b4730c74
Use string length diff heuristic to skip Levenshtein Algo (#369)

When using the --fuzzy option to try and find close matches locally,
the edit distance algorithm used is O(N^2), which can get painful on
CPU constrained systems when working in folders with tens of thousands
of files in it.

The lower bound on the calculated Levenshtein distance is the difference
of the two strings being compared, so if that difference is larger than
the current best match, the calculation of the exact edit distance between
the two strings can be skipped.

Testing on the OpenSUSE package repo has shown a 50% reduction in the CPU time
required to plan the rsync transaction.
generator.c
util1.c