Comments (9)
Ok, thanks Matthie. I've started converting to a PR. No major problems so far...
from stringdistances.jl.
Yeah, using sorted arrays (sorted on the qgram) for pre-calculation makes quite a big difference (7x to 13x faster than "vanilla" StringDistancces.evaluate) on each comparison on my machine) in scenarios where you need to compare multiple times on some strings:
https://gist.github.com/robertfeldt/072147dc606c878080cd70972d76c8dd
Note also the possible re-design of the QgramDistances by using counters. To me it seems a bit cleaner and more flexible than having the counting code inside each Qgramdistance, but YMMV.
from stringdistances.jl.
Actually this can be sped up further with an optimized loop over the sorted qgram count arrays by:
- Using an inner for-loop over one of the arrays when the other one is "empty"
- Using Base.cmp once instead of multiple comparisons on the SubString's
Full code is here:
https://gist.github.com/robertfeldt/289b58f6efecaf051b3c0ad69cd0bd85
but the only real change is the _yield_on_co_count_pairs2
This takes the speedup from the 7x-13x range up to 17-20x faster than vanilla StringDistances.evaluate, so about another factor of about 1.5. This makes a big difference in for example distance matrix calculations.
from stringdistances.jl.
Thanks Robert. This looks amazing. Please do a PR if you can!
I have two comments for the PR. First, could you find a way to implement it without increasing timings for simple comparisons? I'm fine having two code paths, even it leads to some code duplication.
Second, I'd like to avoid defining(dist::QGramDistance)(s1::Vector{Pair}, s2::Vector{Pair})
since it conflicts with the general definition of dist(::QGramDistance)(s1, s2)
for two iterators. It seems better to only define (dist::QGramDistance)(s1::QGramCount, s2::QGramCount)
, which is not ambiguous if QGramCount
is not an iterator.
from stringdistances.jl.
Ok, PR now done. Hopefully I understood your two comments and have managed to align with them:
When we have discussed and hopefully merged this there are two more PRs I can do if there is interest:
-
pairwise(dist, strings::Vector{AbstractString}; precalc::Bool = true) - which calculated the distance matrix between all pairs of strings and uses precalculation if the flag is true (and if there are at least, say, 5 strings in the vector, since precalculation saves time from 3-4 or so)
-
Add more Qgram distances, in particular the different compression distances based on qgram dictionaries. This should be easy with the new design of the PR.
from stringdistances.jl.
Note that there are some additional speedup ideas that can be done for the IntersectionDists that I didn't do now since I wanted to stay close to the code of my gists. I doubt it will make a big difference but this:
@inline countleft!(c::ThreeCounters{Int, QD}, n1::Integer) where {QD<:IntersectionDist} =
c.left += (n1 > 0)
can actually be written simply:
@inline countleft!(c::ThreeCounters{Int, QD}, n1::Integer) where {QD<:IntersectionDist} =
c.left += 1
since countleft!
(and its "friends" for the same counter) will only be called when the arguments are >0. I doubt this will make a big difference and there is some risk in this if someone "forgets" about this in the future.
A potentially larger gain might be had by introducing calls to something like initleft!(counter, length(d1))
before starting to loop in the countmatches!
methods since we actually know how many unique qgrams each of the strings/objects has upfront. Then the countleft!
and countright!
methods can be blank/do nothing for the IntersectionDists which Julia can hopefully optimize quite a lot. Thus Jaccard, SorensenDice, and Overlap should have quite some gains from this, I think.
from stringdistances.jl.
Yes, a pairwise
method, following the Distances
API, would be great too.
from stringdistances.jl.
Beyond pairwise
, it would also be great to use this precounting for the findnearest
and findall
methods
from stringdistances.jl.
Closing this since the speedup PR has been merged. Will now think about the
- pairwise,
- more qgram distances, and
- findnearest/findall updates
and post as issues (before implementing) or do PRs, as needed. Thanks.
from stringdistances.jl.
Related Issues (20)
- Phonetic distance HOT 1
- Tag a new version HOT 1
- `Base.findmin(s1, s2, dist::Partial)`
- bug in `DamerauLevenshtein` HOT 9
- `compare` with `Partial` distances gives negative answers HOT 4
- DamerauLevenshtein() vs Levenshtein() why the same distance ? HOT 1
- (Partial) Hamming distance HOT 5
- TagBot trigger issue HOT 5
- Simpler QGramDistances implementation and prep for general dictionaries and iterators HOT 5
- `Partial` only looks at substrings of the same length... HOT 1
- pairwise not working with StringDistances HOT 3
- unexpected behavior when computing distance with an array HOT 2
- Non-strings HOT 4
- The value of "compare" is probably wrong. HOT 1
- Feature Request: Parallel processing HOT 4
- incremental compilation may be fatally broken for this module HOT 5
- Julia v1.7 Jaro() doesn't work HOT 2
- incomplete readme documentation HOT 1
- NaN (or ArgumentError) from QGram distances for short strings HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from stringdistances.jl.