diff options
| -rw-r--r-- | README.md | 129 |
1 files changed, 129 insertions, 0 deletions
diff --git a/README.md b/README.md new file mode 100644 index 0000000..b3d8a90 --- /dev/null +++ b/README.md @@ -0,0 +1,129 @@ + +# Interoperability of Similarity Hashing Schemes + +This (work-in-progress) document proposes specific document fingerprinting +algorithms, configuration, and practices for use in identifying and +cross-referencing nearly identical documents in several medias. For example, +web content across various HTML encodings and web design revisions, or research +publications across PDF, HTML, and XML formats. + +The motivation to come to a public consensus on specific details of these +techniques is to enhance collaboration in efforts like web archiving, +automated document identification, verifying repository contents, and +near-duplicate-detection across distributed datasets. + +These techniques are variously refered to as "near duplicate detection" and +"similarity hashing". The major advances in this area historically came from +commercial search engine development and the field of information retrieval in +academia. + +Contributions, corrections, and feedback to this document welcomed! You can use +github features (issues and pull-requests) or email contributors directly. + +## Background + +The techniques described here usually complement both regular content hashing +and full-document similarity measures. Regular hashing (or digests) generally +have the property that exact byte-for-byte file matches will have equal hashes, +but any small difference between files results in a completely different hash. +The hash is of a fixed length of some 40 to 64 bytes (very small compared to +document size). This is useful for fast equality checking and verify the +integrity of files, but is too brittle for use identification across media. +Similarity measures (such as edit distance or cosine similarity) often take a +full document (or an extract set of tokens from the document) and give a +fractional measure of similarity. They have the property of being relatively +inefficient for lookups in large corpuses because each document must be +compared one-to-one. + +Similarity hashing is often used as an optimization on top of similarity +measures: the hashes of all documents are pre-computed and then sorted, and +only those documents within a fixed distance in the sorted list need to be +compared. This reduces identification of near-duplicates in a corpus from +`O(N^2)` similarity computations to `O(N)` similarity compurations. Indexed +lists also reduce work in the context of individual lookup query for large +corpuses. + +Some notable algorithms to consider are: + +- `simhash` +- `minhash` + +However, the papers describing these algorithms have a few parameters (eg, hash +bit length, token hash algorithm), and leave several important steps up to the +implementor, such as: + +- media-specific content extraction (eg, stripping some or all HTML tags) +- input encoding normalization (UTF-8, etc) +- tokenization (particularly for non-latin languages) +- stop words +- string serialization (eg, base16, base32, or base64 encoding) +- prefixes or short identifiers for specific schemes + +These parameters are usually left to be tuned by implementors. Some parameters +can still be left to tuning by implementors, because they happen at comparison +time, not during batch indexing: + +- number of segmented rotations when sorting and distance of match (in bit + flips) to seach for +- algorithm or measure used for final similarity measurement + +Note that unlike regular hashing algorithms, the details for similarity hashes +don't necessarily need to be specified in completeness: if differences between +implementations only result in (statistically) tiny changes in the hash, hashes +should still compare somewhat accurately. Complete reproducibility (exact +similarity hash output for exact document input) between implementations is +desirable, but not strictly necessary in all cases, leaving some wiggle room +for implementors and optimization. + +## Proposed Schemes + +Similar to the `blake2` and `SHA` families of hashes, I can imagine that a +small (1-4) set of variants might be useful for use in different contexts. It's +also good practice to build software, protocols, and data models to permit +swapping out algorithms for future flexibility, though of course the whole +concept here is to settle on a small number of consensus schemes for +interoperability. + +TODO: summary table here + +### simhash-doc + +The roughly defined scope for this scheme would be "documents" of length +between one and fifty pages when printed. If it could scale down to 2-3 +paragraphs and up to thousand-page documents that would be great, but it should +be optimized for the narrower scope. It should be useful across media (web +pages, PDFs, plain text, etc), and across the most popular languages. + +Proposed extraction and tokenization: + +- strip all metadata and styling when extracting. include figure captions, + table contents, quoted text. Do include reference lists, but do not include + tokens from URLs or identifiers. +- UTF-8 encoded tokens +- fallback to unicode word separators for tokenization (TODO: ???) +- no zero-width or non-printing unicode modifiers +- tokens should include only "alphanumeric" characters (TODO: as defined by + unicode plane?) +- numbers (unless part of an alphanumeric string, eg an acronym) should not be + included +- tokens (words) must be 3 characters minimum +- OPTIONALLY, a language-specific stop-list appropriate for search-engine + indexing may be used. + +Proposed algorithm and parameters: + +- `simhash` algorithm +- TODO: fast token hashing algorithm? +- TODO: 64x signed 8-bit buckets during calculation +- 64bit length final form +- base32 (non-capitalization-sensitive) when serialized as a string + +Recommended lookup parameters: + +- TODO: how many columns in rotation? +- TODO: N-bit window +- TODO: cosine similarity measure? edit distance? +- TODO: 0.XYZ considered a loose match, 0.XYZ considered a close match + +## References + |