starfuzz

-module(starfuzz@similarity).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/starfuzz/similarity.gleam").
-export([levenshtein/2, jaro/2, jaro_winkler/2, dice/2, jaccard/2, cosine/2]).

-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.

?MODULEDOC(
    " A module providing similarity scoring algorithms.\n"
    " Similarity scores are normalized between `0.0` (completely different) and `1.0` (identical).\n"
).

-file("src/starfuzz/similarity.gleam", 14).
?DOC(
    " Computes normalized Levenshtein similarity.\n"
    " Returns a value between `0.0` and `1.0`.\n"
).
-spec levenshtein(binary(), binary()) -> float().
levenshtein(A, B) ->
    A_chars = gleam@string:to_graphemes(A),
    B_chars = gleam@string:to_graphemes(B),
    Len_a = erlang:length(A_chars),
    Len_b = erlang:length(B_chars),
    case (Len_a =:= 0) andalso (Len_b =:= 0) of
        true ->
            1.0;

        false ->
            Max_len = case Len_a > Len_b of
                true ->
                    Len_a;

                false ->
                    Len_b
            end,
            Dist = starfuzz@distance:levenshtein(A, B),
            1.0 - (case erlang:float(Max_len) of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator -> erlang:float(Dist) / Gleam@denominator
            end)
    end.

-file("src/starfuzz/similarity.gleam", 35).
?DOC(
    " Computes the Jaro similarity score between two strings.\n"
    " Returns a value between `0.0` and `1.0`.\n"
).
-spec jaro(binary(), binary()) -> float().
jaro(A, B) ->
    A_chars = gleam@string:to_graphemes(A),
    B_chars = gleam@string:to_graphemes(B),
    Len_a = erlang:length(A_chars),
    Len_b = erlang:length(B_chars),
    case (Len_a =:= 0) andalso (Len_b =:= 0) of
        true ->
            1.0;

        false ->
            case (Len_a =:= 0) orelse (Len_b =:= 0) of
                true ->
                    +0.0;

                false ->
                    Max_len = case Len_a > Len_b of
                        true ->
                            Len_a;

                        false ->
                            Len_b
                    end,
                    Search_range = case (Max_len div 2) - 1 of
                        R when R < 0 ->
                            0;

                        R@1 ->
                            R@1
                    end,
                    A_indexed = gleam@list:index_map(
                        A_chars,
                        fun(C, I) -> {C, I} end
                    ),
                    B_indexed = gleam@list:index_map(
                        B_chars,
                        fun(C@1, I@1) -> {C@1, I@1} end
                    ),
                    {Matched_a, Matched_b_indices} = gleam@list:fold(
                        A_indexed,
                        {[], gleam@set:new()},
                        fun(State, Item) ->
                            {Acc, Matched_b} = State,
                            {A_char, I@2} = Item,
                            Match_b = gleam@list:find(
                                B_indexed,
                                fun(B_item) ->
                                    {B_char, J} = B_item,
                                    (((B_char =:= A_char) andalso (J >= (I@2 - Search_range)))
                                    andalso (J =< (I@2 + Search_range)))
                                    andalso not gleam@set:contains(Matched_b, J)
                                end
                            ),
                            case Match_b of
                                {ok, {_, J@1}} ->
                                    {[Item | Acc],
                                        gleam@set:insert(Matched_b, J@1)};

                                {error, nil} ->
                                    {Acc, Matched_b}
                            end
                        end
                    ),
                    Matches_count = erlang:length(Matched_a),
                    case Matches_count of
                        0 ->
                            +0.0;

                        _ ->
                            Matched_a_ordered = lists:reverse(Matched_a),
                            Matched_b_ordered = gleam@list:filter(
                                B_indexed,
                                fun(Item@1) ->
                                    gleam@set:contains(
                                        Matched_b_indices,
                                        erlang:element(2, Item@1)
                                    )
                                end
                            ),
                            Mismatches = begin
                                _pipe = gleam@list:zip(
                                    Matched_a_ordered,
                                    Matched_b_ordered
                                ),
                                _pipe@1 = gleam@list:filter(
                                    _pipe,
                                    fun(P) ->
                                        {{Char_a, _}, {Char_b, _}} = P,
                                        Char_a /= Char_b
                                    end
                                ),
                                erlang:length(_pipe@1)
                            end,
                            Transpositions = Mismatches div 2,
                            M = erlang:float(Matches_count),
                            La = erlang:float(Len_a),
                            Lb = erlang:float(Len_b),
                            T = erlang:float(Transpositions),
                            (((case La of
                                +0.0 -> +0.0;
                                -0.0 -> -0.0;
                                Gleam@denominator -> M / Gleam@denominator
                            end) + (case Lb of
                                +0.0 -> +0.0;
                                -0.0 -> -0.0;
                                Gleam@denominator@1 -> M / Gleam@denominator@1
                            end)) + (case M of
                                +0.0 -> +0.0;
                                -0.0 -> -0.0;
                                Gleam@denominator@2 -> (M - T) / Gleam@denominator@2
                            end)) / 3.0
                    end
            end
    end.

-file("src/starfuzz/similarity.gleam", 135).
-spec common_prefix_len(list(binary()), list(binary()), integer()) -> integer().
common_prefix_len(A, B, Count) ->
    case {Count < 4, A, B} of
        {true, [Ha | Ta], [Hb | Tb]} when Ha =:= Hb ->
            common_prefix_len(Ta, Tb, Count + 1);

        {_, _, _} ->
            Count
    end.

-file("src/starfuzz/similarity.gleam", 121).
?DOC(
    " Computes the Jaro-Winkler similarity score between two strings.\n"
    "\n"
    " Winkler's optimization adds a prefix boost (up to 4 characters) to Jaro's score\n"
    " if the strings start with the exact same prefix.\n"
).
-spec jaro_winkler(binary(), binary()) -> float().
jaro_winkler(A, B) ->
    Jaro_score = jaro(A, B),
    case Jaro_score > 0.7 of
        false ->
            Jaro_score;

        true ->
            A_chars = gleam@string:to_graphemes(A),
            B_chars = gleam@string:to_graphemes(B),
            Prefix_len = common_prefix_len(A_chars, B_chars, 0),
            Jaro_score + ((0.1 * erlang:float(Prefix_len)) * (1.0 - Jaro_score))
    end.

-file("src/starfuzz/similarity.gleam", 144).
-spec list_frequencies(list(EDA)) -> gleam@dict:dict(EDA, integer()).
list_frequencies(Items) ->
    gleam@list:fold(
        Items,
        maps:new(),
        fun(Acc, Item) -> case gleam_stdlib:map_get(Acc, Item) of
                {ok, Count} ->
                    gleam@dict:insert(Acc, Item, Count + 1);

                {error, nil} ->
                    gleam@dict:insert(Acc, Item, 1)
            end end
    ).

-file("src/starfuzz/similarity.gleam", 153).
-spec intersection_size(list(EDE), list(EDE)) -> integer().
intersection_size(A, B) ->
    A_freqs = list_frequencies(A),
    {Size, _} = gleam@list:fold(
        B,
        {0, A_freqs},
        fun(State, Item) ->
            {Count, Freqs} = State,
            case gleam_stdlib:map_get(Freqs, Item) of
                {ok, Freq} when Freq > 0 ->
                    {Count + 1, gleam@dict:insert(Freqs, Item, Freq - 1)};

                _ ->
                    {Count, Freqs}
            end
        end
    ),
    Size.

-file("src/starfuzz/similarity.gleam", 169).
?DOC(
    " Computes Sørensen-Dice similarity over token multisets.\n"
    " Returns a value between `0.0` and `1.0`.\n"
).
-spec dice(list(EDH), list(EDH)) -> float().
dice(A, B) ->
    Len_a = erlang:length(A),
    Len_b = erlang:length(B),
    case (Len_a =:= 0) andalso (Len_b =:= 0) of
        true ->
            1.0;

        false ->
            Isect = intersection_size(A, B),
            case erlang:float(Len_a + Len_b) of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator -> 2.0 * erlang:float(Isect) / Gleam@denominator
            end
    end.

-file("src/starfuzz/similarity.gleam", 183).
?DOC(
    " Computes Jaccard similarity index over token multisets.\n"
    " Returns a value between `0.0` and `1.0`.\n"
).
-spec jaccard(list(EDK), list(EDK)) -> float().
jaccard(A, B) ->
    Len_a = erlang:length(A),
    Len_b = erlang:length(B),
    case (Len_a =:= 0) andalso (Len_b =:= 0) of
        true ->
            1.0;

        false ->
            Isect = intersection_size(A, B),
            case erlang:float((Len_a + Len_b) - Isect) of
                +0.0 -> +0.0;
                -0.0 -> -0.0;
                Gleam@denominator -> erlang:float(Isect) / Gleam@denominator
            end
    end.

-file("src/starfuzz/similarity.gleam", 197).
?DOC(
    " Computes Cosine similarity of token frequency vectors (bag-of-words model).\n"
    " Returns a value between `0.0` and `1.0`.\n"
).
-spec cosine(list(EDN), list(EDN)) -> float().
cosine(A, B) ->
    Len_a = erlang:length(A),
    Len_b = erlang:length(B),
    case (Len_a =:= 0) andalso (Len_b =:= 0) of
        true ->
            1.0;

        false ->
            case (Len_a =:= 0) orelse (Len_b =:= 0) of
                true ->
                    +0.0;

                false ->
                    A_freqs = list_frequencies(A),
                    B_freqs = list_frequencies(B),
                    Dot = gleam@dict:fold(
                        A_freqs,
                        +0.0,
                        fun(Acc, Item, Count_a) ->
                            case gleam_stdlib:map_get(B_freqs, Item) of
                                {ok, Count_b} ->
                                    Acc + (erlang:float(Count_a) * erlang:float(
                                        Count_b
                                    ));

                                {error, nil} ->
                                    Acc
                            end
                        end
                    ),
                    Norm_a = gleam@float:square_root(
                        gleam@dict:fold(
                            A_freqs,
                            +0.0,
                            fun(Acc@1, _, Count) ->
                                F = erlang:float(Count),
                                Acc@1 + (F * F)
                            end
                        )
                    ),
                    Norm_b = gleam@float:square_root(
                        gleam@dict:fold(
                            B_freqs,
                            +0.0,
                            fun(Acc@2, _, Count@1) ->
                                F@1 = erlang:float(Count@1),
                                Acc@2 + (F@1 * F@1)
                            end
                        )
                    ),
                    case {Norm_a, Norm_b} of
                        {{ok, Na}, {ok, Nb}} when (Na > +0.0) andalso (Nb > +0.0) ->
                            case (Na * Nb) of
                                +0.0 -> +0.0;
                                -0.0 -> -0.0;
                                Gleam@denominator -> Dot / Gleam@denominator
                            end;

                        {_, _} ->
                            +0.0
                    end
            end
    end.