CN104008187A - 一种基于最小编辑距离的半结构化文本匹配方法 - Google Patents

Abstract

本发明属于自然语言处理领域，提出一种基于最小编辑距离的半结构化文本匹配方法。该方法包括如下步骤：一、对数据进行预处理；二、离线训练，确定对数似然率算法和左右熵算法阈值；三、结合这两种算法，在线为待评测的半结构化文本中非结构化文本抽取多词表达集合；四、利用抽取的多词表达集合，加上原评测文本中的结构化串，得到该文本的基于多词表达集合的文本表达；五、利用基于最小编辑距离的半结构化文本匹配方法，计算输入的半结构化文本和待匹配的半结构化文本的匹配度；六、以特征集合的相似度来衡量文本的匹配度，输出排序结果(Top-N)。利用本发明实施例，能够提高半结构化文本的匹配准确度，具有很大的实用价值。

Description

一种基于最小编辑距离的半结构化文本匹配方法

技术领域

本发明属于自然语言处理领域，特别涉及一种基于最小编辑距离的半结构化文本匹配方法。

背景技术

网络信息的海量增加使得信息检索成为信息获取的重要途径。基于关键词的信息检索已得到了广泛的研究和应用。但是，基于关键词在很多场合下并不能满足日益增长的各种信息获取需求。比如，个人职位搜索，在网络上有许多职位描述，当输入一个关键词时，是可以返回一些满足条件的职位信息，但是，仅凭几个关键词往往很难准确获得所需信息，更为有效的职位搜索是基于求职简历的直接搜索。即输入一份简历，通过简历信息与职位数据的全文匹配，返回与简历要求相吻合的职位信息。在相反方向，公司人才搜索也是同样的情况，需要输入一个职位要求，去和简历数据进行匹配。除了职位和人才搜索，婚介、房租等等都存在供需双方的信息匹配问题。而不论是哪一方的信息，都不是用简单的几个关键词进行描述，而是采用了一个文本进行描述，在描述文本中，可以包括结构化数据，如简历中的身高、年龄、学历等可以结构化地给出，也包含半结构甚至是非结构化的数据，比如简历中的教育和工作经历，个人兴趣，专长以及自我评价等，都可能以半结构或非结构化的方式出现。而往往在求职时，这些非结构化具有重要的作用。

于是，在这种应用中，问题的关键是文本的匹配。与此相关的文本相似度研究也有很丰富的成果，其中典型的是基于向量空间模型的文本相似度计算。其它如基于VSM的文档聚类、基于VSM的文本分类、基于VSM的信息检索等研究，在这些研究中，文本特征的选择、特征值的计算以及相似度度量是关键因素。

传统的计算文本相似度的方法主要有基于向量空间模型(VSM)夹角余弦距离文本相似度算法、基于词共现的文本相似度计算算法、基于事件的文本相似度计算算法等。但是在上述职位搜索等类型的文本匹配应用中，我们采用的是多词表达作为简历职位文本的特征，多词表达的颗粒度一般都比较大，而特征个数也比较少，存在数据很稀疏的问题，传统的基于向量空间模型的计算文本相似度的方法，不是很适用于职位搜索排序，它的计算结果很大可能为0。同时考虑到从用户的角度出发，用简历文本主动地去计算与职位文本的相似度，简历具有主动性，职位具有被动性，这与计算两平等的一般文本间的相似度的物理意义不同。

发明内容

本发明提供一种基于最小编辑距离的半结构化文本匹配方法，包含以下步骤：

一、对数据进行预处理，分别把训练和测试的半结构化文本分成两部分：结构化文本和非结构化文本，并对非结构化文本进行分词处理。

二、根据训练数据，确定对数似然率算法(LLR)和左右熵算法(LRE)的阈值，具体方法如下：

1)首先利用对数似然率(LLR)公式,在非结构化文本中抽取多词表达候选，

$\mathrm{LLR}(x,y)=2(a*\log \frac{a*N}{(a+b)(a+c)}+b*\log \frac{b*N}{(a+b)(b+d)}+c*\log \frac{c*N}{(c+d)(a+c)}+d*\log \frac{d*N}{(c+d)(b+d)})$

计算相邻单元间的score值，其中a:X与Y同时出现的频次；b:紧邻着X右边的词不是Y的频次；c:紧邻着Y左边的词不是X的频次；d:两个紧邻着的词既不是X，也不是Y的频次，即d＝N-a-b-c(N为语料集中词的总数)；按score值的大小依次构建二叉树，给定一个LLR阈值，如果某节点的score值大于阈值，则以此节点为根的二叉树除叶子节点外的每个节点就是多词表达候选；

2)利用左右熵进一步过滤基于LLR算法得到的多次表达候选，其特征在于，

其中，xy表示候选的单元，a，b分别是左接和右接候选单元xy的汉字，当给定一个左右熵阈值，大于阈值的候选确定为多词表达；

3)根据训练集中抽取的多词表达的正确率和召回率，同时确定两个算法的最佳阈值。

三、根据LLR算法和LRE算法，并利用离线训练出的LLR算法和LRE算法的阈值，在线地为每一个测试的半结构化文本中非结构化文本抽取一个多词表达集合。

四、利用上一步抽取的多词表达集合，再加上这些文本中的原结构化串，就可以得到该文本的基于多词表达集合的文本表达，用多词表达集合和结构化字符串来表征文本。

五、利用发明人提出的基于最小编辑距离(MED)的匹配度计算模型，计算输入的半结构化文本和待匹配的半结构化文本的匹配度，具体方法如下：

1)两个串之间基于MED的相似度s₁、s₂为两个符号串；

2)两个串集合R,J，R＝{r₁,r₂,...,r_i,...,r_n}、J＝{j₁,j₂,...,j_k,...,j_m}，r_i(1≤i≤n)和j_k(1≤k≤m)均为符号串，集合相似度定义为

$P(R,J)=\left\{\begin{array}{c}\frac{|R\∩J|+\underset{\∀r\∈\{R-J\}}{\mathrm{\Σ}}\mathrm{Max}\{F(r,j),\∀j\∈\{J-R\left\}\right\}}{\left|R\right|},\left|R\right|\≠0,|R-J|*|J-R|\≠0\\ 1,|R-J|=0\\ \frac{\left|J\right|}{\left|R\right|},|J-R|=0,\left|R\right|\≠0\end{array}\right.$

其中，|R|＝n，|J|＝m分别表示关键词集合R和J中关键词的个数；|R∩J|表示集合R和集合J相同的串的个数；R-J表示所有属于集合R而不属于集合J中的串组成的集合；J-R表示所有属于集合J而不属于集合R中的串组成的集合。

六、对计算出的匹配度按从大到小排序，输出排序结果(Top-N)，最靠前表示匹配度最强，最靠后表示匹配度最弱。

本发明的有益效果在于，相对于基于传统的向量空间模型中余弦距离的方法，试验结果验证了本发明在半结构化文本匹配中具有更高的准确率和召回率，具有很强的实用性。

附图说明

图1是本发明的流程图。

具体实施方式

本发明提供下面将结合附图对本发明具体实施方式进行详细说明。

图1是本发明的流程图，其中虚线表示训练部分流程走向，实现表示测试部分流程走向，包括以下步骤：

第一步：预处理。

步骤S1：把半结构化文本分成两部分：结构化文本和非结构化文本，并对非结构化文本进行分词处理。

第二步：根据训练数据，确定对数似然率算法(LLR)和左右熵算法(LRE)的阈值。

步骤S2：根据对数似然率算法抽取多词表达候选；

步骤S3：根据左右熵算法确定最终的多词表达；

步骤S4:根据F-measure值确定LLR算法和LRE算法的阈值。

第三步：抽取测试文本特征表示。

步骤S5：根据LLR算法和LRE算法，并利用训练得到的阈值，抽取测试文本非结构化部分的文本中的多词表达集合；

步骤S6：使用测试文本中结构化文本集合和抽取的多词表达集合的并集作为原半结构化文本的特征表示。

第四步：计算匹配度并输出结果。

步骤S7：利用发明人提出的基于最小编辑距离的匹配度计算模型计算两半结构化文本的匹配度；

步骤S8：对匹配度进行降序排列，输出结果。

下面将对每个步骤进行具体的说明：

步骤S1分别把训练和测试的半结构化文本分成两部分：结构化文本和非结构化文本，并对结构化文本进行分词处理。

步骤S2在非结构化文本抽取多词表达，利用对数似然率(LLR)公式

$\mathrm{LLR}(x,y)=2(a*\log \frac{a*N}{(a+b)(a+c)}+b*\log \frac{b*N}{(a+b)(b+d)}+c*\log \frac{c*N}{(c+d)(a+c)}+d*\log \frac{d*N}{(c+d)(b+d)})$

计算相邻单元间的score值，其中a:X与Y同时出现的频次；b:紧邻着X右边的词不是Y的频次；c:紧邻着Y左边的词不是X的频次；d:两个紧邻着的词既不是X，也不是Y的频次，即d＝N-a-b-c(N为语料集中词的总数)；按score值的大小依次构建二叉树，给定一个LLR阈值，如果某节点的score值大于阈值，则以此节点为根的二叉树除叶子节点外的每个节点就是多词表达候选。

步骤S3利用左右熵进一步过滤基于LLR算法得到的多次表达候选，其特征在于，

其中，xy表示候选的单元，a，b分别是左接和右接候选单元xy的汉字，当给定一个左右熵阈值，大于阈值的候选确定为多词表达。

步骤S4根据训练集中抽取的多词表达的正确率和召回率，同时确定两个算法各自的最佳阈值。

步骤S5根据LLR算法和LRE算法，并利用离线训练出的LLR算法和LRE算法的阈值，在线地为每一个测试的半结构化文本中非结构化文本抽取一个多词表达集合。

步骤S6利用上一步抽取的多词表达集合，再加上这些文本中的原结构化串，就可以得到该文本的基于多词表达集合的文本表达，用多词表达集合和结构化字符串来表征文本。

步骤S7利用发明人提出的基于最小编辑距离的匹配度计算模型，计算输入的半结构化文本和待匹配的半结构化文本的匹配度，具体方法如下：

1)两个串之间基于MED的相似度s₁、s₂为两个符号串；

2)两个串集合R,J，R＝{r₁,r₂,...,r_i,...,r_n}、J＝{j₁,j₂,...,j_k,...,j_m}，r_i(1≤i≤n)和j_k(1≤k≤m)均为符号串，集合相似度定义为

$P(R,J)=\left\{\begin{array}{c}\frac{|R\∩J|+\underset{\∀r\∈\{R-J\}}{\mathrm{\Σ}}\mathrm{Max}\{F(r,j),\∀j\∈\{J-R\left\}\right\}}{\left|R\right|},\left|R\right|\≠0,|R-J|*|J-R|\≠0\\ 1,|R-J|=0\\ \frac{\left|J\right|}{\left|R\right|},|J-R|=0,\left|R\right|\≠0\end{array}\right.$

其中，|R|＝n，|J|＝m分别表示关键词集合R和J中关键词的个数；|R∩J|表示集合R和集合J相同的串的个数；R-J表示所有属于集合R而不属于集合J中的串组成的集合；J-R表示所有属于集合J而不属于集合R中的串组成的集合。

步骤S8对计算出的匹配度按从大到小排序，输出排序结果，最靠前表示匹配度最强，最靠后表示匹配度最弱。

以上结合附图对所提出的基于最小编辑距离的半结构化文本匹配方法的具体实施方式进行了阐述。通过以上实施方式的描述，所属领域的一般技术人员可以清楚的了解到本发明可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以计算机软件产品的形式体现，该软件产品存储在一个存储介质中，包括若干指令用以使得一台或多台计算机设备执行本发明各个实施例所述的方法。

依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。综上所述，本说明书内容不应理解为对本发明的限制。

以上所述的本发明实施方式，并不构成对发明保护范围的限定。任何在本发明的精神和原则之内所作的修改、等同替换和改进等，均应包含在本发明的保护范围之内。

Claims (5)

1.一种基于最小编辑距离的半结构化文本匹配方法，其特征在于，包括以下步骤：

⑴对数据进行预处理，把半结构化文本分成两部分：结构化文本和非结构化文本，并对非结构化文本进行分词处理；

⑵离线训练：根据对数似然率算法(LLR)和左右熵算法(LRE)，抽取训练数据的非结构化文本部分中的多词表达，来确定对数似然率算法和左右熵算法的阈值；

⑶根据LLR算法和LRE算法，并利用离线训练出的LLR算法和LRE算法的阈值，在线地为每一个待测试的半结构化文本中非结构化文本抽取一个多词表达集合；

⑷利用上一步抽取的多词表达集合，再加上这些文本中的原结构化串，就可以得到该文本的基于多词表达集合的文本表达，用多词表达集合和结构化字符串来表征文本；

⑸利用基于基于最小编辑距离的半结构化文本匹配方法，计算输入的半结构化文本和待匹配的半结构化文本的相似度(匹配度)；

⑹以特征集合的相似度来衡量文本的相似度(匹配度)，对计算出的匹配度按从大到小排序，输出排序结果(Top-N)，最靠前表示匹配度最强，最靠后表示匹配度最弱。

2.根据权利要求1所述的一种基于最小编辑距离的半结构化文本匹配方法中，训练对数似然率算法(LLR)的阈值特征在于，利用对数似然率(LLR)公式

$\mathrm{LLR}(x,y)=2(a*\log \frac{a*N}{(a+b)(a+c)}+b*\log \frac{b*N}{(a+b)(b+d)}+c*\log \frac{c*N}{(c+d)(a+c)}+d*\log \frac{d*N}{(c+d)(b+d)})$

计算相邻单元间的score值，其中a:X与Y同时出现的频次；b:紧邻着X右边的词不是Y的频次；c:紧邻着Y左边的词不是X的频次；d:两个紧邻着的词既不是X，也不是Y的频次，即d＝N-a-b-c(N为语料集中词的总数)；按score值的大小依次构建二叉树，给定一个LLR阈值，如果某节点的score值大于阈值，则以此节点为根的二叉树除叶子节点外的每个节点就是多词表达候选。

3.根据权利要求1所述的利用左右熵进一步过滤基于LLR算法得到的多次表达候选，其特征在于，

其中，xy表示候选的单元，a，b分别是左接和右接候选单元xy的汉字，当给定一个左右熵阈值，大于阈值的候选确定为多词表达。

4.根据权利要求1所述的确定对数似然率算法和左右熵算法的阈值，其特征在于，根据训练集中抽取的多词表达的正确率和召回率，同时确定两个算法的最佳阈值。

5.根据权利要求1所述的一种基于最小编辑距离的半结构化文本匹配方法，其特征在于，以最小编辑距离为基础定义两个文本特征集合的相似度模型步骤为：

1)两个串之间基于MED的相似度s₁、s₂为两个符号串；

2)两个串集合R,J，R＝{r₁,r₂,...,r_i,...,r_n}、J＝{j₁,j₂,...,j_k,...,j_m}，r_i(1≤i≤n)和j_k(1≤k≤m)均为符号串，集合相似度定义为

$P(R,J)=\left\{\begin{array}{c}\frac{|R\∩J|+\underset{\∀r\∈\{R-J\}}{\mathrm{\Σ}}\mathrm{Max}\{F(r,j),\∀j\∈\{J-R\left\}\right\}}{\left|R\right|},\left|R\right|\≠0,|R-J|*|J-R|\≠0\\ 1,|R-J|=0\\ \frac{\left|J\right|}{\left|R\right|},|J-R|=0,\left|R\right|\≠0\end{array}\right.$

其中，|R|＝n，|J|＝m分别表示关键词集合R和J中关键词的个数；|R∩J|表示集合R和集合J相同的串的个数；R-J表示所有属于集合R而不属于集合J中的串组成的集合；J-R表示所有属于集合J而不属于集合R中的串组成的集合。