<commit_before>﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProbabilisticDataStructures
{
    /// <summary>
    /// MinHash is a variation of the technique for estimating similarity between
    /// two sets as presented by Broder in On the resemblance and containment of
    /// documents:
    ///
    /// http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf
    ///
    /// This can be used to cluster or compare documents by splitting the corpus
    /// into a bag of words. MinHash returns the approximated similarity ratio of
    /// the two bags. The similarity is less accurate for very small bags of words.
    /// </summary>
    public static class MinHash
    {
        private static Random random = new Random();

        /// <summary>
        /// Returns the similarity between two bags.
        /// </summary>
        /// <param name="bag1">The first bag</param>
        /// <param name="bag2">The second bag</param>
        /// <returns>The similarity between the bags</returns>
        public static float Similarity(string[] bag1, string[] bag2)
        {
            var k = bag1.Length + bag2.Length;
            var hashes = new int[k];
            for (int i = 0; i < k; i++)
            {
                var a = random.Next();
                var b = random.Next();
                var c = random.Next();
                var x = computeHash((uint)(a * b * c), (uint)a, (uint)b, c);
                hashes[i] = (int)x;
            }

            var bMap = bitMap(bag1, bag2);
            var minHashValues = hashBuckets(2, k);
            minHash(bag1, 0, minHashValues, bMap, k, hashes);
            minHash(bag2, 1, minHashValues, bMap, k, hashes);
            return similarity(minHashValues, k);
        }

        private static void minHash(
            string[] bag,
            int bagIndex,
            int[][] minHashValues,
            Dictionary<string, bool[]> bitArray,
            int k,
            int[] hashes)
        {
            var index = 0;
            foreach (var element in bitArray)
            {
                for (int i = 0; i < k; i++)
                {
                    if (bag.Contains(element.Key))
                    {
                        var hindex = hashes[index];
                        if (hindex < minHashValues[bagIndex][index])
                        {
                            minHashValues[bagIndex][index] = hindex;
                        }
                    }
                }
                index++;
            }<commit_msg>Speed up the MinHash.Similarity() check by parallelizing the inner for loop.<commit_after>﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ProbabilisticDataStructures
{
    /// <summary>
    /// MinHash is a variation of the technique for estimating similarity between
    /// two sets as presented by Broder in On the resemblance and containment of
    /// documents:
    ///
    /// http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf
    ///
    /// This can be used to cluster or compare documents by splitting the corpus
    /// into a bag of words. MinHash returns the approximated similarity ratio of
    /// the two bags. The similarity is less accurate for very small bags of words.
    /// </summary>
    public static class MinHash
    {
        private static Random random = new Random();

        /// <summary>
        /// Returns the similarity between two bags.
        /// </summary>
        /// <param name="bag1">The first bag</param>
        /// <param name="bag2">The second bag</param>
        /// <returns>The similarity between the bags</returns>
        public static float Similarity(string[] bag1, string[] bag2)
        {
            var k = bag1.Length + bag2.Length;
            var hashes = new int[k];
            for (int i = 0; i < k; i++)
            {
                var a = random.Next();
                var b = random.Next();
                var c = random.Next();
                var x = computeHash((uint)(a * b * c), (uint)a, (uint)b, c);
                hashes[i] = (int)x;
            }

            var bMap = bitMap(bag1, bag2);
            var minHashValues = hashBuckets(2, k);
            minHash(bag1, 0, minHashValues, bMap, k, hashes);
            minHash(bag2, 1, minHashValues, bMap, k, hashes);
            return similarity(minHashValues, k);
        }

        private static void minHash(
            string[] bag,
            int bagIndex,
            int[][] minHashValues,
            Dictionary<string, bool[]> bitArray,
            int k,
            int[] hashes)
        {
            var options = new ParallelOptions();
            options.MaxDegreeOfParallelism = 4;
            var index = 0;

            foreach (var element in bitArray)
            {
                Parallel.For(0, k, options, (i, loopState) =>
                {
                    if (bag.Contains(element.Key))
                    {
                        var hindex = hashes[index];
                        if (hindex < minHashValues[bagIndex][index])
                        {
                            minHashValues[bagIndex][index] = hindex;
                        }
                    }
                });
                index++;
            }
{'fraction_non_alphanumeric': 0.10776574261061135, 'fraction_numerical': 0.006058380760051404, 'mean_word_length': 1.479745106964042, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 26, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6524761', 'n_tokens_mistral': 1482, 'n_tokens_neox': 1404, 'n_words': 448}