用于匹配实体的系统和方法及其中使用的同义词群组织器

摘要

提供了一种用于管理至少一个同义词群的方法，其中，该方法包括以下步骤：在同义词群包括不止一个同义词时，计算在同义词群的所有同义词的每两个同义词之间指示这两个同义词相互相似程度的相似性值。本发明还提供同义词群组织器、使用同义词群组织器的匹配系统及其方法。

说明书

技术领域

本发明涉及数据采集和分析领域，并且具体地说，涉及用于确定匹配系统收到的实体是否与以前收到的实体匹配的方法及系统，以及系统中使用的组件。这些组件包括用于组织同义词的同义词群组织器。本发明还涉及用于实现如上所述系统、方法及其组件的计算机程序和计算机程序产品。

背景技术

在过去5-10年内，“搜索”已变成在全球的人们之间在数字界的一个现象。在典型的搜索情况中，短的搜索查询用于查找大或至少更大的文档。典型的示例是因特网搜索引擎或安装在库计算机上以便搜索库中存储的文章或书籍的搜索引擎。

如上所述的传统搜索情形与典型匹配情形不同。在匹配情形中，两个或更多个用户将数据输入到系统中以便查明该数据是否与其它用户输入的数据匹配。也就是说，与搜索情形不同，输入信息到系统的所有用户都关注查找匹配信息。在搜索情形中，仅录入搜索查询的用户关注匹配结果，搜索查询在典型情况下是一个或多个关键词的形式。从技术角度而言，匹配系统与搜索引擎不同，至少表现在匹配系统要索引进入的“查询”，这是因为这些查询也是以前或以后收到的查询的潜在匹配。为区分“匹配查询”和常规搜索查询，在“匹配查询”中传送到匹配系统的数据将在本文档通篇中称为“实体”。

匹配系统能够在许多不同类型的匹配服务中使用。此类服务的示例有在线找工作/招聘服务、电子商务服务及约会服务。

Ericsson以前提交的专利申请PCT/EP2008/066617公开了此类匹配系统，该匹配系统能够确定从第一用户的客户端装置收到的第一实体是否与在每个实体与一个或多个索引点相关联的索引中索引的多个实体至少之一匹配。

实体例如可以是文本文件、图像文件、音频文件或具有能够“转换”成词或符号的其它序列的任何其它类型的数据，而词或符号的其它序列能够用作索引点，表征与其相关联的实体。

PCT/EP2008/066617公开了在一个单一操作中执行实体插入和搜索的方式，以提高系统用于的匹配服务的用户感知质量以及降低在匹配系统中所需计算容量。它也减少了在系统中查找所有潜在匹配所需的时间。

在现有技术的匹配系统中，一实体匹配另一实体意味着这些实体具有共同的至少一个索引点，即，在索引中存在两个实体均相关联的至少一个索引点。然而，当前匹配系统在用于确定实体是否应与某个索引点相关联的准则上是严格的。具体而言，当前匹配系统不能将搜索实体与包含搜索实体中存在的词的同义词的实体相关联。换而言之，当前匹配系统不能提供实际上与搜索实体有关的更多实体。例如，在搜索实体包含表述“整理房间”时，根据当前匹配系统，包含“整理房间”的相似含意的“家居清洁”的实体不能被视为是匹配实体，这使得当前匹配系统较不适用。

另外，词的实际含意在演进，现有词的新含意由于信息通信，特别是因特网在全球的使用原因而产生。匹配系统应足够灵活以反映词的含意的动态更改。

因此，与根据现有技术的匹配系统相关联的一个问题是如何提供具有与搜索实体相似的含意、但未与匹配的实体包含搜索实体的相同词的更多实体，以提高系统用于的匹配服务的用户感知质量。另一问题是如何动态更新匹配系统以反映词的演进含意。

发明内容

本发明的目的是解决或至少减轻匹配系统的上述问题的至少之一。

此目的通过用于管理至少一个同义词群的方法而得以实现，每个同义词群包括第一部分和第二部分，且每个同义词群包括至少一个同义词，第一部分包括是代表用于同义词群的特定类别的词的同义词，并且第二部分包括同义词群的所有其它同义词，其中，该方法包括以下步骤：在同义词群包括不止一个同义词时，计算在同义词群的所有同义词的每两个同义词之间指示这两个同义词相互相似程度的相似性值。

根据本发明的一实施例，计算每两个同义词之间相似性值的步骤包括以下步骤：为同义词群中的每个同义词确定页面分级值；基于同义词群的两个同义词的页面分级值，计算在这两个同义词之间的初始相似性值；以及将这两个同义词之间的初始相似性值设置为在同义词群的每两个同义词之间的相似性值。

根据本发明的一实施例，计算在同义词群中两个同义词之间的相似性值的步骤包括以下步骤：基于在会话时段内恰巧使用两个同义词的第二同义词时使用这两个同义词的第一同义词的条件概率并基于在会话时段内恰巧使用第一同义词时使用第二同义词的条件概率，计算这两个同义词之间的动态相似性值；以及将这两个同义词之间的动态相似性值设置为在每两个同义词之间的相似性值。

根据本发明的一实施例，计算相似性值的步骤包括基于在两个同义词之间的初始相似性值和在这两个同义词之间的动态相似性值，设置在同义词群中两个同义词之间的相似性值的步骤。

根据本发明的另一方面，提供了一种同义词群组织器，包括：至少一个同义词群，每个同义词群包括第一部分和第二部分，且每个同义词群包括至少一个同义词，第一部分包括是代表用于同义词群的特定类别的词的同义词，并且第二部分包括同义词群的所有其它同义词，其中，在同义词群包括不止一个同义词时，所述同义词群包括在同义词群中所有同义词的每两个同义词之间指示所述两个同义词相互相似程度的相似性值；以及适用于执行本发明的方法的管理引擎。

根据本发明的另一方面，提供了一种匹配系统，包括：至少一个同义词群，每个同义词群包括第一部分和第二部分，且每个同义词群包括至少一个同义词，第一部分包括是代表用于同义词群的特定类别的词的同义词，并且第二部分包括同义词群中的所有其它同义词，其中，在同义词群包括不止一个同义词时，同义词群包括同义词群中所有同义词的每两个同义词之间指示所述两个同义词相互相似程度的相似性值；以及与至少一个同义词群的一个或多个同义词群相关联的至少一个实体。

根据本申请的又一方面，提供了一种用于添加新实体到匹配系统中的方法，所述方法包括以下步骤：将新实体预处理成至少一个词；以及对于新实体的每个词：搜索包含对应于词的同义词的同义词群；以及将新实体与搜索到的同义词群相关联。

根据本发申请的又一方面，提供了一种用于确定从客户端装置收到的第一实体是否与匹配系统中的至少一个实体匹配的方法，所述方法包括以下步骤：将第一实体预处理成至少一个词；对于第一实体的每个词：搜索包含对应于所述词的同义词的同义词群；以及搜索与搜索到的同义词群相关联的实体，并且创建词的相关联实体集合，其中每个搜索到的实体作为词的相关联实体集合的项目；通过合并第一实体的每个词的相关联实体集合，为第一实体创建合并的实体集合，其中，合并的实体集合的每个项目是独特实体，并且每个项目包含用于对在每个词的所有相关联实体集合中出现的独特实体的数量进行计数的计数器；以及如果合并的实体集合包含计数器的值大于阈值的任何实体项目，则确定从客户端装置收到的第一实体匹配，否则确定从客户端实体收到的第一实体不匹配。

通过使用同义词群组织器组织词，带有相似含意的所有词能够编组到一个同义词群中。当此类同义词群与匹配系统结合使用时，可能在基于同义词群形成关联时在带有相似含意的实体之间形成链接，因此，可能提供带有与搜索实体相似含意的更多匹配实体。

另外，使用同义词群的两个同义词之间的相似性值，可能提供指示这两个同义词相互相似程度的量。还可能的是，基于在同义词群的两个同义词之间的相似性值，计算两个实体之间的相似性，这使得提供搜索实体的匹配的实体的适当分级成为可能。

基于使用同义词群组织器的用户行为统计，可使用贝叶斯定理动态修改同义词群的两个同义词之间的相似性值。通过动态更新同义词群的两个同义词之间的相似性值，可能的是，更准确地反映在两个同义词之间的相似性，并且还可能的是，基于在同义词群的每两个同义词之间的相似性值更新同义词群中的同义词。

在下文的描述中和在随附权利要求书中将描述根据本发明的同义词群组织器和匹配系统的更多有利特征。

此外，本发明涉及用于促使服务器节点执行如上所述的那些方法的计算机程序和包含其上存储有此类计算机程序的存储媒体的计算机程序产品。

附图说明

结合附图阅读时，将从本发明的示范实施例的以下详细描述中更容易理解本发明的目的、优点和效果及特征，其中：

图1示出根据本发明的一实施例的示范同义词群组织器；

图2a和2b以示意图方式分别示出根据本发明的实施例，在同义词群组织器中同义词群的结构；

图3示出流程图，该流程图示出根据本发明的一实施例，用于在同义词群组织器的同义词群中两个同义词之间计算初始相似性值的方法；

图4示出在图3所示方法中使用的同义词图表；

图5示出流程图，该流程图示出根据本发明的一实施例，用于保持在同义词群组织器的同义词群中两个同义词之间的相似性值的方法；

图6示出流程图，该流程图示出根据本发明的一实施例，用于从同义词群中删除不相关同义词的方法；

图7示出流程图，该流程图示出根据本发明的一实施例，用于将新同义词添加到同义词群中的方法；

图8示出根据本发明的一实施例的示范匹配系统；

图9示出流程图，该流程图示出根据本发明的一实施例，用于将新实体添加到匹配系统中的方法；

图10示出流程图，该流程图示出根据本发明的一实施例，用于确定从客户端装置收到的第一实体是否与匹配系统中至少一个实体匹配的方法；

图11示出流程图，该流程图示出根据本发明的一实施例，用于计算在两个匹配的实体之间相似性的方法；以及

图12示出框图，该框图示出用于实现本发明的实施例的典型服务器；以及 

图13示出保存或携带由服务器使用的程序代码的存储器单元的示意图。

具体实施方式

虽然本发明包括各种修改和备选构造，但在图形中示出并且将在下文详细描述本发明的实施例。然而，要理解的是，特定的描述和图形无意将本发明限为公开的特定形式。相反，要求权利的发明的范围要包括落入如随附权利要求书表述的本发明的范围内的其所有修改和备选构造。

图1示出根据本发明的一实施例的示范同义词群组织器100。同义词群组织器100在此实施例中是服务器主机，并且包括至少一个同义词群(101 -103)和用于管理同义词群组织器100的这些同义词群的管理引擎105。

这些同义词群可存储在同义词群组织器100中的数据库108中，并且实际上，同步词群组织器中同义词群的数量取决于在同义词群组织器中使用的词的语言，典型情况下，在同义词群组织器中使用的词是英文时，同义词群组织器能够包括一万个同义词群。

图2a示出根据本发明的一实施例，在同义词群组织器中同义词群的结构。如图2a所示，每个同义词群101-103包括第一部分和第二部分，下文在描述中将第一部分称为头部110，并且下文在描述中将第二部分称为同义词指示器部分120。头部110包括表示同义词群的特定类的最常用词，而同义词指示器部分120包括同义词群的头部中词的所有其它同义词。视头部110中词的含意而定，同义词指示器部分120可不必包括任何同义词。例如，在头部110中带有词“北京”的同义词群101在同义词指示器部分120中不包括任何同义词，并且在头部110中带有词“清洁”的同义词群102此处在同义词指示器部分120中包括6个同义词。

可存在在同义词指示器部分120中组织同义词的多种方式。在一种方式中，同义词指示器部分120能够包括同义词列表，每个同义词作为同义词列表的一个项目。在另一种方式中，同义词指示器部分120能够包括其中每个项目指向同义词的同义词指示器列表。在又一种方式中，同义词指示器部分120能够包括链接的列表，通过将一个同义词与另一同义词链接而将所有同义词链接在一起。应注意的是，本发明只要求对应于头部中的词的所有同义词包括在同义词指示器部分120中，并且在同义词指示器部分120中组织这些同义词的所有方式都在本发明的保护范围内。

图2b以示意图方式示出同义词群的另一结构。根据语义定义，词A是词B的同义词意味着词A具有与词B完全或几乎相同的含意，词A是词B的上位词意味着词A具有比词B更广的含意，并且词A是词B的下位词意味着词A具有比词B更具体的含意。根据本申请的一实施例，在描述通篇中使用的术语“同义词”应包括语义定义的“同义词”、“上位词”和“下位词”的所有方式。在图2b中，同义词群的结构更反映词的语义定义，详细地说，同义词指示器部分120进一步分成三个部分：同义词部分，包括是带有与头部中的词相似含意的词的同义词（对应于语义定义的术语“同义词”）；超类部分，包括是包含与头部中的词相似含意的根源词（parent words）的同义词（对应于语义定义的术语“上位词”）；以及子类部分，包括是与头部中的词相似含意的扩展词的同义词（对应于语义定义的术语“下位词”）。普林斯顿大学所著的著名同义词词典WordNet（有关详情，请访问http://wordnet.princeton.edu/）具有与结合图2a和2b所定义的那些内容相似的结构，并且根据本发明的一实施例，同义词群组织器的那些同义词群从此类同义词词典推导。

有多种方式来选择同义词之中的词作为同义词群的头部110中的词。例如，能够基于具体的服务或应用上下文选择此类词，例如，如果它是象清洁等日常生活有关的服务，则使用例如“清洁”等最常见的服务类别名称作为头部中的词；如果它是位置，则使用例如“Kista”等位置的最常见名称作为头部中的词；如果它是商品或产品，则也使用例如“移动电话”等最常见的名称作为头部中的词。在另一种方式中，头部中的词应该是根据同义词群组织器100的用户数据的历史统计出现或呈现次数最多的名称。一种方式可以是计算同义词群中每个同义词的页面分级(PR)值（这将在下面的描述中详细描述），并且选择同义词群中具有最高PR值的同义词作为头部中的词。

可基于字母表顺序组织同义词群，典型情况下从同义词群的头部中词的“a”开始。应注意的是，同义词群的所有其它组织方式能够使每个同义词群在同义词群组织器内可搜索，此类组织方式便均在本申请的保护范围内。

为给出有关同义词群中两个同义词相互相似程度的计量，每个同义词群包括在同义词群的所有同义词的每两个同义词之间的，所述相似性值指示这两个同义词相互相似程度。同义词群组织器基于这些相似性值管理同义词群的同义词。

再参照图1，管理引擎105负责管理同义词群(101-103)，即，对于每个同义词群计算相似性值，在同义词群组织器的实际使用期间更新相似性值，在同义词群组织器的实际使用期间管理每个同义词群的要素。在下面的描述中结合图3-7详细描述管理引擎105为计算相似性值和管理同义词群而执行的方法。

应理解的是，同义词群组织器100的所示结构只是示范，并且同义词群组织器能够以许多其它方式实现。例如，用于存储同义词群的数据库108能够在专用服务器节点中被托管，并且管理引擎105位于与托管数据库108的服务器通信的另一服务器中，以便对同义词群进行的所有过程能够由管理引擎105执行。

存在多种方式用来计算在同义词群中两个同义词之间的相似性值。在最初根据同义词词典创建同义词群组织器的同义词群时，根据本发明的一实施例，在同义词群中两个同义词之间的相似性值能够设成在同义词群中两个同义词之间的初始相似性值。

图3示出流程图，所述流程图示出根据本发明的一实施例、由管理引擎105执行的用于计算同义词群组织器的同义词群中两个同义词之间的初始相似性值的页面分级方法300。

页面分级方面300是基于以下原理：首先，如果两个词A和B是同义词，则在描述其定义中必须有多个相同词，或者两个词A和B必须经常一起使用以定义某一其它第三词；其次，在知道A和B是同义词时，同时如果B在A的定义中存在，这意味着A引用B，则B应包括A的页面分级值。

此方法300从步骤S310开始，其中，从同义词词典加载同义词群中每个同义词的定义。例如，对于图1和2的同义词群102，每个同义词的定义如下：

能够看到，在这些上面提及的定义中，同义词群中的同义词频繁地用于定义相同群中的其它同义词。

因此，在步骤S320中，从同义词定义中推导同义词图表，所述同义词图表包括相同同义词群中同义词之间关系链接。如果B出现在A的定义中，则存在从同义词A指向同义词B的定向链接，并且相应地，B的页面分级值应包括A的页面分级值。图4示出根据这些上面提及的定义的同义词群102的同义词图表。例如，由于同义词“清洁”出现在同义词“整洁”、“打扫房屋”、“家政”、“打扫”和“洗”的定义中，因此，存在从同义词“整洁”、“打扫房屋”、“家政”、“打扫”和“洗”指向同义词“清洁”等的定向链接。应理解的是，同义词图表不得理解为要向用户显示的可见图表。

在步骤S330中，每个同义词的页面分级值的定义是基于在此同义词的定义中出现的所有同义词的页面分级值，详细地说，同义词的页面分级值定义为：

其中，W是被定义的同义词；T1，...Tn是在相同同义词群中同义词W的定义中出现的同义词；PR(T1)，...PR(Tn)分别是同义词T1，...Tn的页面分级值；C(T1)，...C(Tn)分别是在同义词T1，...Tn的定义中出现的相同同义词群中其它同义词的数量；以及d是设在0和1之间的阻尼因数。在一实施例中，阻尼因数d设为0.15，以便每个同义词的页面分级值能够在下一步骤S340中稳定地收敛到准确的值。

例如，对于图1和2的同义词群102，同义词群的每个同义词的页面分级值能够定义为：

详细地说，同义词“清洁”出现在同义词“整洁”、“打扫房屋”、“家政”、“打扫”和“洗”的定义中，因此，“清洁”的页面分级值包含同义词“整洁”、“打扫房屋”、“家政”、“打扫”和“洗”的页面分级值。另外，根据这些同义词的上述定义，在“整洁”、“打扫房屋”、“家政”、“打扫”和“洗”的定义中出现的其它同义词的数量分别是1、2、1、1和2，这意味着C(整洁)、C(打扫房屋)、C(家政)、C(打扫)和C(洗)的值分别设为1、2、1、1和2。而且相同的分析也适用于其它同义词。

随后在步骤S340中，将未知页面分级值的初始值设为1，并且迭代定义每个同义词的页面分级值多次。迭代越多，结果就越准确。根据本申请的一实施例，迭代的次数设为log2(N)，其中，N是同义词群中同义词的数量。例如，对于同义词群102，N=7，并且迭代的次数设为3。下面的表1显示在迭代期间同义词群102的每个同义词的页面分级值。

表1：迭代期间每个同义词的页面分级值 

从表1中能够看到，在3轮迭代后，这些页面分级几乎收敛到准确的值。

在每个同义词的页面分级值已收敛到准确的值后，在步骤S350中，基于这两个同义词A和B的页面分级值计算在两个同义词A、B之间的初始相似性值，详细地说，通过如下等式计算初始相似性值：

其中，A、B是同义词群的同义词；PR(A)和PR(B)分别是同义词A和B的页面分级值，以及Sim_i(A,B)是在两个同义词A与B之间的初始相似性值。

表2显示基于上面提及的计算，在同义词群102中每两个同义词之间的初始相似性值。

可选的是，如果同义词群的结构如图2b所示，即，同义词群的同义词指示器部分120进一步分成同义词部分、超类部分和子类部分，则页面分级方法300能够还包括步骤S360，以通过为头部、同义词部分、超类部分和子类部分中呈现的同义词赋予不同权重W来改进同义词群中两个同义词A与B之间的初始相似性值Sim_i(A,B)。详细地说，还将同义词群中两个同义词A与B之间的初始相似性值改进为：

其中，w(A)和w(B)分别是同义词A与B的权重因数，以及

对于属于头部的同义词，w=0；

对于属于同义词部分的同义词，w=0；

对于属于超类部分的同义词，w=0.2；以及

对于属于子类部分的同义词，w=0.2。

在同义词群组织器100已被创建后，在典型情况下，它用在匹配系统中，并且匹配系统能够收集使用该同义词群组织器的用户行为统计。基于相同同义词群中两个同义词的使用的用户行为统计，能够动态调整在这两个同义词之间的相似性值。例如，如果用户在短时隙内一起搜索“家政”和“打扫房屋”的概率十分高，则它意味着“家政”和“打扫房屋”十分相似，并且在它们之间的对应相似性值应很高；并且如果用户一起搜索“洗”和“整洁”的概率在短时隙内比较低，则它意味着它们不是很相关，并且它们之间的对应相似性值应很低。

能够通过贝叶斯定理计算该概率。在贝叶斯定理中，在有新证据的条件下，能够通过以下方式调整概率：

其中

H表示特定假设，这可以是或不是某一零假设。

P(H)被称作在新证据E变得可用之前推断的H的先验概率。

P(E|H)被称作如果假设H恰巧为真时看到证据E的条件概率。对于固定的E，在它被视为假设H的函数时，它也被称作似然函数。

P(E)被称作E的边缘概率；在所有可能假设下见证新证据E的先验概率。它能够计算为互斥假设的任何完全集的所有概率与对应条件概率的积的总和：

P(H|E)被称作在给定E的条件下H的后验概率。

在同义词群中两个同义词之间的动态相似性值能够基于这两个同义词的使用统计、根据贝叶斯定理来计算。基于在会话时段内恰巧使用同义词B时使用同义词A的条件概率并基于在会话时段内恰巧使用同义词A时使用同义词B的条件概率，能够计算两个同义词A与B之间的动态相似性值：

其中，Sim_m(A,B)是两个同义词A与B之间的动态相似性值；P(A|B)是在会话时段内恰巧使用同义词B时使用同义词A的条件概率；以及P(B|A)是在会话时段内恰巧使用同义词A时使用同义词B的条件概率。会话时段设为短时隙。典型情况下，会话时段能够设成在3秒到30分钟的范围。在一实施例中，会话值设成30秒。

表3和4基于在我们的实验期间收集的一些使用统计显示在同义词群102中两个同义词之间的条件概率和动态相似性值。

随着匹配系统和同义词群组织器的继续使用，用户行为统计的量将持续增长，在两个同义词之间的相似性值更加取决于这两个同义词的使用统计，也就是说，在同义词群中两个同义词之间的动态相似性值相比初始相似性值对两个同义词之间相似性值有更大影响。

同义词群中两个同义词之间的相似性值应受初始相似性值和动态相似性值两者影响。根据本发明的一实施例，相似性值能够设成：

其中，Sim_i(A,B)是两个同义词A与B之间的初始相似性值，Sim_m(A,B)是两个同义词A与B之间的动态相似性值；以及q是调整因数，其值在0到1之间。

调整因数q随着匹配系统所收集的用户使用统计的量的增大而降低，q的初始值设成1，并且q的最小最终值设成0，能够基于使用同义词群组织器的用户行为统计的量手动配置q。也就是说，在包括同义词群组织器的匹配系统刚投入实践时，相似性值很大程度上是基于初始相似性值，并且调整因数q设成1。然而，在匹配系统已实践很长时间并且收集了足够的使用统计时，动态相似性值将对相似性值影响最大，并且调整因数q最终设成0。

图5示出流程图，该流程图示出根据本发明的一实施例，由管理引擎105执行的用于保持在同义词群组织器的同义词群中两个同义词之间的相似性值的方法500。

该方法500从步骤S510开始，其中收集匹配系统的使用统计，尤其是同义词群组织器的使用统计。随后，在步骤S520中，分析使用统计以便为同义词群组织器的每个同义词群中的所有同义词推导同义词A相对于同义词B的条件概率P(A|B)。在步骤S530中，基于在步骤S520中推导的条件概率P(A|B)和上面提及的等式(6)，计算两个同义词之间的动态相似性值。随后，过程继续到步骤S540，其中基于使用统计的量确定调整因数q。在步骤S550中，基于前面确定的初始相似性值、动态相似性值和调整因数，根据上面提及的等式(7)，确定同义词群中两个同义词之间的相似性值。

应注意的是，在对匹配系统所收集的使用统计进行分析时，不但推导同义词A相对于相同同义词群的同义词B的条件概率P(A|B)，而且也推导同义词A相对于不同同义词群的同义词B的条件概率P(A|B)。如果来自不同同义词群的两个同义词A和B频繁地在短的时隙内一起使用，也就是说，同义词A相对于不同同义词群的同义词B的条件概率P(A|B)十分高，则这两个同义词A和B应具有相似的含意，并且它们应放在相同同义词群中。另一方面，如果一个同义词与群中的所有其它同义词之间的相似性值太低，这意味着此同义词可能与该同义词群的含意不是很相关，因此，应将它从该同义词群中逐出。

图6示出根据本发明的一实施例，由管理引擎105执行的用于从同义词群中删除不相关同义词的方法600。此方法600从步骤S610开始，其中从同义词群中选择同义词A。随后在步骤S620中，获得在同义词A与所有其它同义词之间的相似性值。应注意的是，这些相似性值能够根据如前面所述的任何方法计算。在步骤S630中，同义词A的平均相似性值计算为：

其中，M是同义词群中同义词的数量，Bj是同义词群中的同义词。应注意的是，Sim(A, A)的值定义为1。

过程继续到步骤S640，其中比较在步骤S630中计算得到的同义词A的平均相似性值和第一阈值。如果该平均相似性值低于第一阈值（从0到1的范围，尤其是取值03），则在步骤S650中从同义词中删除此同义词，并随后继续到步骤S660。在步骤S660中，确定同义词群中是否仍有其它同义词要检查。如果留有同义词要检查，则此方法继续到步骤S670以从该同义词群中选择另一同义词作为同义词A，并且重复步骤S620到S660的过程。在已完全检查同义词群的所有同义词时，随后结束方法600的过程。

应注意的是，如果在步骤S650中从同义词群中删除的同义词A是头部的同义词，则选择同义词群的同义词指示器部分中带有最高PR值或平均相似性值的同义词作为头部的同义词。而且可选的是，如果该同义词A也是第二同义词群的同义词，则同义词群中的所有其它同义词能够移到第二同义词群。

图7示出根据本发明的一实施例，由管理引擎105执行的用于添加新同义词到同义词群的方法700。此方法700从步骤S710开始，其中，基于使用统计，根据等式(6)计算在新同义词NW与同义词群SG的所有同义词之间的动态相似性值。在步骤S720中，将在新同义词NW与同义词群SG之间的平均相似性值Sim(NW, SG)计算为：

其中，M是同义词群SG中同义词的数量，Bj是同义词群SG中的同义词。

在步骤S730中，确定在新同义词NW与同义词群SG之间的平均相似性值Sim(NW, SG)是否高于第二阈值（从0到1的范围，尤其是取值0.6）。如果平均相似性值Sim(NW, SG)高于第二阈值，则在步骤S740中，将新同义词NW添加到同义词群SG中，以在步骤S710中获得的动态同义词值作为在新添加的同义词与同义词群中所有其它同义词之间的相似性值。

应注意的是，要添加到同义词群中的新同义词NW可已经属于另一同义词群，或者不属于任何同义词群。然而，在添加此类新同义词到同义词群中时，不必从该同义词所属的以前同义词群中删除此类同义词。也就是说，可允许一个同义词出现在多个同义词群中，并且还可能的是，两个同义词能够均出现在不同同义词群中。

已在上面描述同义词群组织器的详细结构。在下述内容中，将详细描述根据本发明的一实施例、同义词群组织器结合用于管理实体的匹配系统的使用。如前面所述，实体例如可以是文本文件、图像文件、音频文件或具有能够“转换”成词或符号的其它序列的属性的任何其它类型的数据，而词或符号的其它序列能够用作索引点，表征与其相关联的实体。

图8示出根据本发明的一实施例的示范匹配系统800。匹配系统800适用于管理从客户端装置收到的实体，这包括将从用户810A的客户端装置815A收到的实体添加到匹配系统800中，并且确定从用户810B的客户端装置815B收到的实体是否与以前收到并由此存储在匹配系统800中的实体匹配。匹配系统800包括通信服务器830、应用服务器850和数据库服务器870，这些服务器以通信方式连接以便如图中双向箭头所示交换数据。

在典型情况下，用户810A、810B利用其客户端装置815A、815B通过因特网访问由匹配系统800托管的匹配服务。通信服务器830负责处理与客户端装置815A、815B的通信。在一个实施例中，通信服务器830可以是web服务器，并且在客户端装置815A、815B与通信服务器830之间的通信是基于HTTP有关协议。

数据库服务器870包括存储匹配系统800所收到的所有实体的数据库871。在数据库871中存储新实体时，为它分配了独特地标识该信息的实体标识参数875A、875B。数据库871因此充当实体存储装置，并且实体标识参数875A、875B是在实体存储装置中查找实体的关键字。实体标识参数875A、875B在下文将称为实体ID。

应用服务器850包括匹配引擎851，匹配引擎851包括添加新实体到匹配系统中和确定从客户端装置收到的实体是否与匹配系统中以前收到的实体匹配所需的所有功能。应用服务器850也包括增强同义词群组织器855。增强同义词群组织器855与如上所述同义词群组织器很相似，不同之处是增强同义词群组织器的同义词群还包括指示与同义词群相关联的所有实体的实体部分以有利于搜索匹配实体。在一示范实施例中，实体是文本字符串，并且增强同义词群组织器855的同义词群的实体部分包含与同义词群相关联的实体的实体ID 875A、875B的列表。在增强同义词群组织器855中，一个实体与一个或多个同义词群相关联。一个实体和另一实体如果均与多个共同同义词群相关联，则能够说它们至少在一定程度上匹配。虽然增强同义词群组织器855在此实施例中位于应用服务器850中，但增强同义词群组织器855可象图1的同义词群组织器100一样也正好位于匹配系统800中的另一节点中。增强同义词群组织器855如何定位不应理解为根据本发明的匹配系统800的限制性特征。

应注意的是，在匹配系统800中，匹配引擎851执行与实体有关的所有功能，这也可涉及修改增强群组织器855的同义词群（例如，同义词群的实体部分），而增强同义词群组织器855也可包括用于管理同义词群的管理引擎。在本发明的一实施例中，匹配引擎851和增强同义词群组织器的管理引擎能够组合在一起以形成新匹配引擎，以便与同义词群有关的所有操作能够由新匹配引擎执行。在另一实施例中，增强群组织器855能够合并到匹配系统中，这意味着用于存储同义词群的数据库变成匹配系统的标准组件，管理引擎的功能合并到匹配引擎851中。匹配系统的组件如何组织不应限制本申请的保护范围。

应理解的是，所示匹配系统体系结构只是示范，并且匹配系统800能够以许多其它方式实现。例如，通信服务器830和/或数据库服务器870可包括在应用服务器850中，使得整个匹配系统800位于一个单一服务器节点内。

图9示出根据本发明的一实施例，用于将新实体添加到匹配系统中的方法900。方法900能够由匹配系统的匹配引擎851执行，并且此方法从步骤S910开始，其中将新实体添加到数据服务器中并为新实体分配实体ID。

在步骤S920中，在进一步处理新实体前，应预处理新实体的文本。预处理可包括去除不必要的字符，例如，在文本末端的特殊字符“.”，并且将新实体的文本划分成关键词。例如，关键词将由Lucene API（开放源搜索软件，http://lucene.apache.org/）识别和分段。例如，带有文本“家庭清洁”的新实体将被划分成关键词“家庭”和“清洁”。

对于从新实体识别的每个关键词，在步骤S930中，在同义词群组织器中搜索带有对应于关键词的同义词的同义词群。存在用来确定同义词是否对应于该关键词的多种方式。例如，如果同义词和关键词相同，或者同义词包含关键词的所有字符，或者关键词包含同义词的所有字符，则认为同义词对应于关键词。所有这些方式均在本申请的保护范围内。

在步骤S940中，确定是否找到任何同义词群。如果找到任何同义词群，则在步骤S970中，将新实体与那些找到的同义词群相关联，这可包括如下步骤：将新实体的实体ID与找到的同义词群的每个同义词群相关联。如果未找到同义词群，则在步骤S950中，将头部设为关键词的新同义词群添加到同义词群组织器中，并且在步骤S960中，将新实体与新添加的同义词群相关联。

为新实体的每个关键词重复进行步骤S930到S970。在已处理新实体的所有关键词后，完成添加新实体的过程。

例如，关于图1和2所示的同义词群组织器，处理新添加的实体“家庭清洁”和“整理房间”被处理成与同义词群“清洁”相关联。

图10示出根据本发明的一实施例，用于确定从客户端收到的实体是否与匹配系统中的至少一个实体匹配的方法1000。方法1000能够由匹配系统的匹配引擎851执行，并且此方法1000从步骤S1010开始，该步骤相似于如图9的步骤S920中提及的过程，其中，收到的实体被分成多个关键词。如果可能将从客户端收到的实体添加到匹配系统中，并且同时确定收到的实体是否与匹配系统中的实体匹配，则能够在步骤S1010前执行步骤S910。

对于所收到实体的每个关键词，在步骤S1020中，在同义词群组织器中搜索带有对应于关键词的同义词的同义词群。有用来确定同义词是否对应于关键词的多种方式。例如，如果同义词和关键词相同，或者同义词包含关键词的所有字符，或者关键词包含同义词的所有字符，则认为同义词对应于关键词。所有这些方式均在本申请的保护范围内。

随后在步骤S1030中，确定是否已找到任何同义词群。如果没有找到同义词群，则添加新的对应同义词群是可选的，并且如果收到的实体存储在数据服务器中，则将收到的实体与新添加的同义词群相关联。此类过程相似于图9中的那些步骤S950和S960。为简明起见，忽略了这些过程的细节。

如果在步骤S1030中找到任何同义词群，则在步骤S1040中，获得与找到的同义词群相关联的实体集合。如果收到的实体存储在数据服务器中，则方法可选择性地包含相似于方法900中步骤S970的步骤，以进一步将收到的实体与找到的同义词群相关联。

在为收到的实体的每个关键词循环后，则获得与对应于收到的实体的每个关键词的同义词群相关联的实体集合。随后，在后面的步骤中，应处理实体的那些集合。根据本申请的一个实施例，在构成第一实体的大部分关键词在与构成第二实体的那些关键词相同的同义词群内时，认为第一实体与第二实体匹配。详细地说，如果对于构成第一实体的所有关键词，在步骤S1040中在相关联实体集合中找到第二实体时，则将第一实体和第二实体称为完全匹配。如果仅对于构成第一实体的部分关键词，在步骤S1040中在相关联实体集合中找到第二实体时，则将第一实体和第二实体称为部分匹配。例如，在图8的同义词群组织器中，实体“家庭清洁”与实体“清洁住房”由于实体“家庭清洁”的关键词“家庭”和“清洁”全部在与实体“清洁住房”相关联的同义词群中而完全匹配；实体“北京家庭清洁”与实体“清洁住房”由于关键词“北京”未出现在与实体“清洁住房”相关联的任何同义词群中而部分匹配。如果在两个实体之间的匹配部分太低，则这两个实体被视为不匹配。例如，如果第一实体的仅50%的关键词与第二实体匹配，则不应认为这两个实体匹配。根据本发明的一实施例，应定义匹配比率，以便仅匹配的关键词高于所有关键词的匹配比率的第一实体应被视为与第二实体匹配。在此实施例中，匹配比率设成在51-100%范围中的任何值，并且优选设成80%。

回到方法1000，在步骤S1050中，与对应于收到的实体的每个关键词的同义词群相关联的实体集合经处理以便为收到的实体获得合并的实体集合。详细地说，实体的这些集合被合并成实体的一个集合，其中，仅独特的实体作为合并的集合中的项目出现，并且合并的集合中没有任何两个项目包括相同实体。合并的集合中的每个实体具有附加字段计数器，计数器用于对在循环通过收到的实体的关键词后得到的实体的那些集合中出现的实体的出现次数进行计数。

在步骤S1060中，确定在合并的集合中是否有任何实体带有的计数器字段的值大于（收到的实体的关键词的数量* 匹配比率），也就是说，是否有任何实体被视为被收到的实体匹配。如果未找到实体，则在步骤S1080中将有关未找到匹配实体的信息返回到客户端，并且结束该过程。如果找到任何实体，则在步骤S1070中基于在收到的实体与那些找到的实体的每个实体之间的相似性将那些找到的实体分级，并且将分级的实体输出到客户端。

结合图11，进一步描述在步骤S1070中确定两个实体之间相似性的详细过程。

图11示出根据本发明的一实施例、用于计算两个匹配的实体E1与E2之间相似性S(E1, E2)的方法1100。此方法从步骤S1110开始，其中获取实体E1的所有关键词，并且将相似性S(E1, E2)的初始值设成0。随后，方法1100继续为实体E1的每个关键词i循环。

在步骤S1120中，获取包含对应于关键词i的同义词并且与实体E2相关联的同义词群。由于如下事实：实体E1和E2可部分匹配，因此，可能不存在既包含对应于关键词i的同义词又包含对应于实体E2的任何关键词的同义词的任何同义词群。

在步骤S1130中，确定是否存在此类同义词群。如果不存在，则方法继续到步骤S1150，其中，用于关键词i的相似性值S(i)设成0。如果此类同义词群存在，则在步骤S1140中，获取在对应于关键词i的同义词与实体E2关联同义词群所依据的同义词之间的相似性值，并且将用于关键词i的相似性值S(i)设成在两个同义词之间的相似性值。

也可能的是，能够在步骤S1120中找到不止一个同义词群，也就是说，有不止一个同义词群不仅包含对应于关键词i的同义词而且包含对应于实体E2的任何关键词的同义词。在此情况下，优选对于在步骤S1120中找到的所有实体群获得两个同义词之间的所有相似性值，并且将用于关键词的相似性值S(i)设成所有实体群之中的最高相似性值。

在步骤S1160中，两个匹配的实体E1与E2之间的相似性S(E1, E2)加上用于关键词i的相似性值S(i)。在对实体E1的每个关键词进行处理后，随后在步骤S1170中，将相加的相似性S(E1, E2)除以实体E1的关键词的数量以获得两个实体E1与E2之间的最终相似性S(E1, E2)。

应注意的是，在匹配系统800中，其中的组件根据要实现的功能在逻辑上被划分，但本发明不限于此，匹配系统800中的相应组件能够根据要求再划分或组合，例如，一些组件可组合成单个组件，或者一些组件能够进一步划分成更多子组件。

本发明的实施例可在硬件中实现，或者实现为在一个或多个处理器上运行的软件模块，或者以其组合实现。也就是说，本领域技术人员将理解，诸如专用集成电路(ASIC)或数字信号处理器(DSP)等特殊硬件电路可在实践中用于实现根据本发明的一实施例的匹配系统800的所有组件的一些或所有功能。包括匹配引擎851的匹配系统800的组件的一些或所有功能可备选由应用服务器850中的微处理器与例如对应于匹配引擎851的匹配引擎计算机程序组合实现，该匹配引擎计算机程序在微处理器上运行时促使应用服务器执行例如结合图9和10提及的步骤。本发明也可实施为用于执行本文中所述的任何方法的部分或全部的一个或多个装置或设备程序（例如计算机程序和计算机程序产品）。实施本发明的此类程序可存储在计算机可读媒体上，或者例如能够是采取一个或多个信号的形式。此类信号可以是可从因特网网站下载的数据信号，或者在载波信号上提供的信号或以任何其它形式提供的信号。

例如，图12示出例如应用服务器等能够实现本发明的实施例的服务器，该服务器能够以常规的方式包括处理器1210和采取存储器1220形式的计算机程序产品/计算机可读媒体。存储器1220可以是电子存储器，如闪存、EEPROM（电可擦除可编程只读存储器）、EPROM（可擦除可编程只读存储器）、硬盘或ROM。存储器1220能够具有用于执行前面所述任何方法步骤的程序代码1230的空间。例如，用于程序代码1230的空间可包括用于如前面结合图3-7所述管理同义词群的程序1231、用于如前面结合图9所述添加新实体到匹配系统中的程序1232及用于如前面结合图10所述确定从客户端收到的实体是否与匹配系统中至少一个实体匹配的程序1233。程序代码能够已写入一个或多个计算机程序产品，即程序代码载体，如硬盘、压缩光盘(CD)、存储卡或软盘，或者能够从一个或多个计算机程序产品读取或已读取。此类计算机程序产品一般情况下是如图13所示能够是便携式或固定式的存储器单元。它能够具有大致如图12的服务器的存储器1220中一样布置的存储器段、存储器单元和存储器空间。程序代码例如能够以适合的方式压缩。一般情况下，存储器单元因此包括计算机可读代码，即，能够由诸如1210等电子处理器读取的代码，所述代码在由服务器运行时，促使服务器执行步骤以执行服务器根据上面的描述执行的一个或多个过程或过程步骤。

应注意的是，上述实施例是说明本发明，而不是限制本发明，替代实施例可由本领域技术人员设计而不脱离随附权利要求书的范围。词语“包括”不排除存在但在权利要求书中未列出的要素或步骤。要素前面的词“一”不排除存在多个此类要素。本发明能够借助于包括多种不同要素的硬件或借助于适当编程的计算机实现。在列出多个部件的单元权利要求中，这些部件中的多个部件能够明确在相同硬件项目中实施。诸如第一、第二、第三等此类词语的使用不表示任何顺序，它们能够简单地解释为名称。