text

defmodule Text.Distance do
  @moduledoc """
  String edit-distance algorithms.

  ### Why this module exists

  Elixir's standard library includes `String.jaro_distance/2` and
  `String.bag_distance/2`, but both functions return values in
  `[0.0, 1.0]` where `1.0` means "identical" and `0.0` means "completely
  different". That is a *similarity* measure named "distance", which is
  inconsistent with how virtually every other ecosystem (Python's
  `Levenshtein` package, Rust's `strsim`, JavaScript's `string-similarity`
  …) defines distance.

  This module provides the conventional definitions instead — `0` (or
  `0.0`) means identical, larger values mean more different — and adds
  the algorithms the standard library does not ship: Levenshtein,
  Damerau-Levenshtein, Hamming, and Jaro-Winkler. Callers wanting the
  similarity form of any of these should use `Text.Similarity` (which
  returns `1.0 - distance` for the bounded forms).

  ### Granularity

  All algorithms operate at the *grapheme* level, matching the
  convention used by `String.jaro_distance/2`. A grapheme is one
  user-perceived character — `"é"` (U+00E9) and `"é"` (U+0065 + U+0301)
  are both a single grapheme, even though their byte representations
  differ. For ASCII-only inputs the grapheme-level analysis is
  equivalent to byte-level operation.

  ### Algorithms

  | Function | Returns | Range | Definition |
  |---|---|---|---|
  | `levenshtein/2` | non-negative integer | `0..max(len(a), len(b))` | minimum number of insertions, deletions, and substitutions |
  | `damerau_levenshtein/2` | non-negative integer | `0..max(len(a), len(b))` | Levenshtein plus adjacent transposition (optimal-string-alignment variant) |
  | `hamming/2` | non-negative integer | `0..len` (raises if lengths differ) | substitutions only |
  | `jaro/2` | float | `0.0..1.0` | `1.0 - String.jaro_distance/2` |
  | `jaro_winkler/2` | float | `0.0..1.0` | Jaro with a prefix bonus, then `1.0 - similarity` |

  """

  @doc """
  Returns the Levenshtein distance between `a` and `b`.

  The Levenshtein distance is the minimum number of single-grapheme
  insertions, deletions, or substitutions needed to transform `a` into
  `b`.

  ### Arguments

  * `a` is a UTF-8 string.

  * `b` is a UTF-8 string.

  ### Returns

  * A non-negative integer.

  ### Examples

      iex> Text.Distance.levenshtein("kitten", "sitting")
      3

      iex> Text.Distance.levenshtein("Saturday", "Sunday")
      3

      iex> Text.Distance.levenshtein("", "abc")
      3

      iex> Text.Distance.levenshtein("naïve", "naive")
      1

  """
  @spec levenshtein(String.t(), String.t()) :: non_neg_integer()
  def levenshtein(a, b) when is_binary(a) and is_binary(b) do
    a_graphemes = String.graphemes(a)
    b_graphemes = String.graphemes(b)
    do_levenshtein(a_graphemes, b_graphemes)
  end

  defp do_levenshtein([], b), do: length(b)
  defp do_levenshtein(a, []), do: length(a)

  defp do_levenshtein(a, b) do
    initial_row = Enum.to_list(0..length(b))

    a
    |> Enum.with_index(1)
    |> Enum.reduce(initial_row, fn {a_char, i}, prev_row ->
      build_levenshtein_row(b, a_char, i, prev_row)
    end)
    |> List.last()
  end

  defp build_levenshtein_row(b, a_char, row_index, [first_prev | rest_prev]) do
    do_build_levenshtein_row(b, a_char, [row_index], first_prev, rest_prev)
  end

  defp do_build_levenshtein_row([], _a_char, acc, _prev_diag, _rest_prev) do
    Enum.reverse(acc)
  end

  defp do_build_levenshtein_row(
         [b_char | b_rest],
         a_char,
         [last_curr | _] = acc,
         prev_diag,
         [next_prev | next_rest]
       ) do
    cost = if a_char == b_char, do: 0, else: 1

    curr =
      (next_prev + 1)
      |> min(last_curr + 1)
      |> min(prev_diag + cost)

    do_build_levenshtein_row(b_rest, a_char, [curr | acc], next_prev, next_rest)
  end

  @doc """
  Returns the Damerau-Levenshtein distance between `a` and `b`.

  This is the *optimal-string-alignment* (OSA) variant, which is what
  most libraries mean by "Damerau-Levenshtein": Levenshtein with the
  added operation of transposing two adjacent graphemes, with the
  restriction that no substring is edited more than once. The full
  Damerau-Levenshtein distance (without the no-repeat-edit
  restriction) is rarely used in practice and not provided here.

  ### Arguments

  * `a` is a UTF-8 string.

  * `b` is a UTF-8 string.

  ### Returns

  * A non-negative integer.

  ### Examples

      iex> Text.Distance.damerau_levenshtein("ca", "ac")
      1

      iex> Text.Distance.damerau_levenshtein("kitten", "sitting")
      3

      iex> Text.Distance.damerau_levenshtein("abcdef", "bacdfe")
      2

      iex> Text.Distance.damerau_levenshtein("", "abc")
      3

  """
  @spec damerau_levenshtein(String.t(), String.t()) :: non_neg_integer()
  def damerau_levenshtein(a, b) when is_binary(a) and is_binary(b) do
    a_arr = a |> String.graphemes() |> List.to_tuple()
    b_arr = b |> String.graphemes() |> List.to_tuple()

    do_damerau_levenshtein(a_arr, b_arr)
  end

  defp do_damerau_levenshtein(a_arr, b_arr) do
    m = tuple_size(a_arr)
    n = tuple_size(b_arr)

    cond do
      m == 0 -> n
      n == 0 -> m
      true -> compute_damerau(a_arr, b_arr, m, n)
    end
  end

  defp compute_damerau(a_arr, b_arr, m, n) do
    initial =
      Enum.reduce(0..m, %{}, fn i, acc -> Map.put(acc, {i, 0}, i) end)
      |> then(fn acc ->
        Enum.reduce(0..n, acc, fn j, acc -> Map.put(acc, {0, j}, j) end)
      end)

    final =
      Enum.reduce(1..m, initial, fn i, d_acc ->
        Enum.reduce(1..n, d_acc, fn j, d ->
          fill_damerau_cell(d, a_arr, b_arr, i, j)
        end)
      end)

    Map.fetch!(final, {m, n})
  end

  defp fill_damerau_cell(d, a_arr, b_arr, i, j) do
    a_i = elem(a_arr, i - 1)
    b_j = elem(b_arr, j - 1)
    cost = if a_i == b_j, do: 0, else: 1

    base =
      (Map.fetch!(d, {i - 1, j}) + 1)
      |> min(Map.fetch!(d, {i, j - 1}) + 1)
      |> min(Map.fetch!(d, {i - 1, j - 1}) + cost)

    value =
      if i > 1 and j > 1 and elem(a_arr, i - 1) == elem(b_arr, j - 2) and
           elem(a_arr, i - 2) == elem(b_arr, j - 1) do
        min(base, Map.fetch!(d, {i - 2, j - 2}) + 1)
      else
        base
      end

    Map.put(d, {i, j}, value)
  end

  @doc """
  Returns the Hamming distance between two equal-length strings.

  The Hamming distance is the number of grapheme positions at which the
  two strings differ. It is undefined for strings of different length;
  passing such strings raises `ArgumentError`.

  ### Arguments

  * `a` is a UTF-8 string.

  * `b` is a UTF-8 string of the same grapheme length as `a`.

  ### Returns

  * A non-negative integer.

  ### Examples

      iex> Text.Distance.hamming("karolin", "kathrin")
      3

      iex> Text.Distance.hamming("karolin", "kerstin")
      3

      iex> Text.Distance.hamming("1011101", "1001001")
      2

      iex> Text.Distance.hamming("", "")
      0

  """
  @spec hamming(String.t(), String.t()) :: non_neg_integer()
  def hamming(a, b) when is_binary(a) and is_binary(b) do
    a_graphemes = String.graphemes(a)
    b_graphemes = String.graphemes(b)

    if length(a_graphemes) != length(b_graphemes) do
      raise ArgumentError,
            "Hamming distance is undefined for strings of different grapheme " <>
              "length (#{length(a_graphemes)} vs #{length(b_graphemes)})"
    end

    a_graphemes
    |> Enum.zip(b_graphemes)
    |> Enum.count(fn {x, y} -> x != y end)
  end

  @doc """
  Returns the Jaro distance between `a` and `b`.

  Jaro distance is a normalised metric in `[0.0, 1.0]` where `0.0`
  means the strings are identical and `1.0` means they have nothing in
  common. It is computed as `1.0 - String.jaro_distance(a, b)` — the
  standard library's "jaro_distance" function actually returns a
  similarity, despite the name.

  ### Arguments

  * `a` is a UTF-8 string.

  * `b` is a UTF-8 string.

  ### Returns

  * A float in `[0.0, 1.0]`.

  ### Examples

      iex> Text.Distance.jaro("MARTHA", "MARTHA")
      0.0

      iex> Text.Distance.jaro("MARTHA", "MARHTA") |> Float.round(4)
      0.0556

      iex> Text.Distance.jaro("DIXON", "DICKSONX") |> Float.round(4)
      0.2333

      iex> Text.Distance.jaro("", "")
      0.0

  """
  @spec jaro(String.t(), String.t()) :: float()
  def jaro(a, b) when is_binary(a) and is_binary(b) do
    1.0 - String.jaro_distance(a, b)
  end

  @doc """
  Returns the Jaro-Winkler distance between `a` and `b`.

  Jaro-Winkler is the Jaro similarity boosted by a per-grapheme bonus
  for shared prefixes (up to four graphemes), then expressed as a
  distance: `1.0 - similarity`. Two strings sharing a long prefix end
  up much closer than under plain Jaro.

  ### Arguments

  * `a` is a UTF-8 string.

  * `b` is a UTF-8 string.

  ### Options

  * `:prefix_scale` — the per-grapheme prefix bonus, traditionally
    `0.1` (the maximum value before Jaro-Winkler can exceed 1.0).
    Defaults to `0.1`.

  * `:max_prefix_length` — the prefix length is capped at this many
    graphemes. Defaults to `4`.

  ### Returns

  * A float in `[0.0, 1.0]`.

  ### Examples

      iex> Text.Distance.jaro_winkler("MARTHA", "MARHTA") |> Float.round(4)
      0.0389

      iex> Text.Distance.jaro_winkler("DIXON", "DICKSONX") |> Float.round(4)
      0.1867

      iex> Text.Distance.jaro_winkler("MARTHA", "MARTHA")
      0.0

  """
  @spec jaro_winkler(String.t(), String.t(), keyword()) :: float()
  def jaro_winkler(a, b, options \\ []) when is_binary(a) and is_binary(b) do
    prefix_scale = Keyword.get(options, :prefix_scale, 0.1)
    max_prefix = Keyword.get(options, :max_prefix_length, 4)

    similarity = String.jaro_distance(a, b)
    prefix = common_prefix_length(a, b, max_prefix)
    1.0 - (similarity + prefix * prefix_scale * (1.0 - similarity))
  end

  defp common_prefix_length(a, b, max) do
    a_prefix = a |> String.graphemes() |> Enum.take(max)
    b_prefix = b |> String.graphemes() |> Enum.take(max)

    a_prefix
    |> Enum.zip(b_prefix)
    |> Enum.take_while(fn {x, y} -> x == y end)
    |> length()
  end

  ## ── set-based metrics over character n-grams ────────────────────

  @doc """
  Returns the Jaccard distance between `a` and `b` computed on
  character n-grams (shingles).

  Defined as `1 - |A ∩ B| / |A ∪ B|` where `A` and `B` are the
  sets of n-grams of each string.

  ### Arguments

  * `a` is a string.

  * `b` is a string.

  ### Options

  * `:n` — n-gram size in graphemes. Defaults to `2` (character
    bigrams).

  ### Returns

  * A float in `[0.0, 1.0]`. `0.0` for identical strings; `1.0`
    when the n-gram sets are completely disjoint.

  ### Examples

      iex> Text.Distance.jaccard("night", "nacht")
      0.8571428571428572

      iex> Text.Distance.jaccard("kitten", "kitten")
      0.0

      iex> Text.Distance.jaccard("abcdef", "uvwxyz")
      1.0

  """
  @spec jaccard(String.t(), String.t(), keyword()) :: float()
  def jaccard(a, b, options \\ []) when is_binary(a) and is_binary(b) do
    n = Keyword.get(options, :n, 2)
    {intersection, union} = intersection_and_union_sizes(a, b, n)

    case union do
      0 -> 0.0
      _ -> 1.0 - intersection / union
    end
  end

  @doc """
  Returns the Sørensen–Dice distance between `a` and `b` computed on
  character n-grams.

  Defined as `1 - 2|A ∩ B| / (|A| + |B|)`. Closely related to Jaccard
  but weights matches more heavily; widely used for fuzzy string
  matching where a slightly more forgiving score is desirable.

  ### Arguments

  * `a` is a string.

  * `b` is a string.

  ### Options

  * `:n` — n-gram size in graphemes. Defaults to `2`.

  ### Returns

  * A float in `[0.0, 1.0]`. `0.0` for identical strings; `1.0`
    when the n-gram sets are completely disjoint.

  ### Examples

      iex> Text.Distance.sorensen_dice("night", "nacht")
      0.75

      iex> Text.Distance.sorensen_dice("kitten", "kitten")
      0.0

      iex> Text.Distance.sorensen_dice("abcdef", "uvwxyz")
      1.0

  """
  @spec sorensen_dice(String.t(), String.t(), keyword()) :: float()
  def sorensen_dice(a, b, options \\ []) when is_binary(a) and is_binary(b) do
    n = Keyword.get(options, :n, 2)
    {intersection, size_a, size_b} = intersection_and_sizes(a, b, n)
    total = size_a + size_b

    case total do
      0 -> 0.0
      _ -> 1.0 - 2 * intersection / total
    end
  end

  @doc """
  Returns the Tanimoto distance between `a` and `b` over character
  n-grams.

  For binary feature vectors (which is what we have when treating
  n-grams as set membership) Tanimoto reduces to Jaccard — so this
  is an alias maintained for callers who specifically want the
  Tanimoto name.

  ### Arguments

  * `a` is a string.

  * `b` is a string.

  ### Options

  Same as `jaccard/3`.

  ### Returns

  * A float in `[0.0, 1.0]`. Identical to the result of
    `jaccard/3` with the same arguments.

  ### Examples

      iex> Text.Distance.tanimoto("night", "nacht") == Text.Distance.jaccard("night", "nacht")
      true

  """
  @spec tanimoto(String.t(), String.t(), keyword()) :: float()
  defdelegate tanimoto(a, b, options \\ []), to: __MODULE__, as: :jaccard

  @doc """
  Returns the cosine distance between `a` and `b` over character
  n-grams treated as a binary bag of features.

  Defined as `1 - |A ∩ B| / sqrt(|A| · |B|)`.

  ### Arguments

  * `a` is a string.

  * `b` is a string.

  ### Options

  * `:n` — n-gram size in graphemes. Defaults to `2`.

  ### Returns

  * A float in `[0.0, 1.0]`. `0.0` for identical strings; `1.0`
    when the n-gram sets are completely disjoint.

  ### Examples

      iex> Text.Distance.cosine("night", "nacht")
      0.75

      iex> Text.Distance.cosine("kitten", "kitten")
      0.0

      iex> Text.Distance.cosine("abcdef", "uvwxyz")
      1.0

  """
  @spec cosine(String.t(), String.t(), keyword()) :: float()
  def cosine(a, b, options \\ []) when is_binary(a) and is_binary(b) do
    n = Keyword.get(options, :n, 2)
    {intersection, size_a, size_b} = intersection_and_sizes(a, b, n)

    case size_a * size_b do
      0 -> 0.0
      product -> 1.0 - intersection / :math.sqrt(product)
    end
  end

  # Compute the intersection size and union size of two strings'
  # n-gram sets in one pass. Returns `{intersection_size, union_size}`.
  @spec intersection_and_union_sizes(String.t(), String.t(), pos_integer()) ::
          {non_neg_integer(), non_neg_integer()}
  defp intersection_and_union_sizes(a, b, n) do
    set_a = ngram_set(a, n)
    set_b = ngram_set(b, n)
    intersection = Enum.count(Map.keys(set_a), &Map.has_key?(set_b, &1))
    union = map_size(set_a) + map_size(set_b) - intersection
    {intersection, union}
  end

  # Compute intersection size and the two individual set sizes.
  @spec intersection_and_sizes(String.t(), String.t(), pos_integer()) ::
          {non_neg_integer(), non_neg_integer(), non_neg_integer()}
  defp intersection_and_sizes(a, b, n) do
    set_a = ngram_set(a, n)
    set_b = ngram_set(b, n)
    intersection = Enum.count(Map.keys(set_a), &Map.has_key?(set_b, &1))
    {intersection, map_size(set_a), map_size(set_b)}
  end

  # Build a map of grapheme n-grams of `string` (used as a set; values
  # are always `true`). Avoids `MapSet` to sidestep its opaque-type
  # interaction with dialyzer.
  @spec ngram_set(String.t(), pos_integer()) :: %{optional(String.t()) => true}
  defp ngram_set(string, n) when n >= 1 do
    graphemes = String.graphemes(string)

    case length(graphemes) do
      0 ->
        %{}

      len when len < n ->
        %{Enum.join(graphemes) => true}

      _ ->
        graphemes
        |> Enum.chunk_every(n, 1, :discard)
        |> Map.new(fn chunk -> {Enum.join(chunk), true} end)
    end
  end
end