优化多词编辑距离的速度

我有一个元胞数组字典，其中包含很多单词（约 15000 个）。

我想计算函数strdist（计算 Levenshtein 距离）所有单词对。我尝试了两种方法，但它们都很慢。什么是更有效的解决方案？

这是我的代码（dict_keys 是我长度为 m 的元胞数组）：

1)

matrix = sparse(m,m);
for i = 1:m-1;
    matrix(i,:) = cellfun( @(u) strdist(dict_keys{i},u), dict_keys );
end

2)

matrix = sparse(m,m);
for i = 1:m-1;
  for j = i+1:m
     matrix(i,j) = strdist(dict_keys{i},dict_keys{j});
  end   
end

函数“strdist”不是内置的 matlab 函数，所以我猜你是从文件交换 http://de.mathworks.com/matlabcentral/fileexchange/17585-calculation-of-distance-between-strings/content/strdist.m。这也是为什么你的两种方法在时间上大致相等，cellfun内部只是扩展成一个循环。

If strdist是对称的，即 strdist(a,b)==strdist(b,a) 但是您可以节省一半的计算量。好像是这样，所以只计算所有情况j<i在第二个循环中（您正在执行的操作）。

否则，您可以在 C 中将 strdist 实现为 mex 函数，并且可能会看到一些显着的速度改进。 Levenshtein 距离的 C 实现可以在以下位置找到：Rosettacode.org http://rosettacode.org/wiki/Levenshtein_distance#C.

或者深入研究算法如何计算两个字符串的距离的细节，看看是否可以将其矢量化并减少二次运行时间。然而这可能并不容易。

最后，如果您拥有并行计算工具箱许可和多核 CPU，您可以轻松并行化您的代码，因为strdist调用之间完全独立。