# Set Similarity

> NumKong for C++

Packed-binary metrics operate on packed words, not on byte-wise booleans.
That is why `u1x8_t` exists as a storage type instead of pretending that `bool[8]` is the right primitive.

```c
nk_u1x8_t a[128], b[128];
nk_u32_t hamming = 0;
nk_f32_t jaccard = 0;
nk_hamming_u1_best(a, b, 128 * 8, &hamming, capabilities, NULL);
nk_jaccard_u1_best(a, b, 128 * 8, &jaccard, capabilities, NULL);
```

`nk_jaccard_u32_best` is a dense word-wise kernel rather than a sorted-set operation.
It walks two arrays of `n` 32-bit words position by position and returns `1 - matches / n`.

```c
nk_u32_t a[] = {1, 3, 5, 7, 9}, b[] = {1, 3, 5, 8, 10};
nk_f32_t jaccard_words = 0;
nk_jaccard_u32_best(a, b, 5, &jaccard_words, capabilities, NULL); // 1 - matches / n
assert(jaccard_words > 0.0f && jaccard_words < 1.0f && "3 of 5 words match");
```

Sorted arrays of integer identifiers are handled by the sparse kernels instead, described below.

`#include <numkong/set.hpp>`

## hamming

Hamming distance: Σ(aᵢ ⊕ bᵢ).

```cpp
template <numeric_dtype in_type_, numeric_dtype result_type_ = typename in_type_::hamming_result_t>
status_t hamming(
    in_type_ const *a,
    in_type_ const *b,
    std::size_t d,
    result_type_ *r,
    nk_capability_t capabilities = default_capabilities(),
    nk_stream_t stream = nullptr) noexcept;
```

```cpp
template <numeric_dtype in_type_, numeric_dtype result_type_ = typename in_type_::hamming_result_t, vector_of<in_type_> a_type_, vector_of<in_type_> b_type_>
expected<result_type_> hamming(
    a_type_ const & a,
    b_type_ const & b,
    nk_capability_t capabilities = default_capabilities()) noexcept;
```

Hamming distance between two bit runs of equal dimensions; [`unexpected_dimensions_k`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#unexpected_dimensions_k) when they differ or either run is strided or ends mid-value.

- `a` (in): First input vector
- `b` (in): Second input vector
- `d` (in): Counts dimensions, a multiple of the values per byte.
- `r` (out): Pointer to output count
- `capabilities` (in): Capabilities to pick from, or zero for the C++ template
- `stream` (in): Null on the CPU, or the stream of the device `capabilities` describes

## jaccard

Jaccard distance: 1 − |A ∩ B| / |A ∪ B|.

```cpp
template <numeric_dtype in_type_, numeric_dtype result_type_ = typename in_type_::jaccard_result_t>
status_t jaccard(
    in_type_ const *a,
    in_type_ const *b,
    std::size_t d,
    result_type_ *r,
    nk_capability_t capabilities = default_capabilities(),
    nk_stream_t stream = nullptr) noexcept;
```

```cpp
template <numeric_dtype in_type_, numeric_dtype result_type_ = typename in_type_::jaccard_result_t, vector_of<in_type_> a_type_, vector_of<in_type_> b_type_>
expected<result_type_> jaccard(
    a_type_ const & a,
    b_type_ const & b,
    nk_capability_t capabilities = default_capabilities()) noexcept;
```

Jaccard distance between two bit runs, failing like the concept [`hamming`](#hamming).

For [u1x8_t](https://www.unum.cloud/docs/numkong/cpp/scalar-types.md#u1x8_t) bit vectors, uses popcount(AND) / popcount(OR). For u16_t/u32_t element vectors, uses count of matching elements / total.

- `a` (in): First input vector
- `b` (in): Second input vector
- `d` (in): Counts dimensions, a multiple of the values per byte.
- `r` (out): Pointer to output distance
- `capabilities` (in): Capabilities to pick from, or zero for the C++ template
- `stream` (in): Null on the CPU, or the stream of the device `capabilities` describes