请问我这个关于simhash的perl脚本正确否？

sohusina

我想比较两个字符串的相似度，用到了simhash和hamming distance。网上都是Python和java的例子，我拿来改了改。应该是正确的，但是又没有把握，感觉我的算法和网上的特别是python版本的差距很大。请各位看看。

我的perl版本：

1. #!/bin/perl
   
2. 
   
3. sub hash{
   
4. my ($input)=@_;
   
5. my @chars=split "",$input;
   
6. my $hash=5381;
   
7. foreach(@chars){
   
8.   $hash += ($hash << 5) + ord($_);
   
9. }
   
10. return $hash;
    
11. }
    
12. 
    
13. sub simhash{
    
14. my @tokens=@_;
    
15. my @simhash=();
    
16. 
    
17. foreach (@tokens){
    
18. my $hash=hash($_);
    
19. foreach (0 .. 31){
    
20.   my $current_bit=$hash & 0x1;
    
21.   if ($current_bit == 0){
    
22.    $simhash[$_]--;
    
23.   }else {
    
24.    $simhash[$_]++;
    
25.   }
    
26.   
    
27. $hash = $hash >>1;
    
28. }
    
29. }
    
30. 
    
31. my $simhash=0;
    
32. @simhash= reverse @simhash;
    
33. 
    
34. foreach(@simhash){
    
35. if ($_ > 0){
    
36. $simhash=($simhash << 1)+ 0x1;
    
37. }else{
    
38. $simhash=$simhash << 1;
    
39. }
    
40. }
    
41. 
    
42. return $simhash;
    
43. }
    
44. 
    
45. sub hamming_distance{
    
46. my ($ourhash,$otherhash)=@_;
    
47. my $x=$ourhash ^ $otherhash;
    
48. printf "ourhash=%x,otherhash=%x,x=%d\n",$ourhash,$otherhash,$x;
    
49. my $tot=0;
    
50. while ($x) {
    
51. $tot += 1;
    
52. $x &=$x -1;
    
53. }
    
54. return $tot;
    
55. }
    
56. 
    
57. 
    
58. while (chomp ($_ = <STDIN>)){
    
59. my @test=qw (ok are you ready go);
    
60. my @test2=split /\s+/, $_;
    
61. 
    
62. my $sim1=simhash(@test);
    
63. my $sim2=simhash(@test2);
    
64. 
    
65. printf "test=%x,test2=%x\n",$sim1,$sim2;
    
66. 
    
67. my $simi=$sim1 < $sim2 ? $sim1 / $sim2 : $sim2 / $sim1;
    
68. print $simi . "\n";
    
69. 
    
70. my $hamming=hamming_distance($sim1,$sim2);
    
71. print $hamming . "\n";
    
72. #exit(0);
    
73. }

复制代码

下面是网上的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))

复制代码

104359176

1. use Text::Levenshtein qw(distance);
   
2. 
   
3. print distance("foo","four");
   
4. # prints "2"
   
5. 
   
6. my @words     = qw/ four foo bar /;
   
7. my @distances = distance("foo",@words);
   
8. 
   
9. print "@distances";
   
10. # prints "2 0 3"

复制代码

rubyish

3 Q ~ ~