尝试查找 600,000 个条目的每个组合之间的距离 (python)

Question

我有一组大约 ~600,000 个电子邮件地址，我必须为一个项目进行分析。目标是使用 Levenshtein 距离找到每封电子邮件的名称与所有其他电子邮件之间的相似之处，因此 @ 之前的部分。我正在考虑创建所有组合并将它们输入到 HDF 文件或内存中的东西中，但生成所有这些电子邮件地址需要很长时间。有没有办法通过并行处理或池化来加速循环，这样它就不会花费几天的时间来运行。

我的第一组代码是一个生成器，这样我就不会在内存中运行它，第二组代码应用距离指标。我没有使用HDF文件的所有代码，而是将其附加到列表中以加快速度。

def makeCombos(data, i=2):
for combo in map(list, combinations(data, i)):
yield combo
l = []
def combos(data):
for x in makeCombos(data):
if levenshteinDistanceDP(x[0], x[1]) < 4:
l.append(x)

我还研究了使用某种最近邻算法，例如 annoy，因为它们的计算效率似乎更高。但是我在弄清楚如何矢量化电子邮件地址甚至设置这样的模型时遇到了很多麻烦。

任何建议都会有所帮助。

Answer 1

您可以使用multiprocessing模块并行化处理，如下所示。 此外，使用itertools模块生成组合。

import itertools, multiprocessing
def combos(data):
with multiprocessing.Pool() as pool:
combos = itertools.combinations(data, 2)
return [x for x in pool.starmap(levenshteinDistanceDP, combos) if x < 4]

Answer 2

TL;DR：正如这里所描述的，莱文斯坦距离可能不是衡量所有邮件距离的最佳方法。最好使用替代距离，甚至完全改变方法。此外，启发式方法可用于加快执行速度。

由于您有k字符串并且想要比较所有对，因此总体复杂性O(k^2 L)其中L是计算levenshteinDistanceDP的复杂性。因此，主要是由于k^2因素，在您的情况下，该算法至少需要几个小时/几天才能完成。

为了显著降低计算的复杂性，汉明距离和杰卡德相似性是一个良好的开端。

如果使用近似值没问题，您也可以：

• 设计一个函数f将邮件转换为具有代表性的数字描述符(即。特征向量(，同时保留局部性(邮件的接近程度(;
• 对每个邮件字符串s应用函数f(s);
• 有效地比较所有结果对(例如，使用二进制空间分区，如K-D树，或统计/分类方法(。

然而，困难的部分是找到一个好的f候选人(机器学习方法可以帮助找到它(。

请注意，在应用当前确切方法之前，您可以使用上述方法显着过滤结果。如果近似值从未高估实际距离(即。可接受的启发式(。

---

更新：

一个简单的可接受的启发式是包含字符频率的向量的(校正(曼哈顿距离(即给定集合中每个字符的出现次数(。 下面是使用此启发式方法的代码示例：

# Count the number of 'a', 'b', 'c' ..., 'y', 'z' and '0', '1', ..., '9' in the string s
def freq(s):
res = np.zeros(36, dtype=int)
for c in map(ord, s.upper()):
if c >= 65 and c <= 90: # A-Z
res[c-65] += 1
elif c >= 48 and c <= 57: # 0-9
res[c-48+26] += 1
return res
# Compare the two frequency vectors fs and ft
def freqDist(fs, ft):
manDist = np.abs(fs-ft).sum()
return (manDist + 1) // 2
# Faster heuristic but not admissible (ie. approximation)
def freqDistApprox(fs, ft):
return np.abs(fs-ft).sum()
l = []
def fasterCombos(data):
maxi = len(list(makeCombos(data)))
count = 0
freqs = {s: freq(s) for s in data}  # Precompute frequencies (feature vectors)
for x in makeCombos(data):
s, t = x[0], x[1]
if freqDist(freqs[s], freqs[t]) < 4: # Estimate the levenshtein distance quickly
if levenshteinDistanceDP(s, t) < 4:
l.append(x)

这种简单的启发式方法应该会显著减少计算的列文施泰因距离的数量。但是，它往往明显低估了距离。freqDistApprox以近似结果为代价加快执行速度。

一旦找到一个好的启发式方法，就可以使用二进制空间分区来仅比较彼此靠近的特征向量(估计的Levenshtein距离足够近(。这可以通过迭代所有特征向量并检查它们的邻域来非常有效地完成。算法的复杂性O(k n (L + D log(k)))其中n是近邻的平均数量(0 < n <= k(，D每个特征向量的维度。

最后，请注意，最坏情况的复杂性仍然O(k^2)因为如果所有邮件相等或接近相等，l可以包含O(k^2)对(Levenshtein 距离非常小，这是n ~= k的情况(。但是，当邮件彼此非常不同(或距离阈值足够小(并且使用了良好的启发式方法时，结果方法应该要快得多(因为n << k(。