text - 删除属于其他字符串的子字符串

Question

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

例如，给定(“大车”、“大车”、“在大车”、“买大车”、“买大车”、“买大房子”)那么结果应该be ("at the big car", "buy a big car", "buy a big house");对输出进行排序并不重要。

因为我的集合有 100,000 个字符串，所以无法对每个字符串与所有其他字符串进行强力测试。

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

或者，任何人都可以补充我的一些想法:

• 如果我先对字符串进行排序，那么应该更容易在字符串的开头(以及使用反向排序的字符串的结尾)挑选子字符串？其他地方还需要处理子串。

• 使用树结构？像下面这样的东西？ (i) 向每个字符串添加 START 和 END 标记； (ii) 树中的第一个节点是 START； (iii) string "big car"--> 新分支 START-big-car-END，但是当添加 "the big car"时，分支变为 START-the-big-car-END； (iv) 一旦插入所有字符串，然后读取从 START 到 END 的所有路径。鉴于可能有大量单词(至少 1000 个)，不确定这一点。此外，同一个词在一个句子中出现多次的问题。

• 我能否在暴力破解中添加某种内存，以便可以首先将处理的下一个字符串与一组先前删除的字符串进行比较？

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)

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

注意:我按长度 (DESC) 对 input_df 进行排序以获得最佳性能