删除其中一个字符串是另一个字符串的子串

Question

给定一组字符串，我需要删除集合中任何一个子字符串的字符串。子字符串可以出现在任何位置。我预计至少50%的字符串将是其他字符串的子字符串。我的字符串是来自大型自然语言语料库的n-gram。

例如，给定（“the big car”，“big car”，“at the big car”，“buy a big car”，“buy a big”，“buy a big house”），则结果应为（“at the big car”，“buy a big car”，“buy a big house”）; 输出的顺序不重要。

因为我的集合有成千上万个字符串，所以无法对每个字符串进行暴力测试。

有人知道这个问题的标准解决方案吗？

或者，有没有人能补充一些我已经想到的想法：

- 如果我先对字符串进行排序，则更容易挑选字符串开头（和反向排序的字符串结尾）的子字符串？仍需要处理其他地方的子字符串。 - 使用树形结构？类似于以下内容：（i）为每个字符串添加START和END标记；（ii）树中的第一个节点是START；（iii）字符串“big car”->新分支START-big-car-END，但是当添加“the big car”时，分支变为START-the-big-car-END；（iv）一旦插入所有字符串，则从START到END读取所有路径。鉴于可能存在大量单词（至少1000个），我不确定这一点。同一个单词在句子中出现多次的问题。 - 我能否在暴力测试中添加某种记忆，以便可以首先将下一个要处理的字符串与先前删除的字符串集进行比较？

- user1651661

---

我猜你想要一个算法？如果你想要一个在特定编程语言如C#中移除子字符串的示例代码，我认为你可以使用Lambda表达式，它的性能不会很慢。 - cat916

Aho-Corasick算法可能是一个不错的选择。 - Fathi Alwosaibi

Answer 1

我正在使用R中的lapply函数来实现这个目标：

calc <- function(e, df){
    i <- 1
    while (!(grepl(e[[1]],df[i,1], fixed=TRUE, ignore.case = TRUE)) & i <=nrow(df)){

        i <- i + 1

    }       
    return (df[i,])
}


    reduced  <- lapply(input_df[,1], calc, df=input_df)
    output_df <- do.call(rbind,reduced)

在大型数据集上表现良好，但在非常大的数据集上表现不佳。

注意：我按长度（降序）对input_df进行排序以获得最佳性能。

- Saqib Ali