2

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

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

因为我的套装有 100,000 根琴弦，所以对每根琴弦进行暴力测试不是一种选择。

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

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

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

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

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

4

1 回答 1

0

我正在使用 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 进行排序以获得最佳性能

于 2019-05-25T05:28:46.213 回答