基于URL的搜索查询聚类：内存优化方案及现成类库咨询

嘿，我明白你现在遇到的问题了——基于共享URL对搜索查询做聚类，核心是把有至少3个共同URL的查询归为一组，但原来的递归遍历算法内存占用太高，想找更高效的实现方式对吧？先梳理下你的场景和现有代码的问题，再给你推荐最优的解决方案。

首先看你给出的示例数据结构：

$words = [
    [
        "word" => "wardrobe in the bedroom",
        "id" => 1,
        "urls" => ["url_1", "url_2", "url_3", "url_4", "url_5"]
    ],
    [
        "word" => "wardrobe in the living room",
        "id" => 2,
        "urls" => ["url_1", "url_2", "url_3", "url_4", "url_5"]
    ],
    [
        "word" => "white wardrobe in the bedroom",
        "id" => 3,
        "urls" => ["url_1", "url_2", "url_3", "url_4", "url_5"]
    ]
    // ... 更多查询元素
];

你当前的递归实现确实存在内存和性能问题：

function cluster($words, $group = array()) {
    $first_elem = array_shift($words);
    $first_group = $first_elem['id'];
    $array_urls = $first_elem['urls'];
    foreach ($words as $i=>$data) {
        $check = array_intersect_key($array_urls, $data['urls']);
        if(count($check) >= 3) {
            $group[$first_group][$i] = $data['word'];
            unset($words[$i]);
        }
    }
    if(!empty($words)) return cluster($words, $group);
    return $group;
}

现有代码的核心问题 #

• 递归栈溢出风险：每次递归都会创建新的函数栈帧，当查询数量很大时，栈内存会快速累积，甚至触发PHP的栈溢出限制
• 数组重构开销：array_shift和unset操作会让PHP重新分配数组内存，频繁的数组修改会大幅增加内存占用
• 低效的双重遍历：外层递归+内层foreach的逻辑是O(n²)的时间复杂度，数据量越大，计算和内存消耗越夸张

优化方案：使用并查集（Union-Find）数据结构 #

并查集是专门处理连通分量分组问题的高效数据结构，它的时间复杂度接近O(α(n))（α是阿克曼函数的反函数，增长极慢，几乎可以看作常数），内存开销远低于递归遍历。

第一步：实现轻量并查集类

class UnionFind {
    private $parent = [];
    private $rank = [];

    public function __construct($elementIds) {
        foreach ($elementIds as $id) {
            // 每个元素初始父节点是自己
            $this->parent[$id] = $id;
            $this->rank[$id] = 0;
        }
    }

    // 查找元素的根节点（带路径压缩，减少后续查找开销）
    public function find($x) {
        if ($this->parent[$x] !== $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    // 合并两个元素所在的集合（按秩合并，保持树的平衡）
    public function union($x, $y) {
        $xRoot = $this->find($x);
        $yRoot = $this->find($y);

        if ($xRoot === $yRoot) {
            return; // 已经在同一组，无需合并
        }

        // 把秩小的树合并到秩大的树下，保持平衡
        if ($this->rank[$xRoot] < $this->rank[$yRoot]) {
            $this->parent[$xRoot] = $yRoot;
        } else {
            $this->parent[$yRoot] = $xRoot;
            if ($this->rank[$xRoot] === $this->rank[$yRoot]) {
                $this->rank[$xRoot]++;
            }
        }
    }

    // 获取所有分组（键是根节点ID，值是该组的所有元素ID）
    public function getGroups() {
        $groups = [];
        foreach ($this->parent as $id => $root) {
            $rootId = $this->find($id);
            $groups[$rootId][] = $id;
        }
        return $groups;
    }
}

第二步：编写聚类逻辑

function clusterQueries($words) {
    // 提前建立ID到查询的映射，避免后续重复遍历查找
    $idToQuery = [];
    $allIds = [];
    foreach ($words as $query) {
        $id = $query['id'];
        $idToQuery[$id] = $query;
        $allIds[] = $id;
    }

    // 初始化并查集
    $uf = new UnionFind($allIds);

    // 提前把每个查询的URL转为关联数组，方便快速计算交集
    $queryUrlMaps = [];
    foreach ($words as $query) {
        $queryUrlMaps[$query['id']] = array_flip($query['urls']);
    }

    // 遍历所有查询对，检查共同URL数量，满足条件则合并分组
    $wordCount = count($words);
    for ($i = 0; $i < $wordCount; $i++) {
        $queryA = $words[$i];
        $idA = $queryA['id'];
        $urlsA = $queryUrlMaps[$idA];

        for ($j = $i + 1; $j < $wordCount; $j++) {
            $queryB = $words[$j];
            $idB = $queryB['id'];

            // 已经在同一组的跳过，避免重复计算
            if ($uf->find($idA) === $uf->find($idB)) {
                continue;
            }

            $urlsB = $queryUrlMaps[$idB];
            // 计算共同URL数量
            $commonCount = count(array_intersect_key($urlsA, $urlsB));
            if ($commonCount >= 3) {
                $uf->union($idA, $idB);
            }
        }
    }

    // 转换为最终的分组结果（包含查询文本）
    $rawGroups = $uf->getGroups();
    $result = [];
    foreach ($rawGroups as $rootId => $ids) {
        $result[$rootId] = array_map(function($id) use ($idToQuery) {
            return $idToQuery[$id]['word'];
        }, $ids);
    }

    return $result;
}

关于现成类库 #

PHP生态中没有专门针对这类URL聚类的专属类库，但并查集是通用的数据结构，你可以找到一些第三方PHP数据结构包包含它的实现。不过我更推荐自己实现，因为代码量很小，轻量且完全可控，不需要引入额外依赖。

内容的提问来源于stack exchange，提问作者gooex