"how numbers are stored and used in computers"

Jaccard Distance

The Jaccard distance is a measure of dissimilarity between two sets. When applied to strings, the sets are typically created using character n-grams or word sets. The distance is calculated as one minus the Jaccard similarity coefficient.

O(m·n)

space

O(1)

O(n)·O(n)

Cosine distance

O(n)·O(1)

Hamming distance

O(m+n)·O(m+n)

Jaccard distance

Sorensen-Dice coefficient

Overlap coefficient

O(m·n)·O(m·n)

Levenshtein distance

Damerau-Levenshtein distance

O(m·n)·O(1)

Jaro-Winkler distance

O(n)

time

O(m·n)

Mathematical Definition

The Jaccard distance between two strings and is defined as:

where:

and are the sets created from strings and
denotes the cardinality of set
denotes set intersection
denotes set union

The sets can be created using:

Character n-grams (e.g., bigrams, trigrams)
Word sets
Shingle sets (overlapping n-grams)

Properties

The Jaccard distance exhibits several important mathematical properties. It produces a value ranging from 0 to 1, where 0 indicates identical strings. The distance is symmetric, meaning the distance from string A to B is the same as from B to A. It satisfies the triangle inequality, making it a proper metric. The distance is always non-negative, and it has the unique property of being invariant to string length, making it particularly useful for comparing texts of different sizes.

Applications

The Jaccard distance has found widespread application in various text processing and data analysis tasks. In document similarity analysis, it helps identify similar documents by comparing their word or character sets. For plagiarism detection, it provides an effective way to measure the overlap between different texts. In data deduplication systems, it helps identify and remove duplicate records. The distance is also valuable in information retrieval systems, where it helps rank search results by relevance. Additionally, it plays a crucial role in text mining applications, helping to identify patterns and relationships in large text corpora.

Implementation

code.ts
1function jaccardDistance(s1: string, s2: string): number {
2    // Implementation coming soon
3}

References

Jaccard, P. (1901). Étude comparative de la distribution florale dans une portion des Alpes et des Jura. Bulletin de la Société Vaudoise des Sciences Naturelles, 37, 547-579.
Tan, P. N., Steinbach, M., & Kumar, V. (2005). Introduction to Data Mining. Pearson Education.