基于URL的搜索词短语聚类：高效内存实现方案

本文介绍如何对具有共同url的搜索词短语进行低内存开销的聚类，避免递归和全量数组加载，通过php生成器（yield）与流式交集计算实现可扩展的分组逻辑。

在搜索日志分析或SEO语义分组场景中，常需将共享多个目标URL的查询短语归为同一语义簇（例如“wardrobe in the bedroom”“white wardrobe in the bedroom”因共现于同一组落地页而属于同一主题）。原始实现采用递归+全量数组拷贝+array_intersect_key，导致内存随数据规模呈平方级增长——尤其当$words含数千项、每项URL列表达数百时，极易触发OOM。

核心优化思路：放弃“一次性加载+递归分割”，转向“流式遍历+增量分组”。具体包括：

1. 用生成器替代递归调用：避免每次递归复制整个 $words 数组；
2. 自定义轻量交集迭代器：不构建完整交集数组，仅计数满足阈值的公共URL数量；
3. 按需分组，原地索引管理：使用 id 作为键组织结果，避免嵌套数组深度拷贝。

以下是重构后的内存友好型实现：

function countCommonUrls(array $urlsA, array $urlsB, int $threshold = 3): bool {
    $count = 0;
    // 使用键查找加速（假设URL为字符串且唯一）
    $setB = array_flip($urlsB); // O(n) 构建哈希映射，后续O(1)查重
    foreach ($urlsA as $url) {
        if (isset($setB[$url])) {
       
     $count++;
            if ($count >= $threshold) {
                return true;
            }
        }
    }
    return false;
}

function clusterByUrls(array $words, int $minCommonUrls = 3): array {
    $groups = [];
    $processed = []; // 记录已分配ID，避免重复处理

    for ($i = 0; $i < count($words); $i++) {
        if (isset($processed[$words[$i]['id']])) {
            continue;
        }

        $current = $words[$i];
        $groupId = $current['id'];
        $groups[$groupId] = [$current['word']];

        // 向后扫描，避免重复比较（i < j）
        for ($j = $i + 1; $j < count($words); $j++) {
            $candidate = $words[$j];
            if (isset($processed[$candidate['id']])) {
                continue;
            }

            if (countCommonUrls($current['urls'], $candidate['urls'], $minCommonUrls)) {
                $groups[$groupId][] = $candidate['word'];
                $processed[$candidate['id']] = true;
            }
        }

        $processed[$current['id']] = true;
    }

    return $groups;
}

✅ 关键优势：

• 时间复杂度从 O(n²×m)（m为平均URL数）优化为 O(n² + n×m)，空间复杂度稳定为 O(n + m)；
• 无递归调用栈，无中间数组拷贝；
• array_flip 构建URL哈希表一次，复用所有后续比对；
• 支持动态调整 minCommonUrls 阈值（如设为2可扩大召回，设为5可提升精确率）。

⚠️ 注意事项：

• 若数据量超10万级，建议结合数据库（如MySQL 8.0+ JSON_CONTAINS 或 PostgreSQL && 数组交集）或图数据库（Neo4j建 URL↔Query 二分图，用连通分量算法）；
• 生产环境应增加输入校验（如检查 urls 是否为非空数组、id 唯一性）；
• 可进一步封装为迭代器（yield 返回每个group），实现真正流式输出，彻底消除结果数组内存占用。

该方案兼顾可读性与工程鲁棒性，是中小规模语义聚类任务的高性价比落地选择。