使用R删除字符串中的重复元素

Question

我计划从字符串中删除重复的元素(每个元素包含两个或多个字符).例如,从"aaa"我期待"aaa",从"aaaa"我期待"aa",从"abababcdcd"我看到"abcd",从"cdababcdcd"我期待"cdabcd".

我试过了gsub("(.{2,})\\1+","\\1",str).它适用于案例1-3,但在案例4中失败.如何解决这个问题？

Answer 1

解决方案

解决方案是依赖 PCRE 或 ICU 正则表达式引擎，而不是 TRE。

将基本 Rgsub与perl=TRUE（它使用PCRE 正则表达式引擎）和"(?s)(.{2,})\\1+"模式一起使用，或使用具有相同模式的stringr::str_replace_all()（它使用ICU 正则表达式引擎）：

> x <- "cdababcdcd"
> gsub("(?s)(.{2,})\\1+", "\\1", x, perl=TRUE)
[1] "cdabcd"
> library(stringr)
> str_replace_all(x, "(?s)(.{2,})\\1+", "\\1")
[1] "cdabcd"

该(?s)标志是.匹配任何字符（包括换行符）所必需的（在 TRE 正则表达式中，.默认情况下匹配所有字符）。

细节

TRE 正则表达式不擅长处理主要与回溯相关的“病态”情况，回溯直接涉及量词（我将某些部分加粗）：

TRE中使用的匹配算法在正在搜索的文本长度中使用线性最坏情况时间，在所使用的正则表达式长度中使用二次最坏情况时间。换句话说，该算法的时间复杂度为O(M2N)，其中M是正则表达式的长度，N是文本的长度。所使用的空间也是正则表达式长度的二次方，但不取决于搜索的字符串。这种二次行为仅发生在病理情况下，这在实践中可能非常罕见。

可预测的匹配速度
由于 TRE 中使用的匹配算法，任何调用所消耗的最大时间regexec()始终与搜索字符串的长度成正比。有一个例外：如果使用反向引用，则匹配所需的时间可能会随着字符串的长度呈指数增长。这是因为匹配反向引用是一个 NP 完全问题，并且在最坏的情况下几乎肯定需要指数时间来匹配。

在这些情况下，当 TRE 无法计算匹配字符串的所有可能性时，它不会返回任何匹配项，而是按原样返回字符串。因此，通话中没有任何变化gsub。