短文本相似度校验算法

Nodejs | 2022-06-16 20:11:34 1562次 4次

介绍

在编写复杂业务代码时,尤其是超级复杂业务时,难免会创建很多相似方法,所以可以基于 eslint 自定义规则创建一种短文本(函数名、常量)相似方法校验规则,在一定程度上可以减少重复代码或轮子的出现。本文着重介绍此应用的基础——短文本相似度检验,此类算法应用研究已经发展数十年,有较多优秀的算法出现,比如基于机器学习和一些距离计算等。

本文基于谷歌最早发表的《detecting near-duplicates for web crawling》一种网页去重算法——simhash 算法,此算法适用于大量级文本,并且计算速度很快,它和普通的 hash 算法相比而言是一种局部敏感 hash 算法。

距离算法

各种“距离”的应用场景简单概括为:

空间:欧氏距离;

路径:曼哈顿距离;

国际象棋国王:切比雪夫距离;

以上三种的统一形式: 闵可夫斯基距离;

加权:标准化欧氏距离;

排除量纲和依存:马氏距离;

向量差距:夹角余弦;

编码差别:汉明距离;

集合近似度:杰卡德类似系数与距离;

但是距离度量与相似度量还是有一点点区别的。距离度量,一般情况下距离是大于 0 的数,比如计算两个文本的编辑距离;而相似性或相异性通常数值介于 [0, 1] 之间,相似性与相异性统称为邻近度。

本文中介绍的算法应用就是汉明距离+最短编辑距离组合相结合进行短文本相似度比较。

simhash 算法原理

1、分词

给出一段文本,需要先通过分词算法(中文目前可以使用——jieba算法),将连续的字序列按照一定的规范重新组合成词序列的过程。比如:

【我在公司敲键盘】

分词后

‘我’ ‘在’ ‘公司’ ‘敲’ ‘键盘’

但是本次算法实现是针对英文短文本相似度比较,可以简单的进行单个字符分词计算。 


2、hash

经过分词后,将每个词组转化为 hash 值(二进制表示),方便后续计算,有了此 hash 值可以进行很多操作,比如进行特征映射,将特征表述映射到二维坐标,有了二位坐标可以进行向量夹角计算对比相似度或者向量所在象限进行比较,再或者还可以进行其他一些距离计算(simhash 就是使用的汉明距离)。


3、加权

有了分词的 hash 结果,可以进行不同权重的配置,比如上述句子中主(我)、谓(敲)、宾语(键盘)配置权重为10,状语(公司)权重为 20,其他词不分配权重,公式表示如下:

20220616202251.jpg


按照上述示例有五个分词,计算出五组 hash 值,对应的也应该分配 5 个权重值,接下来进行权重配比,首先需要将每个词的 hash 值通过一个数组表示方便计算:

    20220616202302.jpg


加权重:

20220616202308.jpg


4、合并

上面每组单词计算后的 hash 值是多个序列,需要进行合并操作为一个序列,如:


20220616202317.jpg


对应位置的值进行累加,合并后的值:

20220616202351.jpg


5、降维

降维这一步操作很简单,将上一步骤计算的结果转为二进制表示即可,即大于0为1,小于0为0,如下:

20220616202401.jpg

通过最终计算的这个 hash 值,可以对比两个句子的汉明距离,通过距离的值判断两个文本的相似度。

20220616202407.jpg

6、补充

simhash 适合海量文本的对比计算,由于我们的实际应用需要进行函数名等短文本对比,仅通过此算法准确度会小一些,因为是通过 hash 值计算,两个英文字符对比出来很有可能相似度很高,所以补充一个最短编辑距离进行相互结合,相似度高的情况下编辑距离但是很长则认为不相似。

js 实现

const {
    createHash
} = require('crypto');

const bigInts = require("big-integer");

/**
 * simhash 相似度匹配算法
 * simhash 的主要思想是将高维的特征向量(文本可转换为高维向量表示)映射成低维的特征向量,通过计算两个向量的汉明距离(Hamming Distance)来确定文本的相似度。 
 * 其中,汉明距离,表示在两个等长字符串中对应位置不同字符的个数。
 * 在此算法基础上增加最小编辑距离计算,增加小文本的校验准确性
 * 
 * 具体步骤:
 *  1、分词
 *  2、hash
 *  3、加权
 *  4、合并
 *  5、降维
 * 
 * 工具使用:
    const simHash = new SimHash();
    console.log(simHash.isSame('getRuoteType', 'getTypes')
 * 
 */
class SimHash {

    HASH_SIZE = 128;

    isSame = (str1, str2) => {
        const hm = this.hammingDistance(
            this.run(str1),
            this.run(str2)
        );

        const same = 100 - hm * 100 / 128;
        const minVal = minDistance(str1, str2);

        // 结果准确性还需要进一步的大量数据计算一个拐点值
        if (same > 90 || (minVal < Math.min(str1.length, str2.length) / 5)) {
            return true;
        }
        return false;
    }

    token = (s) => {
        // 如许长文本检测 使用jieba 进行自然语言处理分词 目前只针对函数名 直接截取即可
        return s.split('');
    }

    hash = (message) => {
        const md5 = createHash('md5');

        //hex 转化为十六进制
        const digest = md5.update(message, 'utf8').digest('hex'); 
        const bit = bigInts(digest, 16).toString(2);
        return bit;
    }

    // MD5哈希二进制最高位如果为 0,则不存储,比如 a 计算 hash 后长度为 124 位,需要前置补位
    fillHash = (strToken) => {
        // hash 计算
        let itemHash = this.hash(strToken);
        
        if (itemHash.length < this.HASH_SIZE) {
            const que = this.HASH_SIZE - itemHash.length;
            for(let j = 0; j < que; j++){
                itemHash = '0' + itemHash;
            }
        }

       return itemHash;
    }

    weightHash = (itemHash) => {
        const itemHashArr = itemHash.split('');

        // 加权 由于没有进行分词 加权目前全部为 1
        for (let j = 0, len = itemHashArr.length; j < len; j++) {
            if (itemHashArr[j] == '1') {
                itemHashArr[j] ++;
            }else{
                itemHashArr[j] --;
            }
        }

        return itemHashArr;
    }
    
    mergeHash = (itemHashArr, res) => {
        for (let j = 0, len = itemHashArr.length; j < len; j++) {
            itemHashArr[j] += res[j] || 0;
        }

        return itemHashArr;
    }

    binaryStr = (res) => {
        let str = '';
        for (let i = 0, len = res.length; i < len; i++) {
            if (res[i] <= 0) {
                str += '0';
            } else {
                str += '1';
            }
        }

        return str;
    }

    hammingDistance = (bit1, bit2) => {
        const bit1Arr = bit1.split('');
        const bit2Arr = bit2.split('');

        let hm = 0;

        for (let i = 0, len = bit1Arr.length; i < len; i++) {
            if (bit1Arr[i] !== bit2Arr[i]) {
                hm ++;
            }
        }

        return hm;
    }

    run = (str) => {
        // const hashList = new Array(128).fill(0);
        const hashList = new Array(this.HASH_SIZE);
        for (let i = 0, len = hashList.length; i < len; i++) {
            hashList[i] = 0;
        }

        // 分词
        const tokenList = this.token(str);

        // 合并值
        let res = [];

        for (let i = 0, len = tokenList.length; i < len; i++) {
            // hash 计算
            let itemHash = this.fillHash(tokenList[i]);

            // 加权
            const itemHashArr = this.weightHash(itemHash);

            // 合并
            const val = this.mergeHash(itemHashArr, res);
            res = val;
        }

        // 降维
        const binaryStr = this.binaryStr(res);

        // 提供此值计算海明距离
        return binaryStr;
    }
}

// 最小编辑距离
function minDistance (str1, str2) {
    let m = str1.length;
    let n = str2.length;

    // 最小编辑距离是dp[i+1][j+1]
    let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

    // base case
    for (let i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = j;
    }

    // 自底向上求解
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 相同字符跳过
            if (str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 删除 插入 替换 寻找最小操作步骤
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,
                    dp[i][j - 1] + 1,
                    dp[i - 1][j - 1] + 1
                );
            }
        }
    }

    return dp[m][n];
};

const {text1, text2} = require('./test');

const simHash = new SimHash();
text1.map((item, i) => {
    console.log(simHash.isSame(item, text2[i]))
})


数据验证

20220616171534.jpg

汉明距离为 3 时结果是最准确的,但是进行短文本计算时这个值为 1 时更为准确一些(具体证明步骤或数学证明暂无)。并且在进行编辑距离的对比时也加入了字符串长度的影响因素。

实际应用

可以补充 eslint 规则,开发时进行和自己一些基础库中已经沉淀的方法进行比较,避免重复逻辑的编写。

但是此时思考一个问题,如何去查找,在大量原始数据中如何快速找到相似的名称,如果采用顺序遍历对比的方式则耗时会特别长,所以论文中也给出了算法思路和实现的几种方式在 3.1.1 Exploration of Design Parameters 章节中:

1、首先对于集合 Q 构建多个表 T1,T2…Tt,每一个表都是采用对应的置换函数 π(i) 将 64-bit 的指纹中的某 p(i) 位序列置换换到整个序列的最前面。即每个表存储都是整个 Q 的指纹的复制置换。

2、对于给定的 F,在每个 Ti 中进行匹配,寻找所有前 pi 位与 F 经过 π(i) 置换后的前 pi 位相同的指纹。

3、对于所有在上一步中匹配到的置换后的指纹,计算其是否与 π(i) (F) 至多有 k-bit 不同。

主要是有四种拆分方法:

1、将64位分割为 11、11、11、11、10、10位,随机选取其中两部分作为前P(i)位;
2、将64位分割为 13、13、13、13、12位,随机选取其中两部分作为前P(i)位;
3、将64位分割为 16、16、16、16位,随机选取一个部分;将剩余部分分为12、12、12、12,随机选取一部分;将这两部分作为前P(i)位;
4、将64位分割为 16、16、16、16位,随机选取其中一部分作为前P(i)位

其中第四种是最优的一种解法,原理就是依赖“抽屉原理”,分割后随机选取一部分,将库中的数据 hash 值相应位置的 hash 值进行对比,如果一样则将库中数据提取出来暂存,再进行一轮对比,如果符合上述代码计算出的结果(k=1 || distance)则判定为相似。

其中论文中还介绍了 3.2 Compression of Finger 一种 hash 压缩算法,看不懂,结束了。






4人赞

分享到: