根据相似性对字符串进行排序

Question

考虑以下字符串:

• 你好
• 再见
• 你好
• =(再见)
• (你好)
• 再见
• 氦

我知道,我正试图以这样的方式对这些词进行排序,以至于类似的词汇汇集在一起

1. alphanumerical sorting 不是一种选择
2. 删除特殊字符",-_ and etc然后比较肯定是有帮助的,但结果将不如我希望的那么好.

注意 :

可能没有多少不同的期望输出,其中一个是:

期望的输出:

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

所以我的问题是,如果有一个java包比较字符串并最终根据它进行排序.

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

更新:找到相似之处肯定是我的问题的一部分,但主要问题是排序部分.

Answer 1

这是一种可能的方法。

计算每对字符串之间的编辑距离/编辑距离，然后将字符串视为完整的图形，其中边权重来自编辑距离。为这些权重选择一个阈值，并删除所有过高的权重。然后找到该图中的派系。如果您的门槛相当低，也许甚至找到连接的组件也是一种选择。

注意：也许最好用 @dognose 发布的链接中的相似性度量之一替换一些编辑距离。另请注意，如果您有大量字符串，则查找派系会非常慢