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

Question

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

构建此程序以提高效率的最佳方式是什么？显然，我可以避免计算 A 和 B 部分的 Dice，然后是 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());
}

我的最终目标是为每个与另一个部分的 Dice 系数大于 0.9 的部分输出一个 ID。

感谢您提供的任何建议!

Answer 1

对所有字符串进行一次传递，并构建一个 HashMap，将每个二元组映射到包含该二元组的字符串的一组索引。 (目前，您正在为每个字符串冗余地构建二元组 900,000 次。)

然后遍历所有集合，并构建一个包含 [index,index] 对的 HashMap 到 common-bigram 计数。 (后一个 Map 不应包含冗余键对，例如 [1,2] 和 [2,1] —— 只存储一个或另一个。)

这两个步骤都可以很容易地并行化。如果您需要一些示例代码，请告诉我。

注意 不过有一件事:从英文字母表的 26 个字母中，总共可以形成 26x26 = 676 个双字母组。其中许多永远不会或几乎永远不会被发现，因为它们不符合英语拼写规则。由于您正在为每个字符串构建集合 的双字母组，并且字符串很长，您可能会在每个字符串中找到几乎相同的双字母组。如果您要为每个字符串建立 list 双字母组(换句话说，如果计算每个双字母组的频率)，则更有可能您实际上能够测量字符串之间的相似程度，但是维基百科文章中给出的骰子系数的计算将不起作用；你必须找到一个新的公式。

我建议您继续研究确定字符串之间相似性的算法，尝试实现其中的一些算法，并在较小的一组字符串上运行它们以查看它们的工作情况。