如何在MySQL/MariaDB中分组仅差1位字符的7位车牌

核心需求 #

• 所有车牌为固定7位字符，需将**满足与组内至少一个车牌仅存在1位字符差异（含连锁相似，如ABC1234→ABG1234→ABO1234）**的车牌归为同一组
• 分组需限定在同一15分钟时间窗口内（已通过timekey实现）
• 分组后需在单独列中拼接组内所有相关车牌

现有基础逻辑 #

已实现同一时间窗内相同车牌的分组，查询语句如下：

select plate, floor(unix_timestamp(date)/(15 * 60)) as timekey 
from table 
group by plate, timekey 
order by date desc

解决方案思路 #

直接使用Levenshtein距离全量计算会导致大数据场景下性能爆炸，因此采用掩码匹配+连通分量合并的思路：

1. 对每个车牌生成7个"掩码键"：将车牌的每一位依次替换为通配符（如下划线），仅差1位的车牌必然共享至少一个掩码键
2. 基于时间窗+掩码键分组，得到初步关联的车牌集合
3. 合并重叠的集合（连通分量），得到最终的相似车牌组

具体实现（以Spark/Hive SQL为例） #

WITH dedup_plates AS (
    -- 先去重同一时间窗内的重复车牌，减少数据量
    SELECT DISTINCT 
        plate,
        floor(unix_timestamp(date)/(15*60)) AS timekey
    FROM your_table
),
plate_masks AS (
    -- 为每个车牌生成7个掩码键
    SELECT 
        plate,
        timekey,
        concat('_', substr(plate,2,6)) AS mask1,
        concat(substr(plate,1,1), '_', substr(plate,3,5)) AS mask2,
        concat(substr(plate,1,2), '_', substr(plate,4,4)) AS mask3,
        concat(substr(plate,1,3), '_', substr(plate,5,3)) AS mask4,
        concat(substr(plate,1,4), '_', substr(plate,6,2)) AS mask5,
        concat(substr(plate,1,5), '_', substr(plate,7,1)) AS mask6,
        concat(substr(plate,1,6), '_') AS mask7
    FROM dedup_plates
),
unpivoted_masks AS (
    -- 将多列掩码转为行，方便分组
    SELECT plate, timekey, mask1 AS mask FROM plate_masks
    UNION ALL
    SELECT plate, timekey, mask2 AS mask FROM plate_masks
    UNION ALL
    SELECT plate, timekey, mask3 AS mask FROM plate_masks
    UNION ALL
    SELECT plate, timekey, mask4 AS mask FROM plate_masks
    UNION ALL
    SELECT plate, timekey, mask5 AS mask FROM plate_masks
    UNION ALL
    SELECT plate, timekey, mask6 AS mask FROM plate_masks
    UNION ALL
    SELECT plate, timekey, mask7 AS mask FROM plate_masks
),
mask_based_groups AS (
    -- 按时间窗和掩码分组，得到初步关联的车牌集合
    SELECT 
        timekey,
        mask,
        collect_set(plate) AS plate_list
    FROM unpivoted_masks
    GROUP BY timekey, mask
),
connected_components AS (
    -- 递归合并重叠的组（连通分量）
    SELECT 
        timekey,
        plate_list AS group_plates,
        plate_list AS current_plates
    FROM mask_based_groups
    UNION ALL
    SELECT 
        c.timekey,
        array_distinct(concat(c.group_plates, m.plate_list)) AS group_plates,
        m.plate_list AS current_plates
    FROM connected_components c
    JOIN mask_based_groups m 
        ON c.timekey = m.timekey
        AND size(array_intersect(c.current_plates, m.plate_list)) > 0
        AND size(array_except(m.plate_list, c.group_plates)) > 0
),
final_groups AS (
    -- 去重最终分组，确保同一组仅保留一条记录
    SELECT 
        timekey,
        group_plates,
        concat_ws(',', sort_array(group_plates)) AS group_id
    FROM connected_components
    GROUP BY timekey, group_id, group_plates
)
-- 关联原始表，输出每个车牌对应的分组及组内所有车牌
SELECT 
    t.plate,
    t.timekey,
    f.group_id,
    concat_ws(';', f.group_plates) AS related_plates
FROM your_table t
JOIN final_groups f 
    ON t.timekey = f.timekey
    AND array_contains(f.group_plates, t.plate)
ORDER BY t.date DESC;

性能优化建议 #

• 前置去重：先对同一timekey下的重复车牌去重，大幅减少后续处理的数据量
• UDF简化掩码生成：可以编写自定义UDF一次性生成所有掩码，替代重复的substr拼接逻辑
• GraphFrames替代递归CTE：如果Spark版本支持，使用GraphFrames库构建车牌节点与掩码边，调用连通组件算法（Connected Components），性能更适合超大规模数据集

示例输出 #

假设同一时间窗内有车牌AAU1234、AAV1234、AAW1234，最终输出中这三个车牌的related_plates列都会显示为AAU1234;AAV1234;AAW1234

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