如何实现拼写纠错功能?

本贴最后更新于 2269 天前,其中的信息可能已经天翻地覆

在使用搜索引擎时,当我们输入错误的关键词时,当然这里的错误是拼写错误,搜索引擎的下拉框中仍会显示以正确关键词为前前辍的提示,当你直接回车搜索错误的关键词时,搜索引擎的结果中仍包括正确关键词的结果。你有没有想过它是如何实现的呢?

显示正确的提示

显示正确的结果

前文已经分享如何使用前辍树实现搜索框的关键词提示功能。大家很容易想到以上纠错功能的实现,关键在于给定一个错误的关键词,如何返回一个正确的关键词。

最简单的方法,我们使用一个数组来存储正确关键词,对于给定的关键词,我们遍历此数组,找到与给定关键词最接近的那个词返回即可。

如何找到最接近的那个词呢?也就是说如何量化两个字符串的相似度。通常有两种方法:一种是求两个字符串的编辑距离,编辑距离越小,两个字符串越相近。另一种是求两个子符串的最长公共子串长度,长度越大,两个字符串越相近。

**编辑距离(莱文斯坦距离)**就是从一个词变成另一个词需要的最小编辑次数。这里的编辑是指删除、替换、或插入。比如 facbok 和 facebook 的编辑距离就是 2 ,因为最小的操作是插入 2 次。比如 faccbook 和 facebook 的编辑距离就是 1 ,因为只需要替换 1 次。

最长公共子串长度从相反的角度来量化相似度,通过最小次数的删除,增加操作后,两个字符串达到相同时的长度。比如 facbok 和 facebook 的最大公共子串长度是 6。

如何求两个字符串的编辑距离?

先考虑如何人脑如何有效的识别编辑距离:

facbok (字符串a) facebook (字符串b)

初始编辑距离为 0,分别遍历两个字符串,如果一样,则指针 index 后移,如果不一样,有以下三种情况:

1、在字符串 a (或字符串 b) 中 index 处的字符删除,编辑距离 +1,然后比较 a[index+1] 与 b[index]

2、在字符串 a (或字符串 b) 中,a[index]前的位置插入一个字符,编辑距离 +1,然后比较 a[index] 与 b[index+1]

3、在字符串 a (或字符串 b) 中,a[index]的位置替换一个字符,编辑距离 +1,然后比较 a[index+1] 与 b[index+1]

循环结束,比较 3 种情况,找出距离最小的即可。
基于以上思路,我们可以画个表格来尝试找规律:

状态转移

字符 f = f ,因此单元格 B2 的值为 0 ,相应的 f 与 fa 的编辑距离为 1 因此 C2 的位置是 1,同理可得第 1 行和第 A 列的编辑距离。

接下来求 C3,C3 的值可以 C2 增加一个字符,B3 删除一个字符,或者 B2 替换一个字符转化而来,这三者的最小距离为
min(1+1,1+1,0+0) = 0 ,同样的道理可以得出其余所有格子的数值。

比如:E5 = min(E4+1,D5+1, 0+INT(E1!=A5)) = 1

最终的结果即 I7 的结果为 2。

以上过程可以很容易翻译成代码。

def levenshtein_dp(s: str, t: str) -> int: ''' 计算莱文斯坦距离(Levenshtein distance),距离越小,说明两个单词越相近,时间复杂度为 O(mxn) :param s: :param t: :return: ''' m, n = len(s), len(t) table = [[0] * (n + 1) for _ in range(m + 1)] table[0] = [j for j in range(n + 1)] # print(table) for i in range(m + 1): table[i][0] = i for i in range(1, m + 1): for j in range(1, n + 1): table[i][j] = min(1 + table[i - 1][j], 1 + table[i][j - 1], int(s[i - 1] != t[j - 1]) + table[i - 1][j - 1]) return table[-1][-1]

为了得到正确的函数,你还需要类似以下功能的函数:

def get_right_word(self,input_word): ''' 输入一个单词,返回正确的单词 :param input_word: :return: ''' words = self.get_all_words()#获取所有正确的单词 right_word = input_word min_distance = 99999 for item in words: distance = levenshtein_dp(input_word,item) if min_distance > distance: min_distance = distance right_word = item return right_word

结果前文中的前辍树,你可以很容易实现拼写纠错功能。

下面给出一种最长子串的求法,供参考:

def common_substring_dp(s: str, t: str) -> int: m, n = len(s), len(t) table = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): table[i][j] = max(table[i - 1][j], table[i][j - 1], int(s[i - 1] == t[j - 1]) + table[i - 1][j - 1]) return table[-1][-1]

测试

我使用 cet4 词库来测试一下使用莱文斯坦距离和最长公共子串长度获取的正确单词有什么不同,附完整代码如下:

# -*- codeing:utf-8 -*- def levenshtein_dp(s: str, t: str) -> int: ''' 计算莱文斯坦距离(Levenshtein distance),距离越小,说明两个单词越相近,时间复杂度为 O(mxn) :param s: :param t: :return: ''' m, n = len(s), len(t) table = [[0] * (n + 1) for _ in range(m + 1)] table[0] = [j for j in range(n + 1)] # print(table) for i in range(m + 1): table[i][0] = i for i in range(1, m + 1): for j in range(1, n + 1): table[i][j] = min(1 + table[i - 1][j], 1 + table[i][j - 1], int(s[i - 1] != t[j - 1]) + table[i - 1][j - 1]) return table[-1][-1] def common_substring_dp(s: str, t: str) -> int: m, n = len(s), len(t) table = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): table[i][j] = max(table[i - 1][j], table[i][j - 1], int(s[i - 1] == t[j - 1]) + table[i - 1][j - 1]) return table[-1][-1] def get_right_word_from_levenshtein_dp(all_words,input_word): ''' 输入一个单词,返回计算莱文斯坦距离最小的单词 :param input_word: :return: ''' words = all_words #获取所有正确的单词 right_word = input_word min_distance = 99999 for item in words: distance = levenshtein_dp(input_word,item) if min_distance > distance: min_distance = distance right_word = item return right_word def get_right_word_from_common_substring_dp(all_words,input_word): ''' 输入一个单词,返回最长公共子串长度最大的单词 :param input_word: :return: ''' words = all_words #获取所有正确的单词 right_word = input_word min_distance = 0 for item in words: distance = common_substring_dp(input_word,item) if min_distance < distance: min_distance = distance right_word = item return right_word if __name__ == '__main__': all_words = [] with open("cet4.txt",encoding="gbk",mode="r") as r: for line in r: word = line.strip().split(" ")[0] if word != '' and len(word) > 2: all_words.append(word) while True: input_word = input("please input a word.(q for quit.): ") if input_word == 'q': break right_word = get_right_word_from_levenshtein_dp(all_words,input_word) print("the right word in cet4 is(levenshtein_dp): ",right_word) print(levenshtein_dp(right_word,input_word)) right_word = get_right_word_from_common_substring_dp(all_words,input_word) print("the right word in cet4 is(common_substring_dp): ",right_word) print(common_substring_dp(right_word,input_word))

运行效果如下:

please input a word.(q for quit.): afection the right word in cet4 is(levenshtein_dp): affection 1 the right word in cet4 is(common_substring_dp): affection 8 please input a word.(q for quit.): advertise the right word in cet4 is(levenshtein_dp): adjective 3 the right word in cet4 is(common_substring_dp): advertisement 9 please input a word.(q for quit.): atmosph the right word in cet4 is(levenshtein_dp): almost 3 the right word in cet4 is(common_substring_dp): atmosphere 7 please input a word.(q for quit.): assembl the right word in cet4 is(levenshtein_dp): assemble 1 the right word in cet4 is(common_substring_dp): assemble 7 please input a word.(q for quit.):

结论

测试了 4 个错误的单词,有 2 个返回的单词二者返回是一致的,有 2 个返回不一致。

比如:advertise 使用莱文斯坦距离返回正确单词是 adjective
使用最长公共子串长度返回的则是 advertisement,显然返回 advertisement 是输入者较为期望的结果。在某些场景下,莱文斯坦距离更有效。

因此没有一个放置四海而皆准的办法,实际使用中要结合具体需求,比如还可以加入搜索关键词热度等指标加以权衡。

希望本篇文章能让你开发的系统中的输入框更加智能。

(完)

专注有价值的技术分享。欢迎订阅我的微信公众号 somenzz,及时获得更新。

  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    554 引用 • 675 回帖 • 1 关注
  • 动态规划
    6 引用 • 1 回帖
  • 拼写纠错
    1 引用

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 爬虫

    网络爬虫(Spider、Crawler),是一种按照一定的规则,自动地抓取万维网信息的程序。

    106 引用 • 275 回帖
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    6 引用 • 143 回帖
  • 代码片段

    代码片段分为 CSS 与 JS 两种代码,添加在 [设置 - 外观 - 代码片段] 中,这些代码会在思源笔记加载时自动执行,用于改善笔记的样式或功能。

    用户在该标签下分享代码片段时需在帖子标题前添加 [css] [js] 用于区分代码片段类型。

    208 引用 • 1469 回帖 • 1 关注
  • OpenCV
    15 引用 • 36 回帖
  • 旅游

    希望你我能在旅途中找到人生的下一站。

    100 引用 • 905 回帖
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    173 引用 • 414 回帖 • 359 关注
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    91 引用 • 59 回帖
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    108 引用 • 295 回帖
  • GitBook

    GitBook 使您的团队可以轻松编写和维护高质量的文档。 分享知识,提高团队的工作效率,让用户满意。

    3 引用 • 8 回帖
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    167 引用 • 408 回帖 • 484 关注
  • 黑曜石

    黑曜石是一款强大的知识库工具,支持本地 Markdown 文件编辑,支持双向链接和关系图。

    A second brain, for you, forever.

    25 引用 • 254 回帖 • 2 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3203 引用 • 8217 回帖 • 2 关注
  • ZooKeeper

    ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是 Google 的 Chubby 一个开源的实现,是 Hadoop 和 HBase 的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、分布式同步、组服务等。

    61 引用 • 29 回帖 • 7 关注
  • RESTful

    一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

    30 引用 • 114 回帖 • 6 关注
  • abitmean

    有点意思就行了

    36 关注
  • Facebook

    Facebook 是一个联系朋友的社交工具。大家可以通过它和朋友、同事、同学以及周围的人保持互动交流,分享无限上传的图片,发布链接和视频,更可以增进对朋友的了解。

    4 引用 • 15 回帖 • 441 关注
  • 锤子科技

    锤子科技(Smartisan)成立于 2012 年 5 月,是一家制造移动互联网终端设备的公司,公司的使命是用完美主义的工匠精神,打造用户体验一流的数码消费类产品(智能手机为主),改善人们的生活质量。

    4 引用 • 31 回帖
  • Typecho

    Typecho 是一款博客程序,它在 GPLv2 许可证下发行,基于 PHP 构建,可以运行在各种平台上,支持多种数据库(MySQL、PostgreSQL、SQLite)。

    12 引用 • 67 回帖 • 445 关注
  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 61 关注
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议,它实现了浏览器与服务器之间的全双工通信(full-duplex)。

    48 引用 • 206 回帖 • 281 关注
  • AngularJS

    AngularJS 诞生于 2009 年,由 Misko Hevery 等人创建,后为 Google 所收购。是一款优秀的前端 JS 框架,已经被用于 Google 的多款产品当中。AngularJS 有着诸多特性,最为核心的是:MVC、模块化、自动化双向数据绑定、语义化标签、依赖注入等。2.0 版本后已经改名为 Angular。

    12 引用 • 50 回帖 • 516 关注
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    36 引用 • 35 回帖
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖
  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1340 回帖
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖 • 1 关注
  • Chrome

    Chrome 又称 Google 浏览器,是一个由谷歌公司开发的网页浏览器。该浏览器是基于其他开源软件所编写,包括 WebKit,目标是提升稳定性、速度和安全性,并创造出简单且有效率的使用者界面。

    63 引用 • 289 回帖
  • 招聘

    哪里都缺人,哪里都不缺人。

    188 引用 • 1057 回帖