06.C2W1.Auto-correct

往期文章请点这里

Overview

本周学习目标：
●What is autocorrect?
●Building the model
●Minimum edit distance
●Minimum edit distance algorithm

Autocorrect

What is autocorrect?

Autocorrect 是一个自动更正输入错误的功能，通常集成在智能手机、电脑或其他电子设备的输入法中。当用户输入文本时，Autocorrect 会检测到拼写错误或语法错误，并自动更正它们，以提高输入效率和准确性。这个功能通过内置的字典和算法来识别和纠正错误，有时还会根据用户的输入习惯和常用词汇进行个性化调整。然而，Autocorrect 有时也会因为误解用户的意图而更改正确的单词或短语，导致一些有趣的错误或误解。

中文输入法其实也有，例如sougou的模糊音设置（兰方人表示很赞）

正确的autocorrect

错误的autocorrect，改的单词没有问题，但是不符合上下文

How it works

1. Identify a misspelled word
2. Find strings n edit distance away
3. Filter candidates
4. Calculate word probabilities

示例：
先找到一个错误单词：deah
找到n个候选编辑距离：
_eah
d_ar
de_r
…
etc
过滤候选词：
yeah
dear
dean
…
etc
计算候选词的概率，选最大那个：dear

Building the model

1.Identify a misspelled word
最简单的方法就是通过词库判断，当然这个判断不一定准确：

if word not in vocab:
	misspelled =True

2.Find strings n edit distance away
这里n可以是1，2，3，等等。
这里的编辑是指：an operation performed on a string to change it，主要包括：
Insert (add a letter)，例如对于‘to’在不同位置插入不同的单个字母可以得到不同单词‘top’, ‘two’
Delete (remove a letter)，例如‘hat’在不同位置删除不同的单个字母可以得到不同结果: ‘ha’, ‘at’, ‘ht’
Switch (swap 2 adjacent letters)，例如letters)‘eta’交换任意两个字母的位置可以得到： ‘eat’,‘tea’，这里指的是交换两个字母的位置，类似‘ate’是不符合交换这个概念的。
Replace (change 1 letter to another)，例如‘jaw’替换任意一个字母得到：‘jar’,‘paw’,…
这个步骤就是根据给定的字符串，使用以上四种编辑方式，找出所有可能在n个编辑距离的结果，形成候选词列表
3.Filter candidates
对候选词列表进行过滤，这里直接简单粗暴的使用第一步中的方法，将候选词列表中不在词库的单词去掉。
4.Calculate word probabilities
Example: “I am happy because I am learning”
假设语料库就是这个句子，则单词概率可以从下表计算：

计算公式为：
$$P(w)=\frac{C(w)}{V}$$
例如单词am的概率为：$P(am)=\frac{C(w)}{V}=\frac{2}{7}$
在autocorrect中，我们只需要找到单词概率最高的那个候选词即可。

Minimum edit distance

主要内容：
● How to evaluate similarity between 2 strings?
● Minimum number of edits needed to transform 1 string
into the other
最小编辑距离在以下任务有应用：Spelling correction, document similarity, machine
translation, DNA sequencing, and more
已知的编辑操作有三种：Insert，Delete ，Replace （这里吧Switch给剔除了，估计这个操作复杂度挺高）

计算单词play到stay的编辑次数：
p → s : replace
l → t : replace
一共两次
除了考虑编辑次数，还需要考虑编辑的代价，例如：

上面play到stay的编辑代价为：2×2=4
我们需要最小化编辑距离就是要最小化所有所需编辑代价的总和。
例子：
如果要对很长的单词、甚至超长DNA序列找最小编辑距离：

如果采用枚举的方式将所有操作对字符串序列进行遍历，会使用很长时间。
下面将讲解表格法（动态规划）来加速枚举所有可能的字符串和编辑操作。

Minimum edit distance algorithm

Source: play → Target: stay
将源单词和目标单词按以下方式排列：

每个单词的起始处加上井号，我们的目标是填充中间的空白矩阵$D$

D[2,3] = pl → sta，表示pl到sta的最小距离，这里pl是单词play的前两个字母，sta是目标单词stay的前三个字母，也可以表示为：D[2,3] = source[:2] → target[:3]，更通用的形式是
$$D[i,j]=source[:i]\to target[:j]$$
当填充到矩阵的右下角D[m,n]的时候，就得到了整个字符串的最小编辑距离。
$$D[m,n]=source\to target$$

填充顺序是从左上角开始，向下再向右：

下面来看具体步骤：
#号代表空白字符，从空白到空白字符（# → #）编辑代价为0：

从p到空白字符编辑操作是delete，编辑代价是1：

从空白字符到s编辑操作是insert，编辑代价是1：

从p到s编辑操作可有多种
1.insert+ delete（p → ps → s），编辑代价是2：
2.delete+ insert（p → # → s），编辑代价是2：
3.replace（p → s），编辑代价是2：
其实这些不同编辑操作得到的2是基于前面算出来的结果进行计算得到的，例如第一种操作中的插入s已经算过了就是1，然后是删除p也是1，最后加起来就是2，路径是紫色+一个删除；第二种操作是蓝色+一个插入
对于第三种，我们可以看做是从空白处出发，直接到替换操作，其代价是0+2。

可以看到，整个填充过程是基于之前的计算结果来进行的，下面我们将把这一过程通用化为一个公式，以便于填充矩阵的剩余部分。

Minimum edit distance Part 2

这里我们来填写第一列的内容：

使用以下公式：
$$D[i,j]=D[i-1,j]+del\_cost$$

在$D[4,0]$处，得到的是从play到空白字符串的最小编辑距离，相当于删除4个字母的成本。
同样的对于第一行，使用以下公式：
$$D[i,j]=D[i,j-1]+ins\_cost$$
可以得到：

进一步给出通用公式：
$$D[i,j]=\{\begin{array}{l}D[i-1,j]+\text{del\_cost}\\ D[i,j-1]+\text{ins\_cost}\\ D[i-1,j-1]+\{\begin{array}{ll}\text{rep\_cost};& \text{if }src[i]\ne tar[j]\\ 0;& \text{if }src[i]=tar[j]\end{array}\end{array}$$
例如:

$$\begin{array}{c}D[i-1,j]+1=2\\ D[i,j-1]+1=2\\ D[i-1,j-1]+2=2\end{array}\}\text{min}=2$$
接下来填充剩余部分：

用热图显示，可以观察到，由于两个单词最后两个字母都是ay，所以对角线的编辑距离代价到4之后就不再变化了。

Minimum edit distance Part 3

总结需要用到的三个东西：
●Levenshtein distance
●Backtrace
●Dynamic programming

Levenshtein distance（莱温斯坦距离）：
莱温斯坦距离是一种度量两个序列（例如两个字符串）差异的方法，通过计算将一个序列转换为另一个序列所需的最少单字符编辑（插入、删除或替换）次数。
在Minimum edit distance问题中，Levenshtein distance提供了一种量化两个字符串之间差异的标准。

Backtrace（回溯）：
在动态规划问题中，回溯是一种从最终结果反向工作到初始状态的过程，目的是找到达到该结果的路径或解决方案。
对于Minimum edit distance，回溯可以帮助我们从动态规划表的最终状态开始，逆向追踪出将一个字符串转换为另一个字符串所需的具体编辑操作序列。

Dynamic programming（动态规划）：
动态规划是一种算法策略，用于解决具有重叠子问题和最优子结构特性的问题。它通过将问题分解为更小的子问题，并将子问题的解存储起来（通常是在表格中），以避免重复计算，从而提高效率。
在计算Minimum edit distance时，动态规划用于构建一个表格，其中每个单元格代表将两个字符串的前i个字符和前j个字符转换所需的最小编辑次数。通过填充这个表格，我们可以找到将整个字符串转换所需的最小编辑次数。

这三个概念在Minimum edit distance问题中的应用通常遵循以下步骤：

1. 使用动态规划构建一个表格，其中表格的每个元素D[i, j]代表将源字符串的前i个字符转换为目标字符串的前j个字符所需的最小编辑次数。
2. 通过比较源字符串和目标字符串的相应字符，根据是否需要插入、删除或替换字符来更新表格中的值。
3. 一旦表格被完全填充，最终的最小编辑距离就是表格中对应于两个字符串长度的元素D[m, n]的值，其中m和n分别是两个字符串的长度。
4. 如果需要找到实际的编辑序列，可以通过回溯从D[m, n]开始，逆向追踪到表格的起点，以确定哪些编辑操作被执行了。