package util;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
/**
* 計算文本相似
*/
public class SimHash {
private Stringtokens;
? ? private BigIntegerintSimHash;
? ? private StringstrSimHash;
? ? private int hashbits =64;
? ? public SimHash(String tokens) {
this.tokens = tokens;
? ? ? ? this.intSimHash =this.simHash();
? ? }
public SimHash(String tokens, int hashbits) {
this.tokens = tokens;
? ? ? ? this.hashbits = hashbits;
? ? ? ? this.intSimHash =this.simHash();
? ? }
public BigIntegersimHash() {
int[] v =new int[this.hashbits];
? ? ? ? StringTokenizer stringTokens =new StringTokenizer(this.tokens);
? ? ? ? while (stringTokens.hasMoreTokens()) {
String temp = stringTokens.nextToken();
? ? ? ? ? ? BigInteger t =this.hash(temp);
? ? ? ? ? ? for (int i =0; i
BigInteger bitmask =new BigInteger("1").shiftLeft(i);
? ? ? ? ? ? ? ? if (t.and(bitmask).signum() !=0) {
v[i] +=1;
? ? ? ? ? ? ? ? }else {
v[i] -=1;
? ? ? ? ? ? ? ? }
}
}
BigInteger fingerprint =new BigInteger("0");
? ? ? ? StringBuffer simHashBuffer =new StringBuffer();
? ? ? ? for (int i =0; i
if (v[i] >=0) {
fingerprint = fingerprint.add(new BigInteger("1").shiftLeft(i));
? ? ? ? ? ? ? ? simHashBuffer.append("1");
? ? ? ? ? ? }else{
simHashBuffer.append("0");
? ? ? ? ? ? }
}
this.strSimHash = simHashBuffer.toString();
? ? ? ? System.out.println(this.strSimHash +" length " +this.strSimHash.length());
? ? ? ? return fingerprint;
? ? }
private BigIntegerhash(String source) {
if (source ==null || source.length() ==0) {
return new BigInteger("0");
? ? ? ? }else {
char[] sourceArray = source.toCharArray();
? ? ? ? ? ? BigInteger x = BigInteger.valueOf(((long) sourceArray[0]) <<7);
? ? ? ? ? ? BigInteger m =new BigInteger("1000003");
? ? ? ? ? ? BigInteger mask =new BigInteger("2").pow(this.hashbits).subtract(
new BigInteger("1"));
? ? ? ? ? ? for (char item : sourceArray) {
BigInteger temp = BigInteger.valueOf((long) item);
? ? ? ? ? ? ? ? x = x.multiply(m).xor(temp).and(mask);
? ? ? ? ? ? }
x = x.xor(new BigInteger(String.valueOf(source.length())));
? ? ? ? ? ? if (x.equals(new BigInteger("-1"))) {
x =new BigInteger("-2");
? ? ? ? ? ? }
return x;
? ? ? ? }
}
public int hammingDistance(SimHash other) {
BigInteger x =this.intSimHash.xor(other.intSimHash);
? ? ? ? int tot =0;
? ? ? ? //統(tǒng)計x中二進(jìn)制位數(shù)為1的個數(shù)
? ? ? ? //我們想想，一個二進(jìn)制數(shù)減去1，那么，從最后那個1（包括那個1）后面的數(shù)字全都反了，對吧，然后，n&(n-1)就相當(dāng)于把后面的數(shù)字清0，
? ? ? ? //我們看n能做多少次這樣的操作就OK了。
? ? ? ? while (x.signum() !=0) {
tot +=1;
? ? ? ? ? ? x = x.and(x.subtract(new BigInteger("1")));
? ? ? ? }
return tot;
? ? }
public int getDistance(String str1, String str2) {
int distance;
? ? ? ? if (str1.length() != str2.length()) {
distance = -1;
? ? ? ? }else {
distance =0;
? ? ? ? ? ? for (int i =0; i < str1.length(); i++) {
if (str1.charAt(i) != str2.charAt(i)) {
distance++;
? ? ? ? ? ? ? ? }
}
}
return distance;
? ? }
public ListsubByDistance(SimHash simHash, int distance){
int numEach =this.hashbits/(distance+1);
? ? ? ? List characters =new ArrayList();
? ? ? ? StringBuffer buffer =new StringBuffer();
? ? ? ? int k =0;
? ? ? ? for(int i =0; i
boolean sr = simHash.intSimHash.testBit(i);
? ? ? ? ? ? if(sr){
buffer.append("1");
? ? ? ? ? ? }
else{
buffer.append("0");
? ? ? ? ? ? }
if( (i+1)%numEach ==0 ){
BigInteger eachValue =new BigInteger(buffer.toString(),2);
? ? ? ? ? ? ? ? //System.out.println("----" +eachValue );
? ? ? ? ? ? ? ? buffer.delete(0, buffer.length());
? ? ? ? ? ? ? ? characters.add(eachValue);
? ? ? ? ? ? }
}
return characters;
? ? }
public static void main(String[] args) {
String s ="普京高度評價習(xí)主席在俄中關(guān)系發(fā)展中發(fā)揮的重要作用，強調(diào)不久前習(xí)主席對俄進(jìn)行國事訪問取得圓滿成功，相信俄中關(guān)系將繼續(xù)保持良好發(fā)展勢頭。";
? ? ? ? SimHash hash1 =new SimHash(s, 64);
? ? ? ? System.out.println(hash1.intSimHash +"? " + hash1.intSimHash.bitLength());
? ? ? ? hash1.subByDistance(hash1, 3);
? ? ? ? System.out.println("\n");
? ? ? ? s ="普京高度評價習(xí)主席在俄中關(guān)系發(fā)展中發(fā)揮的重要作用，強調(diào)不久前習(xí)主席對俄進(jìn)行國事訪問取得圓滿成功";
? ? ? ? SimHash hash2 =new SimHash(s, 64);
? ? ? ? System.out.println(hash2.intSimHash+"? " + hash2.intSimHash.bitCount());
? ? ? ? hash1.subByDistance(hash2, 3);
? ? ? ? s ="普京高度評價習(xí)主席在俄中關(guān)系發(fā)展中發(fā)揮的重要作用，強調(diào)不久前習(xí)主席對俄進(jìn)行國事訪問取得圓滿成功，相信俄中關(guān)系將繼續(xù)保持良好發(fā)展勢頭。";
? ? ? ? SimHash hash3 =new SimHash(s, 64);
? ? ? ? System.out.println(hash3.intSimHash+"? " + hash3.intSimHash.bitCount());
? ? ? ? hash1.subByDistance(hash3, 3);
? ? ? ? System.out.println("============================");
? ? ? ? int dis = hash1.getDistance(hash1.strSimHash,hash2.strSimHash);
? ? ? ? System.out.println(hash1.hammingDistance(hash2) +" "+ dis);
? ? ? ? int dis2 = hash1.getDistance(hash1.strSimHash,hash3.strSimHash);
? ? ? ? System.out.println(hash1.hammingDistance(hash3) +" " + dis2);
? ? }
}
