I have a class called FindSimilar
which uses minHash to find similarities between 2 sets (and for this goal, it works great). My problem is that I need to compare more than 2 sets, more specifically, I need to compare a given set1
with an unknown amount of other sets. Here is the class:
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Set;
public class FindSimilar<T>
{
private int hash[];
private int numHash;
public FindSimilar(int numHash)
{
this.numHash = numHash;
hash = new int[numHash];
Random r = new Random(11);
for (int i = 0; i < numHash; i++)
{
int a = (int) r.nextInt();
int b = (int) r.nextInt();
int c = (int) r.nextInt();
int x = hash(a * b * c, a, b, c);
hash[i] = x;
}
}
public double similarity(Set<T> set1, Set<T> set2)
{
int numSets = 4;
Map<T, boolean[]> bitMap = buildBitMap(set1, set2);
int[][] minHashValues = initializeHashBuckets(numSets, numHash);
computeFindSimilarForSet(set1, 0, minHashValues, bitMap);
computeFindSimilarForSet(set2, 1, minHashValues, bitMap);
return computeSimilarityFromSignatures(minHashValues, numHash);
}
private static int[][] initializeHashBuckets(int numSets,
int numHashFunctions)
{
int[][] minHashValues = new int[numSets][numHashFunctions];
for (int i = 0; i < numSets; i++)
{
for (int j = 0; j < numHashFunctions; j++)
{
minHashValues[i][j] = Integer.MAX_VALUE;
}
}
return minHashValues;
}
private static double computeSimilarityFromSignatures(
int[][] minHashValues, int numHashFunctions)
{
int identicalFindSimilares = 0;
for (int i = 0; i < numHashFunctions; i++)
{
if (minHashValues[0][i] == minHashValues[1][i])
{
identicalFindSimilares++;
}
}
return (1.0 * identicalFindSimilares) / numHashFunctions;
}
private static int hash(int x, int a, int b, int c)
{
int hashValue = (int) ((a * (x >> 4) + b * x + c) & 131071);
return Math.abs(hashValue);
}
private void computeFindSimilarForSet(Set<T> set, int setIndex,
int[][] minHashValues, Map<T, boolean[]> bitArray)
{
int index = 0;
for (T element : bitArray.keySet())
{
/*
* for every element in the bit array
*/
for (int i = 0; i < numHash; i++)
{
/*
* for every hash
*/
if (set.contains(element))
{
/*
* if the set contains the element
*/
int hindex = hash[index];
if (hindex < minHashValues[setIndex][index])
{
/*
* if current hash is smaller than the existing hash in
* the slot then replace with the smaller hash value
*/
minHashValues[setIndex][i] = hindex;
}
}
}
index++;
}
}
public Map<T, boolean[]> buildBitMap(Set<T> set1, Set<T> set2)
{
Map<T, boolean[]> bitArray = new HashMap<T, boolean[]>();
for (T t : set1)
{
bitArray.put(t, new boolean[] { true, false });
}
for (T t : set2)
{
if (bitArray.containsKey(t))
{
// item is present in set1
bitArray.put(t, new boolean[] { true, true });
}
else if (!bitArray.containsKey(t))
{
// item is not present in set1
bitArray.put(t, new boolean[] { false, true });
}
}
return bitArray;
}
public static void main(String[] args)
{
Set<String> set1 = new HashSet<String>();
set1.add("FRANCISCO");
set1.add("abc");
set1.add("SAN");
Set<String> set2 = new HashSet<String>();
set2.add("b");
set2.add("a");
set2.add("SAN");
set2.add("USA");
FindSimilar<String> minHash = new FindSimilar<String>(set1.size() + set2.size());
System.out.println("Set1 : " + set1);
System.out.println("Set2 : " + set2);
System.out.println("Similarity between two sets: "
+ minHash.similarity(set1, set2));
}
}
I need to use the similarity
method on more than 2 sets. The problem is that I can't find a way to go over all of them. If I create a for
, I can't say I want to compare set1
and seti
. I am not sure if I am making sense, I must admit I am a bit confused.
The goal of the program is to compare users. A user has a list of contacts (other users) and similar users have similar contacts. Each set is a user and the contents of the sets will be their contacts.
I have found a (not sure if) cheesy solution for my problem by placing all sets
inside an ArrayList
structure and then converting it to an actual array
:
ArrayList<Set<String>> list = new ArrayList<Set<String>>();
for(int i = 0; i < numPeople; i++){
Set<String> set1 = new HashSet<String>();
list.add(set1);
//another for goes here later on
}
Set<String>[] bs = list.toArray(new Set[0]);
.
.
.
public static void main(String[] args)
{
.
.
.
for(int i = 1; i<bs.length; i++){
System.out.format("Set %d: ", i+1);
System.out.println(bs[0]);
System.out.println("Similarity between two sets: "
+ minHash.similarity(bs[0], bs[i]));
}
}
This gives off a The expression of type Set[] needs unchecked conversion to conform to Set<String>[]
warning, but runs fine. This does exactly what I wanted it to (I still need a for
to put data inside the sets
, but that shouldn't be hard. If anyone could tell me if this solution should be used or if there is a better alternative, I'd like to hear it, since I am still learning and any info would be useful.