如何在Julia中高效使用StringDistances的findall()匹配选区名称

问题背景 #

有一个包含近9000条30年历史记录的DataFrame（comb），其中WD22NM字段存储英国选区名称。由于选区更名、格式差异（如St/St.、and/&、Pembroke West/Pembroke: West），需要用StringDistances查找近似匹配，但当前遍历比对的方式速度极慢，处理9000条记录需数分钟。

原始代码：

for (i, s) in enumerate(comb.WD22NM)
    MatchIndex = findall(lowercase(s), lowercase.(comb[i:length(comb.WD22NM), :WD22NM]), TokenMax(Levenshtein()); min_score=0.95)
    if length(MatchIndex) > 1
        MatchIndex .+= (i-1)
        deleteat!(MatchIndex, (j for j in eachindex(MatchIndex) if MatchIndex[j] == i))
        @printf(io_buf,"%5.4i %-50.48s %-75s \n", i, s, comb.WD22NM[MatchIndex])
    end
end

提速优化建议 #

1. 预计算标准化名称，消除重复转换与格式差异 #

先对所有选区名称做标准化处理，统一格式，将大部分格式差异直接归一化，减少后续近似匹配的工作量：

function standardize_name(s::AbstractString)
    s_clean = lowercase(s)
    # 统一缩写格式：St. → St
    s_clean = replace(s_clean, r"st\." => "st")
    # 统一连词：& → and
    s_clean = replace(s_clean, "&" => "and")
    # 统一分隔符：移除冒号后多余空格
    s_clean = replace(s_clean, r":\s+" => " ")
    # 合并连续空格
    s_clean = replace(s_clean, r"\s+" => " ")
    return strip(s_clean)
end

# 预计算所有标准化后的名称，避免循环内重复转换
standardized_names = standardize_name.(comb.WD22NM)

标准化后，很多原本需要近似匹配的条目会变成完全匹配，可直接用groupby分组，仅对剩余不匹配的条目做近似比对。

2. 用BKTree替换全量遍历，降低时间复杂度 #

原始代码为O(n²)的全量比对，9000条数据会产生8100万次比对。改用BKTree（专为近似字符串匹配设计的树结构），可将时间复杂度降至O(n log n)：

using StringDistances, BKTree

# 基于标准化名称构建BKTree，使用TokenMax(Levenshtein)距离算法
min_score = 0.95
distance_threshold = 1 - min_score  # 将分数阈值转换为距离阈值（TokenMax分数范围0-1，分数越高越相似）
tree = BKTree(TokenMax(Levenshtein()), standardized_names)

# 遍历每个条目，查找符合条件的近似匹配
for (i, s) in enumerate(standardized_names)
    # 查找所有距离≤阈值的条目，排除自身
    matches = find(tree, s, distance_threshold)
    match_indices = [idx for (idx, _) in matches if idx > i]
    
    if !isempty(match_indices)
        @printf(io_buf,"%5.4i %-50.48s %-75s \n", i, comb.WD22NM[i], comb.WD22NM[match_indices])
    end
end

BKTree会根据字符串距离跳过不可能匹配的分支，大幅减少比对次数。

3. 优化循环内的数组操作，减少中间变量 #

原始代码中每次循环都会生成子数组并调整索引，带来额外开销。优化后直接基于全量数组筛选j > i的条件，避免数组切片与索引调整：

• 预计算所有标准化/小写名称，避免循环内重复转换生成中间向量
• 查找匹配时直接筛选idx > i，无需后续的索引偏移与deleteat!操作

4. 优先处理完全匹配，减少近似比对范围 #

先对标准化后的名称做分组，将完全匹配的条目直接归类，仅对分组后的"唯一候选"做近似匹配：

using DataFrames

# 添加标准化名称列到DataFrame
comb[!, :standardized] = standardized_names

# 按标准化名称分组，获取完全匹配的条目
grouped = groupby(comb, :standardized)
for g in grouped
    if nrow(g) > 1
        # 输出完全匹配的条目
        first_idx = findfirst(==(g[1, :standardized]), standardized_names)
        @printf(io_buf,"%5.4i %-50.48s %-75s \n", first_idx, g[1, :WD22NM], g[2:end, :WD22NM])
    end
end

# 提取唯一的标准化名称，仅对这些做近似匹配
unique_names = unique(standardized_names)
unique_indices = indexin(unique_names, standardized_names)

# 用BKTree处理唯一名称的近似匹配（代码类似步骤2，仅遍历unique_indices）

这一步可将需要近似比对的条目数量从9000降至数百甚至更少，进一步提升速度。

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