查看哪个模式匹配单个单词的有效方法

Question

我正在创建一个函数来找出最适合单个字符串的搜索模式。要匹配的字符串将与可能有数百种可能模式的表格进行比较，以查看它是否与其中任何一种匹配。

我现在有一个不太优雅的函数，它可以将所有模式读入内存表并遍历它们以查看每个模式是否匹配。它有效，但想到在生产环境中使用它让我感到恶心，尤其是当模式表增长到数千个模式时。

要匹配的示例字符串：'Master'

可能的模式：

1. 先生
2. abc%
3. xyz%
4. A B C D

结果将与模式#1 匹配。

在这个场景中，我需要能够匹配潜在的部件号、品牌和其他可能拼错的短语。我正在合并 Double Metaphone，但是当涉及到只有一个模式才能捕捉到的其他项目时，我需要知道哪些模式是匹配的。“StringToSearch”只会返回 1 个匹配的模式。

有没有人有理论或其他代码类型可以帮助我完成这个反向模式匹配过程？

Answer 1

在不知道您的实际场景是什么样的情况下，我可能会执行以下操作：

USE tempdb;

IF OBJECT_ID(N'dbo.Strings', N'U') IS NOT NULL
DROP TABLE dbo.Strings;
CREATE TABLE dbo.Strings
(
    TargetString varchar(46) NOT NULL
);

IF OBJECT_ID(N'dbo.Matches', N'U') IS NOT NULL
DROP TABLE dbo.Matches;
CREATE TABLE dbo.Matches
(
    PossibleMatch varchar(46) NOT NULL
);

INSERT INTO dbo.Strings(TargetString)
VALUES ('Master');

INSERT INTO dbo.Matches(PossibleMatch)
VALUES ('m%r')
    , ('abc%')
    , ('zyx%')
    , ('a%bcd')

SELECT *
FROM dbo.Strings s
    INNER JOIN dbo.Matches m ON s.TargetString LIKE m.PossibleMatch

????????????????????????????????????
? 目标字符串？可能匹配？
????????????????????????????????????
? 掌握 ？先生 ？
????????????????????????????????????

如果您通过解释数据的设计方式以及您的确切设计目标来更准确地描述您的场景是什么，您将获得一组更好的答案。

为了查看这种方法是否足够有效，我通过添加几个索引和一堆数据扩展了上面的 MCVE：

这些表现在有聚集索引：

IF OBJECT_ID(N'dbo.Strings', N'U') IS NOT NULL
DROP TABLE dbo.Strings;
CREATE TABLE dbo.Strings
(
    TargetString varchar(46) NOT NULL
        PRIMARY KEY CLUSTERED
);

IF OBJECT_ID(N'dbo.Matches', N'U') IS NOT NULL
DROP TABLE dbo.Matches;
CREATE TABLE dbo.Matches
(
    PossibleMatch varchar(46) NOT NULL
        PRIMARY KEY CLUSTERED
);

这将在Strings表中插入 50,000 个单词：

;WITH src AS (
    SELECT v.val
    FROM (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9))v(val)
)
, src26 AS 
(
    SELECT TOP(26) Num = (v.val * 10) + v1.val
    FROM src v
        CROSS JOIN src v1
    ORDER BY v.val, v1.val
)
, words AS
(
    SELECT c1 = CHAR(65 + s1.num)
        , c2 = CHAR(65 + s2.num)
        , c3 = CHAR(65 + s3.num)
        , c4 = CHAR(65 + s4.num)
        , c5 = CHAR(65 + s5.num)
    FROM src26 s5
        CROSS JOIN src26 s4
        CROSS JOIN src26 s3
        CROSS JOIN src26 s2
        CROSS JOIN src26 s1
)
INSERT INTO dbo.Strings(TargetString)
SELECT TOP(50000) words.c1
    + words.c2
    + words.c3
    + words.c4
    + words.c5
FROM words
ORDER BY CRYPT_GEN_RANDOM(5);

该表中的行示例：

??????????????????
? 目标字符串？
??????????????????
? UKMBL ?
? ASOCG ?
? XWACG ?
? NHRXQ ?
? LFMBR ?
? 爱克洛？
? 公关人员？
? IIFPD ?
? OCLJQ ?
? NJBMB ?
??????????????????

接下来，我们将Matches使用通配符在表中创建 1,000,000 行：

;WITH src AS (
    SELECT v.val
    FROM (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9))v(val)
)
, src26 AS 
(
    SELECT TOP(26) Num = (v.val * 10) + v1.val
    FROM src v
        CROSS JOIN src v1
    ORDER BY v.val, v1.val
)
, words AS
(
    SELECT c1 = CHAR(65 + s1.num)
        , c2 = CHAR(65 + s2.num)
        , c3 = CHAR(65 + s3.num)
        , c4 = CHAR(65 + s4.num)
        , c5 = CHAR(65 + s5.num)
    FROM src26 s5
        CROSS JOIN src26 s4
        CROSS JOIN src26 s3
        CROSS JOIN src26 s2
        CROSS JOIN src26 s1
)
INSERT INTO dbo.Matches(PossibleMatch)
SELECT TOP(1000000) REPLACE(words.c1, 'A', '_')
    + REPLACE(words.c2, 'E', '_')
    + REPLACE(words.c3, 'I', '_')
    + REPLACE(words.c4, 'O', '_')
    + REPLACE(words.c5, 'U', '%')
FROM words
WHERE NOT (words.c1 = 'A' AND words.c2 = 'E' AND words.c3 = 'I' AND words.c4 ='O' AND words.c5 <> 'U');

SELECT TotalMatches = (SELECT COUNT(1) FROM dbo.Matches)
    , TotalStrings = (SELECT COUNT(1) FROM dbo.Strings)

以下是这些行的示例：

?????????????????????
? 可能匹配？
?????????????????????
? LDBFB ?
? IWLMB ?
? FNBAA ?
? _ZEVC？
? BSZDB ?
? 特里布？
? XVLNA ?
? VLPDB ?
? UI_IA ?
? FNLCB ?
?????????????????????

从上面的示例中可以看出，某些行具有 T-SQL 单字符通配符_，而某些行没有通配符。

现在，我们将运行一些代码，看看我们是否可以从Matches匹配的行中找到一行Strings：

SELECT *
FROM dbo.Strings s
    LEFT JOIN dbo.Matches m ON s.TargetString LIKE m.PossibleMatch
WHERE s.TargetString = (
    SELECT TOP(1) Strings.TargetString
    FROM dbo.Strings 
    ORDER BY CRYPT_GEN_RANDOM(5)
    )

该WHERE子句从Strings表中随机选择一个单词。您可能需要多次运行此程序，然后才能获得Matches表中具有匹配值的单词。

查找Strings表中的任何给定单词，并关联Matches：

SELECT *
FROM dbo.Strings s
    LEFT JOIN dbo.Matches m ON s.TargetString LIKE m.PossibleMatch
WHERE s.TargetString = 'JRZPC'

此查询的计划：

在我的系统上，此查询在大约 100 毫秒内执行。

该查询的结果：

????????????????????????????????????
? 目标字符串？可能匹配？
????????????????????????????????????
? JRZPC ? ___个人电脑 ？
? JRZPC ? __Z_C ?
? JRZPC ? __ZPC ?
? JRZPC ? _R__C ?
? JRZPC ? _R_PC ?
? JRZPC ? _RZ_C ?
? JRZPC ? _RZPC ?
????????????????????????????????????

如果您打算每分钟运行数百或数千个这样的查询，您可能需要重新考虑该策略，但这就是把马放在购物车之前。

如果你想把它作为一个函数来实现，我会考虑这个：

CREATE FUNCTION dbo.FindMatches
(
    @TargetString varchar(46)
)
RETURNS TABLE
WITH SCHEMABINDING
AS RETURN
(
    SELECT m.PossibleMatch
    FROM dbo.Matches m
    WHERE @TargetString LIKE m.PossibleMatch
);
GO

该代码创建了一个模式绑定的表值函数，该函数与目标查询“内联”，并且与此类事情的效率一样高。

这将是您如何调用该函数的示例：

SELECT s.TargetString
    , fm.PossibleMatch
FROM dbo.Strings s
    CROSS APPLY dbo.FindMatches(s.TargetString) fm
WHERE s.TargetString = 'AMLAA'