CosineSimilarity.cs

using System;
using System.Collections.Generic;

namespace Algorithms.Strings.Similarity;

public static class CosineSimilarity
{
    /// <summary>
    /// Calculates the Cosine Similarity between two strings.
    /// Cosine Similarity is a measure of similarity between two non-zero vectors of an inner product space.
    /// It measures the cosine of the angle between the two vectors.
    /// </summary>
    /// <param name="left">The first string.</param>
    /// <param name="right">The second string.</param>
    /// <returns>
    /// A double value between 0 and 1 that represents the similarity
    /// of the two strings.
    /// </returns>
    public static double Calculate(string left, string right)
    {
        // Step 1: Get the vectors for the two strings
        // Each vector represents the frequency of each character in the string.
        var vectors = GetVectors(left.ToLowerInvariant(), right.ToLowerInvariant());
        var leftVector = vectors.leftVector;
        var rightVector = vectors.rightVector;

        // Step 2: Calculate the intersection of the two vectors
        // The intersection is the set of characters that appear in both strings.
        var intersection = GetIntersection(leftVector, rightVector);

        // Step 3: Calculate the dot product of the two vectors
        // The dot product is the sum of the products of the corresponding values of the characters in the intersection.
        var dotProduct = DotProduct(leftVector, rightVector, intersection);

        // Step 4: Calculate the square magnitude of each vector
        // The magnitude is the square root of the sum of the squares of the values in the vector.
        var mLeft = 0.0;
        foreach (var value in leftVector.Values)
        {
            mLeft += value * value;
        }

        var mRight = 0.0;
        foreach (var value in rightVector.Values)
        {
            mRight += value * value;
        }

        // Step 5: Check if either vector is zero
        // If either vector is zero (i.e., all characters are unique), the Cosine Similarity is 0.
        if (mLeft <= 0 || mRight <= 0)
        {
            return 0.0;
        }

        // Step 6: Calculate and return the Cosine Similarity
        // The Cosine Similarity is the dot product divided by the product of the magnitudes.
        return dotProduct / (Math.Sqrt(mLeft) * Math.Sqrt(mRight));
    }

    /// <summary>
    /// Calculates the vectors for the given strings.
    /// </summary>
    /// <param name="left">The first string.</param>
    /// <param name="right">The second string.</param>
    /// <returns>A tuple containing the vectors for the two strings.</returns>
    private static (Dictionary<char, int> leftVector, Dictionary<char, int> rightVector) GetVectors(string left, string right)
    {
        var leftVector = new Dictionary<char, int>();
        var rightVector = new Dictionary<char, int>();

        // Calculate the frequency of each character in the left string
        foreach (var character in left)
        {
            leftVector.TryGetValue(character, out var frequency);
            leftVector[character] = ++frequency;
        }

        // Calculate the frequency of each character in the right string
        foreach (var character in right)
        {
            rightVector.TryGetValue(character, out var frequency);
            rightVector[character] = ++frequency;
        }

        return (leftVector, rightVector);
    }

    /// <summary>
    /// Calculates the dot product between two vectors represented as dictionaries of character frequencies.
    /// The dot product is the sum of the products of the corresponding values of the characters in the intersection of the two vectors.
    /// </summary>
    /// <param name="leftVector">The vector of the left string.</param>
    /// <param name="rightVector">The vector of the right string.</param>
    /// <param name="intersection">The intersection of the two vectors, represented as a set of characters.</param>
    /// <returns>The dot product of the two vectors.</returns>
    private static double DotProduct(Dictionary<char, int> leftVector, Dictionary<char, int> rightVector, HashSet<char> intersection)
    {
        // Initialize the dot product to 0
        double dotProduct = 0;

        // Iterate over each character in the intersection of the two vectors
        foreach (var character in intersection)
        {
            // Calculate the product of the corresponding values of the characters in the left and right vectors
            dotProduct += leftVector[character] * rightVector[character];
        }

        // Return the dot product
        return dotProduct;
    }

    /// <summary>
    /// Calculates the intersection of two vectors, represented as dictionaries of character frequencies.
    /// </summary>
    /// <param name="leftVector">The vector of the left string.</param>
    /// <param name="rightVector">The vector of the right string.</param>
    /// <returns>A HashSet containing the characters that appear in both vectors.</returns>
    private static HashSet<char> GetIntersection(Dictionary<char, int> leftVector, Dictionary<char, int> rightVector)
    {
        // Initialize a HashSet to store the intersection of the two vectors.
        var intersection = new HashSet<char>();

        // Iterate over each key-value pair in the left vector.
        foreach (var kvp in leftVector)
        {
            // If the right vector contains the same key, add it to the intersection.
            if (rightVector.ContainsKey(kvp.Key))
            {
                intersection.Add(kvp.Key);
            }
        }

        return intersection;
    }
}