实现SimHash算法代码,Python代码库,德仔网

代码语言
代码分类
【Python】实现SimHash算法
作者: / 发布于2011/1/4/ 793
统的hash函数能够将一样的文本生成一样的hash函数，但是，通过simhash方法，能够差不多相同的文档得到的hash函数也比较相近。
<div>
<table style="font-family: monospace" class="python codes">
    <tbody>
        <tr class="li1">
            <td style="line-height: 150%; font-family: Verdana, Monospace; font-size: 12px; font-weight: bold; margin-right: 10px">
            <pre style="line-height: 150%; font-family: Verdana, Monospace; font-size: 12px; font-weight: bold; margin-right: 10px"><span style="font-style: italic; color: #808080">#!/usr/bin/env python</span>
<span style="font-style: italic; color: #808080"># -*- coding=utf-8 -*-</span>

<span style="font-style: italic; color: #808080"># Implementation of Charikar simhashes in Python</span>
<span style="font-style: italic; color: #808080"># See: http://dsrg.mff.cuni.cz/~holub/sw/shash/#a1</span>

<span style="color: #0099cc">class</span> simhash<span style="color: black">(</span><span style="color: black">)</span>:
  <span style="color: #0099cc">def</span> <span style="color: #0000cd">__init__</span><span style="color: black">(</span><span style="color: #0000ff">self</span>, tokens=<span style="color: #483d8b">''</span>, hashbits=<span style="color: #ff4500">128</span><span style="color: black">)</span>:
    <span style="color: #0000ff">self</span>.<span style="color: black">hashbits</span> = hashbits
    <span style="color: #0000ff">self</span>.<span style="color: #0000ff">hash</span> = <span style="color: #0000ff">self</span>.<span style="color: black">simhash</span><span style="color: black">(</span>tokens<span style="color: black">)</span>

  <span style="color: #0099cc">def</span> <span style="color: #0000cd">__str__</span><span style="color: black">(</span><span style="color: #0000ff">self</span><span style="color: black">)</span>:
    <span style="color: #0099cc">return</span> <span style="color: #0000ff">str</span><span style="color: black">(</span><span style="color: #0000ff">self</span>.<span style="color: #0000ff">hash</span><span style="color: black">)</span>

  <span style="color: #0099cc">def</span> <span style="color: #0000cd">__long__</span><span style="color: black">(</span><span style="color: #0000ff">self</span><span style="color: black">)</span>:
    <span style="color: #0099cc">return</span> <span style="color: #0000ff">long</span><span style="color: black">(</span><span style="color: #0000ff">self</span>.<span style="color: #0000ff">hash</span><span style="color: black">)</span>

  <span style="color: #0099cc">def</span> <span style="color: #0000cd">__float__</span><span style="color: black">(</span><span style="color: #0000ff">self</span><span style="color: black">)</span>:
    <span style="color: #0099cc">return</span> <span style="color: #0000ff">float</span><span style="color: black">(</span><span style="color: #0000ff">self</span>.<span style="color: #0000ff">hash</span><span style="color: black">)</span>

  <span style="color: #0099cc">def</span> simhash<span style="color: black">(</span><span style="color: #0000ff">self</span>, tokens<span style="color: black">)</span>:
    <span style="font-style: italic; color: #808080"># Returns a Charikar simhash with appropriate bitlength</span>
    v = <span style="color: black">[</span><span style="color: #ff4500">0</span><span style="color: black">]</span><span style="color: #66cc66">*</span><span style="color: #0000ff">self</span>.<span style="color: black">hashbits</span>

    <span style="color: #0099cc">for</span> t <span style="color: #0099cc">in</span> <span style="color: black">[</span><span style="color: #0000ff">self</span>._string_hash<span style="color: black">(</span>x<span style="color: black">)</span> <span style="color: #0099cc">for</span> x <span style="color: #0099cc">in</span> tokens<span style="color: black">]</span>:
      bitmask = <span style="color: #ff4500">0</span>
      <span style="font-style: italic; color: #808080">#print (t)</span>
      <span style="color: #0099cc">for</span> i <span style="color: #0099cc">in</span> <span style="color: #0000ff">range</span><span style="color: black">(</span><span style="color: #0000ff">self</span>.<span style="color: black">hashbits</span><span style="color: black">)</span>:
        bitmask = <span style="color: #ff4500">1</span> <span style="color: #66cc66"><<</span> i
        <span style="font-style: italic; color: #808080">#print(t,bitmask, t & bitmask)</span>
        <span style="color: #0099cc">if</span> t <span style="color: #66cc66">&</span> bitmask:
          v<span style="color: black">[</span>i<span style="color: black">]</span> += <span style="color: #ff4500">1</span> <span style="font-style: italic; color: #808080">#查看当前bit位是否为1，是的话则将该位+1</span>
        <span style="color: #0099cc">else</span>:
          v<span style="color: black">[</span>i<span style="color: black">]</span> += -<span style="color: #ff4500">1</span> <span style="font-style: italic; color: #808080">#否则得话，该位减1</span>

    fingerprint = <span style="color: #ff4500">0</span>
    <span style="color: #0099cc">for</span> i <span style="color: #0099cc">in</span> <span style="color: #0000ff">range</span><span style="color: black">(</span><span style="color: #0000ff">self</span>.<span style="color: black">hashbits</span><span style="color: black">)</span>:
      <span style="color: #0099cc">if</span> v<span style="color: black">[</span>i<span style="color: black">]</span> <span style="color: #66cc66">></span>= <span style="color: #ff4500">0</span>:
        fingerprint += <span style="color: #ff4500">1</span> <span style="color: #66cc66"><<</span> i
<span style="font-style: italic; color: #808080">#整个文档的fingerprint为最终各个位大于等于0的位的和</span>
    <span style="color: #0099cc">return</span> fingerprint

  <span style="color: #0099cc">def</span> _string_hash<span style="color: black">(</span><span style="color: #0000ff">self</span>, v<span style="color: black">)</span>:
    <span style="font-style: italic; color: #808080"># A variable-length version of Python's builtin hash</span>
    <span style="color: #0099cc">if</span> v == <span style="color: #483d8b">""</span>:
      <span style="color: #0099cc">return</span> <span style="color: #ff4500">0</span>
    <span style="color: #0099cc">else</span>:
      x = <span style="color: #0000ff">ord</span><span style="color: black">(</span>v<span style="color: black">[</span><span style="color: #ff4500">0</span><span style="color: black">]</span><span style="color: black">)</span><span style="color: #66cc66"><<</span><span style="color: #ff4500">7</span>
      m = <span style="color: #ff4500">1000003</span>
      mask = <span style="color: #ff4500">2</span><span style="color: #66cc66">**</span><span style="color: #0000ff">self</span>.<span style="color: black">hashbits</span>-<span style="color: #ff4500">1</span>
      <span style="color: #0099cc">for</span> c <span style="color: #0099cc">in</span> v:
        x = <span style="color: black">(</span><span style="color: black">(</span>x<span style="color: #66cc66">*</span>m<span style="color: black">)</span>^ord<span style="color: black">(</span>c<span style="color: black">)</span><span style="color: black">)</span> <span style="color: #66cc66">&</span> mask
      x ^= <span style="color: #0000ff">len</span><span style="color: black">(</span>v<span style="color: black">)</span>
      <span style="color: #0099cc">if</span> x == -<span style="color: #ff4500">1</span>:
        x = -<span style="color: #ff4500">2</span>
      <span style="color: #0099cc">return</span> x

  <span style="color: #0099cc">def</span> hamming_distance<span style="color: black">(</span><span style="color: #0000ff">self</span>, other_hash<span style="color: black">)</span>:
    x = <span style="color: black">(</span><span style="color: #0000ff">self</span>.<span style="color: #0000ff">hash</span> ^ other_hash.<span style="color: #0000ff">hash</span><span style="color: black">)</span> <span style="color: #66cc66">&</span> <span style="color: black">(</span><span style="color: black">(</span><span style="color: #ff4500">1</span> <span style="color: #66cc66"><<</span> <span style="color: #0000ff">self</span>.<span style="color: black">hashbits</span><span style="color: black">)</span> - <span style="color: #ff4500">1</span><span style="color: black">)</span>
    tot = <span style="color: #ff4500">0</span>
    <span style="color: #0099cc">while</span> x:
      tot += <span style="color: #ff4500">1</span>
      x <span style="color: #66cc66">&</span>= x-<span style="color: #ff4500">1</span>
    <span style="color: #0099cc">return</span> tot

  <span style="color: #0099cc">def</span> similarity<span style="color: black">(</span><span style="color: #0000ff">self</span>, other_hash<span style="color: black">)</span>:
    a = <span style="color: #0000ff">float</span><span style="color: black">(</span><span style="color: #0000ff">self</span>.<span style="color: #0000ff">hash</span><span style="color: black">)</span>
    b = <span style="color: #0000ff">float</span><span style="color: black">(</span>other_hash<span style="color: black">)</span>
    <span style="color: #0099cc">if</span> a<span style="color: #66cc66">></span>b: <span style="color: #0099cc">return</span> b/a
    <span style="color: #0099cc">return</span> a/b

<span style="color: #0099cc">if</span> __name__ == <span style="color: #483d8b">'__main__'</span>:
  <span style="font-style: italic; color: #808080">#看看哪些东西google最看重？标点？</span>
  s = <span style="color: #483d8b">'看看哪些东西google最看重？标点？'</span>
  hash1 =simhash<span style="color: black">(</span>s.<span style="color: black">split</span><span style="color: black">(</span><span style="color: black">)</span><span style="color: black">)</span>
  <span style="font-style: italic; color: #808080">#print("0x%x" % hash1)</span>
  <span style="font-style: italic; color: #808080">#print ("%s\t0x%x" % (s, hash1))</span>

  s = <span style="color: #483d8b">'看看哪些东西google最看重！标点！'</span>
  hash2 = simhash<span style="color: black">(</span>s.<span style="color: black">split</span><span style="color: black">(</span><span style="color: black">)</span><span style="color: black">)</span>
  <span style="font-style: italic; color: #808080">#print ("%s\t[simhash = 0x%x]" % (s, hash2))</span>

  <span style="color: #0099cc">print</span> <span style="color: #483d8b">'%f%% percent similarity on hash'</span> <span style="color: #66cc66">%</span><span style="color: black">(</span><span style="color: #ff4500">100</span><span style="color: #66cc66">*</span><span style="color: black">(</span>hash1.<span style="color: black">similarity</span><span style="color: black">(</span>hash2<span style="color: black">)</span><span style="color: black">)</span><span style="color: black">)</span>
  <span style="color: #0099cc">print</span> hash1.<span style="color: black">hamming_distance</span><span style="color: black">(</span>hash2<span style="color: black">)</span>,<span style="color: #483d8b">"bits differ out of"</span>, hash1.<span style="color: black">hashbits</span></pre>
            </td>
        </tr>
    </tbody>
</table>
</div>
试试其它关键字
　SimHash　
同语言下
可能有用的
贡献的其它代码Label