一个模糊匹配算法+打分机制

共计 4052 个字符，预计需要花费 11 分钟才能阅读完成。

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

✅ Subsequence Matching（子序列匹配）

它的核心思想是：

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

比如：

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

模糊匹配系统，能够：

• ✅ 匹配子序列（如 "mno" 匹配 "MB_YESNO"）
• ✅ 根据匹配质量打分
• ✅ 将匹配结果按打分排序，最好匹配排最前

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

1. 是否匹配单词的开头（比如 _, 大写字母后的开始）
2. 匹配字符是否靠得近
3. 字符连续匹配是否越多越好
4. 匹配位置是否越靠前越好

匹配例子

MB_YESNO  输入 m_no 就能匹配到
MB_YESNO 因为 m 开头 on 又匹配到了后面 YESNO 的内容

使用 m_yo 也能匹配到, 因为 m开头, m往下有个y, y往下有个o
MB_YESNO

m_no 只要文本是有 m , m 后面有个_, _后面有个n, n后面有个o, 这种文本都能匹配, 不需要连续出现, 只要后面有就行
MB_ICONQUESTION 所以  m_no 能匹配到
MB_YESNO 这个使用 m_no 也能能匹配到

m_wcg
WM_WINDOWPOSCHANGED
WM_WINDOWPOSCHANGING
WM_WININICHANGE

代码

#include <vector>
#include <algorithm>


/// <summary>
/// 模糊匹配分数, 并按得分排序, 传递要搜索的数量和查询的字符串, 返回得分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<std::pair<int, int>> 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[qi]) == towlower(target[ti]))
            {
                score += 10;    // 基础匹配分

                // 位置相关奖励
                if (ti == 0)
                {
                    if (qi == 0)
                    {
                        score += 50;  // 双首字母匹配
                    }
                    else
                    {
                        score += 30;  // 目标首字母匹配
                    }
                }
                else if (qi == 0)
                {
                    score += 20;  // 查询首字母出现在目标中
                }

                // 单词边界检测
                if (ti > 0 && (
                    target[ti - 1] == L'_' ||
                    target[ti - 1] == L' ' ||
                    target[ti - 1] == L'-' ||
                    (iswlower(target[ti - 1]) && iswupper(target[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<std::pair<int, int>> 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[0]);

    auto results = FuzzyMatchAndScore(count, L"m_no", [&candidates](int i)
    {
        return candidates[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;
}

输出结果:

长度匹配因素 = 查询文本长度 / 目标文本长度
匹配位置因素 = 1.0 – (目标文本查询位置 / 目标文本长度)
计算公式: (总分 * (0.5 + 0.5 * 长度匹配因素)) * (0.7 + 0.3 * 匹配位置因素)

m_no   MB_YESNO

m_no   MB_ICONQUESTION

m_no   MB_ABORTRETRYIGNORE

m_no   MESSAGEBOX_YESNO

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

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

总共匹配到 4 项：
        MB_YESNO(得分: 62)
        MB_ABORTRETRYIGNORE(得分: 47)
        MESSAGEBOX_YESNO(得分: 45)
        MB_ICONQUESTION(得分: 31)