在文本聚类、日志清洗、重复数据合并等预处理场景中，精确字符串去重无法满足需求，需要基于相似度阈值对模糊重复的字符串进行去重，将相似度高于阈值的字符串归为同一类，仅保留每类的代表样本。这种处理方式能有效减少后续聚类的噪声，提升整体处理效率。
核心实现思路
整个模糊去重流程分为三个核心步骤：首先计算所有字符串两两之间的相似度，然后基于相似度阈值筛选关联对，最后通过聚类逻辑将关联的字符串归为同一组，每组保留一个样本。其中相似度计算是核心环节，本文选择编辑距离作为相似度衡量标准，因为其实现简单，对短文本、拼写差异类的相似字符串识别效果较好。
编辑距离与相似度转换
编辑距离指的是将一个字符串转换为另一个字符串所需的最少插入、删除、替换操作次数。我们可以通过编辑距离计算两个字符串的相似度，公式为：相似度 = 1 - 编辑距离 / 两个字符串的最大长度。当相似度大于等于设定的阈值时，认为两个字符串属于模糊重复。
下面是实现编辑距离计算和相似度转换的C++代码：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
// 计算两个字符串的编辑距离
int calcEditDistance(const std::string& s1, const std::string& s2) {
int len1 = s1.length();
int len2 = s2.length();
// 创建二维dp数组，dp[i][j]表示s1前i个字符和s2前j个字符的编辑距离
std::vector<std::vector<int>> dp(len1 + 1, std::vector<int>(len2 + 1, 0));
// 初始化边界：空字符串到另一个字符串的编辑距离为另一个字符串的长度
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
// 填充dp数组
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = std::min({dp[i-1][j] + 1, // 删除s1当前字符
dp[i][j-1] + 1, // 插入s2当前字符到s1
dp[i-1][j-1] + 1}); // 替换s1当前字符为s2当前字符
}
}
}
return dp[len1][len2];
}
// 根据编辑距离计算相似度，返回0到1之间的值，值越大越相似
double calcSimilarity(const std::string& s1, const std::string& s2) {
if (s1.empty() && s2.empty()) {
return 1.0;
}
int editDist = calcEditDistance(s1, s2);
int maxLen = std::max(s1.length(), s2.length());
return 1.0 - (double)editDist / maxLen;
}
基于相似度阈值的聚类去重
得到字符串两两之间的相似度后，我们可以使用类似并查集的思路进行聚类：如果两个字符串的相似度大于等于阈值，就将它们归为同一类，最终每个类只保留第一个出现的字符串作为代表样本。
下面是完整的模糊去重实现代码：
// 并查集实现，用于合并相似的字符串分组
class UnionFind {
private:
std::vector<int> parent;
public:
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找根节点，带路径压缩
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 合并两个节点所在的分组
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
};
// 字符串模糊去重函数
// strs: 输入的字符串列表
// threshold: 相似度阈值，范围0到1，大于等于该值认为字符串相似
// 返回去重后的字符串列表
std::vector<std::string> fuzzyDeduplicate(const std::vector<std::string>& strs, double threshold) {
int n = strs.size();
if (n == 0) {
return {};
}
UnionFind uf(n);
// 两两计算相似度，满足阈值的合并分组
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double sim = calcSimilarity(strs[i], strs[j]);
if (sim >= threshold) {
uf.unite(i, j);
}
}
}
// 收集每个分组的代表字符串，保留第一个出现的
std::vector<std::string> result;
std::vector<bool> added(n, false);
for (int i = 0; i < n; i++) {
int root = uf.find(i);
if (!added[root]) {
result.push_back(strs[root]);
added[root] = true;
}
}
return result;
}
// 测试示例
int main() {
std::vector<std::string> testStrs = {
"苹果手机",
"苹果智能手机",
"华为手机",
"华为智能机",
"小米手机",
"苹果手机 pro"
};
double threshold = 0.7; // 相似度阈值设为0.7
std::vector<std::string> dedupResult = fuzzyDeduplicate(testStrs, threshold);
std::cout << "去重后的字符串列表：" << std::endl;
for (const auto& s : dedupResult) {
std::cout << s << std::endl;
}
return 0;
}
参数调整说明
相似度阈值的选择需要根据实际场景调整：如果场景对去重严格，希望仅保留高度相似的字符串，可以将阈值设为0.8到0.9；如果希望保留更多语义相近的字符串，可以将阈值设为0.6到0.7。另外，如果处理的字符串长度较长，也可以考虑替换相似度算法为余弦相似度，适配长文本的场景。
注意事项
- 上述实现的时间复杂度为O(n² * L)，其中n是字符串数量，L是字符串平均长度，适合处理万级以内的字符串数据，如果数据量更大可以考虑先通过哈希、前缀树等方式做粗筛，减少需要计算相似度的字符串对数量。
- 编辑距离对字符顺序敏感，如果场景中存在语序调换的相似字符串，需要调整相似度计算逻辑，比如先对字符串按字符排序再计算编辑距离，或者结合其他相似度算法。
- 聚类时选择每个组的第一个字符串作为代表，也可以根据需求调整为代表字符串长度最长、出现频率最高的样本。