fuzzy matching (模糊匹配), 具体可以称为:

✅ Subsequence Matching（子序列匹配）

它的核心思想是：

cha询串的字符按照顺序出现在目标串中，但不要求连续。

比如：

cha询 "m_no" 可以匹配 "MB_YESNO"，因为字符 'm' → '_' → 'n' → 'o' 以此顺序在目标串中依次出现。

模糊匹配系统，能够：

✅ 匹配子序列（如 "m_no" 匹配 "MB_YESNO"）

✅ 根据匹配质量打分

✅ 将匹配结果按打分排序，最好匹配排最前

这种机制可以参考开源工具 fzy、fzf 使用的模糊搜索评分算法，它综合了以下因素：

是否匹配单词的开头（比如 _, 大写字母后的开始）

匹配字符是否靠得近

字符连续匹配是否越多越好

匹配位置是否越靠前越好

匹配例子

MB_YESNO 输入 m_no 就能匹配到

代码

#include <vector>

#include <algorithm>



/// <summary>

/// 模糊匹配分数, 并按得分排序, 传递要搜索的数量和cha询的字符串, 返回得分0以上的匹配项

/// </summary>

/// <typeparam name="_Pr">函数指针类型, 用于获取候选字符串</typeparam>

/// <param name="count">要搜索的数量</param>

/// <param name="query">要搜索的字符串</param>

/// <param name="_Pred">获取候选字符串的函数指针</param>

/// <returns>返回匹配结果, 结果包含索引和得分, 结果是按得分从高到低排序的</returns>

template<typename _Pr> 

inline std::vector> FuzzyMatchAndScore(size_t count, const wchar_t* query, _Pr&& _Pred)

{

    // 精确打分算法

    static auto fuzzyMatchScore = [](const wchar_t* query, const wchar_t* target) -> int

    {

        int score = 0;

        int last_match = -1;

        size_t qi = 0, ti = 0;

        size_t query_len = wcslen(query);

        size_t target_len = wcslen(target);



        while (qi < query_len && ti < target_len)

        {

            if (towlower(query[zxsq-anti-bbcode-qi]) == towlower(target[zxsq-anti-bbcode-ti]))

            {

                score += 10;    // 基础匹配分



                // 位置相关奖励

                if (ti == 0)

                {

                    if (qi == 0)

                    {

                        score += 50;  // 双首字母匹配

                    }

                    else

                    {

                        score += 30;  // 目标首字母匹配

                    }

                }

                else if (qi == 0)

                {

                    score += 20;  // cha询首字母出现在目标中

                }



                // 单词边界检测

                if (ti > 0 && (

                    target[ti - 1] == L'_' ||

                    target[ti - 1] == L' ' ||

                    target[ti - 1] == L'-' ||

                    (iswlower(target[ti - 1]) && iswupper(target[zxsq-anti-bbcode-ti]))))

                {

                    score += 25;    // _ 后 / 单词边界 +25

                }



                if (last_match >= 0)

                {

                    int gap = static_cast<int>(ti - last_match - 1);

                    if (gap == 0)

                    {

                        score += 25;    // 连续匹配 +25

                        // 如果是连续第二个字符

                        if (last_match > 0 && ti - last_match == 1)

                        {

                            score += 10;

                        }

                    }

                    else

                    {

                        score -= std::min(static_cast<int>(pow(gap, 1.5)), 15); // 跳跃惩罚：单次惩罚最大 -15

                    }

                }



                last_match = static_cast<int>(ti);

                ++qi;

            }

            ++ti;

        }



        if (qi == query_len)

        {

            // 长度匹配因素

            float length_ratio = static_cast<float>(query_len) / target_len;

            score = static_cast<int>(score * (0.5f + 0.5f * length_ratio));



            // 匹配位置因素

            float position_ratio = 1.0f - (static_cast<float>(ti) / target_len);

            score = static_cast<int>(score * (0.7f + 0.3f * position_ratio));



            return std::max(score, 1);  // 匹配成功，至少1分

        }

        return 0;

    };



    std::vector> results;



    for (int i = 0; i < (int)count; ++i)

    {

        int score = fuzzyMatchScore(query, _Pred(i));

        if (score > 0)

        {

            results.push_back({ i, score });

        }

    }



    // 按得分从高到低排序

    std::sort(results.begin(), results.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b)

    {

        return a.second != b.second ? a.second > b.second : a.first < b.first;

    });



    return results;

}

调用例子

#include <iostream>

#include <climits>

#include <locale.h> 



int main() {



    setlocale(LC_ALL, "chs");



    const wchar_t* candidates[] = {

        L"MB_YESNO",

        L"MB_ICONQUESTION",

        L"MB_ABORTRETRYIGNORE",

        L"IDOK",

        L"IDCANCEL",

        L"MESSAGEBOX_YESNO"

    };



    const size_t count = sizeof(candidates) / sizeof(candidates[zxsq-anti-bbcode-0]);



    auto results = FuzzyMatchAndScore(count, L"m_no", [&candidates](int i)

    {

        return candidates[zxsq-anti-bbcode-i];

    });



    wprintf(L"总共匹配到 %zu 项：\n", results.size());

    for (const auto& result : results)

    {

        wprintf(L"\t%s（得分: %d）\n", candidates[result.first], result.second);

    }



    return 0;

}

输出结果:

总共匹配到 4 项：

        MB_YESNO(得分: 62)

        MB_ABORTRETRYIGNORE(得分: 47)

        MESSAGEBOX_YESNO(得分: 45)

        MB_ICONQUESTION(得分: 31)

长度匹配因素 = cha询文本长度 / 目标文本长度

匹配位置因素 = 1.0 - (目标文本cha询位置 / 目标文本长度)

计算公式: (总分 (0.5 + 0.5 长度匹配因素)) (0.7 + 0.3 匹配位置因素)

m_no MB_YESNO

步骤	匹配字符	位置	得分说明
1	m	0	基础+10, 双首字母匹配+50
2	_	2	基础+10, 跳跃1个字符惩罚-1
3	n	6	基础+10, 跳跃3个字符惩罚-5
4	o	7	基础+10, 连续匹配+25, 二次连续+10

总分: 10+50+10-1+10-5+10+25+10=119

长度匹配因素: 4 / 8 = 0.5

匹配位置因素: 1.0 - (8 / 8) = 0.0

最终得分：套入长度/位置因素, 总得分62

m_no MB_ICONQUESTION

步骤	匹配字符	位置	得分说明
1	m	0	基础+10, 双首字母匹配+50
2	_	2	基础+10, 跳跃1个字符惩罚-1
3	n	6	基础+10, 跳跃3个字符惩罚-5
4	o	13	基础+10, 跳跃6个字符惩罚-14

总分: 10+50+10-1+10-5+10-14=70

长度匹配因素: 4 / 15 = 0.266666681

匹配位置因素: 1.0 - (14 / 15) = 0.0666666627

最终得分：套入长度/位置因素, 总得分31

m_no MB_ABORTRETRYIGNORE

步骤	匹配字符	位置	得分说明
1	m	0	基础+10, 双首字母匹配+50
2	_	2	基础+10, 跳跃1个字符惩罚-1
3	n	15	基础+10, 跳跃12个字符惩罚-15
4	o	16	基础+10, 连续匹配+25, 二次连续+10

总分: 10+50+10-1+10-15+10+25+10=109

长度匹配因素: 4 / 19 = 0.210526317

匹配位置因素: 1.0 - (17 / 19) = 0.105263174

最终得分：套入长度/位置因素, 总得分47

m_no MESSAGEBOX_YESNO

步骤	匹配字符	位置	得分说明
1	m	0	基础+10, 双首字母匹配+50
2	_	10	基础+10, 跳跃9个字符惩罚-15
3	n	14	基础+10, 跳跃3个字符惩罚-5
4	o	15	基础+10, 连续匹配+25, 二次连续+10

总分: 10+50+10-15+10-5+10+25+10=105

长度匹配因素: 4 / 15 = 0.25

匹配位置因素: 1.0 - (16 / 16) = 0.0

最终得分：套入长度/位置因素, 总得分45

IDOK 和 IDCANCEL 得分为0, 没有匹配到, 这里就没有列出表格

得到以上分数后进行排序, 得分越大越靠前

文章发表于: https://www.kuodafu.com/?p=178