c++怎么实现一个简单的模糊搜索算法_C++中实现模糊匹配与编辑距离算法-C++-PHP中文网

c++怎么实现一个简单的模糊搜索算法_C++中实现模糊匹配与编辑距离算法

冰火之心

发布： 2025-11-20 19:26:02

原创

372人浏览过

编辑距离指将一个字符串转为另一个的最少单字符操作次数，常用动态规划实现，通过设定最大允许距离实现模糊搜索。

c++怎么实现一个简单的模糊搜索算法_c++中实现模糊匹配与编辑距离算法

在C++中实现模糊搜索，核心思路是通过计算两个字符串之间的“距离”来衡量它们的相似度。最常用的方法是编辑距离（Levenshtein Distance）算法。它表示将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除、替换）。

什么是编辑距离？

编辑距离可以用来判断两个字符串的相似程度。比如：

"kitten" → "sitting" 的编辑距离是 3
"hello" → "helli" 的编辑距离是 1

距离越小，字符串越相似。我们可以设定一个阈值，比如最大允许距离为2，超过就不算匹配，从而实现模糊搜索。

用动态规划实现编辑距离

使用二维数组 dp[i][j] 表示 str1 前 i 个字符到 str2 前 j 个字符的最小编辑距离。

立即学习“C++免费学习笔记（深入）”；

PhotoG

PhotoG是全球首个内容营销端对端智能体

121

查看详情

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int levenshteinDistance(const std::string& a, const std::string& b) {
    int m = a.size();
    int n = b.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));

    // 初始化边界：从空串变成目标串
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    // 填表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1]; // 相同字符，无需操作
            } else {
                dp[i][j] = 1 + std::min({
                    dp[i-1][j],   // 删除
                    dp[i][j-1],   // 插入
                    dp[i-1][j-1]  // 替换
                });
            }
        }
    }
    return dp[m][n];
}

登录后复制

实现简单的模糊搜索功能

有了编辑距离函数后，就可以对一组候选字符串进行匹配，找出与目标词足够接近的结果。

void fuzzySearch(const std::vector<std::string>& dictionary,
                 const std::string& query,
                 int maxDistance = 2) {
    std::cout << "Searching for: " << query << "\n";
    std::cout << "Results (distance <= " << maxDistance << "):\n";

    for (const auto& word : dictionary) {
        int dist = levenshteinDistance(query, word);
        if (dist <= maxDistance) {
            std::cout << "  \"" << word << "\" (distance: " << dist << ")\n";
        }
    }
}

登录后复制

测试示例：

int main() {
    std::vector<std::string> words = {
        "apple", "apply", "apples", "banana", "orange",
        "application", "applet", "hello", "help"
    };

    fuzzySearch(words, "appl", 1);   // 应该匹配 apple, apply, applet 等
    return 0;
}

登录后复制