diff options
| -rw-r--r-- | Cargo.toml | 3 | ||||
| -rw-r--r-- | katex-header.html | 22 | ||||
| -rw-r--r-- | src/chebyshev.rs | 7 | ||||
| -rw-r--r-- | src/cos.rs | 56 | ||||
| -rw-r--r-- | src/distance.rs | 37 | ||||
| -rw-r--r-- | src/euclid.rs | 7 | ||||
| -rw-r--r-- | src/hamming.rs | 7 | ||||
| -rw-r--r-- | src/lp.rs | 13 | ||||
| -rw-r--r-- | src/taxi.rs | 7 |
9 files changed, 141 insertions, 18 deletions
@@ -20,3 +20,6 @@ rand = "0.7.3" [[bench]] name = "benches" harness = false + +[package.metadata.docs.rs] +rustdoc-args = ["--html-in-header", "katex-header.html"]
\ No newline at end of file diff --git a/katex-header.html b/katex-header.html new file mode 100644 index 0000000..4e73ba1 --- /dev/null +++ b/katex-header.html @@ -0,0 +1,22 @@ +<!-- Credit: https://stackoverflow.com/a/54573800 --> +<!-- Credit: https://github.com/m-ou-se/rust-horrible-katex-hack/blob/master/src/lib.rs --> + +<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.11.1/katex.min.css" integrity="sha384-zB1R0rpPzHqg7Kpt0Aljp8JPLqbXI3bhnPWROx27a9N0Ll6ZP/+DiW/UqRcLbRjq" crossorigin="anonymous" /> +<script defer src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.11.1/katex.min.js" integrity="sha384-y23I5Q6l+B6vatafAwxRu/0oK/79VlbSz7Q9aiSZUvyWYIYsd+qj+o24G5ZU2zJz" crossorigin="anonymous"></script> +<script> + document.addEventListener("DOMContentLoaded", () => { + let codes = [...document.getElementsByTagName("code")]; + for (let code of codes) { + if (code.classList.contains("language-math")) { + let p = document.createElement("p"); + katex.render(code.textContent, p, { displayMode: true }); + let pre = code.parentNode; + pre.parentNode.replaceChild(p, pre); + } else if (/^\$.*\$$/.test(code.textContent)) { + let span = document.createElement("span"); + katex.render(code.textContent.slice(1, -1), span); + code.parentNode.replaceChild(span, code); + } + } + }); +</script> diff --git a/src/chebyshev.rs b/src/chebyshev.rs index fa8e92c..335b6f1 100644 --- a/src/chebyshev.rs +++ b/src/chebyshev.rs @@ -44,6 +44,13 @@ impl<T: Coordinates> Coordinates for Chebyshev<T> { } /// Compute the Chebyshev distance between two points. +/// +/// ```math +/// \begin{aligned} +/// \mathrm{chebyshev\_distance}(x, y) &= \|x - y\|_\infty \\ +/// &= \max_i |x_i - y_i| +/// \end{aligned} +/// ``` pub fn chebyshev_distance<T, U>(x: T, y: U) -> T::Value where T: Coordinates, @@ -12,8 +12,16 @@ use std::cmp::Ordering; /// /// Use [cosine_distance] instead if you are implementing [Proximity::distance()]. /// +/// ```math +/// \begin{aligned} +/// \mathrm{cosine\_similarity}(x, y) &= \frac{x \cdot y}{\|x\| \|y\|} \\ +/// &= \frac{\sum_i x_i y_i}{\sqrt{\sum_i x_i^2} \sqrt{\sum_i y_i^2}} \\ +/// &= \cos \theta +/// \end{aligned} +/// ``` +/// /// [cosine *similarity*]: https://en.wikipedia.org/wiki/Cosine_similarity -/// [Proximity::distance()]: Proximity#method.distance +/// [Proximity::distance()]: Proximity#tymethod.distance pub fn cosine_similarity<T, U>(x: T, y: U) -> T::Value where T: Coordinates, @@ -39,6 +47,15 @@ where /// Compute the [cosine distance] between two points. /// +/// ```math +/// \begin{aligned} +/// \mathrm{cosine\_distance}(x, y) &= 1 - \mathrm{cosine\_similarity}(x, y) \\ +/// &= 1 - \frac{x \cdot y}{\|x\| \|y\|} \\ +/// &= 1 - \frac{\sum_i x_i y_i}{\sqrt{\sum_i x_i^2} \sqrt{\sum_i y_i^2}} \\ +/// &= 1 - \cos \theta +/// \end{aligned} +/// ``` +/// /// [cosine distance]: https://en.wikipedia.org/wiki/Cosine_similarity pub fn cosine_distance<T, U>(x: T, y: U) -> T::Value where @@ -97,8 +114,16 @@ where /// /// Use [prenorm_cosine_distance] instead if you are implementing [Proximity::distance()]. /// +/// ```math +/// \begin{aligned} +/// \mathrm{prenorm\_cosine\_similarity}(x, y) &= x \cdot y \\ +/// &= \sum_i x_i y_i \\ +/// &= \cos \theta +/// \end{aligned} +/// ``` +/// /// [cosine *similarity*]: https://en.wikipedia.org/wiki/Cosine_similarity -/// [`Proximity::distance()`]: Proximity#method.distance +/// [`Proximity::distance()`]: Proximity#tymethod.distance pub fn prenorm_cosine_similarity<T, U>(x: T, y: U) -> T::Value where T: Coordinates, @@ -118,6 +143,15 @@ where /// Compute the [cosine distance] between two pre-normalized (unit magnitude) points. /// +/// ```math +/// \begin{aligned} +/// \mathrm{prenorm\_cosine\_distance}(x, y) &= 1 - \mathrm{prenorm\_cosine\_similarity}(x, y) \\ +/// &= 1 - x \cdot y \\ +/// &= 1 - \sum_i x_i y_i \\ +/// &= 1 - \cos \theta +/// \end{aligned} +/// ``` +/// /// [cosine distance]: https://en.wikipedia.org/wiki/Cosine_similarity pub fn prenorm_cosine_distance<T, U>(x: T, y: U) -> T::Value where @@ -175,6 +209,15 @@ where /// Compute the [angular distance] between two points. /// +/// ```math +/// \begin{aligned} +/// \mathrm{angular\_distance}(x, y) &= \arccos(\mathrm{cosine\_similarity}(x, y)) \\ +/// &= \arccos \left( \frac{x \cdot y}{\|x\| \|y\|} \right) \\ +/// &= \arccos \left( \frac{\sum_i x_i y_i}{\sqrt{\sum_i x_i^2} \sqrt{\sum_i y_i^2}} \right) \\ +/// &= \theta +/// \end{aligned} +/// ``` +/// /// [angular distance]: https://en.wikipedia.org/wiki/Cosine_similarity#Angular_distance_and_similarity pub fn angular_distance<T, U>(x: T, y: U) -> AngularDistance<T::Value> where @@ -257,6 +300,15 @@ where /// Compute the [angular distance] between two points. /// +/// ```math +/// \begin{aligned} +/// \mathrm{prenorm\_angular\_distance}(x, y) &= \arccos(\mathrm{prenorm\_cosine\_similarity}(x, y)) \\ +/// &= \arccos(x \cdot y) \\ +/// &= \arccos \left( \sum_i x_i y_i \right) \\ +/// &= \theta +/// \end{aligned} +/// ``` +/// /// [angular distance]: https://en.wikipedia.org/wiki/Cosine_similarity#Angular_distance_and_similarity pub fn prenorm_angular_distance<T, U>(x: T, y: U) -> AngularDistance<T::Value> where diff --git a/src/distance.rs b/src/distance.rs index 9ff9fd4..20d862b 100644 --- a/src/distance.rs +++ b/src/distance.rs @@ -15,11 +15,15 @@ impl<T: Num + NumAssign + Signed + Copy + PartialOrd> Value for T {} /// An implementation may be an actual numerical distance, or an [order embedding] of the true /// distance. This allows for optimizations whenever distances can be compared more efficiently /// than their exact values can be computed, as is the case for [Euclidean distance]. Implementors -/// must satisfy, for all distances `x` and `y`: +/// must satisfy, for all distances `$x$` and `$y$`: /// -/// * `x < y` iff `x.value() < y.value()` -/// * `x.value() < y` iff `x.value() < y.value()` -/// * `x < y.value()` iff `x.value() < y.value()` +/// ```math +/// \begin{aligned} +/// x.\mathrm{value}() &< y.\mathrm{value}() & &\iff& x.\mathrm{value}() &< y \\ +/// & & &\iff& x &< y.\mathrm{value}() \\ +/// & & &\iff& x &< y +/// \end{aligned} +/// ``` /// /// [order embedding]: https://en.wikipedia.org/wiki/Order_embedding /// [Euclidean distance]: crate::euclid::EuclideanDistance @@ -79,19 +83,26 @@ impl<'k, 'v, K: Proximity<V>, V> Proximity<&'v V> for &'k K { /// Marker trait for [metric spaces]. /// -/// A metric must be symmetric and obey the [triangle inequality]. More precisely, let `x`, `y`, -/// and `z` be any elements of a metric space, and let `d(x, y) = x.distance(y).value()`. Then the -/// following rules must hold: +/// A metric must be symmetric and obey the [triangle inequality]. More precisely, let `$x$`, +/// `$y$`, and `$z$` be any elements of a metric space, and let +/// `$d(x, y) = x.\mathrm{distance}(y).\mathrm{value}()$`. Then the following rules must hold: /// -/// * `d(x, x) == 0`, -/// * `d(x, y) == d(y, z)` (symmetry), and -/// * `d(x, z) <= d(x, y) + d(y, z)` (triangle inequality). +/// ```math +/// \begin{aligned} +/// d(x, x) &= 0 \\ +/// d(x, y) &= d(y, x) & \text{(symmetry)} \\ +/// d(x, z) &\le d(x, y) + d(y, z) & \text{(triangle inequality)} +/// \end{aligned} +/// ``` /// /// Those conditions also imply the following condition: /// -/// * `d(x, y) >= 0` (non-negativity) -/// -/// Because we do not prohibit `d(x, y) == 0` for distinct `x` and `y`, these spaces are more +/// ```math +/// \begin{aligned} +/// d(x, y) &\ge \rlap{0}\phantom{d(x, y) + d(y, z)} & \text{\phantom{(triangle inequality)}\llap{(non-negativity)}} +/// \end{aligned} +/// ``` +/// Because we do not prohibit `$d(x, y) = 0$` for distinct `$x$` and `$y$`, these spaces are more /// properly known as [pseudometric spaces]. This distinction is usually unimportant. /// /// [metric spaces]: https://en.wikipedia.org/wiki/Metric_space diff --git a/src/euclid.rs b/src/euclid.rs index 4f2309a..0f2281e 100644 --- a/src/euclid.rs +++ b/src/euclid.rs @@ -47,6 +47,13 @@ impl<T: Coordinates> Coordinates for Euclidean<T> { } /// Compute the Euclidean distance between two points. +/// +/// ```math +/// \begin{aligned} +/// \mathrm{euclidean\_distance}(x, y) &= \|x - y\|_2 \\ +/// &= \sqrt{\sum_i (x_i - y_i)^2} +/// \end{aligned} +/// ``` pub fn euclidean_distance<T, U>(x: T, y: U) -> EuclideanDistance<T::Value> where T: Coordinates, diff --git a/src/hamming.rs b/src/hamming.rs index c6822ee..da959b4 100644 --- a/src/hamming.rs +++ b/src/hamming.rs @@ -25,6 +25,13 @@ impl<T> Hamming<T> { } /// Compute the Hamming distance between two integers. +/// +/// ```math +/// \begin{aligned} +/// \mathrm{hamming\_distance}(x, y) &= |\{i \mid x_i \ne y_i\}| \\ +/// &= \mathrm{popcount}(x \wedge y) +/// \end{aligned} +/// ``` pub fn hamming_distance<T: PrimInt>(x: T, y: T) -> i32 { (x ^ y).count_ones() as i32 } @@ -1,4 +1,4 @@ -//! [L<sup>p</sup> spaces](https://en.wikipedia.org/wiki/Lp_space). +//! [`$L^p$` spaces](https://en.wikipedia.org/wiki/Lp_space). use crate::coords::Coordinates; @@ -25,9 +25,16 @@ pub use crate::chebyshev::Chebyshev as Linf; /// Compute the L<sup>∞</sup> distance between two points. pub use crate::chebyshev::chebyshev_distance as linf_distance; -/// Compute the [L<sup>p</sup> distance] between two points. +/// Compute the [`$L^p$` distance] between two points. /// -/// [L<sup>p</sup> distance]: https://en.wikipedia.org/wiki/Lp_space +/// ```math +/// \begin{aligned} +/// \mathrm{lp\_distance}(p, x, y) &= \|x - y\|_p \\ +/// &= \left( \sum_i |x_i - y_i|^p \right)^{1/p} +/// \end{aligned} +/// ``` +/// +/// [`$L^p$` distance]: https://en.wikipedia.org/wiki/Lp_space pub fn lp_distance<T, U>(p: T::Value, x: T, y: U) -> T::Value where T: Coordinates, diff --git a/src/taxi.rs b/src/taxi.rs index 83ebccf..f22afb0 100644 --- a/src/taxi.rs +++ b/src/taxi.rs @@ -44,6 +44,13 @@ impl<T: Coordinates> Coordinates for Taxicab<T> { } /// Compute the taxicab distance between two points. +/// +/// ```math +/// \begin{aligned} +/// \mathrm{taxicab\_distance}(x, y) &= \|x - y\|_1 \\ +/// &= \sum_i |x_i - y_i| +/// \end{aligned} +/// ``` pub fn taxicab_distance<T, U>(x: T, y: U) -> T::Value where T: Coordinates, |