探究similarity函数字符串相似度算法过程

PostgreSQL pg_tgrm 扩展提供了处理文本相似度和模糊查询的功能，特别是通过使用三元组（trigram）索引来加速全文搜索。其中最重要的是similarity函数。这个函数返回两个字符串之间的相似度得分，分数范围从0到1，其中1表示两个字符串完全相同。

使用示例

SELECT username, similarity(username, 'JohnDoe') AS sim
FROM users
WHERE similarity(username, 'JohnDoe') > 0.5
ORDER BY sim DESC;

这将返回所有与"JohnDoe"相似度超过0.5的用户名，并按照相似度得分降序排列.

本文主要探究该函数的算法过程以及在前端的应用场景

算法过程

similarity函数背后的算法过程主要依赖于三元组（trigrams）的概念。三元组指的是文本中任意三个连续字符的组合。通过比较两个字符串的三元组集合，similarity函数能够计算出字符串之间的相似度。下面是算法过程的详细解释：

1. 生成三元组

首先，从输入的两个字符串中生成三元组。对于每一个字符串，从第一个字符开始，取三个连续的字符形成一个三元组，然后移动一个字符继续生成下一个三元组，直到字符串结束。例如，字符串abcde会产生以下三元组：abc, bcd, cde。

2. 构建三元组集合

对于每一个字符串，构建一个包含所有生成的三元组的集合。集合中元素是唯一的，相同的三元组只出现一次。

3. 计算交集和并集

接着，找到两个字符串三元组集合的交集和并集。交集是两个集合共有的三元组，而并集是两个集合所有三元组的组合。

4. 计算相似度

最后，使用以下公式计算相似度：

similarity = |intersection| / |union|

其中|intersection|是交集中三元组的数量，|union|是并集中三元组的数量。这个比率表示两个字符串三元组集合之间的重叠程度，从而反映了字符串本身的相似度。

算法特点

• 效率：通过使用三元组而不是单个字符或单词，能够更高效地处理文本相似度计算，特别是较长的字符串。但对于短字符串，相似度得分可能不如预期那样有意义。在处理稀疏集合时可能不够敏感，因为它只关注共同元素而不考虑元素的频率或权重。在某些情况下，可能需要采用更复杂的方法
• 容错性：三元组方法对于拼写错误、字符插入、删除或替换具有一定的容忍度。即使字符串有小的差异，只要它们共享足够的三元组，similarity函数仍能给出较高的相似度得分。

为啥是三元组，而不是二元组四元组或者其他长度的元组，应该是基于查询效果和效率的平衡考虑，较短的元祖(比如二元组)局部特征更低，可能无法充分区分不同的字符串导致相似度得分过高。较长的元祖某些情况可能提供更精确的匹配，但可能由于过于严格导致相似度得分过低。pg_trgm的作者可能已经基于测试和经验选择了三元组。

JS示例

const trigrams = (str) => {
  const result = [];
  for (let i = 0; i < str.length - 2; i++) {
    result.push(str.substring(i, i + 3));
  }
  return new Set(result);
}

const similarity = (str1, str2) => {
  const trigramsStr1 = trigrams(str1.toLowerCase());
  const trigramsStr2 = trigrams(str2.toLowerCase());

  const intersection = new Set(
    [...trigramsStr1].filter(x => trigramsStr2.has(x))
  );
  const union = new Set([...trigramsStr1, ...trigramsStr2]);

  return intersection.size / union.size;
}

上述仅为简单示例，在实际应用中，你可能需要对性能进行优化，例如使用缓存机制存储已经计算过的相似度得分，或者使用更高效的数据结构来存储和检索建议。

应用场景

在实际应用中，similarity函数可以用于多种场景，包括但不限于：

• 拼写纠正：寻找接近用户输入的正确拼写的词语
• 模糊搜索：进行近似匹配查询
• 文本分析：比较不同文档或字符串的相似性，用于抄袭检测或内容推荐