基于子字符串长度匹配的高效SQL桶排序

Question

给定包含按字母顺序索引的字符串的SQL数据库表，如何执行按子字符串匹配排序的搜索查询？

例如，给定数据集：

bad
banana
bandana
banker
bed
brother

和搜索字符串band，我希望得到如下排序的结果

bandana (index 0-3 matched)
banana  (index 0-2 matched)
banker
bad     (index 0-1 matched)
bed     (index 0 matched)
brother

注意，我们只关心匹配的子字符串的长度。每个桶中的匹配不需要按字母顺序排序，我只关心它们落入的桶。

因此，我天真地认为这个问题涉及到：

1. 查看每一行的子字符串长度与我的输入匹配
2. 根据匹配长度将每一行放入适当的桶中。
3. 按降序排列桶，即(4个字符匹配，3个字符匹配，2个.)

但是这听起来很昂贵，所以我如何在SQL或C#中实现它，并有效地实现它呢？

有类似的问题/模式，我可以从中受益吗？

非常感谢

Answer 1

不确定这是否是最有效的方法，但是。

使用数字表，将字符串拆分为字符，并将其加入到搜索字符串的拆分中，然后按计数和字符串进行排序。

DECLARE @t TABLE ( string VARCHAR(50) )

INSERT INTO @t (string)
VALUES 
    ('bad'),
    ('banana'),
    ('bandana'),
    ('banker'),
    ('bed'),
    ('brother')

DECLARE @search VARCHAR(50) = 'band'

;WITH numbers AS
(
    SELECT TOP 10000 ROW_NUMBER() OVER(ORDER BY t1.number) AS n
    FROM master..spt_values t1 
    CROSS JOIN master..spt_values t2
)   
SELECT string
FROM @t t
CROSS APPLY (
    SELECT SUBSTRING(t.string, numbers.n, 1) c, n
    FROM numbers
    WHERE numbers.n <= LEN(string)
) s1
JOIN (
    SELECT SUBSTRING(@search, numbers.n, 1) c, n
    FROM numbers
    WHERE numbers.n <= LEN(@search)
) s2 ON s2.c = s1.c
    AND s2.n = s1.n 
GROUP BY string
ORDER BY COUNT(1) DESC, string

演示

Answer 2

字符串操作和sql-server并不是最佳匹配的afaik。

我最好的选择是尝试一种改进型的拜耳-摩尔-霍斯波尔，以找到匹配字符的数量。然而，在错过的时候，你不会跳过完整的单词长度，只会跳过最大匹配的长度。然后简单地插入到顶部的桶中。