最长匹配子字符串 [英] Longest matching substring

查看：16 发布时间：2022/4/14 10:34:44 postgresql plpgsql

本文介绍了最长匹配子字符串的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

如何在varchar变量中搜索最长的匹配项？例如，表GOB具有如下条目：

magic_word |  prize
===================
         sh|  $0.20
        sha|  $0.40
       shaz|  $0.60
      shaza|  $1.50

我想编写一个plpgsql函数，该函数在其他参数中接受一个字符串作为输入(例如shazam)，并在具有最长匹配子字符串的GOB行上返回‘PRIVE’列。在所示的示例中，将在带有MAGIC_WORDshaza的行上$1.50。

我可以处理的所有函数格式，它只是匹配的位。我想不出一个优雅的解决方案。我猜这可能真的很容易，但我正在挠头。我不知道开头的输入字符串，因为它将派生自对另一个表的查询结果。

有什么想法吗？

SELECT magic_word
FROM   gob
WHERE  'shazam' LIKE (magic_word || '%')
ORDER  BY magic_word DESC
LIMIT  1;

这是可行的，因为最长的匹配项排在最后，所以我排序DESC并挑选第一个匹配项。

我假设从您的示例中，您希望从字符串的开头匹配Left-Anchored。如果想要匹配字符串中的任何位置(使用索引备份成本更高，甚至更难)，请使用：

...
WHERE  'shazam' LIKE ('%' || magic_word || '%')
...

查询不是sargable。如果您有其他信息，比如可以作为索引基础的最小长度，以减少要考虑的行数，这可能会有很大帮助。它需要使您的表中低于~5%的标准才能有效。因此，首字母(自然的最小选择)可能有用，也可能没用。但开头的两三个字母可能会有相当大的帮助。

事实上，您可以迭代地对其进行优化。大致如下：
尝试15个字母的单词的部分索引+
如果未找到，请尝试12个字母+
如果未找到，请尝试9个字母+
...

我在dba上的相关回答中概述的一个简单案例。SE：

另一种方法是使用三元组索引。为此，您需要额外的模块pg_trgm。通常，您会在包含长字符串的表中使用短模式进行搜索。但三叉树也适用于你的反向方法，但有一些限制。显然，您不能使用三元语法匹配一个较长字符串中间只有两个字符的字符串……测试角落案例。
这里有许多答案，所以有更多的信息。示例：

在这个密切相关的问题下考虑搜索字符串表的解决方案。使用递归CTE实现：

这篇关于最长匹配子字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文