如何计算两个字符向量的Damerau-Levenshtein距离，将每个元素视作单个字符

核心实现思路 #

原生stringdist的method = "dl"计算规则，是把输入的字符串按单个字符拆成序列后，计算插入、删除、替换、相邻字符转置四种操作的最小次数。要让向量的每个元素等价为一个“单个字符”，只需要把每个向量元素映射成一个长度严格为1、且不会和原始内容冲突的独立标识，把整个向量拼接成符合单字符序列规则的虚拟字符串，再走原生计算流程即可。

操作流程 #

• 提取两个向量中的所有非重复元素，为每个元素分配专属的单字符替换值。选用Unicode私人使用区的字符做替换最稳妥，这类字符不会和普通英文单词的内容重叠，不会出现拆分歧义
• 按照映射关系把原始向量的每个元素替换为对应单字符，将替换后的字符按原顺序拼接成完整字符串
• 对拼接得到的两个字符串调用stringdist的DL方法计算，得到的结果就是元素粒度的Damerau-Levenshtein距离

可复现代码 #

library(stringdist)

# 定义原始待计算向量
A <- c("apple", "banana", "citrus")
B <- c("apple", "citrus", "banana")

# 生成元素到单字符的映射
unique_elems <- unique(c(A, B))
# 生成对应数量的Unicode私人使用区单字符，与常规文本无冲突
single_char_map <- intToUtf8(0xe000 + seq_along(unique_elems) - 1, multiple = TRUE)
elem_mapping <- setNames(single_char_map, unique_elems)

# 将向量转换为等长的单字符序列虚拟字符串
A_virtual <- paste0(elem_mapping[A], collapse = "")
B_virtual <- paste0(elem_mapping[B], collapse = "")

# 计算元素粒度的DL距离
stringdist(A_virtual, B_virtual, method = "dl")
# 输出结果为1，与预期一致

关键注意点 #

• 映射用的替换字符必须严格为单字符，不能使用多字符的字符串做替换，否则会破坏计算粒度和单字符规则的一致性
• 替换字符不能和原始元素中包含的字符重复，否则会导致字符串拆分时把替换标识拆成多个单元，最终计算结果出现偏差

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