如何仅使用PostgreSQL创建简单的模糊搜索？

Question

我在我的RoR网站上的搜索功能中遇到了一点问题。我有许多带有一些代码的产品。这个代码可以是任何字符串，例如“AB-123-lHdfj”。现在我使用ILIKE操作符来查找产品：

Product.where("code ILIKE ?", "%" + params[:search] + "%")

代码正常运行，但无法找到类似于"AB123-lHdfj"或"AB123lHdfj"这样的产品。

我该怎么办？也许Postgres有一些字符串规范化函数或其他方法可以帮助我吗？

- Alve

Answer 1

Postgres提供了几个字符串比较函数的模块，例如soundex和metaphone。但是你会想要使用levenshtein编辑距离函数。

Example:

test=# SELECT levenshtein('GUMBO', 'GAMBOL');
 levenshtein
-------------
           2
(1 row)

2 是两个单词之间的编辑距离。当您将其应用于多个单词并按照编辑距离结果排序时，您将得到所需的模糊匹配类型。

尝试此查询示例：（当然，要使用您自己的对象名称和数据）

SELECT * 
FROM some_table
WHERE levenshtein(code, 'AB123-lHdfj') <= 3
ORDER BY levenshtein(code, 'AB123-lHdfj')
LIMIT 10

这个查询的意思是：

给我所有数据中代码值与输入值'AB123-lHdfj'之间编辑距离小于3的前10个结果。你将得到所有代码值与'AB123-lHdfj'相差不超过3个字符的行...

注意：如果出现类似以下错误：

function levenshtein(character varying, unknown) does not exist

使用以下命令安装 fuzzystrmatch 扩展：

test=# CREATE EXTENSION fuzzystrmatch;

- Paul Sasik

---

我添加了一个简单的硬编码查询示例，应该足以让您开始。不要忘记确保fuzzystrmatch模块对您可用：http://www.postgresonline.com/journal/categories/57-fuzzystrmatch - Paul Sasik

Levenshtein是一个昂贵的函数，这是每次调用都运行两次Levenshtein吗？ - triunenature

@triunenature 实际调用次数取决于优化程度。如果优化器足够智能，它将只调用一次并缓存结果。我还应该指出，即使未经过优化，调用的复杂度也是线性的，而不是指数级别，因此性能影响并不严重。 - Paul Sasik

感谢您提醒我需要安装fuzzystrmatch才能在PostgreSQL中使用levenshtein。这帮助我摆脱了“提示：没有与给定名称和参数类型匹配的函数。您可能需要添加显式类型转换”的问题。 - andilabs

注意！还有一个名为levenshtein_less_equal()的函数！这是Levenshtein函数的加速版本，仅在关心小距离时使用。如果实际距离小于或等于max_d，则levenshtein_less_equal返回正确的距离；否则它将返回大于max_d的某个值。如果max_d为负，则行为与levenshtein相同。test=# SELECT levenshtein_less_equal('extensive', 'exhaustive',2); - simUser

Answer 2

Paul告诉你关于levenshtein()的事情。那是一个非常有用的工具，但对于大表格来说速度很慢。它必须为每一行计算与搜索项的Levenshtein距离。这是非常耗费资源的，并且无法使用索引。"加速"变体levenshtein_less_equal()对于长字符串来说更快，但没有索引支持仍然很慢。

如果你的需求就像例子所示的那样简单，你仍然可以使用LIKE。只需在WHERE子句中将搜索项中的任何-替换为%。所以不是：

WHERE code ILIKE '%AB-123-lHdfj%'

使用：

WHERE code ILIKE '%AB%123%lHdfj%'

或者，动态地：

WHERE code ILIKE '%' || replace('AB-123-lHdfj', '-', '%') || '%'

在“LIKE”模式中，%代表0到n个字符。或者使用_表示正好一个字符。或者使用正则表达式进行更智能的匹配：

WHERE code ~* 'AB.?123.?lHdfj'

.? ... 0或1个字符

或者：

WHERE code ~* 'AB\-?123\-?lHdfj'

\-? ... 0或1个破折号

您可能希望在LIKE或正则表达式模式中转义特殊字符。请参见：

• 用于正则表达式或LIKE模式的转义函数

---

如果你的实际问题更加复杂，并且需要更快的解决方案，那么根据你的需求，有各种选择：

• 当然，你可以使用全文搜索。但在你的情况下，这可能有点过头了。

• 更合适的选择是使用附加模块pg_trgm进行三元匹配。参见：

  • 如何在tsvector中使用Levenshtein函数？
  • PostgreSQL LIKE查询性能变化
  • Depesz的相关博客文章

  自从PostgreSQL 9.1版本以后，可以将其与LIKE、ILIKE、~或~*结合使用。
  在这个上下文中也很有意思的是该模块的similarity()函数或%运算符。

• 最后，你还可以实现一个手工解决方案，使用一个函数来规范化要搜索的字符串。例如，你可以将AB1-23-lHdfj转换为ab123lhdfj，将其保存在另外一列中，并使用相同方式转换的术语进行搜索。

  或者，可以使用表达式索引代替多余的列。（涉及的函数必须是IMMUTABLE的。）可能还可以将其与上述的pg_tgrm结合使用。

模式匹配技术概述：

- 使用LIKE、SIMILAR TO或正则表达式进行模式匹配的方法。

- Erwin Brandstetter