利用 @RichardScriven 的见解,
adist
可以用于 计算“近似字符串距离”,我制作了一个更全面的函数。请注意,
"trafos"
代表用于确定两个字符串之间“距离”的“转换”(示例在底部)。
编辑 此答案可能会产生错误/意外结果;如 @wdkrnls 所指出的:
引用:
我对 "apple" 和 "big apple bagels" 运行了您的函数,它返回了 "appl"。我本应该期望得到 "apple"。
请参见下面的解释错误的结果。我们从一个函数开始,以获取列表中的
longest_string
:
longest_string <- function(s){return(s[which.max(nchar(s))])}
然后,我们可以使用@RichardSriven的工作和stringi库:
library(stringi)
lcsbstr <- function(a,b) {
sbstr_locations<- stri_locate_all_regex(drop(attr(adist(a, b, counts=TRUE), "trafos")), "M+")[[1]]
cmn_sbstr<-stri_sub(longest_string(c(a,b)), sbstr_locations)
longest_cmn_sbstr <- longest_string(cmn_sbstr)
return(longest_cmn_sbstr)
}
或者我们可以重写代码,避免使用任何外部库(仍然使用R的本地adist
函数):
lcsbstr_no_lib <- function(a,b) {
matches <- gregexpr("M+", drop(attr(adist(a, b, counts=TRUE), "trafos")))[[1]];
lengths<- attr(matches, 'match.length')
which_longest <- which.max(lengths)
index_longest <- matches[which_longest]
length_longest <- lengths[which_longest]
longest_cmn_sbstr <- substring(longest_string(c(a,b)), index_longest , index_longest + length_longest - 1)
return(longest_cmn_sbstr )
}
以上两个函数仅将'hello '
识别为最长公共子串,而不是'hello r'
(无论哪个参数更长):
identical('hello',
lcsbstr_no_lib('hello', 'hello there'),
lcsbstr( 'hello', 'hello there'),
lcsbstr_no_lib('hello there', 'hello'),
lcsbstr( 'hello there', 'hello'))
最近编辑
请注意这个结果有一些奇怪的行为:
lcsbstr('hello world', 'hello')
#[1] 'hell'
我原本期待的是
'hello'
,但由于转换实际上通过删除将w
orld中的“o”移动到hell
o中成为“o” - 只有
hell部分被认为是符合
M
的匹配。
drop(attr(adist('hello world', 'hello', counts=TRUE), "trafos"))
使用
Levenstein工具 可以观察到这种行为,它提供了两个可能的解决方案,相当于这两个转换。
#[1] "MMMMDDDMDDD"
#[1] "MMMMMDDDDDD"
我不知道我们是否可以配置 adist
以偏爱一种解决方案?(这些转换具有相同的“权重”--相同数量的“M”和“D” - 不知道如何优先考虑具有更多连续 M
的转换)
最后,别忘了 adist 允许你传递 ignore.case = TRUE
(默认为 FALSE
)
adist
的 "trafos"
属性是关键;它是从一个字符串到另一个字符串所需的 "transformations":
变换序列作为返回值的 "trafos"
属性返回,表示为字符串,其中包含元素 M
、I
、D
和 S
,分别表示匹配、插入、删除和替换。
LCS
函数并不是找到最长公共子串,而是找到最长公共子序列 - 因此你得到的结果就是这样。这就是子序列的定义。这些问题相关但解决方案相当不同,最长公共子序列问题是计算机科学中更经典的问题,因此更常被实现。 - Konrad Rudolph