假设有一个单词集,我想根据他们的char包(multiset)对它们进行聚类.例如
{茶,吃,阿巴,阿巴,你好}
将聚集成
{{tea,eat},{abba,aabb},{hello}}.
abbaaabb由于它们具有相同的char包,即两个a和两个,因此聚集在一起b.
为了使它高效,我能想到的一种天真的方式是将每个单词转换成一个char-cnt系列,例如,abba并且aabb将被转换为a2b2,tea/eat将被转换为a1e1t1.这样我就可以构建一个字典并用相同的键组合单词.
这里有两个问题:首先我必须对字符进行排序以构建密钥; 第二,字符串键看起来很笨拙,性能不如char/int键.
有没有更有效的方法来解决问题？
我会分两步完成此操作，首先根据长度对所有单词进行排序，然后分别处理每个子集（这是为了避免以后出现大量重叠。）
下一步更难，有很多方法可以做到。最简单的方法之一是为每个字母分配一个数字（例如，a = 1、b = 2 等），然后将每个单词的所有值相加，从而为每个单词分配一个整数。然后您可以根据这个整数值对单词进行排序，这大大减少了您必须比较的数量。
根据您的数据集，您可能仍然有很多重叠（“bad”和“cac”会生成相同的整数哈希），因此您可能需要设置一个阈值，如果一个存储桶中有太多单词，则重复前一个步骤与另一个散列（只是为字母分配不同的数字）除非有人查看了您的代码并设计了一个单词列表来搞乱您，否则这应该将重叠减少到几乎没有。
请记住，当您期望同一字符包中包含少量单词时，此方法将非常有效。如果您的数据是很多长单词，仅放入几个字符袋中，那么您在最后一步中进行的比较次数将是天文数字，在这种情况下，您最好使用您所描述的方法- 不可能有重叠的一个。