PostgreSQL里的17种文本相似算法与GIN索引 - pg_similarity

标签

PostgreSQL , 文本相似 , pg_similarity , pg_trgm , rum , fuzzymatch gin , smlar


背景

文本相似算法,结合PostgreSQL的开放索引框架GIN,可以实现各种相似算法的文本高效检索。

PostgreSQL中常见的文本相似搜索插件:rum, pg_trgm, fuzzymatch, pg_similarity, smlar。

其中pg_similarity支持的算法达到了17种。

Introduction

pg_similarity is an extension to support similarity queries on PostgreSQL.

The implementation is tightly integrated in the RDBMS in the sense that it defines operators
so instead of the traditional operators (= and <>) you can use ~~~ and ! (any of these
operators represents a similarity function).

pg_similarity has three main components:

Functions:

a set of functions that implements similarity algorithms available in the literature.

These functions can be used as UDFs and, will be the base for implementing the similarity operators;

Operators:

a set of operators defined at the top of similarity functions.

They use similarity functions to obtain the similarity threshold and,
compare its value to a user-defined threshold to decide if it is a match or not;

Session Variables:

a set of variables that store similarity function parameters. Theses variables can be defined at run time.

  • L1 Distance (as known as City Block or Manhattan Distance);
  • Cosine Distance;
  • Dice Coefficient;
  • Euclidean Distance;
  • Hamming Distance;
  • Jaccard Coefficient;
  • Jaro Distance;
  • Jaro-Winkler Distance;
  • Levenshtein Distance;
  • Matching Coefficient;
  • Monge-Elkan Coefficient;
  • Needleman-Wunsch Coefficient;
  • Overlap Coefficient;
  • Q-Gram Distance;
  • Smith-Waterman Coefficient;
  • Smith-Waterman-Gotoh Coefficient;
  • Soundex Distance.

用法如下

Algorithm Function Operator Use Index? Parameters
L1 Distance block(text, text) returns float8 ~++ yes pg_similarity.block_tokenizer (enum)
pg_similarity.block_threshold (float8)
pg_similarity.block_is_normalized (bool)
Cosine Distance cosine(text, text) returns float8 ~## yes pg_similarity.cosine_tokenizer (enum)
pg_similarity.cosine_threshold (float8)
pg_similarity.cosine_is_normalized (bool)
Dice Coefficient dice(text, text) returns float8 ~-~ yes pg_similarity.dice_tokenizer (enum)
pg_similarity.dice_threshold (float8)
pg_similarity.dice_is_normalized (bool)
Euclidean Distance euclidean(text, text) returns float8 ~!! yes pg_similarity.euclidean_tokenizer (enum)
pg_similarity.euclidean_threshold (float8)
pg_similarity.euclidean_is_normalized (bool)
Hamming Distance hamming(bit varying, bit varying) returns float8
hamming_text(text, text) returns float8
~@~ no pg_similarity.hamming_threshold (float8)
pg_similarity.hamming_is_normalized (bool)
Jaccard Coefficient jaccard(text, text) returns float8 ~?? yes pg_similarity.jaccard_tokenizer (enum)
pg_similarity.jaccard_threshold (float8)
pg_similarity.jaccard_is_normalized (bool)
Jaro Distance jaro(text, text) returns float8 ~%% no pg_similarity.jaro_threshold (float8)
pg_similarity.jaro_is_normalized (bool)
Jaro-Winkler Distance jarowinkler(text, text) returns float8 ~@@ no pg_similarity.jarowinkler_threshold (float8)
pg_similarity.jarowinkler_is_normalized (bool)
Levenshtein Distance lev(text, text) returns float8 ~== no pg_similarity.levenshtein_threshold (float8)
pg_similarity.levenshtein_is_normalized (bool)
Matching Coefficient matchingcoefficient(text, text) returns float8 ~^^ yes pg_similarity.matching_tokenizer (enum)
pg_similarity.matching_threshold (float8)
pg_similarity.matching_is_normalized (bool)
Monge-Elkan Coefficient mongeelkan(text, text) returns float8 ~|| no pg_similarity.mongeelkan_tokenizer (enum)
pg_similarity.mongeelkan_threshold (float8)
pg_similarity.mongeelkan_is_normalized (bool)
Needleman-Wunsch Coefficient needlemanwunsch(text, text) returns float8 ~#~ no pg_similarity.nw_threshold (float8)
pg_similarity.nw_is_normalized (bool)
Overlap Coefficient overlapcoefficient(text, text) returns float8 ~** yes pg_similarity.overlap_tokenizer (enum)
pg_similarity.overlap_threshold (float8)
pg_similarity.overlap_is_normalized (bool)
Q-Gram Distance qgram(text, text) returns float8 ~~~ yes pg_similarity.qgram_threshold (float8)
pg_similarity.qgram_is_normalized (bool)
Smith-Waterman Coefficient smithwaterman(text, text) returns float8 ~=~ no pg_similarity.sw_threshold (float8)
pg_similarity.sw_is_normalized (bool)
Smith-Waterman-Gotoh Coefficient smithwatermangotoh(text, text) returns float8 ~!~ no pg_similarity.swg_threshold (float8)
pg_similarity.swg_is_normalized (bool)
Soundex Distance soundex(text, text) returns float8 ~*~ no

参考

http://pgsimilarity.projects.pgfoundry.org/

https://github.com/eulerto/pg_similarity

https://www.pgcon.org/2009/schedule/attachments/108_pg_similarity.pdf

http://www.sigaev.ru/git/gitweb.cgi?p=smlar.git;a=summary

https://github.com/postgrespro/rum

https://www.postgresql.org/docs/9.6/static/fuzzystrmatch.html

https://www.postgresql.org/docs/9.6/static/pgtrgm.html

时间: 2024-09-14 16:56:21

PostgreSQL里的17种文本相似算法与GIN索引 - pg_similarity的相关文章

PostgreSQL GIN索引实现原理

标签 PostgreSQL , GIN , 内核 , 实现原理 , PostgreSQL数据库内核分析 背景 本文参考并扩展自如下文档,修正了一些内容(大多数是由于版本不同造成的差异) <PostgreSQL数据库内核分析> ( 成书较早,大量内容基于8.4的代码编写 ) 以及 http://zisedeqing.blog.163.com/blog/static/95550871201621623458216/ ( 大量内容参考自 PostgreSQL数据库内核分析 ) 术语 本文适用的一些术

17种Mac常见问题的解决方法

Mac是非常可靠稳定的电脑,但这并不意味着它们就不会出错,不会坏,不会犯傻.我们总结出了一些Mac的"啊哦"的镜头,并告诉你如何对付它们并防止再次发生. 没有电脑是永远不会出问题的.即使是Mac也有犯脾气的时候,突然的不好好工作了,从一个乖宝宝变成了一个大魔头. 如果说,PC有时候很固执任性的话,那么Mac就有些难搞定了.通常情况下它们只在及其恶略的生存条件下才会起义--比如说你给MacBook喝了一点果汁什么的.就像人一样,Mac工作时间长了,也需要一点时间休息. 不管Mac出了什么

苹果mac电脑17种常见问题的解决方法

随着时代的发展,苹果mac以它美观的外表以及系统的稳定抓住越来越多用户的心. Mac是非常可靠稳定的电脑,但这并不意味着它们就不会出错,不会坏,不会犯傻.我们总结出了一些Mac的"啊哦"的镜头,并告诉你如何对付它们并防止再次发生. 没有电脑是永远不会出问题的.即使是Mac也有犯脾气的时候,突然的不好好工作了,从一个乖宝宝变成了一个大魔头. 如果说,PC有时候很固执任性的话,那么Mac就有些难搞定了.通常情况下它们只在及其恶略的生存条件下才会起义--比如说你给MacBook喝了一点果汁什

《算法导论(原书第3版)》一1.2 作为一种技术的算法

1.2 作为一种技术的算法 假设计算机是无限快的并且计算机存储器是免费的,你还有什么理由来研究算法吗?即使只是因为你还想证明你的解法会终止并以正确的答案终止,那么回答也是肯定的. 如果计算机无限快,那么用于求解某个问题的任何正确的方法都行.也许你希望你的实现在好的软件工程实践的范围内(例如,你的实现应该具有良好的设计与文档),但是你最常使用的是最容易实现的方法. 当然,计算机也许是快的,但它们不是无限快.存储器也许是廉价的,但不是免费的.所以计算时间是一种有限资源,存储器中的空间也一样.你应该明

php四种基础排序算法的运行时间比较

/**  * php四种基础排序算法的运行时间比较  * @authors Jesse (jesse152@163.com)  * @date    2016-08-11 07:12:14  */ //冒泡排序法 function bubbleSort($array){     $temp = 0;     for($i = 0;$i < count($array) -1;$i++){         for($j = 0;$j < count($array) - 1 -$i;$j++){  

PHP实现四种基础排序算法的运行时间比较(推荐)

许多人都说算法是程序的核心,算法的好坏决定了程序的质量.作为一个初级phper,虽然很少接触到算法方面的东西.但是对于基本的排序算法还是应该掌握的,它是程序开发的必备工具.下面通过本文给大家介绍PHP实现四种基础排序算法的运行时间比较,一起看下吧. 废话不多说了,直接给大家贴代码了. 具体代码如下所示: /** * php四种基础排序算法的运行时间比较 * @authors Jesse (jesse152@163.com) * @date 2016-08-11 07:12:14 */ //冒泡排

无序列表-列表里的符号与文本之间可以设置间距么?

问题描述 列表里的符号与文本之间可以设置间距么? 如图,如果想把小黑点放在图片的前面,怎么放?另外小黑点和文本(此处是图片)的间距可以设置吗? 解决方案 设置padding-left <ul> <li style="padding-left:30px">aaa</li> <li>aaa</li> <li>aaa</li> <li>aaa</li> </ul> 解决方案

子集和问题:一种组合生成算法

今天在网上看见这么一道题目:给你m个数,从里面找出和为sum的n个数,问一共能找到多少组这样的 数. 根据我的理解,这是一道组合生成的题目.令m个数组成的集合为M,就是要找到所有元素个数为n且和 为sum的子集. 最笨的方法是生成所有的子集,然后进行验证,这样复杂度为阶乘.显然有一种改进的算法,在笨方 法中,我们连元素个数不为n的子集都生成了,而这显然是不必要的.这种改进想到很容易,但实现起来 有点困难,经过数个小时的艰苦奋战,我终于设计了一种原创性的组合生成算法,虽然它应该早被计算机 科学家想

Oracle中三种表连接算法的总结

Oracle有三种表连接技术,分别是嵌套连接.合并连接和哈希连接.以下就是对这三种表连接算法进行了详细的分析介绍,需要的朋友可以参考下   1. 嵌套循环连接 (NESTED LOOP Join)嵌套连接把要处理的数据集分为外循环(驱动数据源)和内循环(被驱动数据源),外循环只执行一次(先执行),内循环执行的次数等于外循环执行的数据集个数. 这种连接的好处是内存使用非常少. 如果驱动数据源有限,且被驱动表在连接列上有相应的索引,则这种连接方式才是高效的. 在OLTP系统上常见到这种连接方式. 2