首页> 疑难解答

Node.js / javascript minhash模块,为类似文本输出类似的hashstring

withpy 2021-06-19

简介我正在寻找一个node.js / Javascript模块,它将minhash算法应用于字符串或更大的文本,并为该文本返回一个“识别”或“特征”字节串或十六进制字符串。 ...

我正在寻找一个node.js / Javascript模块,它将minhash算法应用于字符串或更大的文本,并为该文本返回一个“识别”或“特征”字节串或十六进制字符串。如果我将算法应用于另一个类似的文本字符串,则哈希字符串也应该类似。这样的模块是否已经存在?

到目前为止我正在研究的模块只能直接比较文本和直接计算比较文本中某种类型的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算法中的重点,但是,我不知道如何创建类似的hashstring ..而且到目前为止我找到的所有库,只比较直接2个文件和创建一个相似系数,但它们不会创建一个特定于文档的哈希字符串...与所有算法的相似之处在于,它们为其单词标记(或带状疱疹)数组创建了哈希crc32(或类似)哈希值。但我仍然不知道他们如何比较这些哈希...

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>

1
投票

如果您只打算一次比较两个文档(文档A与文档B的相似程度如何?),那么将每个文档的minhashes存储为连接字符串就可以了。您可以通过将每个文档的字符串拆分回其组成的minhashes并计算共享多少个minhashes(相同)来比较这两个文档。

但是,如果你想问“其他哪些文档与文档A类似”,那么这是一个糟糕的解决方案,因为你必须将doc A单独与你之前看过的其他文档进行比较。更糟糕的是,如果要在语料库中找到所有文档到文档的相似性,则必须将每个文档与每个其他文档进行比较。在一组1000个文档中,需要499,500个比较。拥有一百万个文档,这是近5000亿次比较。这是一个O(n2)问题。

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

您可能只对相似性感兴趣,例如,至少有一半的minhashes被共享(估计50%的jaccard相似度),但是仍然需要大量的计算才能找到它们,因为可能有数百万个文档共享至少有一个minhash与传入的文档,你需要计算每个共享哈希的数量。 Locality sensitive hashing可以大大减少命中数(以及所需的存储量)。

相关文章

  • 如果输入参数在Django模板中无效,如何抛出异常

    如果模板输入参数无效,有没有办法抛出异常?在django旧版本中,我们可以像下面的代码那样做。但是最新的django版本怎么样?可以选择设置......

  • Kubernetes API服务器和Kubelet通信

    API服务器的IP地址为172.0.1.1。当API服务器地址与Kubelet 10250端口通信时,它总是报告错误:E0402 03:27:12.970501 1 upgradeaware.go:310] ...

  • 强制Google表格“立即重新发布”

    Google文档电子表格允许您将数据作为.XLS文件或.CSV等发布到网络。我有一个编辑电子表格的系统,当我完成后,我运行一个脚本,下载....

  • 从动态产品页面中选择产品并将其传递到其他页面

    我正在为学校开发一个网站。在该网站上,您可以找到飞机及其规格。在将它们上传到公共页面之前,管理员必须验证它们。这就是我......

  • 触发onclick方法时收到错误

    所以我在我的xml布局中为我的保存按钮定义了onclick方法,然后在我的对话框片段中创建了该方法,但是当点击保存按钮时,应用程序崩溃并且我收到...

  • 非空字符串包装器

    我的java代码中有一种情况,我必须对字符串参数进行大量的空检查:someService.someUpdateFunc(Optional.ofNullable(personPhone.getName())。orElse(“”),...