java simhash

作者:原创时间:2022-04-20
文档

java simhash是什么?让我们一起来了解一下吧!

java simhash是java程序中的一种算法。Simhash算法产生与2002年,设计非常美妙,它输入是一个向量,得出的结果是一个F位的签名值。

Simhash和一般的hash算法不同,它具有两个关键的特点:

1.一个文档的指纹是所有属性的某种hash;

2.相似文档的hash应该是相似的;

 simhash 算法如下:
1,将一个 f 维的向量 V 初始化为 0 ; f 位的二进制数 S 初始化为 0 ;
2,对每一个特征:用传统的 hash 算法对该特征产生一个 f 位的签名 b 。对 i=1 到 f :
如果b 的第 i 位为 1 ,则 V 的第 i 个元素加上该特征的权重;
否则,V 的第 i 个元素减去该特征的权重。 
3,如果 V 的第 i 个元素大于 0 ,则 S 的第 i 位为 1 ,否则为 0 ;
4,输出 S 作为签名。

simhash 算法代码:

package com.xxxx.checkandbigdataquery.utils;
 
import it.unimi.dsi.fastutil.longs.LongOpenHashSet;
import it.unimi.dsi.fastutil.longs.LongSet;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.nio.CharBuffer;
import java.util.Set;
 
 
/**
 * a basic SimHash implementation
 *
 *
 */
public class SimHash {
  public static final int  HASH_SIZE          = 64;
  public static final long HASH_RANGE         = 2 ^ HASH_SIZE;
  public static MurmurHash hasher             = new MurmurHash();
 
  /**
   * use short cuts to obtains a speed optimized simhash calculation
   *
   * @param s
   *          input string
   * @return 64 bit simhash of input string
   */
 
  private static final int FIXED_CGRAM_LENGTH = 4;
 
  public static long computeOptimizedSimHashForString(String s) {
    return computeOptimizedSimHashForString(CharBuffer.wrap(s));
  }
 
  public static long computeOptimizedSimHashForString(CharBuffer s) {
 
    LongSet shingles = new LongOpenHashSet(Math.min(s.length(), 100000));
 
    int length = s.length();
 
    long timeStart = System.currentTimeMillis();
    for (int i = 0; i < length - FIXED_CGRAM_LENGTH + 1; i++) {
      // extract an ngram
 
      long shingle = s.charAt(i);
      shingle <<= 16;
      shingle |= s.charAt(i + 1);
      shingle <<= 16;
      shingle |= s.charAt(i + 2);
      shingle <> 56);
      longAsBytes[1] = (byte) (shingle >> 48);
      longAsBytes[2] = (byte) (shingle >> 40);
      longAsBytes[3] = (byte) (shingle >> 32);
      longAsBytes[4] = (byte) (shingle >> 24);
      longAsBytes[5] = (byte) (shingle >> 16);
      longAsBytes[6] = (byte) (shingle >> 8);
      longAsBytes[7] = (byte) (shingle);
 
      long longHash = FPGenerator.std64.fp(longAsBytes, 0, 8);
      for (int i = 0; i < HASH_SIZE; ++i) {
        boolean bitSet = ((longHash >> i) & 1L) == 1L;
        v[i] += (bitSet) ? 1 : -1;
      }
    }
 
    long simhash = 0;
    for (int i = 0; i < HASH_SIZE; ++i) {
      if (v[i] > 0) {
        simhash |= (1L << i);
      }
    }
    return simhash;
  }
 
  public static long computeSimHashFromString(Set shingles) {
 
    int v[] = new int[HASH_SIZE];
    // compute a set of shingles
    for (String shingle : shingles) {
      byte[] bytes = shingle.getBytes();
      long longHash = FPGenerator.std64.fp(bytes, 0, bytes.length);
      // long hash1 = hasher.hash(bytes, bytes.length, 0);
      // long hash2 = hasher.hash(bytes, bytes.length, (int)hash1);
      // long longHash = (hash1 << 32) | hash2;
      for (int i = 0; i < HASH_SIZE; ++i) {
        boolean bitSet = ((longHash >> i) & 1L) == 1L;
        v[i] += (bitSet) ? 1 : -1;
      }
    }
    long simhash = 0;
    for (int i = 0; i < HASH_SIZE; ++i) {
      if (v[i] > 0) {
        simhash |= (1L << i);
      }
    }
 
    return simhash;
  }
 
  public static int hammingDistance(long hash1, long hash2) {
    long bits = hash1 ^ hash2;
    int count = 0;
    while (bits != 0) {
      bits &= bits - 1;
      ++count;
    }
    return count;
  }
 
  public static long rotate(long hashValue) {
    return (hashValue << 1) | (hashValue >>> -1);
  }
 
  public static void main(String[] args) {
    try {
      // File file1 = new File("/Users/rana/academia.edu_01.html");
      // File file2 = new File("/Users/rana/academia.edu_02.html");
 
      File file1 = new File(args[0]);
      File file2 = new File(args[1]);
 
      byte data1[] = new byte[(int) file1.length()];
      byte data2[] = new byte[(int) file2.length()];
      FileInputStream stream1 = new FileInputStream(file1);
      FileInputStream stream2 = new FileInputStream(file2);
      stream1.read(data1);
      stream2.read(data2);
      String string1 = new String(data1);
      String string2 = new String(data2);
 
      long timeStart = System.currentTimeMillis();
      long simhash1 = computeSimHashFromString(Shingle.shingles(string1));
      long timeEnd = System.currentTimeMillis();
      System.out.println("Old Calc for Document A Took:"
          + (timeEnd - timeStart));
      timeStart = System.currentTimeMillis();
      long simhash2 = computeSimHashFromString(Shingle.shingles(string2));
      timeEnd = System.currentTimeMillis();
      System.out.println("Old Calc for Document B Took:"
          + (timeEnd - timeStart));
      timeStart = System.currentTimeMillis();
      long simhash3 = computeOptimizedSimHashForString(string1);
      timeEnd = System.currentTimeMillis();
      System.out.println("New Calc for Document A Took:"
          + (timeEnd - timeStart));
      timeStart = System.currentTimeMillis();
      long simhash4 = computeOptimizedSimHashForString(string2);
      timeEnd = System.currentTimeMillis();
      System.out.println("New Calc for Document B Took:"
          + (timeEnd - timeStart));
 
      int hammingDistance = hammingDistance(simhash1, simhash2);
      int hammingDistance2 = hammingDistance(simhash3, simhash4);
 
      System.out.println("hammingdistance Doc (A) to Doc(B) OldWay:"
          + hammingDistance);
      System.out.println("hammingdistance Doc (A) to Doc(B) NewWay:"
          + hammingDistance2);
    } catch (IOException e) {
      e.printStackTrace();
    }
  }
}

以上就是小编今天的分享了,希望可以帮助到大家。

显示全文
java simpledateformat java sizeof java sm3加密 文章千古事得失寸心知是谁的名句 诚信的名言名句 关于读书的名言名句 生日的经典名句 感恩老师的名言名句 关于时间的名言名句 活着的经典名句 java snappy 杜甫的名句 java snapshot 孟浩然的名句 关于诚信的名言名句 杜甫的名言名句 杜甫的名句有哪些 杜甫的千古名句 范仲淹的名句 范仲淹的十大经典名句 java shuffle java sha256加密 java portal java pojo java plugin java sftp java plug-in java settimeout java platform java setlayout java serialversionuid java serializable接口 java serializable java sequence java separator java semaphore java selenium java selector java script java sandbox