怎样用C++实现文件内容模糊搜索 近似匹配算法实现

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

// 计算Levenshtein距离
int calculateLevenshteinDistance(const std::string& s1, const std::string& s2) {
    const int len1 = s1.length();
    const int len2 = s2.length();

    // 如果其中一个字符串为空，距离就是另一个字符串的长度
    if (len1 == 0) return len2;
    if (len2 == 0) return len1;

    // dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符的编辑距离
    std::vector<std::vector<int>> dp(len1 + 1, std::vector<int>(len2 + 1));

    // 初始化边界条件
    for (int i = 0; i <= len1; ++i) {
        dp[i][0] = i; // s1 前 i 个字符与空字符串的距离
    }
    for (int j = 0; j <= len2; ++j) {
        dp[0][j] = j; // s2 前 j 个字符与空字符串的距离
    }

    // 填充 dp 表
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1; // 如果字符相同，替换成本为0，否则为1
            dp[i][j] = std::min({dp[i - 1][j] + 1,        // 删除 s1[i-1]
                                 dp[i][j - 1] + 1,        // 插入 s2[j-1]
                                 dp[i - 1][j - 1] + cost}); // 替换 s1[i-1] 为 s2[j-1]
        }
    }
    return dp[len1][len2];
}

// 模糊搜索函数
void fuzzySearchFile(const std::string& filename, const std::string& query, int threshold) {
    std::ifstream file(filename);
    if (!file.is_open()) {
        std::cerr << "错误：无法打开文件 " << filename << std::endl;
        return;
    }

    std::string line;
    int lineNumber = 0;
    // 为了更好的匹配，通常将查询字符串转为小写或统一大小写
    std::string lowerQuery = query;
    std::transform(lowerQuery.begin(), lowerQuery.end(), lowerQuery.begin(), ::tolower);

    while (std::getline(file, line)) {
        lineNumber++;
        // 同样，将当前行内容转为小写进行比较
        std::string lowerLine = line;
        std::transform(lowerLine.begin(), lowerLine.end(), lowerLine.begin(), ::tolower);

        // 简单的包含检查，如果行太短，可能没必要计算距离
        if (lowerLine.length() < lowerQuery.length() - threshold) {
             continue; // 优化：如果行比查询字符串短太多，直接跳过
        }

        // 实际应用中，你可能需要对行进行分词，然后对每个词进行模糊匹配
        // 这里为了简化，我们直接用子串匹配或者全行匹配
        // 更好的做法是，对行中的每个“单词”或“短语”进行模糊匹配
        // 但为了示例简单，我们假设是查找行中是否存在与query模糊匹配的片段

        // 最简单粗暴的，直接计算整行和查询的距离
        // 实际场景中，这可能不是你想要的，因为一行可能很长
        // 更好的方式是，遍历行的所有可能子串，与query进行匹配

        // 为了演示，我们先尝试一个简单的子串模糊匹配逻辑
        // 遍历行中所有长度接近query的子串
        bool foundInLine = false;
        for (size_t i = 0; i <= lowerLine.length(); ++i) {
            // 考虑子串长度在 query.length() +/- threshold 范围内
            for (size_t j = 0; j <= lowerLine.length() - i; ++j) {
                std::string sub = lowerLine.substr(i, j);
                if (sub.empty()) continue; // 避免空字符串

                // 优化：如果子串长度和查询长度差异过大，直接跳过
                if (std::abs(static_cast<int>(sub.length()) - static_cast<int>(lowerQuery.length())) > threshold) {
                    continue;
                }

                int dist = calculateLevenshteinDistance(sub, lowerQuery);
                if (dist <= threshold) {
                    std::cout << "在文件 '" << filename << "' 的第 " << lineNumber << " 行找到匹配: "
                              << line << " (与 '" << query << "' 的距离为 " << dist << ")" << std::endl;
                    foundInLine = true;
                    break; // 找到一个匹配即可，不再检查当前行的其他子串
                }
            }
            if (foundInLine) break; // 当前行已找到，跳到下一行
        }
    }
    file.close();
}

// int main() {
//     // 创建一个测试文件
//     std::ofstream outFile("test_document.txt");
//     outFile << "This is a test document.\n";
//     outFile << "Apples are red.\n";
//     outFile << "I love appple pie.\n"; // 错别字
//     outFile << "Orange and bananna.\n"; // 错别字
//     outFile << "Banana splits are great.\n";
//     outFile << "Aple and pear.\n"; // 错别字
//     outFile.close();

//     std::cout << "--- 搜索 'apple' ---" << std::endl;
//     fuzzySearchFile("test_document.txt", "apple", 1); // 允许1个编辑距离

//     std::cout << "\n--- 搜索 'banana' ---" << std::endl;
//     fuzzySearchFile("test_document.txt", "banana", 1); // 允许1个编辑距离

//     return 0;
// }