    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.bloomfilter;
    018
    019import java.util.function.LongBinaryOperator;
    020
    021/**
    022 * Implementations of set operations on BitMapExtractors.
    023 *
    024 * @since 4.5
    025 */
    026public final class SetOperations {
    027
    028    /**
    029     * Calculates the cardinality of the logical {@code AND} of the bit maps for the two filters.
    030     * @param first the first BitMapExtractor.
    031     * @param second the second BitMapExtractor
    032     * @return the cardinality of the {@code AND} of the filters.
    033     */
    034    public static int andCardinality(final BitMapExtractor first, final BitMapExtractor second) {
    035        return cardinality(first, second, (x, y) -> x & y);
    036    }
    037
    038    /**
    039     * Calculates the cardinality of a BitMapExtractor. By necessity this method will visit each bit map
    040     * created by the bitMapExtractor.
    041     * @param bitMapExtractor the extractor to calculate the cardinality for.
    042     * @return the cardinality of the bit maps produced by the bitMapExtractor.
    043     */
    044    public static int cardinality(final BitMapExtractor bitMapExtractor) {
    045        final int[] cardinality = new int[1];
    046        bitMapExtractor.processBitMaps(l -> {
    047            cardinality[0] += Long.bitCount(l);
    048            return true;
    049        });
    050        return cardinality[0];
    051    }
    052
    053    /**
    054     * Calculates the cardinality of the result of a LongBinaryOperator using the
    055     * {@code BitMapExtractor.makePredicate} method.
    056     * @param first the first BitMapExtractor
    057     * @param second the second BitMapExtractor
    058     * @param op a long binary operation on where x = {@code first} and y = {@code second} bitmap extractors.
    059     * @return the calculated cardinality.
    060     */
    061    private static int cardinality(final BitMapExtractor first, final BitMapExtractor second, final LongBinaryOperator op) {
    062        final int[] cardinality = new int[1];
    063
    064        first.processBitMapPairs(second, (x, y) -> {
    065            cardinality[0] += Long.bitCount(op.applyAsLong(x, y));
    066            return true;
    067        });
    068        return cardinality[0];
    069    }
    070
    071    /**
    072     * Calculates the Cosine distance between two BitMapExtractor.
    073     *
    074     * <p>Cosine distance is defined as {@code 1 - Cosine similarity}</p>
    075     *
    076     * @param first the first BitMapExtractor.
    077     * @param second the second BitMapExtractor.
    078     * @return the jaccard distance.
    079     */
    080    public static double cosineDistance(final BitMapExtractor first, final BitMapExtractor second) {
    081        return 1.0 - cosineSimilarity(first, second);
    082    }
    083
    084    /**
    085     * Calculates the Cosine similarity between two BitMapExtractors.
    086     * <p> Also known as Orchini similarity and the Tucker coefficient of congruence or
    087     * Ochiai similarity.</p>
    088     *
    089     * <p>If either extractor is empty the result is 0 (zero)</p>
    090     *
    091     * @param first the first BitMapExtractor.
    092     * @param second the second BitMapExtractor.
    093     * @return the Cosine similarity.
    094     */
    095    public static double cosineSimilarity(final BitMapExtractor first, final BitMapExtractor second) {
    096        final int numerator = andCardinality(first, second);
    097        // Given that the cardinality is an int then the product as a double will not
    098        // overflow, we can use one sqrt:
    099        return numerator == 0 ? 0 : numerator / Math.sqrt(cardinality(first) * cardinality(second));
    100    }
    101
    102    /**
    103     * Calculates the Cosine similarity between two Bloom filters.
    104     * <p> Also known as Orchini similarity and the Tucker coefficient of congruence or
    105     * Ochiai similarity.</p>
    106     *
    107     * <p>If either filter is empty (no enabled bits) the result is 0 (zero)</p>
    108     *
    109     * <p>This is a version of cosineSimilarity optimized for Bloom filters.</p>
    110     *
    111     * @param first the first Bloom filter.
    112     * @param second the second Bloom filter.
    113     * @return the Cosine similarity.
    114     */
    115    public static double cosineSimilarity(final BloomFilter first, final BloomFilter second) {
    116        final int numerator = andCardinality(first, second);
    117        // Given that the cardinality is an int then the product as a double will not
    118        // overflow, we can use one sqrt:
    119        return numerator == 0 ? 0 : numerator / Math.sqrt(first.cardinality() * second.cardinality());
    120    }
    121
    122    /**
    123     * Calculates the Hamming distance between two BitMapExtractors.
    124     *
    125     * @param first the first BitMapExtractor.
    126     * @param second the second BitMapExtractor.
    127     * @return the Hamming distance.
    128     */
    129    public static int hammingDistance(final BitMapExtractor first, final BitMapExtractor second) {
    130        return xorCardinality(first, second);
    131    }
    132
    133    /**
    134     * Calculates the Jaccard distance between two BitMapExtractor.
    135     *
    136     * <p>Jaccard distance is defined as {@code 1 - Jaccard similarity}</p>
    137     *
    138     * @param first the first BitMapExtractor.
    139     * @param second the second BitMapExtractor.
    140     * @return the Jaccard distance.
    141     */
    142    public static double jaccardDistance(final BitMapExtractor first, final BitMapExtractor second) {
    143        return 1.0 - jaccardSimilarity(first, second);
    144    }
    145
    146    /**
    147     * Calculates the Jaccard similarity between two BitMapExtractor.
    148     *
    149     * <p>Also known as Jaccard index, Intersection over Union, and Jaccard similarity coefficient</p>
    150     *
    151     * @param first the first BitMapExtractor.
    152     * @param second the second BitMapExtractor.
    153     * @return the Jaccard similarity.
    154     */
    155    public static double jaccardSimilarity(final BitMapExtractor first, final BitMapExtractor second) {
    156        final int[] cardinality = new int[2];
    157        first.processBitMapPairs(second, (x, y) -> {
    158            cardinality[0] += Long.bitCount(x & y);
    159            cardinality[1] += Long.bitCount(x | y);
    160            return true;
    161        });
    162        final int intersection = cardinality[0];
    163        return intersection == 0 ? 0 : intersection / (double) cardinality[1];
    164    }
    165
    166    /**
    167     * Calculates the cardinality of the logical {@code OR} of the bit maps for the two filters.
    168     * @param first the first BitMapExtractor.
    169     * @param second the second BitMapExtractor
    170     * @return the cardinality of the {@code OR} of the filters.
    171     */
    172    public static int orCardinality(final BitMapExtractor first, final BitMapExtractor second) {
    173        return cardinality(first, second, (x, y) -> x | y);
    174    }
    175
    176    /**
    177     * Calculates the cardinality of the logical {@code XOR} of the bit maps for the two filters.
    178     * @param first the first BitMapExtractor.
    179     * @param second the second BitMapExtractor
    180     * @return the cardinality of the {@code XOR} of the filters.
    181     */
    182    public static int xorCardinality(final BitMapExtractor first, final BitMapExtractor second) {
    183        return cardinality(first, second, (x, y) -> x ^ y);
    184    }
    185
    186    /**
    187     * Do not instantiate.
    188     */
    189    private SetOperations() {
    190    }
    191}