从语料库中找到匹配的常用词或短语的高效算法

Question

我正在尝试找到一种查找常用短语的有效方法。我想我可以用一个例子更好地解释。

输入：将每一行视为一个句子

B
B C
A B C B
D E
F D E

输出：

B
D E

第 2 行和第 3 行被删除，因为 B（第 1 行）是它们共有的。第 5 行被取消，因为第 4 行很常见。

希望我已经解释清楚了！

我可以通过匹配运行 O(n^2)。欣赏任何更好的东西。

更新：请考虑顺序（例如D E应该匹配句子F D E。E D不应该。）

Answer 1

我能想到的最快的方法是：

public static void main(String[] args) throws Exception {

    List<String> toOutput = new ArrayList<String>();
    BufferedReader br = new BufferedReader(new FileReader("input.txt"));
    String line;
    while ((line = br.readLine()) != null) {
        boolean add = true;

        for (int i = 0; i < toOutput.size(); i++) {
            if (toOutput.get(i).contains(line)) {
                toOutput.remove(i);
            } else if (line.contains(toOutput.get(i))) {
                add = false;
                break;
            }
        }

        if (add) {
            toOutput.add(line);
        }
    }
    br.close();

    for (String s : toOutput) {
        System.out.println(s);
    }
}

input.txt:

B
B C
A B C B
F D E
D E

输出：

B
D E

验证当前句子是否包含我们当前发现的唯一字符串。我不相信有更有效的方法。

从语料库中找到匹配的常用词或短语的高效算法

Efficient algorithm to find matching common words or phrases from a corpus

java

algorithm

text