golang 实现海明距离 demo

tianxingxing · · 1080 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

demo:

package main

import (
    "fmt"
    "math"
    "strconv"
    "strings"
)

type SimHash struct {
    IntSimHash int64
    HashBits   int
}

func main() {
    str := "夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息夜空中最亮的星是否记清那仰望的人  心里的孤独和叹息夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息"
    str2 := "夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息夜空中最亮的星是否记清那仰望的人  心里的孤独和叹息夜空中最亮的星是否记清那仰望的人 心里的孤独和叹息"
    //str3:="nai nai ge xiong cao"
    s := params()
    //str hash 值
    hash := s.Simhash(str)
    fmt.Println(hash)
    //str2 距离
    hash2 := s.Simhash(str2)
    fmt.Println(hash2)
    //计算相似度
    sm := s.Similarity(hash, hash2)
    fmt.Println(sm)
    //距离
    ts := s.HammingDistance(hash, hash2)
    fmt.Println(ts)

}

/**
 距离 补偿
 */
func (s *SimHash) HammingDistance(hash, other int64) int {
    x := (hash ^ other) & ((1 << uint64(s.HashBits)) - 1)
    tot := 0
    for x != 0 {
        tot += 1
        x &= x - 1
    }
    return tot
}

/**
  相似度
 */
func (s *SimHash) Similarity(hash, other int64) float64 {
    a := float64(hash)
    b := float64(other)
    if a > b {
        return b / a
    }
    return a / b
}

/**
  海明距离hash
 */
func (s *SimHash) Simhash(str string) int64 {
     m := strings.Split(str, " ")

    token_int := make([]int, s.HashBits)
    for i := 0; i < len(m); i++ {
        temp :=  m[i]
        t := s.Hash(temp)
        for j := 0; j < s.HashBits; j++ {
            bitMask := int64(1 << uint(j))
            if t&bitMask != 0 {
                token_int[j] += 1
            } else {
                token_int[j] -= 1
            }
        }

    }
    var fingerprint int64 = 0
    for i := 0; i < s.HashBits; i++ {
        if token_int[i] >= 0 {
            fingerprint += 1 << uint64(i)
        }
    }
    return fingerprint
}

/**
  初始化
 */
func params() (s *SimHash) {
    s = &SimHash{}
    s.HashBits = 64
    return s
}

/**
hash 值
 */
func (s *SimHash) Hash(token string) int64 {
    if token == "" {
        return 0
    } else {
        x := int64(int(token[0]) << 7)
        m := int64(1000003)
        mask := math.Pow(2, float64(s.HashBits-1))
        s := strconv.FormatFloat(mask, 'f', -1, 64)
        tsk, _ := strconv.ParseInt(s, 10, 64)
        for i := 0; i < len(token); i++ {
            tokens := int64(int(token[0]))
            x = ((x * m) ^ tokens) & tsk
        }
        x ^= int64(len(token))
        if x == -1 {
            x = -2
        }
        return int64(x)
    }
}

 

本文来自:博客园

感谢作者:tianxingxing

查看原文:golang 实现海明距离 demo

入群交流(和以上内容无关):Go中文网 QQ 交流群:729884609 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

1080 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传