编辑距离指将一个字符串转为另一个的最少单字符操作次数，常用动态规划实现，通过设定最大允许距离实现模糊搜索。
在C++中实现模糊搜索，核心思路是通过计算两个字符串之间的“距离”来衡量它们的相似度。最常用的方法是编辑距离（Levenshtein Distance）算法。它表示将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除、替换）。
什么是编辑距离？
编辑距离可以用来判断两个字符串的相似程度。比如：
“kitten” → “sitting” 的编辑距离是 3 “hello” → “helli” 的编辑距离是 1
距离越小，字符串越相似。我们可以设定一个阈值，比如最大允许距离为2，超过就不算匹配，从而实现模糊搜索。
用动态规划实现编辑距离
使用二维数组 dp[i][j] 表示 str1 前 i 个字符到 str2 前 j 个字符的最小编辑距离。
立即学习“C++免费学习笔记（深入）”；
#include #include #include #include int levenshteinDistance(const std::string& a, const std::string& b) { int m = a.size(); int n = b.size(); std::vector<std::vector> dp(m + 1, std::vector(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& 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 words = { "apple", "apply", "apples", "banana", "orange", "application", "applet", "hello", "help" }; fuzzySearch(words, "appl", 1); // 应该匹配 apple, apply, applet 等 return 0;}
优化和扩展建议
这个基础版本适合学习和小型应用。实际使用中可考虑以下改进：
空间优化：由于 dp 只依赖前一行，可用两个一维数组代替二维数组，降低内存开销。 提前终止：如果某行最小值已超过阈值，可提前退出。 忽略大小写：比较前统一转为小写。 支持通配符或子串匹配：结合 strstr 或正则表达式增强灵活性。
基本上就这些。编辑距离是模糊匹配的基础，理解它之后可以进一步尝试 Damerau-Levenshtein（支持交换操作）、Soundex（按发音匹配）等更复杂的算法。
以上就是c++++怎么实现一个简单的模糊搜索算法_C++中实现模糊匹配与编辑距离算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485146.html
微信扫一扫 
支付宝扫一扫 
