如何做搜索引擎优化 方法(如何量化两个字符串字符串之间的相似度？(图))

　　如何做搜索引擎优化 方法(如何量化两个字符串字符串之间的相似度？(图))

　　在关于Trie树的部分，我们说过使用Trie树可以实现搜索引擎的关键词提示功能，可以节省用户搜索关键词的时间。其实搜索引擎在用户体验方面还有很多优化，比如你可能经常用到的拼写纠正功能。

　　当您不小心在搜索框中输入错误的单词时，搜索引擎会非常智能地检测您的拼写错误并使用相应的正确单词进行搜索。作为软件开发工程师，有没有想过这个功能是如何实现的？

　　如何量化两个字符串的相似度？

　　计算机只识别数字，所以要回答开头的问题，首先要看看如何量化两个字符串之间的相似度？有一个非常有名的量化方法，那就是Edit Distance。

　　顾名思义，编辑距离是指将一个字符串转换为另一个字符串所需的最少编辑操作次数（如添加一个字符、删除一个字符、替换一个字符）。编辑距离越大，两个字符串的相似度越小；相反，编辑距离越小，两个字符串之间的相似度就越大。对于两个相同的字符串，编辑距离为 0。

　　根据收录的编辑操作类型的不同，编辑距离的计算方法有很多种。比较有名的是 Levenshtein distance 和 Longest common substring length。其中，莱文斯坦距离允许增加、删除、替换字符三种编辑操作，最长公共子串长度只允许添加和删除字符两种编辑操作。