CN111274289A - 一种基于符号序列的相似度计算方法 - Google Patents

Abstract

本发明提供了一种基于符号序列的相似度计算方法；所述计算方法根据数据库中序列的内容，使用基于字典的压缩方案生成的规则来度量关系数据库中模式元素之间的相似性；其应用范围可以是一个表的不同属性、一个数据库中的不同表或者不同数据库中的不同表；此方法是一种新的自动模式匹配方法，可以在模式集成、数据仓库、电子商务、语义查询处理、语义网等应用程序域中加以利用；本发明实现了自动监测数据库，能够更准确地反映数据实例中所表达的模式，节省了开发和维护的时间和成本。

Description

一种基于符号序列的相似度计算方法

技术领域

本发明涉及计算机算法领域，尤其涉及一种基于符号序列的相似度计算方法。

背景技术

操作数据库模式信息的一个基本操作是匹配，匹配使用两个模式作为输入，并在这两个模式的元素之间生成映射，这两个模式在语义上相互对应。匹配在许多应用程序中扮演着中心角色，例如面向web的数据集成、电子商务、模式集成、模式演化和迁移、应用程序演化、数据仓库、数据库设计、网站创建和管理以及基于组件的开发。

在当前的数据库应用技术领域，模式匹配扮演着十分重要的作用。几个常见的数据库应用程序域都应用到了模式匹配技术，包括模式集成、数据仓库、电子商务、语义查询处理、语义网等。模式匹配的可定制通用实现可以使构建包含自动模式匹配的应用程序变得更容易。同时，模式匹配的可定制通用实现也可以是数据库管理模型中的一个关键组件，在该模型中，模式匹配操作返回的映射可以作为合并模式或者组合映射的输入。

当前的模式匹配通常由图形用户界面支持的手动执行。这种方法有局限性。手动指定模式匹配是冗长、耗时、易出错和昂贵的。鉴于要集成的数据源和电子商务数量迅速增加，这是一个日益严重的问题。此外，当系统处理更复杂的数据库和应用程序时，它们的模式会变得更大，这会导致执行的匹配数增加。因此，需要一种更快、更少的劳动密集型自动方法。基于上述缺陷，申请人考虑设计一种基于符号序列的相似度计算方法，以解决上述缺陷。

发明内容

为了解决上述现有技术的不足之处，本发明的目的在于提供一种基于符号序列的相似度计算方法，首先在数据库属性的实例中识别重要的模式；然后根据实例中的模式生成规则；最后，规则生成之后，通过比较规则之间的相似度来评估相似度。

本发明提供了一种基于符号序列的相似度计算方法；所述方法包括如下步骤：

1)在数据库序列中识别重要的模式，并将原始的输入序列按照一定规则进行表示；

2)从输入序列中的第一个符号到最后一个符号，通过一次输入一个符号识别原始输入序列中所有重复模式的迭代过程，然后生成模式规则；

3)当一个数据库序列中的所有数据生成模式规则之后，执行一个特殊的后处理；

4)对重复模式生成的规则进行比较，产生相似度得分，进行相似度的评估。

优选的，所述步骤1具体分为以下三个步骤：

1)识别数据库中的原始输入序列；

2)在系统中按照一定的表示规则对原始输入序列进行表示；

3)生成输入序列的一条语法规则。

优选的，所述步骤2具体分为以下十一个步骤：

1)读取数据库序列中的一个标识符；

2)进行判断，此标识符的符号序列中，所有的语法规则是否符合数字唯一性；

3)若所有的语法规则符合数字唯一性，则进行判断，所有的语法规则利用率是否符合规则复用性；

4)若所有的语法规则不符合数字唯一性，则建立一条新的语法规则，然后再进行判断，所有新的语法规则利用率是否符合规则复用性；

5)若所有的语法规则利用率符合规则复用性，则进行判断，所有的语法规则是否同时符合数字唯一性和规则复用性；

6)若所有的语法规则利用率不符合规则复用性，则扩展一条语法规则，然后再进行判断，所有的语法规则是否同时符合数字唯一性和规则复用性；

7)若所有的语法规则不能同时符合数字唯一性和规则复用性，则返回当前所述步骤2；

8)若所有的语法规则同时符合数字唯一性和规则复用性，则进行判断，是否已经读取了数据库序列中的所有标识符；

9)若已经读取了数据库序列中的所有标识符，进入工作结束；

10)工作结束，停止迭代过程；

11)若未能读取数据库序列中的所有标识符，则返回当前所述步骤1，继续读取数据库序列中的另一标识符，继续迭代过程。

优选的，所述步骤3具体分为以下三个步骤：

1)在记录之间分离规则模式；将输入序列中的所有记录均作为单个连续符号序列彼此连接；若记录之间生成语法规则，即此语法规则生成交叉记录，则将此规则的右侧分为两个规则模式，使用“\n”和“\r”作为分隔符；

2)分词规则模式；若当前所述步骤1之后的任何规则模式还有空格，则使用空格字符作为分隔符将所述规则模式分隔成几个较短的规则模式；

3)若当前所述步骤1和步骤2执行之后，有些规则模式只剩下一个终止符符号，则删除。

优选的，所述步骤4具体分为以下三个步骤：

1)当生成两组输入符号序列的模式规则时，比较它们的差异；

2)定义相似性公式：

其中，p(i)是规则(i)中两个输入序列集一组的展开模式，n(i)为规则(i)的参考次数，模式p(i)的长度为l(i)，p(j)为规则(j)中两个输入序列集另一组的扩展模式，模式p(j)的长度为l(j)，p(i，j)为显示的图案，min(p(i，j))为两组p(i)和p(j)中出现相同模式的最小次数，l(i，j)为两组中出现图案的长度；

3)计算相似性的值s，指示两个符号序列集之间的相似性。

同现有技术相比，本发明的有益效果体现在：

(1)此方法为一种自动监测数据库和发现列相似性的方法，无需人工数据库专家的大量工作，节省了开发和维护的时间和成本。

(2)与数据库模式比较方法相比，此方法利用了数据实例，能够更准确地反映数据中所表达的模式，避免了模式匹配方法下模式信息量小而导致的不准确匹配。

(3)此方法使用数据中标识的模式，而不是匹配相同的字符串，赋予了模糊匹配特性，使得数据记录不一定按相同的顺序排列，数据记录的数量也不一定完全相同，其中数据相似性通过比较两个数据库属性生成的规则计算出的接近度值来表示。

附图说明

图1为本发明的一种基于符号序列的相似度计算方法的流程图；

图2为所述相似度计算方法的步骤1的流程图；

图3为所述相似度计算方法的步骤2的流程图；

图4为所述相似度计算方法的步骤3的流程图；

图5为所述相似度计算方法的步骤4的流程图。

具体实施方式

为了能够进一步了解本发明的结构、特征及其他目的，现结合所附较佳实施例附以附图详细说明如下，本附图所说明的实施例仅用于说明本发明的技术方案，并非限定本发明。

首先，如图1所示，图1是本发明的一种基于符号序列的相似度计算方法的流程图；所述软件系统包括所述方法包括如下步骤：首先，在数据库序列中识别重要的模式，并将原始的输入序列按照一定规则进行表示；然后，从输入序列中的第一个符号到最后一个符号，通过一次输入一个符号识别原始输入序列中所有重复模式的迭代过程，生成模式规则；其次，当一个数据库序列中的所有数据生成模式规则之后，执行一个特殊的后处理；最后，对重复模式生成的规则进行比较，产生相似度得分，进行相似度的评估。

进一步地，如图2所示，图2为本发明提供的所述相似度计算方法步骤1的流程图；所述数据库序列中需识别的重要模式，主要分为重复序列和嵌套重复序列；表1显示了一个重复的序列，表2显示了一个嵌套重复的序列；在生成的两个语法规则中，“S”表示原始输入模式的开始，以“S”开头的第一个规则始终与原始输入模式等效。在每个规则中，箭头符号“->”的左侧是非端子，可以扩展到箭头符号的右侧，箭头符号由非端子和端子组成。终止符不能再扩展，因为它们是与原始序列相同的输入符号。每个规则中的箭头两侧都可能出现带方括号[]的大写字母。它们用于指示规则中使用的非终止符。同一个带方括号的大写字母表示扩展规则中的同一对象。当表示非终止符时，使用“[])的目的是区别于原始输入序列中的大写字母，以避免混淆。

表1一个重复的序列

表2一个嵌套重复的序列

此外，如图3所示，图3为本发明提供的所述相似度计算方法步骤2的流程图：所述步骤2的基本思想是，任何出现不止一次的模式都可以被生成该模式的产生式规则替换，并且该过程可以递归地继续。此步骤的特点是不需要提供要监视的特定数据位置或变量，监测是在全局范围内进行的，而不仅仅是在一个特定的位置。

所述步骤2从输入序列中的第一个符号到最后一个符号，通过一次输入一个符号来进行整个模式构建过程。该过程是一个自下而上的过程，它涉及在原始输入符号或以前创建的规则上建立新规则。但是，语法规则必须始终保留两个属性：数字唯一性和规则复用性。

第一，数字唯一性。假设规则S是反映整个序列的顶级规则。当观察到一个新符号(终止符)时，它首先被附加到规则S中，然后新附加的符号和它的前一个符号形成一个新的数字图。如果新的数字出现在语法的其他地方，则违反了第一个约束。在这种情况下，必须创建一个新规则，新创建的数字在右侧，由一个新的非终止符领导。两个原始的数字图被这个新创建的非终止符的引用所代替。但是，在某些情况下，新创建的规则并不总是产生新规则。如果新的DRAM也出现在现有规则的右侧，则不需要创建新规则，因为该DigRAM将由现有规则的非终止符取代。

第二，规则复用性。首先，在生成的语法中，任何规则的右边都只有两个符号长，不管它们是终止符还是非终止符。但是，当一个新符号附加到顶层规则时，将创建更长的规则，该规则可能在该符号之前有一个非终止符符号，因此它们将形成一个数字图。此关系图将首先在语法中创建新规则。但是，如果新规则在语法中只使用一次，则此规则将被删除，并且此规则右侧的数字图将附加到生成此新规则的规则。原因是新规则在整个语法中只被引用一次，它违反了这个规则实用程序约束。

另外，如图4所示，图4为本发明提供的所述相似度计算方法步骤3的流程图；当对一个数据库列中的所有数据使用模式比较方法时，需要在生成所有模式规则后进行比较之前执行一个特殊的后处理步骤。后处理分为以下三个步骤：

1)在记录之间分离规则模式；由于输入到系统的列中的所有记录都作为单个连续符号序列彼此连接，因此可能会在记录之间生成规则。由于记录使用盒式返回(\n)和新行(\r)符号分隔，如果任何规则生成交叉记录，则此规则右侧的模式将被分隔为两个模式，使用“\n”和“\r”作为分隔符号。

2)分词规则模式；如果在步骤1之后处理的任何模式在该模式中还有任何空格，则应使用空格字符作为分隔符将该模式分隔成几个较短的模式。

3)删除作为图案的单端子符号；如果在执行了前两个步骤后，有些模式只剩下一个终止符符号，则应从列表中删除这些模式。

另外，如图5所示，图5为本发明提供的所述相似度计算方法步骤4的流程图；当生成两组输入符号序列的规则时，需要比较它们，并生成一个值来指示这两个符号序列集之间的相似性。计算值仅用于表示相似性。该值以0％到100％的百分比显示，其中0％表示没有与另一个符号集生成的规则相同的规则，100％表示两个符号集中生成的规则完全相同，并且没有只在一个符号集中显示的规则，同样，对于每个规则，规则被重复使用的次数相同。相似性公式定义如下：

其中，p(i)是规则(i)中两个输入序列集一组的展开模式，n(i)为规则(i)的参考次数，模式p(i)的长度为l(i)，p(j)为规则(j)中两个输入序列集另一组的扩展模式，模式p(j)的长度为l(j)，p(i，j)为显示的图案，min(p(i，j))为两组p(i)和p(j)中出现相同模式的最小次数，l(i，j)为两组中出现图案的长度；

相似性值s可以表示如下，其范围在0到1之间；相似度值仅用于近似评估的原因是基于仅生成的规则计算值，而不考虑表示整个输入序列的规则(0)中的终止符。因此，有时，虽然规则相同，但引用的数目相同，但是如果规则(0)中的其余终止符位置不同，则整个输入序列仍然不同。因此，相似性值s只能作为一种指示。

最后，本发明的一种基于符号序列的相似度计算方法，其具体的技术特点如下：

1)其基本思想是首先在数据库属性的实例中识别重要的模式，然后根据实例中的模式生成规则。规则生成之后，可以通过比较规则之间的相似度来评估相似度；

2)通过运用基于符号的类压缩算法的方式来进行符号序列的相似性比较的基本方法；

3)不需要多次扫描，仅仅使用一次扫描即可生成输入符号序列的层级式无重复可扩展性符号树，便捷高效；

4)该方法需要用到的此类生成性模式匹配方法所利用的2条基本规则，数字唯一性和规则复用性；

5)输入的符号序列一次性扫描，从底向上的生成性形成可以比较的层级式符号树的框架模式。

需要声明的是，上述发明内容及具体实施方式意在证明本发明所提供技术方案的实际应用，不应解释为对本发明保护范围的限定。本领域技术人员在本发明的精神和原理内，当可作各种修改、等同替换或改进。本发明的保护范围以所附权利要求书为准。

Claims (5)

1.一种基于符号序列的相似度计算方法，其特征在于，所述方法包括如下步骤：

1)在数据库序列中识别重要的模式，并将原始的输入序列按照一定规则进行表示；

2)从输入序列中的第一个符号到最后一个符号，通过一次输入一个符号识别原始输入序列中所有重复模式的迭代过程，然后生成模式规则；

3)当一个数据库序列中的所有数据生成模式规则之后，执行一个特殊的后处理；

4)对重复模式生成的规则进行比较，产生相似度得分，进行相似度的评估。

2.根据权利要求1所述的相似度计算方法，其特征在于，所述步骤1具体分为以下三个步骤：

1)识别数据库中的原始输入序列；

2)在系统中按照一定的表示规则对原始输入序列进行表示；

3)生成输入序列的一条语法规则。

3.根据权利要求1所述的相似度计算方法，其特征在于，所述步骤2具体分为以下十一个步骤：

1)读取数据库序列中的一个标识符；

2)进行判断，此标识符的符号序列中，所有的语法规则是否符合数字唯一性；

3)若所有的语法规则符合数字唯一性，则进行判断，所有的语法规则利用率是否符合规则复用性；

4)若所有的语法规则不符合数字唯一性，则建立一条新的语法规则，然后再进行判断，所有新的语法规则利用率是否符合规则复用性；

5)若所有的语法规则利用率符合规则复用性，则进行判断，所有的语法规则是否同时符合数字唯一性和规则复用性；

6)若所有的语法规则利用率不符合规则复用性，则扩展一条语法规则，然后再进行判断，所有的语法规则是否同时符合数字唯一性和规则复用性；

7)若所有的语法规则不能同时符合数字唯一性和规则复用性，则返回当前所述步骤2；

8)若所有的语法规则同时符合数字唯一性和规则复用性，则进行判断，是否已经读取了数据库序列中的所有标识符；

9)若已经读取了数据库序列中的所有标识符，进入工作结束；

10)工作结束，停止迭代过程；

11)若未能读取数据库序列中的所有标识符，则返回当前所述步骤1，继续读取数据库序列中的另一标识符，继续迭代过程。

4.根据权利要求1所述的相似度计算方法，其特征在于，所述步骤3具体分为以下三个步骤：

1)在记录之间分离规则模式；将输入序列中的所有记录均作为单个连续符号序列彼此连接；若记录之间生成语法规则，即此语法规则生成交叉记录，则将此规则的右侧分为两个规则模式，使用“\n”和“\r”作为分隔符；

2)分词规则模式；若当前所述步骤1之后的任何规则模式还有空格，则使用空格字符作为分隔符将所述规则模式分隔成几个较短的规则模式；

3)若当前所述步骤1和步骤2执行之后，有些规则模式只剩下一个终止符符号，则删除。

5.根据权利要求1所述的相似度计算方法，其特征在于，所述步骤4具体分为以下三个步骤：

1)当生成两组输入符号序列的模式规则时，比较它们的差异；

2)定义相似性公式：

其中，p(i)是规则(i)中两个输入序列集一组的展开模式，n(i)为规则(i)的参考次数，模式p(i)的长度为l(i)，p(j)为规则(j)中两个输入序列集另一组的扩展模式，模式p(j)的长度为l(j)，p(i，j)为显示的图案，min(p(i，j))为两组p(i)和p(j)中出现相同模式的最小次数，l(i，j)为两组中出现图案的长度；

3)计算相似性的值s，指示两个符号序列集之间的相似性。

Images