免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 5410 | 回复: 2

请问我这个关于simhash的perl脚本正确否? [复制链接]

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2015-02-08 17:30 |显示全部楼层
我想比较两个字符串的相似度,用到了simhash和hamming distance。网上都是Python和java的例子,我拿来改了改。应该是正确的,但是又没有把握,感觉我的算法和网上的特别是python版本的差距很大。请各位看看。

我的perl版本:
  1. #!/bin/perl

  2. sub hash{
  3. my ($input)=@_;
  4. my @chars=split "",$input;
  5. my $hash=5381;
  6. foreach(@chars){
  7.   $hash += ($hash << 5) + ord($_);
  8. }
  9. return $hash;
  10. }

  11. sub simhash{
  12. my @tokens=@_;
  13. my @simhash=();

  14. foreach (@tokens){
  15. my $hash=hash($_);
  16. foreach (0 .. 31){
  17.   my $current_bit=$hash & 0x1;
  18.   if ($current_bit == 0){
  19.    $simhash[$_]--;
  20.   }else {
  21.    $simhash[$_]++;
  22.   }
  23.   
  24. $hash = $hash >>1;
  25. }
  26. }

  27. my $simhash=0;
  28. @simhash= reverse @simhash;

  29. foreach(@simhash){
  30. if ($_ > 0){
  31. $simhash=($simhash << 1)+ 0x1;
  32. }else{
  33. $simhash=$simhash << 1;
  34. }
  35. }

  36. return $simhash;
  37. }

  38. sub hamming_distance{
  39. my ($ourhash,$otherhash)=@_;
  40. my $x=$ourhash ^ $otherhash;
  41. printf "ourhash=%x,otherhash=%x,x=%d\n",$ourhash,$otherhash,$x;
  42. my $tot=0;
  43. while ($x) {
  44. $tot += 1;
  45. $x &=$x -1;
  46. }
  47. return $tot;
  48. }


  49. while (chomp ($_ = <STDIN>)){
  50. my @test=qw (ok are you ready go);
  51. my @test2=split /\s+/, $_;

  52. my $sim1=simhash(@test);
  53. my $sim2=simhash(@test2);

  54. printf "test=%x,test2=%x\n",$sim1,$sim2;

  55. my $simi=$sim1 < $sim2 ? $sim1 / $sim2 : $sim2 / $sim1;
  56. print $simi . "\n";

  57. my $hamming=hamming_distance($sim1,$sim2);
  58. print $hamming . "\n";
  59. #exit(0);
  60. }
复制代码
下面是网上的python版本:
  1. #!/usr/bin/python
  2. # coding=utf-8
  3. class simhash:
  4.    
  5.     #构造函数
  6.     def __init__(self, tokens='', hashbits=128):      
  7.         self.hashbits = hashbits
  8.         self.hash = self.simhash(tokens);
  9.    
  10.     #toString函数   
  11.     def __str__(self):
  12.         return str(self.hash)
  13.    
  14.     #生成simhash值   
  15.     def simhash(self, tokens):
  16.         v = [0] * self.hashbits
  17.         for t in [self._string_hash(x) for x in tokens]: #t为token的普通hash值         
  18.             for i in range(self.hashbits):
  19.                 bitmask = 1 << i
  20.                 if t & bitmask :
  21.                     v[i] += 1 #查看当前bit位是否为1,是的话将该位+1
  22.                 else:
  23.                     v[i] -= 1 #否则的话,该位-1
  24.         fingerprint = 0
  25.         for i in range(self.hashbits):
  26.             if v[i] >= 0:
  27.                 fingerprint += 1 << i
  28.         return fingerprint #整个文档的fingerprint为最终各个位>=0的和
  29.    
  30.     #求海明距离
  31.     def hamming_distance(self, other):
  32.         x = (self.hash ^ other.hash) & ((1 << self.hashbits) - 1)
  33.         tot = 0;
  34.         while x :
  35.             tot += 1
  36.             x &= x - 1
  37.         return tot
  38.    
  39.     #求相似度
  40.     def similarity (self, other):
  41.         a = float(self.hash)
  42.         b = float(other.hash)
  43.         if a > b : return b / a
  44.         else: return a / b
  45.    
  46.     #针对source生成hash值   (一个可变长度版本的Python的内置散列)
  47.     def _string_hash(self, source):      
  48.         if source == "":
  49.             return 0
  50.         else:
  51.             x = ord(source[0]) << 7
  52.             m = 1000003
  53.             mask = 2 ** self.hashbits - 1
  54.             for c in source:
  55.                 x = ((x * m) ^ ord(c)) & mask
  56.             x ^= len(source)
  57.             if x == -1:
  58.                 x = -2
  59.             return x
  60.             
  61. if __name__ == '__main__':
  62.     s = 'This is a test string for testing'
  63.     hash1 = simhash(s.split())
  64.    
  65.     s = 'This is a test string for testing also'
  66.     hash2 = simhash(s.split())
  67.    
  68.     s = 'nai nai ge xiong cao'
  69.     hash3 = simhash(s.split())
  70.    
  71.     print(hash1.hamming_distance(hash2) , "   " , hash1.similarity(hash2))
  72.     print(hash1.hamming_distance(hash3) , "   " , hash1.similarity(hash3))
复制代码

求职 : 软件工程师
论坛徽章:
3
程序设计版块每日发帖之星
日期:2015-10-07 06:20:00程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2016-05-05 06:20:00
发表于 2015-02-27 13:20 |显示全部楼层
  1. use Text::Levenshtein qw(distance);

  2. print distance("foo","four");
  3. # prints "2"

  4. my @words     = qw/ four foo bar /;
  5. my @distances = distance("foo",@words);

  6. print "@distances";
  7. # prints "2 0 3"
复制代码

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2015-06-03 02:02 |显示全部楼层
3 Q ~ ~
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP