计算900,000个字符串之间的Dice系数的有效方法是什么？

Question

我有一个900,000字符串的语料库.它们的长度各不相同,但平均字符数约为4,500.我需要找到计算每个字符串的Dice系数的最有效方法,因为它与每个其他字符串相关.不幸的是,这导致Dice系数算法使用了大约810,000,000,000次.

构建此计划以提高效率的最佳方法是什么？显然,我可以防止计算A和B部分的骰子,然后是B和A - 但这只会使所需的工作减半.我应该考虑采取一些快捷方式或创建某种二叉树？

我正在使用Java中的Dice系数算法的以下实现:

public static double diceCoefficient(String s1, String s2) {
    Set<String> nx = new HashSet<String>();
    Set<String> ny = new HashSet<String>();

    for (int i = 0; i < s1.length() - 1; i++) {
        char x1 = s1.charAt(i);
        char x2 = s1.charAt(i + 1);
        String tmp = "" + x1 + x2;
        nx.add(tmp);
    }
    for (int j = 0; j < s2.length() - 1; j++) {
        char y1 = s2.charAt(j);
        char y2 = s2.charAt(j + 1);
        String tmp = "" + y1 + y2;
        ny.add(tmp);
    }

    Set<String> intersection = new HashSet<String>(nx);
    intersection.retainAll(ny);
    double totcombigrams = intersection.size();

    return (2 * totcombigrams) / (nx.size() + ny.size());
}

我的最终目标是为每个骰子系数大于0.9的部分输出一个ID.

感谢您提供的任何建议!

Answer 1

您应该提出某种不等式，例如： D(X1,X2) > 1-p、D(X1,X3) < 1-q 和 p D(X2,X3) < 1-q+p 。或类似的东西。现在，如果 1-q+p < 0.9，那么您可能不必评估 D(X2,X3)。

PS：我不确定这个确切的不平等，但我有一种直觉，这可能是正确的（但我现在没有足够的时间来实际进行推导）。寻找与其他相似性度量的一些不等式，并查看其中是否有任何一个对于 Dice 系数有效。

===还有===

如果集合 A 中有一个元素，并且阈值是 r (=0.9)，则集合 B 的元素数量 b 应该满足： r*a/(2-r) <= b <= (2 -r)*a/r 。恕我直言，这应该消除大量比较的需要。您可以根据长度对字符串进行排序，并使用上面描述的窗口来限制比较。