python实现simhash算法实例

时间:2023-11-02 23:26:30 

Simhash的算法简单的来说就是,从海量文本中快速搜索和已知simhash相差小于k位的simhash集合,这里每个文本都可以用一个simhash值来代表,一个simhash有64bit,相似的文本,64bit也相似,论文中k的经验值为3。该方法的缺点如优点一样明显,主要有两点,对于短文本,k值很敏感;另一个是由于算法是以空间换时间,系统内存吃不消。

python实现simhash算法实例


#!/usr/bin/python
# coding=utf-8
class simhash:

    #构造函数
    def __init__(self, tokens='', hashbits=128):       
        self.hashbits = hashbits
        self.hash = self.simhash(tokens);

    #toString函数   
    def __str__(self):
        return str(self.hash)

    #生成simhash值   
    def simhash(self, tokens):
        v = [0] * self.hashbits
        for t in [self._string_hash(x) for x in tokens]: #t为token的普通hash值          
            for i in range(self.hashbits):
                bitmask = 1 << i
                if t & bitmask :
                    v[i] += 1 #查看当前bit位是否为1,是的话将该位+1
                else:
                    v[i] -= 1 #否则的话,该位-1
        fingerprint = 0
        for i in range(self.hashbits):
            if v[i] >= 0:
                fingerprint += 1 << i
        return fingerprint #整个文档的fingerprint为最终各个位>=0的和

    #求海明距离
    def hamming_distance(self, other):
        x = (self.hash ^ other.hash) & ((1 << self.hashbits) - 1)
        tot = 0;
        while x :
            tot += 1
            x &= x - 1
        return tot

    #求相似度
    def similarity (self, other):
        a = float(self.hash)
        b = float(other.hash)
        if a > b : return b / a
        else: return a / b

    #针对source生成hash值   (一个可变长度版本的Python的内置散列)
    def _string_hash(self, source):       
        if source == "":
            return 0
        else:
            x = ord(source[0]) << 7
            m = 1000003
            mask = 2 ** self.hashbits - 1
            for c in source:
                x = ((x * m) ^ ord(c)) & mask
            x ^= len(source)
            if x == -1:
                x = -2
            return x
            

if __name__ == '__main__':
    s = 'This is a test string for testing'
    hash1 = simhash(s.split())

    s = 'This is a test string for testing also'
    hash2 = simhash(s.split())

    s = 'nai nai ge xiong cao'
    hash3 = simhash(s.split())

    print(hash1.hamming_distance(hash2) , "   " , hash1.similarity(hash2))
    print(hash1.hamming_distance(hash3) , "   " , hash1.similarity(hash3))


 

标签:python,simhash,算法
0
投稿

猜你喜欢

  • 如何用Matplotlib 画三维图的示例代码

    2023-03-02 15:16:08
  • 利用Python求解阿基米德分牛问题

    2023-11-10 09:36:48
  • keras实现VGG16 CIFAR10数据集方式

    2023-08-19 08:27:08
  • 使用pycharm将自己项目代码上传github(小白教程)

    2022-05-02 20:37:06
  • MySql多表链接查询详细教程

    2024-01-16 06:03:33
  • MySQL 创建多对多和一对一关系方法

    2024-01-29 07:52:37
  • Python中操作mysql的pymysql模块详解

    2024-01-14 08:14:32
  • Vue快速实现通用表单验证的方法

    2024-04-09 10:45:06
  • Python区块链客户端类开发教程

    2023-06-18 03:05:51
  • python检测服务器端口代码实例

    2023-07-07 06:34:14
  • 如何创建SQL Server 2000故障转移群集

    2009-02-13 17:18:00
  • 基于Python 函数和方法的区别说明

    2023-10-03 02:04:01
  • Python CSV 文件解析和生成方法示例

    2022-12-25 10:52:58
  • 如何在SQL Server 2005数据库中导入SQL Server 2008的数据

    2024-01-27 22:05:21
  • Python实现注册登录系统

    2021-10-21 20:01:05
  • Python常用工具之音频调整音量

    2023-10-29 03:15:33
  • Python获取指定文件夹下的文件名的方法

    2022-04-26 03:10:03
  • Access 2002的三个实用技巧

    2007-10-22 12:22:00
  • 如何真正的了解python装饰器

    2023-03-16 09:08:23
  • 利用vue实现打印页面的几种方法总结

    2023-07-02 17:09:48
  • asp之家 网络编程 m.aspxhome.com