码上生活

谐音梗生成器

duck不必,babe无耻……如何批量制造李诞的快乐源泉。(封面灵感来自奇葩说)

阅读全文预计约9分钟

段子:★★

知识:★★★

阅读本文你将学到:字符串相似度

谐音梗,即通过谐音来制造笑点,比如book思议,Tony带水,贪生pass等等。

谐音梗相较于其他段子来说比较容易创作,不用花费太多心思就能创作出令人愉悦的段子。当然,在李诞同学面前讲谐音梗会获得双倍的愉悦。

谐音梗——李诞的快乐源泉

既然谐音梗如此有趣,那我们能否用程序自动生成谐音梗呢?本文中,我们将制作谐音梗生成器,又名李诞同学的快乐源泉

首先,我们要明确目标:给出一个成语(如有备而来),谐音梗生成器可以自动将其中的两个字替换成读音相似的英文单词(如有bear来)。

明确了目标后,谐音梗生成器的大体思路如下:

谐音梗生成器 总流程图

第一步:汉语转拼音

首先,我们将汉字成语(有备而来)转换成拼音(you-bei-er-lai)。

在此类问题上,已有很多现成的函数库,直接调用即可(如python中的xpinyin)

第二步:准备英语词典

紧接着,我们需要准备一个英语词典

为了简化计算,我们只需要考虑最常用的小学词汇,并筛选出所有长度为3-5个字母的单词。

这样选出的单词能保证大部分读者认识,如green,blue,time等等,同时也会减少后面字符串匹配的工作量。毕竟一些如supercali的超长单词是绝对用不上的。

Supercalifragilisticexpialidocious
(人见人爱,花见花开,车见爆胎)

第三步:字符串相似度计算与匹配

已有了一个成语的拼音(YouBeiErLai)以及由上千的简单词汇组成的英语词典后,下一步就是进行字符串匹配了。

这里的匹配不是说找出与成语拼音完全一模一样的英文单词,而是先计算出与成语拼音与各英文单词的相似度,然后进行字符串替换

于是乎,最重要的问题来了:

如何定义两个字符串的相似度?

下面将介绍几种常用的算法。对算法不感兴趣的读者可以跳到第四步。

1. 汉明(Hamming)距离

我们先考虑最简单的情况:两个字符串的长度相等。

汉明(Hamming)距离指的是一个字符串转变成另一个字符串所需要替换的字符个数。简单来说即比较两个字符串各个位置的字符是否相等

字符串A与B有两个位置不相等(第三位和第五位),因此,字符串A与B的汉明距离是2。

一般,我们讨论的相似度取值是在0到1之间,数值越趋近1则两个字符串越相似。因此我们可以定义两个字符串的相似度为其相似的字符数除以字符串总长度,上图中为3/5,即0.6

(另一种对汉明距离的理解是对两个字符串进行异或操作,并统计结果中1的个数。)

2. 编辑距离

接下来,我们讨论两个字符串非等长的情况。

类比于汉明距离为替换字符的个数,在非等长的情况下,我们可以统计字符增删改的次数

编辑距离为对一个字符串进行字符替换、字符添加、字符删除操作,使之变为另一个字符串所需的最少操作步数

在本例中,我们可以删除字符串A的第2位和第3位,并将第五位由字符a替换成字符d,从而三步得到字符串B。于是,字符串A与字符串B的编辑距离为3。

当然,我们也可以对字符串A进行5次删除操作,对字符串B进行3次删除操作,从而使得字符串AB都变成相等的空串,总共需要8步。但这不是字符串A变成字符串B的最少操作步数,因此编辑距离不为8。

我们可以用如下公式计算字符串AB的相似度。在本例中,字符串A与B的相似度为(8-3)/8 = 0.625

编辑距离算法的逻辑看似简单,但算法实现起来需要动一定的脑筋,是一道很经典的动态规划练习题。有兴趣的读者可以前往下面的地址进行尝试。

leetcode-cn.com/problems/edit-distance

3. 余弦相似度

在计算两个向量相似度时,余弦是最常用的一种算法。

我们可以先将字符串转为向量,接着用余弦来计算着两个向量的相似度

那如何将字符串向量化呢?用词袋(Bag of words)模型!

假设字符串A与字符串B如下:

则两个字符串由四种基本字符组成:”a”,”b”,”c”,”d”

于是乎,我们可以统计字符串A和B中包含这四种基本字符的个数,从而构成一串向量。

A={2,2,1,0}, B={1,0,1,1}即字符串A中包含2个字符”a”,2个字符”b”,1个字符”c”和0个字符”d”。字符串B同理。 

值得注意的是词袋模型没有考虑字符出现的先后顺序。字符串”aabbc”可以编码为{2,2,1,0},字符串”cabab”亦可以编码为{2,2,1,0}

经过上述步骤得出字符串AB所对应的向量后,用余弦公式计算两个向量的余弦相似度即可。

余弦公式

余弦相似度也适用于两个文本之间的相似度计算。

4. 其他

除了上述三种相似度以外,其他计算相似度的方式有:

Jaccard 相似度

Dice 相似度

Jaccard和Dice比较适合计算文本之间的相似度。此时,集合A与B代表一段文本,集合内的元素为单词。

上述所有的相似度计算方式除了在字符串匹配时会用到,在如目标检测、人脸识别等其他领域也会用到。

在了解了5种相似度计算的方法后,我们来回顾一下之前提出的疑问:如何定义两个字符串的相似度?

问题的答案是依据具体情况而定的,如果两字符串等长,用汉明编码最简单直接;如果我们想进行两段文本之间的相似度计算,用Jaccard、Dice或余弦相似度会比较好;如果……

当然,就像深度学习中的损失函数一样,除了套用比较著名的公式以外,我们还可以根据具体情况,自行定义相似度计算公式。理解算法的原理比套用算法要重要得多

第四步:最终效果与进一步完善

我们将上述的几个步骤进行一个整合:

给出单词“有备而来”,将其转换成拼音“You Bei Er Lai”

另外,准备好由若干简单英文单词构成的词库。

选择四字词语里的两个字,如选择“备而”(这里的选择可以人工手动选,也可以遍历所有可能的组合,最后选出最佳的结果即可)

“备而”的拼音是“beier”。采用第三步中介绍的某一个算法(如编辑距离)来计算“beier”与英语词典中的所有词(able,above,act…,zoo)的字符串相似度。

最终我们发现单词“beer”与拼音“beier”的相似度最高,高达0.88888(如果按照第三步中对编辑距离的介绍,则其编辑距离为1)

于是,我们可以用单词“beer”来代替拼音“beier”,成语“有备而来”也就变成了“有beer来”

“欢天喜地”变成了“hunt喜地” 

上述方法在部分情况下可以达到不错的效果,但在有些时候,还是略有缺陷的。

比如“不可思议”中的“不可”,拼音是“buke”,发音相似的单词应该是“book”,但是由于编辑距离的定义,“buke”与“book”的编辑距离是4(删除掉buke中的u和e,并加上两个o)。“buke” 与 “bake” 、 “bike” 的编辑距离是1,于是输出结果就成了“bake思议”。

虽说结果也可以,但仍旧有提升的空间。

那有没有什么比较好的提升方法呢?

有的!用音标!

拼音是对中文汉字进行注音,音标是对英文单词进行注音。拼音和音标正好可以对接起来!

新算法的流程图如下:

整体思路保持不变,仍旧是给出汉字“有备而来”,转为拼音“YouBeiErLai”,选择待匹配拼音“BeiEr”。

新算法对要匹配的英文单词进行了修改。首先,我们通过查询英文词典,可以得知每个单词的音标:“beer”对应“ber”,“sky”对应“skaɪ”。

接着,我们手动设置每个音标对应什么声音。比如音标“aɪ”对应中文拼音的“ai”,音标“ð”音似中文的“zhe”,音标“ˈ”是用于表示重读,这里直接忽略。

最后,我们编写一个音标转近似拼音的函数

单词“beer”的音标“ber”近似为拼音后保持不变,仍旧为“ber”,而单词“sky”的音标“skaɪ”近似为拼音后则变为了“skai”。

此时,我们将“有备而来”中的拼音“BeiEr”与这些近似的拼音进行字符串匹配即可。最后发现单词“beer”的近似音标“ber”与拼音“BeiEr”最相似,于是就用“beer”来代替“备而”。

新方法会比直接用英文单词进行字符串相似度计算性能会好一点,但也不会好多少。

比如“不可思议”中的“不可”(“buke”)用旧方法智能找到“bake”,“bike”。使用新方法后可以找出“book”,但同时也找到了其他不太相关的词如“box”,“block”等等。

包括“谐音梗生成器”在内的往期文章代码

已上传至GITHUB

github.com/DrMofu/MLab_wechat

如果你觉得本篇文章比较有意思,欢迎关注技术杂学铺公众号点赞分享本文章。

发表评论