最长匹配子串

Question

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

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

我想编写一个 plpgsql 函数，它在其他参数中接受一个字符串作为输入（例如shazam），并返回具有最长匹配子字符串的 GOB 行上的“奖品”列。在所示的示例中，它将位于$1.50magic_word 行上shaza。

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

有任何想法吗？

Answer 1

简单的解决方案

\n

SELECT magic_word\nFROM   gob\nWHERE  \'shazam\' LIKE (magic_word || \'%\')\nORDER  BY magic_word DESC\nLIMIT  1;\n

\n

这是有效的，因为最长的匹配项排在最后 - 所以我排序DESC并选择第一个匹配项。

\n

我从您的示例中假设您希望从字符串的开头匹配左锚定。如果您想匹配字符串中的任何位置（这会更昂贵并且更难以使用索引进行备份），请使用：

\n

...\nWHERE  \'shazam\' LIKE (\'%\' || magic_word || \'%\')\n...\n

\n

SQL 小提琴。

\n

表现

\n

该查询不可控制。如果您有其他信息（例如可以作为索引基础的最小长度），这可能会很有帮助，以减少要考虑的行数。它需要有一个标准，使您的比例小于表的 5% 才能有效。因此，缩写（自然的最小选择）可能有用，也可能没用。但开头的两三个字母可能会有很大帮助。

\n

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

\n

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

\n

\n
• 空间索引可以帮助 \xe2\x80\x9crange - order by - limit\xe2\x80\x9d 查询
\n

\n

另一种方法是使用三元组索引。pg_trgm为此，您需要额外的模块。通常，您会在具有较长字符串的表中使用短模式进行搜索。但是三元组也适用于你的反向方法，但有一些限制。显然，您无法使用三元组来匹配较长字符串中间只有两个字符的字符串...测试极端情况。
\n这里有很多关于 SO 的答案，其中包含更多信息。例子：

\n

\n
• 有效查询包含子字符串的列
\n

\n

先进的解决方案

\n

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

\n

\n
• 最长前缀匹配
\n

\n