Node.js / javascript minhash 模块，为相似的文本输出相似的哈希字符串

Question

我正在寻找一个 node.js / Java 将 minhash 算法应用于字符串或更大文本的脚本模块，returns 我 "identifying" 或 "characteristic" 该文本的字节串或十六进制字符串。如果我将该算法应用于另一个相似的文本字符串，则哈希字符串也应该相似。是否已经存在这样的模块？

到目前为止，我正在研究的模块只能直接比较文本并直接计算与比较文本的某种数字 jaccard 相似度，但我想为每个文档存储某种哈希字符串, 所以如果我有相似的文本，我可以稍后比较字符串的相似性...

本质上，我要找的是这里的这段代码 (Java): 在 Javascript 中： https://github.com/codelibs/elasticsearch-minhash

例如，对于像这样的字符串： "The quick brown fox jumps over the lazy dog" 和 "The quick brown fox jumps over the lazy d" 它将为第一句话创建一个散列，例如：

"KV5rsUfZpcZdVojpG8mHLA=="

第二个字符串类似于：

KV5rsSfZpcGdVojpG8mGLA==

两个散列字符串差别不大...这就是 minhash 算法的重点，但是，我不知道如何创建类似的散列字符串..到目前为止我发现的所有库，只有直接比较 2 个文档并创建相似系数，但它们不会创建文档特有的哈希字符串...... 与所有算法的相似之处在于，它们为单词标记数组（或带状疱疹）创建散列的 crc32（或类似）散列值。但我仍然不知道他们如何将这些哈希相互比较...

Answer 1

需要 Douglas Duhaime 的 minhash 实现，但计算散列值数组的任何其他实现都可以使用相同的方式。

const str1 = "The quick brown fox jumps over the lazy dog";
const str2 = "The quick brown fox jumps over the lazy d";
console.log(str1);
console.log(str2);
var s1 = str1.split(' ');
var s2 = str2.split(' ');

// create a hash for each set of words to compare
// default numPerm is 128 but that gives very long hash
// below 8, almost similar string will give exactly the same hash
var m1 = new Minhash({numPerm: 8});
var m2 = new Minhash({numPerm: 8});

// update each hash
s1.map(function(w) { m1.update(w) });
s2.map(function(w) { m2.update(w) });


// estimate the jaccard similarity between two minhashes
console.log('jaccard similarity:', m1.jaccard(m2));

// Now to convert hashvalues to a string we use a kind of base64
// encode but since hasvalues is an array of 32bits integer we
// have to explode it into a array of 8bits integers first

// for a given int32 returns 4 bytes
function int32ToBytes(num) {
    // the hexadecimal representation of the largest 32bits unsigned integer is 0xFFFFFFFF
    // the hexadecimal representation of the largest unsigned integer (8bits === a byte) is 0xFF
    // so it is possible to think a 32bits uint (unsigned integer) as the concatenation of 4 8bits uint.
    // the bitwise & operator is the bitwise AND
    // its table of truth is 0 & 0 = 0, 0 & 1 = 0, 1 & 0 = 0 and 1 & 1 = 1
    // for instance 8 & 1 <=> 0b111 & 0b001 <=> 0b001 <=> 1

    // the same is possible with hex representation:
    // 65535 & 255 <=> 0xFFFF & 0x00FF <=> 0x0FF <=> 255
    // 65535 & 65280 <=> 0xFFFF & 0xFF00 <=> 0xFF00 <=> 65280
    // 255 + 65535 = 65535

    // now about the bitwise >> shift operator
    // a >> n shift the number a by n bits to the right
    // in hex FF is 8bits so `0xFF00 >> 8 = 0xFF`
    // this operation is reversible `0xFF << 8 = 0xFF00`

    // 0xFFFF needs 16 bits to be represented, as 0xFF00
    // but 0xFF only needs 8 bits
    // so its possible to split a 16 bits integer into two 8 bits integer this way:
    // int16 = (int16 & 0xFF00) >> 8 + (int16 & 0x00FF) >> 0
    // no information was lost because we're able to do the reverse operation

    // the same principle is used below to encode a 32 bits integer into 4 bytes (8bits integers)
   // max uint32 = 0xFFFFFFFF =
   // 0xFF << 24 + 0xFF << 16 + 0xFF << 8 + 0xFF << 0
    

  
    const arr = [
        (num & 0xff000000) >> 24,
        (num & 0x00ff0000) >> 16,
        (num & 0x0000ff00) >> 8,
        (num & 0x000000ff)
    ];
    return arr;
}

// tolerant base64 encode of 4 bytes
function Uint8ToString(u8a){
  var CHUNK_SZ = 0x8000;
  var c = [];
  for (var i=0; i < u8a.length; i+=CHUNK_SZ) {
    c.push(String.fromCharCode.apply(null, u8a.subarray(i, i+CHUNK_SZ)));
  }
  return c.join("");
}

// tolerant base64 encode of int32 array
function base64EncodeInt32Array(intArray) {
    let str = '';
    intArray.forEach((i) => {
        var u8 = new Uint8Array(int32ToBytes(i));
        var b64encoded = btoa(Uint8ToString(u8));
        str += b64encoded;
    });
    
    return str;
    
}

// replace non significant '==' to shorten hash
console.log(base64EncodeInt32Array(m1.hashvalues).replace(/==/g, ''));
console.log(base64EncodeInt32Array(m2.hashvalues).replace(/==/g, ''));

<script src='https://rawgit.com/duhaime/minhash/master/minhash.min.js'></script>

Answer 2

如果您只想一次比较两个文档（文档 A 与文档 B 的相似程度如何？），那么将每个文档的最小哈希值存储为连接字符串就可以了。您可以通过将每个文档的字符串拆分回组成它们的最小哈希值并计算共享了多少最小哈希值（相同）来比较这两个文档。

但是如果你想问 "what other documents are similar to document A"，这是一个糟糕的解决方案，因为你必须将文档 A 与你之前看到的所有其他文档单独进行比较。更糟糕的是，如果你想在语料库中找到所有 document-to-document 相似之处，你必须将每个文档与其他每个文档进行比较。在一组 1000 份文件中，这将需要 499,500 次比较。有一百万个文档，这就是将近 5000 亿次比较。这是一个 O(n²) 的问题。

相反，执行此操作的适当方法是保留哈希字典，将最小哈希值映射到文档 ID。每次遇到一个新文档时，都会生成它的最小哈希值，然后在哈希字典中查找共享一个或多个这些哈希值的所有其他文档。文档与传入文档共享的散列越多，其估计的 jaccard 相似度就越高。最后，您将新文档的所有 minhashes 添加到哈希字典中，以供将来搜索使用。

您可能只对至少共享一半最小哈希的相似性感兴趣（估计 50% jaccard 相似性），但仍然需要大量计算才能找到这些相似性，因为可能数以百万计的文档与传入文档共享至少一个 minhash，您需要计算每个文档的共享哈希数。 Locality sensitive hashing 可以大大减少命中次数（以及所需的存储空间）。

Node.js / javascript minhash 模块，为相似的文本输出相似的哈希字符串

Node.js / javascript minhash module that outputs a similar hashstring for similar text

javascript

node.js

minhash