利用simhash计算文本相似度

悠悠 2022-02-02 07:31 562阅读 0赞

摘自:http://www.programcreek.com/java-api-examples/index.php?source\_dir=textmining-master/src/com/gta/simhash/SimHash.java

复制代码

  1. package com.gta.simhash;
  2. public class Test {
  3. public static void main(String[] args) {
  4. // TODO Auto-generated method stub
  5. String s3 = "�������Ϻ���������죬���������������������Ͼ������ݣ����������ţ����ϣ��ൺ���人�����ݣ����ڣ��ɶ���������̫ԭ����ɳ�����֣�������֣�ݣ���������������³ľ�룬���ݣ��������Ϸʣ��ߺ�";
  6. String s4 = "�������Ϻ���������죬���������������������Ͼ������ݣ����������ţ����ϣ��ൺ���人�����ݣ����ڣ��ɶ���������̫ԭ����ɳ�����֣�������֣�ݣ�����";
  7. SimHash hash1 = new SimHash(s3, 64, 8);
  8. SimHash hash2 = new SimHash(s4, 64, 8);
  9. hash1.getResult(hash2);
  10. }
  11. }

复制代码

复制代码

  1. package com.gta.simhash;
  2. import java.io.IOException;
  3. import java.math.BigInteger;
  4. import java.util.List;
  5. import java.util.ArrayList;
  6. import org.wltea.analyzer.lucene.IKAnalyzer;
  7. import org.apache.lucene.analysis.TokenStream;
  8. import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
  9. public class SimHash {
  10. private String tokens;
  11. private int hashBits = 64;
  12. private int distance = 5;
  13. public SimHash(String tokens)
  14. {
  15. this.tokens = tokens;
  16. }
  17. public SimHash(String tokens, int hashBits, int distance)
  18. {
  19. this.tokens = tokens;
  20. this.hashBits = hashBits;
  21. this.distance = distance;
  22. }
  23. public List<TermDict> tokenizer()
  24. {
  25. List<TermDict> terms = new ArrayList<TermDict>();
  26. IKAnalyzer analyzer = new IKAnalyzer(true);
  27. try {
  28. TokenStream stream = analyzer.tokenStream("", this.tokens);
  29. CharTermAttribute cta = stream.addAttribute(CharTermAttribute.class);
  30. stream.reset();
  31. int index = -1;
  32. while (stream.incrementToken())
  33. {
  34. if ((index = isContain(cta.toString(), terms)) >= 0)
  35. {
  36. terms.get(index).setFreq(terms.get(index).getFreq()+1);
  37. }
  38. else
  39. {
  40. terms.add(new TermDict(cta.toString(), 1));
  41. }
  42. }
  43. analyzer.close();
  44. } catch (IOException e) {
  45. e.printStackTrace();
  46. }
  47. return terms;
  48. }
  49. public int isContain(String str, List<TermDict> terms)
  50. {
  51. for (TermDict td : terms)
  52. {
  53. if (str.equals(td.getTerm()))
  54. {
  55. return terms.indexOf(td);
  56. }
  57. }
  58. return -1;
  59. }
  60. public BigInteger simHash(List<TermDict> terms)
  61. {
  62. int []v = new int[hashBits];
  63. for (TermDict td : terms)
  64. {
  65. String str = td.getTerm();
  66. int weight = td.getFreq();
  67. BigInteger bt = shiftHash(str);
  68. for (int i = 0; i < hashBits; i++)
  69. {
  70. BigInteger bitmask = new BigInteger("1").shiftLeft(i);
  71. if ( bt.and(bitmask).signum() != 0)
  72. {
  73. v[i] += weight;
  74. }
  75. else
  76. {
  77. v[i] -= weight;
  78. }
  79. }
  80. }
  81. BigInteger fingerPrint = new BigInteger("0");
  82. for (int i = 0; i < hashBits; i++)
  83. {
  84. if (v[i] >= 0)
  85. {
  86. fingerPrint = fingerPrint.add(new BigInteger("1").shiftLeft(i)); // update the correct fingerPrint
  87. }
  88. }
  89. return fingerPrint;
  90. }
  91. public BigInteger shiftHash(String str)
  92. {
  93. if (str == null || str.length() == 0)
  94. {
  95. return new BigInteger("0");
  96. }
  97. else
  98. {
  99. char[] sourceArray = str.toCharArray();
  100. BigInteger x = BigInteger.valueOf((long) sourceArray[0] << 7);
  101. BigInteger m = new BigInteger("131313");
  102. for (char item : sourceArray)
  103. {
  104. x = x.multiply(m).add(BigInteger.valueOf((long)item));
  105. }
  106. BigInteger mask = new BigInteger("2").pow(hashBits).subtract(new BigInteger("1"));
  107. boolean flag = true;
  108. for (char item : sourceArray)
  109. {
  110. if (flag)
  111. {
  112. BigInteger tmp = BigInteger.valueOf((long)item << 3);
  113. x = x.multiply(m).xor(tmp).and(mask);
  114. }
  115. else
  116. {
  117. BigInteger tmp = BigInteger.valueOf((long)item >> 3);
  118. x = x.multiply(m).xor(tmp).and(mask);
  119. }
  120. flag = !flag;
  121. }
  122. if (x.equals(new BigInteger("-1")))
  123. {
  124. x = new BigInteger("-2");
  125. }
  126. return x;
  127. }
  128. }
  129. public BigInteger getSimHash()
  130. {
  131. return simHash(tokenizer());
  132. }
  133. public int getHammingDistance(SimHash hashData)
  134. {
  135. BigInteger m = new BigInteger("1").shiftLeft(hashBits).subtract(new BigInteger("1"));
  136. System.out.println(getFingerPrint(getSimHash().toString(2)));
  137. System.out.println(getFingerPrint(hashData.getSimHash().toString(2)));
  138. BigInteger x = getSimHash().xor(hashData.getSimHash()).and(m);
  139. int tot = 0;
  140. while (x.signum() != 0)
  141. {
  142. tot += 1;
  143. x = x.and(x.subtract(new BigInteger("1")));
  144. }
  145. System.out.println(tot);
  146. return tot;
  147. }
  148. public String getFingerPrint(String str)
  149. {
  150. int len = str.length();
  151. for (int i = 0; i < hashBits; i++)
  152. {
  153. if (i >= len)
  154. {
  155. str = "0" + str;
  156. }
  157. }
  158. return str;
  159. }
  160. public void getResult(SimHash hashData)
  161. {
  162. if (getHammingDistance(hashData) <= distance)
  163. {
  164. System.out.println("match");
  165. }
  166. else
  167. {
  168. System.out.println("false");
  169. }
  170. }
  171. }

复制代码

本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6423442.html,如需转载请自行联系原作者

发表评论

表情:
评论列表 (有 0 条评论,562人围观)

还没有评论,来说两句吧...

相关阅读

    相关 用java计算文本相似

    遇到这样一个需求,需要计算两个文本内容的相似度,以前也接触过,下面列举几种方式,也是我在网上查了很多内容整理的,直接上代码,供大家参考,如果你也有这样的需求,希望能帮到你: