6

我正在使用 Python（并且可以访问 pandas、numpy、scipy）。

我有两个集合字符串集合 A 和集合 B。每个集合 A 和 B 包含 c。2000 个元素（每个元素都是一个字符串）。字符串长度约为 50-100 个字符，最多包含 c。20 个单词（这些集合可能会变得更大）。

我想检查集合 A 的成员是否也是集合 B 的成员。

现在我在想一个简单的实现可以被可视化为一个矩阵，其中 A 和 B 中的成员相互比较（例如 A1 == B1，A1 == B2，A1 == B3 等等......）和布尔值比较中的 (0, 1) 包含矩阵的元素。

有效实施这一点的最佳方法是什么？

两个进一步的阐述：

(i) 我还认为，对于较大的集合，我可以使用 Bloom Filter（例如使用 PyBloom、pybloomfilter）来散列每个字符串（即，我不太介意 fasle positives ......）。这是一个好方法还是我应该考虑其他策略？

(ii) 我正在考虑在字符串之间加入 Levenshtein 距离匹配（我知道这可能很慢），因为我可能需要模糊匹配 - 有没有办法将它与 (i) 中的方法结合起来，或者以其他方式使其更有效？

提前感谢您的帮助！

4

3 回答 3

5

首先，2000 * 100 个字符并没有那么大，你可以直接使用一个集合。

其次，如果您的字符串已排序，则有一种快速方法（我在此处找到）来比较它们，如下所示：

def compare(E1, E2):
    i, j = 0, 0
    I, J = len(E1), len(E2)
    while i < I:
        if j >= J or E1[i] < E2[j]:
            print(E1[i], "is not in E2")
            i += 1
        elif E1[i] == E2[j]:
            print(E1[i], "is in E2")
            i, j = i + 1, j + 1
        else:
            j += 1

它肯定比使用集合要慢，但它不需要将字符串保存到内存中（同时只需要两个）。

对于 Levenshtein 的事情，你可以在 Pypi 上找到一个 C 模块，而且速度非常快。

于 2013-06-23T18:51:38.030 回答
1

如评论中所述：

def compare(A, B):
    return list(set(A).intersection(B))
于 2014-09-11T13:19:41.747 回答
0

这是@michaelmeyer 在此处https://stackoverflow.com/a/17264117/362951提出的功能的修改版本- 在他对我们所在页面顶部问题的回答中。

下面的修改版本也适用于未排序的数据，因为该函数现在包括排序。

这在很多情况下不应该是性能或资源问题，因为 python 排序非常有效。预分类也有帮助。

请注意，“输出”现在也已排序。如果未排序，这将不同于第一个参数的原始顺序。

否则，即使两个数据集都已经排序，排序也不会受到太大影响。

但是如果你想禁止排序，如果两个数据集都已经按升序排序，可以这样调用：

compare(my_data1,my_data2,data_is_sorted=True)

否则：

compare(my_data1,my_data2)

并且该函数接受无序数据。

这是修改后的版本。仅添加了前两行和第三个可选参数：

def compare(E1, E2, data_is_sorted=False):
    if not data_is_sorted:
        E1=sorted(E1)
        E2=sorted(E2)
    i, j = 0, 0
    I, J = len(E1), len(E2)
    while i < I:
        if j >= J or E1[i] < E2[j]:
            print(E1[i], "is not in E2")
            i += 1
        elif E1[i] == E2[j]:
            print(E1[i], "is in E2")
            i, j = i + 1, j + 1
        else:
            j += 1
于 2018-10-10T08:01:36.090 回答