我有这个问题。我有一组非常大的键值对（以百万计），其中某个唯一 id 作为键，一个字符串作为值（对于 2 个或更多键，字符串可能完全相同）。我必须将这些键值对组合在一起，因为第 1 组包含一些 id 字符串对，第 2 组包含一些其他对等。分组需要根据字符串之间的相似性进行，这些字符串实际上是这些对的值。我已经在这些字符串之间实现了 Levenshtein 距离，并将距离小于阈值距离的对组合在一起。我用传统的（非常糟糕的）方式实现了它：将每个字符串相互比较。
我需要一些关于如何优化它的提示。我可以在 Hadoop 中使用 Map-Reduce 将键值对组合在一起吗？我认为 map 和 reduce 函数的输入是单独的和独立的，因此不能“分组”在一起。这是一个k-means聚类问题吗？你能推荐一些其他更快更有效的技术吗？谢谢。
拼写检查器使用 Burkhard-Keller 树（BK-Tree），这里有一个示例https://github.com/mkarlesky/csharp-bk-tree。这在针对现有列表测试一个新单词时非常快，而且还给出了一个“距离”度量，该度量基于将字符串更改为下一个所需的操作数。与给您一个布尔值的简单“包含”测试不同，这为您提供了一种组织可用选项的方法。你可以在这里阅读更多关于它的信息：http: //blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees。我怀疑您可以使用距离来帮助进行聚类。
我想关于 bk 树的主要事情是你可以继续使用 Levenshtein 距离。但也许你已经在使用它了？这种技术并不适合像 k-means 那样选择任意数量的集群。但是我确实看到了一篇关于在 k-means 的上下文中利用一些新的并行处理的有趣文章，这可能会帮助您在 C# 中加快速度：
http://www.codethinked.com/multi-threaded-k-means-clustering-in-net-40
该示例未使用字符串，但我也许 AsParallel 概念将有助于您已经拥有的解决方案的性能？