在自然语言处理的过程中,经常需要判断一个字符串和另外一个字符串之间的一个相似程度,其中常见的一个指标就是编辑距离,即一个字符串最少经过多少次“增删改”某个字符,可以变为另一个字符串。 如“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。 所以目标是可以有选择性地跳过停用词的情况下,问最小的编辑距离是多少。-笔试面试资料

这是qklbishe.com第5607 篇笔试面试资料
提供答案分析,通过本文《在自然语言处理的过程中,经常需要判断一个字符串和另外一个字符串之间的一个相似程度,其中常见的一个指标就是编辑距离,即一个字符串最少经过多少次“增删改”某个字符,可以变为另一个字符串。
如“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。
所以目标是可以有选择性地跳过停用词的情况下,问最小的编辑距离是多少。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

在自然语言处理的过程中,经常需要判断一个字符串和另外一个字符串之间的一个相似程度,其中常见的一个指标就是编辑距离,即一个字符串最少经过多少次“增删改”某个字符,可以变为另一个字符串。
如“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。
所以目标是可以有选择性地跳过停用词的情况下,问最小的编辑距离是多少。

C/C++

在自然语言处理的过程中,经常需要判断一个字符串和另外一个字符串之间的一个相似程度,其中常见的一个指标就是编辑距离,即一个字符串最少经过多少次“增删改”某个字符,可以变为另一个字符串。                  如“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。                  所以目标是可以有选择性地跳过停用词的情况下,问最小的编辑距离是多少。 talkking

//dp求编辑裸题
#include<bits/stdc++.h>

using namespace std;
int dp[1001][1001];
vector<string>d,a,b,anew,bnew;
unordered_map<string,int>mp;
int levenshtein(vector<string> a ,vector<string> b)//编辑距离O(n^2)
{
    dp[0][0]=0;
    for(int i=1;i<=a.size();i++) dp[i][0]=i;
    for(int j=1;j<=b.size();j++) dp[0][j]=j;
    for(int i=1;i<=a.size();i++)
        for(int j=1;j<=b.size();j++){
           dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
           if(a[i-1]!=b[j-1]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
           else dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
        }
    return dp[a.size()][b.size()];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string disableword,s1,s2;
    getline(cin,disableword);
    stringstream ss;
    ss<<disableword;
    while(ss>>disableword){
        d.emplace_back(disableword);
    }
    getline(cin,s1);
    ss.clear();
    ss.str("");
    ss<<s1;
    while(ss>>s1){
        a.emplace_back(s1);
    }
    getline(cin,s2);
    ss.clear();
    ss.str("");
    ss<<s2;
    while(ss>>s2){
        b.emplace_back(s2);
    }
    for(int i=0;i<d.size();i++)
        mp[d[i]]=1;
    for(int i=0;i<a.size();i++)
        if(!mp[a[i]])
           anew.emplace_back(a[i]);
    for(int i=0;i<b.size();i++)
        if(!mp[b[i]])
           bnew.emplace_back(b[i]);
    cout<<levenshtein(anew,bnew)<<endl;
    return 0;
}

今天 11:21:25 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 在自然语言处理的过程中,经常需要判断一个字符串和另外一个字符串之间的一个相似程度,其中常见的一个指标就是编辑距离,即一个字符串最少经过多少次“增删改”某个字符,可以变为另一个字符串。 如“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。 所以目标是可以有选择性地跳过停用词的情况下,问最小的编辑距离是多少。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情