在Python中比较两大字符串的最佳方法

Question

我正在使用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)来散列每个字符串(即我不介意那么多正面...).这是一个好方法还是我应该考虑其他策略？

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

在此先感谢您的帮助!

Answer 1

首先,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

它肯定比使用set慢,但它不需要将字符串保存到内存中(同时只需要两个字符串).

对于Levenshtein来说,有一个C模块可以在Pypi上找到,而且速度非常快.