填空题

特殊的编辑距离

Question

在自然语言处理的过程中，经常需要判断一个字符串和另外一个字符串之间的一个相似程度，其中常见的一个指标就是编辑距离，即一个字符串最少经过多少次“增删改”某个字符，可以变为另一个字符串。

如“abc”与“ac”的编辑距离为1，是因为在a和c中间“增加”一个b即可。如“abcd”与“axc”的编辑距离为2，是因为把“abcd”的b修改为x，然后再删除d即可，共2次操作。

但是在某种场景中，编辑距离定义为词粒度的。比如句子A “I am a coder”与句子B “hello ,  I am a singer”之间，对于句子A可以通过添加"hello"和符号",",  并替换"coder"为"singer"，共3个操作得到句子B。所以可得其基本的编辑距离为3。

在本题中，特别地，对于部分词，比如标点符号“, ”、"hello"对于句子语义的影响并不重要，这部分称之为停用词，这部分可以在匹配的过程中被跳过。比如对于句子A “I am a coder”与句子B “hello ,  I am a singer”，如果加入了停用词的影响，那编辑距离从3降到1。

所以目标是可以有选择性地跳过停用词的情况下，问最小的编辑距离是多少。