字符串与最相似的字符串比较

Question

有没有人知道如果存在给定一个字符串A和一个字符串B数组的算法,将A字符串与B中的所有字符串进行比较,给出输出中最相似的字符串.

对于"最相似的",我的意思是,例如,

如果A字符串是:"hello world你好吗"

然后

"asdf asdewr你好世界怎么asfrqr你"

比以下更相似:

"h2ll4 w1111 h11 111 111"

Answer 1

对此的通常测量是Levenshtein距离.计算从原始距离到每个候选者的Levenshtein距离,并将最小距离作为最可能的候选者.

Answer 2

定义相似性.可以做到这一点的算法包括:

1. Levenshtein/LCS/n-gram距离(将字符串与您集合中的每个字符串进行比较,取最小距离的字符串)
2. tf-idf索引
3. Levenshtein自动机
4. Hopfield网络
5. BK树

所有这些都可以通过C或C++实现.Google可用指标和算法的"字符串相似性","重复查找"或"记录链接".