基于相似性的排序字符串

Question

考虑以下字符串：

• 阿洛
• 再见
• 你好
• =(再见)
• (他)(Llo)
• 再见
• 氦

我试着把这些词分类，使相似的词结合在一起，我知道

1. alphanumerical sorting不是一种选择
2. 移除特殊的字符",-_ and etc，然后进行比较当然是有帮助的，但结果不会如我所希望的那样好。

注:

这方面可能很少有不同的期望产出，其中之一是：

期望输出：

1. 你好
2. 阿洛
3. (他)(Llo)
4. 氦
5. 再见
6. 再见
7. =(再见)

因此，我的问题是，如果有一个java包比较字符串，并最终根据字符串排序。

我听说过像n-gram和skip-gram这样的术语，但并不完全理解它们。我甚至不确定它们是否对我有用。

更新:找到相似点当然是我问题的一部分，但主要问题是排序部分。

Answer 1

这里有一个可能的方法。

计算每对字符串之间的编辑距离/Levenshtein距离，然后将字符串作为一个完整的图来查看，其中边权值来自编辑距离。为这些权重选择一个阈值，并将所有权重移除到较高的水平。然后在这个图中找到集团。如果您的阈值相当低，也许甚至可以选择找到连接的组件。

注意:也许用@dognose发布的链接中的一个相似度量来替换一些编辑距离会更好。另外，请注意，如果您有大量的字符串，那么查找集群将非常缓慢。