minHashを使って2つ以上のセットを比較する

Question

私はFindSimilarというクラスを持っています。このクラスはminHashを使って2セット間の類似点を見つけます（この目的のためにはうまくいきます）。私の問題は、2セット以上を比較する必要があることです。具体的には、与えられたset1と未知の量の他のセットとを比較する必要があります。ここではクラスがある：

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)); 
} 
} 

私は2つの以上のセットに​​メソッドを使用する必要があります。問題は、私がそれらのすべてを乗り越える方法を見つけることができないということです。 forを作成した場合、set1とsetiを比較したいとは言えません。私は理にかなっているかどうか分からないが、私はちょっと混乱していると認めなければならない。

このプログラムの目的は、ユーザーを比較することです。ユーザーは連絡先（他のユーザー）の一覧を持ち、同様のユーザーには同様の連絡先があります。各セットはユーザーであり、セットの内容はその連絡先になります。

Answer 1

私はArrayList構造内のすべてのsetsを配置して、実際の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]));  
    } 
} 

これはThe expression of type Set[] needs unchecked conversion to conform to Set<String>[]警告を放つが、うまく動作します。これはまさに私が望んでいたものです（私はsetsの中にデータを入れるのにまだforが必要ですが、それは難しいはずはありません。もしこのソリューションを使うべきか、私はまだ学習しているので、聞きたいのですが、どんな情報でも便利です。

Answer 2

セット類似性結合アルゴリズムの実装では、セットは通常整数の配列に変換されます。通常、ハッシュマップを使用して行われます。配列はソートされているため、2つのセットの重なりをマージのように計算できます。 。