Sketching

master

Collection of sketching algorithms in Swift
pNre/Sketching

Sketching Algorithms

A collection of sketching algorithms in Swift.

Overview

Installation

Swift Package Manager

In Package.swift add Sketching to the dependencies:

dependencies: [
    .package(url: "https://github.com/pNre/Sketching", .branch("master")),
]

Then reference it in the target that uses the package:

.target(
    name: "CoolExecutable",
    dependencies: ["Sketching"])

Carthage

Add Sketching as a dependency in your project's Cartfile:

github "pNre/Sketching"

BitSet

An array-like structure that is optimized to store bits efficiently.

Usage

//  create a bit set of 100 bits
var s = BitSet(bitWidth: 100)

//  set bit 0 and 2
s[0] = true
s[2] = true
(lldb) po s
BitSet (width=100, value=101)
//  bitwise operators
let conjunction = s1 & s2
let disjunction = s1 | s2
let negation = ~s1

MinHash

Usage

Build a MinHash and insert some elements in it:

var a = MinHash<FNV1AHashing>(hashCount: 64)
a.insert("a".utf8)
a.insert("b".utf8)
a.insert("c".utf8)
var b = MinHash<FNV1AHashing>(hashCount: 64)
b.insert("a".utf8)
b.insert("b".utf8)

Compare the similarity of two MinHash structs:

(lldb) po a.jaccard(b)
0.734375

Form an union between two MinHash:

let c = a.union(b)
(lldb) po a.jaccard(c)
1.0

HyperLogLog

Reference

Usage

var ll = HyperLogLog<FNV1AHashing>()
ll.insert("abc".utf8)
ll.insert("def".utf8)
ll.insert("abc".utf8)
(lldb) po ll.cardinality()
2.007853430022625

Bloom Filter

Usage

Init a BloomFilter with a certain size and number of hash functions:

var f = BloomFilter<FNV1AHashing>(bitWidth: 128, hashCount: 16)

Init a BloomFilter with the expected item count and probability of false positives:

var f = BloomFilter<FNV1AHashing>(expectedCardinality: 10, probabilityOfFalsePositives: 0.001)

Insert some elements:

f.insert("abc".utf8)
f.insert("def".utf8)

Test containment:

(lldb) po f.contains("gh".utf8)
false

Cuckoo Filter

Description

  • Swift Tools 4.2.0
View More Packages from this Author

Dependencies

  • None
Last updated: Fri Mar 15 2024 23:55:45 GMT-0900 (Hawaii-Aleutian Daylight Time)