simhash.mq
[!WARNING]
This project is currently under active development. APIs and features may change without notice.
[!NOTE]
This module needs mq v0.10.1 or later: it uses the hash builtin, band on numbers, and xor, replace and pack on bytes.
Near-duplicate detection for mq, as a module. A SimHash fingerprint is 64 bits where similar texts get fingerprints that differ in few bits, so duplicates can be found without comparing every pair of texts.
Installation
simhash.mq imports ds.mq for its union-find, which is included as a git submodule:
git clone --recurse-submodules https://github.com/harehare/simhash.mq
Use it by adding both directories to the module path:
mq -L simhash.mq -L simhash.mq/vendor/ds.mq -I null 'import "simhash" | simhash::fingerprint("hello world")'
Usage
mq -L . -L vendor/ds.mq -I null '
import "simhash"
| simhash::clusters([
"the quick brown fox jumps over the lazy dog near the river bank today",
"completely unrelated sentence regarding databases indexing and query planning",
"the quick brown fox jumped over the lazy dog near the river bank today",
"another unrelated line about cooking pasta with tomatoes and fresh basil leaves"
], 12)
'
# [[0, 2], [1], [3]]
A fingerprint is a string of 64 characters, each "0" or "1", and the distance between two fingerprints is the number of positions where they differ. Unrelated texts sit around 32 apart.
| Function |
Description |
fingerprint(text) |
fingerprint of the words in a text, ignoring order |
fingerprint_shingles(text, n) |
fingerprint over runs of n words, which also reflects word order |
fingerprint_tokens(tokens) |
fingerprint of an array of tokens; repeated tokens count more |
distance(a, b) |
number of differing positions |
near(a, b, max_distance) |
whether two fingerprints are within max_distance |
clusters(texts, max_distance) |
groups of indexes whose fingerprints chain within max_distance |
cluster_fingerprints(fps, max_distance) |
the same, for fingerprints you already have |
tokenize(text) / shingles(tokens, n) |
the word splitter and the n-word runs used above |
Groups are ordered by their smallest index, and a text that matches nothing is a group of one. Texts with no words get 64 zeros, so they all land in one group.
MinHash
minhash.mq is the other classic approach. A signature is k numbers (the smallest seeded hash over a text's words), and the share of positions two signatures agree on estimates the Jaccard similarity of their word sets. It ignores order and repeated words.
mq -L . -L vendor/ds.mq -I null 'import "minhash" | minhash::clusters(["a b c d", "a b c e", "x y z"], 0.5, 128)'
| Function |
Description |
signature(text, k) |
signature of the words in a text, with k positions |
signature_shingles(text, k, n) |
signature over runs of n words |
signature_tokens(tokens, k) |
signature of an array of tokens |
similarity(a, b) |
share of equal positions, between 0 and 1 |
near(a, b, min_similarity) |
whether the estimated similarity is at least min_similarity |
clusters(texts, min_similarity, k) |
groups of indexes whose signatures chain at min_similarity or more |
cluster_signatures(sigs, min_similarity) |
the same, for signatures you already have |
Unlike the SimHash clustering, this one is approximate: signatures are cut into bands and only those that agree on a whole band are compared, so a pair that is only just similar enough can be missed. A larger k makes both the estimate and the banding sharper.
Notes
- Clustering is exact: it returns the groups a comparison of every pair would, but only compares fingerprints that share a slice of their bits.
max_distance + 1 slices are used, so very large distances compare more pairs.
- Fingerprints chain: if A is near B and B is near C, all three share a group even when A and C are not near each other.
- Words are split on anything that is not a letter or a digit, so text written without spaces stays one token per run.
Development
git submodule update --init
mq-test -L vendor/ds.mq -L . simhash_tests.mq
mq-test -L vendor/ds.mq -L . minhash_tests.mq
mq-bench -L vendor/ds.mq -L . simhash_bench.mq
mq-bench -L vendor/ds.mq -L . minhash_bench.mq
One of the goals of this module is also to check mq for performance problems, so it comes with a benchmark in simhash_bench.mq.