位置编码在数据仓库ETL中的应用

第３３卷　第１期　Ｖｏ１．３３　・计算机工程　２００７年１月　Ｊａｎｕａｒｙ　２００７　Ｎｏ．１　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　软件技术与数据库・　文章编号：１０００－－３４２８（２ｏ　—　————　位置编码在数据仓库ＥＴＬ中的应用　张永　，迟虐先　（１．大连理工大学计算机系，大连１１６０２４；２．辽宁师范大学计算机系，大连１１６０２９）　擅要：为了保证数据仓库中数据的质量，在数据挖掘前必须进行数据清洗。ＥＴＬ是构建数据仓库的重要环节，数据清洗就包含在其中。　而检测和消除数据仓库中的相似重复记录是数据清洗和提高数据质量要解决的关键问题之一。该文将位置编码技术引入到数据仓库ＥＴＬ　中，提出了一种相似重复记录的检测算法，并给出了不同级别匹配阈值的动态确定方法。通过实验表明该算法具有较好的检测效果。　关健词：数据清洗；位置编码；数据仓库；ＥＴＬ；相似重复记录　Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｐｏｓｉｔｉｏｎ－ｃｏｄｉｎｇ　ｉｎ　ＥＴＬ　ｏｆ　Ｄａｔａ　Ｗａｒｅｈｏｕｓｅ　ＺＨＡＮＧ　Ｙｏｎｇ　．ＣＨＩ　Ｚｈｏｎｇｘｉａｎ　（１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｄａｌｉａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ　１　１６０２４；　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ，Ｌｉａｏｎｉｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｌｉａｎ　１　１６０２９）　［Ａｂｓｔｒａｃｔ］Ｄａｔａ　ｃｌｅａｎｉｎｇ　ｓｈｏｕｌｄ　ｂｅ　ｄｏｎｅ　ｂｅｆｏｒｅ　ｄａｔａ　ｍｉｎｉｎｇ　ｉｎ　ｏｒｄｅｒ　ｔＯ　ｉｍｐｒｏｖｅ　ｄａｔａ　ｑｕａｌｉｔｙ　ｏｆ　ｄａｔａ　ｗａｒｅｈｏｕｓｅ．ＥＴＬ　ｉｓ　ａ　ｃｒｕｃｉａｌ　ｐｒｏｃｅｓｓ　ｏｆ　ｃｏｎｓｔｒｕｃｔｉｎｇ　ｄａｔａ　ｗａｒｅｈｏｕｓｅ，ｗｈｉｃｈ　ｉｎｃｌｕｄｅｓ　ｄａｔａ　ｃｌｅａｎｉｎｇ．Ｅｘａｍｉｎｉｎｇ　ａｎｄ　ｅｌｉｍｉｎａｔｉｎｇ　ａｐｐｒｏｘｉｍａｔｅｌｙ　ｄｕｐｌｉｃａｔｅｄ　ｒｅｃｏｒｄｓ　ｉｓ　ｏｎｅ　ｏｆ　ｋｅｙ　ｎｅｅｄｅｄ　ｓｏｌｕｔｉｏｎ　ｆｏｒ　ｄａｔａ　ｃｌｅａｎｉｎｇ　ａｎｄ　ｄａｔａ　ｑｕａｌｉｔｙ　ｉｍｐｒｏｖｉｎｇ．Ｔｈｉｓ　ｐａｐｅｒ　ｉｎｔｒｏｄｕｃｅｓ　ｔｈｅ　ｐｏｓｉｔｉｏｎ—ｃｏｄｉｎｇ　ｔｅｃｈｎｏｌｏｇｙ　ｔＯ　ＥＴＬ　ｏｆ　ｄａｔａ　ｗａｒｅｈｏｕｓｅｐｒｅｓｅｎｔｓ　ａ　，ｎｅｗ　ｅｘａｍｉｎｉｎｇ　ａｌｇｏｒｉｈｍ　ｏｆｔ　ａｐｐｒｏｘｉｍａｔｅｌｙ　ｄｕｐｌｉｃａｔｅｄ　ｒｅｃｏｒｄｓ，ａｎｄ　ｂｒｉｎｇｓ　ｆｏｒｗａｒｄ　ａ　ｄｙｎａｍｉｃ　ｍｅｔｈｏｄ　ｏｆ　ｖａｒｉｎｔ　ｌａｅｖｅｌ　ｍａｔｃｈ　ｔｈｒｅｓｈｏｌｄｓ．　Ｅｘｐｅｒｉｍｅｎｔａｌ　ｃｏｍｐａｒｉｓｏｎ　ｗｉｈ　ｔｈｅ　ｔｐｒｅｖｉｏｕｓ　ｗｏｒｋ　ｉｎｄｉｃａｔｅｓ　ｈａｔｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｐｒｏｐｏｓｅｄ　ｉｓ　ｅｆｆｅｃｔｉｖｅ．　［Ｋｅｙ　ｗｏｒｄｓ］Ｄａｔａ　ｃｌｅａｎｉｎｇ；Ｐｏｓｉｔｉｏｎ—ｃｏｄｉｎｇ；Ｄａｔａ　ｗａｒｅｈｏｕｓｅ；ＥＴＬ；Ａｐｐｒｏｘｉｍａｔｅｌｙ　ｄｕｐｌｉｃａｔｅｄ　ｒｅｃｏｒｄｓ　ｌ概述　大型的现实世界数据库通常有一个共同的特征，即存在　大量的不完整的、含噪音的和不一致的数据。因为用于数据　现可能重复的记录；通过合并，保留或生成一个完整的记录。　数据清洗活动的核心是相似重复记录的识别。从狭义角度来　看，如果两条记录在某些字段上的值相等或足够相似，则认　为这两条记录互为相似重复。数据清洗包括以下几个步骤：　（１）记录排序：选择一个或几个字段作为关键字进行　排序；　（２）识别重复记录：这是本文研究的重点；　挖掘的原始数据源可能是多个数据库或数据仓库，而这些数　据源的结构和规则可能是不同的，这将导致原始数据非常杂　乱和不可用，即使在同一个数据库中，也很可能存在重复的　和不完整的数据信息，为了使这些数据能够符合数据挖掘的　要求，提高效率和得到清晰的结果，必须进行数据的预处理　…。（３）合并重复记录：从相似记录集中获得记录的完整信　息，并作为该记录的表示。　对于相似重复记录，也已经有了一些研究［２－８］。　Ｍ．ｈｅｒｎａｄｅｚ等人提出了一种移动窗Ｉ：１法　来比较相邻记录：　首先将记录按照“关键字排序”，然后通过移动一个大小为ｗ　的“窗Ｉ：１”，每条进入“窗Ｉ：１”的记录与“窗Ｉ：１”中的前Ｗ。１　条记录比较，这样减少了比较的次数，这种算法被称为　ＥＴＬ是数据采集（Ｅｘｔｒａｃｔｉｏｎ）、数据转换（Ｔｒａｎｓｆｏｒｍａｔｉｏｎ）、　数据载入（Ｌｏａｄｉｎｇ）的简称。ＥＴＬ过程就是从数据源采集所需　数据，经过数据转换和清洗等预处理过程，最终按照预先定　义好的数据仓库数据模型，将数据加载到数据仓库中。　数据预处理主要包括数据清洗、数据集成和变换、数据　归约等技术…，而检测和消除数据仓库中的相似重复记录是　数据清洗和提高数据质量要解决的主要问题之一。所谓相似　重复记录是指客观上表示现实世界中的同一实体，由于表述　方式不同或拼写问题而使ＤＢＭＳ不能识别其为重复的记录。　这些重复的记录可能导致建立错误的数据挖掘模型，给后期　ＳＮＭ（Ｓｏｒｔｅｄ　Ｎｅｉｇｈｂｏｒｈｏｏｄ　Ｍｅｔｈｏｄ）算法。但很多算法目前都　是针对西文字符集，对于中文字符集的处理还有待进一步提　高。本文首先分析了在相似重复记录检测方面的一些研究，　指出了一些不足，然后针对西文字符集提出了一种新的检测　方法，并对此做了一些改进，使该算法也能成功地应用到中　文字符集中。同时对于匹配的阈值，也提出了一种动态的方　法来确定。　数据的决策分析产生很大的影响。因此，在ＥＴＬ中，判断两　条记录是否相似重复尤为重要。　造成相似重复记录的原因一般可分为两类：（１）拼写错　误，比如某数据表中包含３个字段：姓名，职业，出生日期，　则对于两条记录ＲＩ＝｛‘‘张三”，“教师”，“１９８５—０７—０６”１，　Ｒ２＝｛‘‘张三”，“教室”，“１９８５—０７—０６”１，可以认为Ｒ２中的“教室”　是拼写错误，它们是重复记录；（２）缩写所引起的等价错误，　比如“Ｄｅｐｔ”和“Ｄｅｐａｒｔｍｅｎｔ”。　数据清洗主要涉及到数据的匹配与合并。通过匹配，发　２相关工作　清除相似重复的记录可以针对两个数据集或者一个合并　作者倚介：张永（１９７５－－），男，博士生，主研方向：数据仓库，数　据挖掘与知识发现；迟忠先，教授、博导　牧藕日期：２００６・Ｏ１一Ｏ５　Ｅ－ｍａｉｌ：ａｙｏｎｇ＿ｚｈ＠１６３．ｃｏｍ　维普资讯 http://www.cqvip.com

后的数据集。首先，需要识别出标识同一个实体的相似重复　记录，即记录匹配过程。判定记录是否通过重复比较记录对　应的字符串之间的相似度来决定记录是否表示现实中同一实　体。与领域无关的（ｆｉｅｌｄ—ｉｎｄｅｐｅｎｄｅｎｔ）记录匹配方法主要思想　是：利用记录问的文本相似度来判定两条记录是否相似，如　果两条记录的文本相似度大于某个预先指定的阈值，那么判　定这两条记录是重复的，反之则不是　Ｊ。记录的匹配方法更　多的是以记录中的字段为基础进行的匹配，常见的方法有：　编辑距离方法　Ｊ，文本相似度度量方法　Ｊ，基于Ｎ—ｇｒａｍ的字　符串匹配方法　Ｊ，Ｃｏｓｉｎｅ相似度方法　Ｊ。　文献【３】中提出了一种ＲＦＭＡ算法。该算法的基本思想　是：两个字段Ａ和Ｂ是匹配的，设定匹配分值为１，当且仅　当它们具有相同的原子串或者一个是另一个的缩写；否则匹　配分值为０。根据不同情况，可以将字段划分成若干个单词　来处理，甚至可以将一个单词再划分成单个字母来处理。Ａ　与Ｂ匹配的相似度为　Ｓｉｒｎ（Ａ，Ｂ）＝　∑　，ＭＡＸ（ｓｃｏｒｅ（ａ　，Ｂ））　Ｊ　Ａ　Ｊ　这里ｓｃｏｒｅ（ａ．，　表示Ａ中的原子串ａｆ在与Ｂ中的每个原子串　匹配的分值，０≤ｓｃｏｒｅ（ａ　≤１，如上述所定义；ＩＡＩ表示Ａ　的长度。如果Ｓｉｍ（Ａ，Ｂ）的值大于某个指定的阈值，则认为Ａ　和Ｂ是相似重复情况，可以进行下一步清理工作。　该方法简单，易于实现。但是该方法往往也引入了过多　的错误匹配情况，比如：２个表示姓名的字段Ａ＝“Ｊｏｈｎ　Ｊｏｈｎｓｏｎ”，Ｂ＝“Ｊｏｈｎｓ　Ｍｉｃｈｅｌｉｎｅ”，根据文献【３】的算法，首先　将Ａ和Ｂ按单词分解，Ａ中的子串”Ｊｏｈｎ”与Ｂ中的”Ｊｏｈｎｓ”　匹配，ｓｃｏｒｅ（“Ｊｏｈｎ”，Ｂ）＝１；同样ｓｃｏｒｅ（“Ｊｏｈｎｓｏｎ”，Ｂ）＝１。从　而Ｓｉｍ（Ａ，Ｂ）＝（１＋１）／２＝１，即Ａ和Ｂ相似度为１。　３相似重复记录的位置编码检谢方法　为了判断一个数据表中的记录是否是相似重复的，可以　先判断记录所拥有的各个属性是否匹配，或者说计算出它们　的匹配程度，然后再考虑整个记录的相似匹配程度。下面描　述的算法思想首先是针对属性级的。当计算出每个属性的匹　配分值后，将这些匹配分值进行有权相加，根据预先设定的　记录级匹配阈值来判断记录是否是相似重复的。当然，对于　不同属性，考虑到属性在记录中的重要程度不一样，可以给　属性赋不同的权值。　３．１位置编码检测方法的描述　通过上述分析，本文仍利用相似度的概念，重新定义了　相似度的计算方法，并提出了一种动态方法来确定匹配阈值。　相似重复记录的位置编码检测方法如下：　（１）将两个字段或字符串Ａ和Ｂ按照基于单词的方式进行　标记（划分）。为了便于后续步骤的解释，假定Ａ的标记个数（记　为ｌＡ１）比Ｂ的标记个数（记为ＩＢＩ）少。　（２）如果ＩＡＩ＝Ｉ，将其按照基于字母的方式进一步标记。如　Ａ＝“ＤＳＳ”，可以将Ａ标记为Ａ＝｛‘‘Ｄ”，“Ｓ”，…Ｓ’｝。如果Ａ中　字母的个数恰好等于Ｂ中基于单词的标记个数，则将Ａ中的　每个字母与Ｂ中的每个单词的首字母比较，如果匹配，则表　明Ａ是Ｂ的缩写形式。比如对于上述的Ａ，若有Ｂ＝“Ｄｅｃｉｓｉｏｎ　Ｓｕｐｐｏｒｔ　Ｓｙｓｔｅｍ”，则Ａ与Ｂ匹配。　（３）否则，Ａ中的每个基于单词的标记ａｉ，分别与Ｂ中的　每个基于单词的标记进行比较，如果在Ｂ中存在某个标记ｂｊ，　使得相似度Ｓｉｍ（ａｉ，ｂｊ）大于或等于设定的阈值，则匹配分值为　ｌ。同时，标记出在Ｂ中的匹配位置Ｐ，该次比较结束。Ａ中　取出下一个标记，从Ｂ中上一次标注位置Ｐ开始向右匹配，　直到全部比较结束为止。　算法的关键在于（３）中单词问的比较，即如何来确定两个　基于单词标记的相似度问题。本文在解决此问题时，借鉴了　生物学中的序列比对方法，引入了罚分机制。基本思想是：２　个基于单词的标记进行比较，首先从第１个标记的首字符开　始依次与第２个标记的字符比较，如果有匹配的字符，则标　注该位置，并设定该处的匹配分值为１；如果第１个标记中２　个连续的字符在第２个标记中的匹配位置有间隔，则引用罚　分。第１次出现匹配间隔，每个间隔位罚０．２分；第２次出　现匹配间隔，每个间隔位罚０．４分；以此类推，每出现一次　间隔的罚分是前次的２倍。　３．２算法举倒　例如：　Ａ＝“ｄｅｐｔ”　Ｂ＝“ｄｅｐａｒｔｍｅｎｔ”　Ｂ：ｄ　ｅ　Ｐ　ａ　ｒ　ｔ　ｍ　ｅ　ｎ　ｔ　Ａ：ｄ　ｅ　Ｐ　ｔ　ｓｃｏｒｅ　ｌ　ｌ　ｌ　ｌ　ｐｅｎａｌｔｙ・－０．２－－０．２　ｓｃｏｒｅ（Ａ，Ｂ）：１＋１＋１．０．２—０．２＋１：３．６　Ｓｉｍ（Ａ，Ｂ）：３．６／４．０：０．９　如果设定阈值为０．７，由于０．９＞０．７，因此Ａ与Ｂ是匹配　的，是相似重复记录。　再例如：Ａ＝“ｄａｍｎ”　Ｂ＝“ｄｅｐａｒｔｍｅｎｔ”　Ｂ：ｄ　ｅ　Ｐ　ａ　ｒ　ｔ　ｍ　ｅ　ｎ　ｔ　Ａ：ｄ　ａ　ｍ　ｎ　ｓｃｏｒｅ　１　１　１　１　ｐｅｎａｌｔｙ　一０．２—０．２　—０．４—０．４　—０．８　ｓｃｏｒｅ（Ａ，Ｂ）：ｌ一０．２—０．２＋１－０．４—０．４＋１—０．８＋１＝２．０　Ｓｉｍ（Ａ，Ｂ）：２．０／４．０＝０．５　同样，如果设定阈值为０．７，由于０．５＜０．７，因此Ａ与Ｂ　不匹配，不是相似重复记录。　３．３匹配■值的动态确定方法　在数据仓库中，为了判断一个表中２个元组是否是相似　重复的，我们通过上述的算法计算出匹配分值后，总是要事　先确定一个匹配阈值。当计算出的分值超过指定的阈值时，　认为匹配成功，它们是相似重复记录；否则，匹配不成功。　但在许多相关算法中，阈值的确定往往依赖于本领域专家的　试验数据。对于非本领域专家的用户而言，可以认为阈值的　确定是一种静态方式；另外，本领域专家所确定的阈值，往　往仅适合于本领域内的应用，对于其它领域并无参考价值。　因此，在实际的应用中，应该有一种与领域无关的、通用的　阈值动态确定方法。　正如前面所述，由于最终两条记录的相似重复匹配情况　依赖于基于单词的标记匹配，因此阈值的动态确定也需要设　定不同的级别，包括基于单词标记级、属性（或字段）级和记　录级。　对于基于单词标记级阈值　的确定，通过一些实验表　明，两个单词Ａ和Ｂ的最大容错字符长度定义为Ｅ　＝　０．２５＊（ＩＡＩ＋ＩＢＩ）／２，即两单词平均长度的２５％。相应的阈值　＝１一Ｅ　／ＩＡＩ。　对于属性级阈值７１Ａ的确定，两个属性值的最多不匹配单　词的个数为ＥＡ＝０．２５＊（ＩＡＩ＋ＩＢＩ）／２，即两属性值中单词平均个　数的２５％。相应的阈值ＴＡ＝１一ＥＡ，ｌＡｌ。注意这里的Ａ和Ｂ　维普资讯 http://www.cqvip.com

表示两个属性值。　对于记录级阈值　的确定，也可采用类似的方法来确　杂度上并没有明显的改善，但是与ＲＦＭＡ算法相比，匹配的　精度提高了。同时还针对不同层次的匹配，给出了匹配阈值　定。由于现实数据表中，各个属性的重要程度不一样，因此　通过给属性赋权值的方法来标记属性的重要性。用　（　１…．，小）来表示各个属性的权重值，则记录级阈值　的计算公　式如下：　＝的动态确定方法。该算法不仅可以应用到西文字符集中，而　且也成功地应用到了中文字符集中，具有较强的通用性。通　过一些实验表明本文的算法具有较好的效果。　参考文簟　∑　Ｉ　１安淑芝．数据仓库与数据挖掘【Ｍ】．北京：清华大学出版社，２００５．　２　Ｈｅｒｎｆｉｎｄｅｚ　Ｍ　Ａ，Ｓａｌｖａｔｏｒｅ　Ｊ．Ｔｈｅ　Ｍｅｒｇｅ／Ｐｕｒｇｅ　Ｐｒｏｂｌｅｍ　ｆｏｒ　Ｌａｒｇｅ　其中　表示ｍ个不同属性的属性阈值，确定方法如上所述。　Ｄａｔａｂａｓｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ，１９９５：１２７—１３８．　３　Ｌｅｅ　Ｍ　Ｌ，Ｌｕ　Ｈ，Ｌｉｎｇ　Ｔ　Ｗ　ｅｔ　ａ１．Ｃｌｅａｎｓｉｎｇ　Ｄａｔａ　ｆｏｒ　Ｍｉｎｉｎｇ　ａｎｄ　４算法在中文字符集中的改进及应用　上述算法能够很好地应用到西文字符集中，但是汉字字　Ｗａｒｅｈｏｕｓｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｅ　１０　Ｉｔｎｔｅｍａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　符的比较却有所不同。我们对该算法稍加改进，即可以用于　Ｄａｔａｂａｓｅ　ａｎｄ　Ｅｘｐｅｒｔ　Ｓｙｓｔｅｍｓ　Ａｐｐｌｉｃａｔｉｏｎ，１９９９：７５１—７６０．　中文字符的匹配问题。考虑算法的第３步，仅针对汉字单个　４ＭｏｎｇｅＡＥ．ＥｌｋａｎＣＰＴｈｅＦｉｅｌｄＭａｔｃｈｉｎｇＰｒｏｂｌｅｍ：Ａｌｇｏｒｉｔｈｍｓａｎｄ　字符来作匹配，类似于算法中基于字符的匹配。　Ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｔｅ　２　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　例如：有２个地址字段值Ａ＝“辽宁师范大学计算机系”，　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａｂａｓｅｓ，１９９６：２６７—２７０．　Ｂ＝“辽师大计算机系”。首先用上述方法来动态确定匹配阈值　５　Ｍｏｎｇｅ　Ａ　Ｅ．Ｍａｔｃｈｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ　Ｗｉｈｔｉｎ　ａ　Ｄｕｐｌｉｃａｔｅ　Ｄｅｔｅｃｔｉｏｎ　Ｔ。Ｔ＝１－（０．２５＂（ＩＡＩ＋ＩＢＩ）／２）／ＩＢＩ＝Ｉ一（０．２５　（１０＋７）／２）／８＝０．７１８　７５。　Ｓｙｓｔｅｍ［Ｊ］．Ｂｕｌｌｅｔｉｎ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｔｅｃｈｎｉｃａｌ　匹配情况如下：　Ｃｏｍｍｉｔｔｅｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｎｎｇ，２０００，２３（４）：１４—２０．　Ａ　＝辽宁师范大学计算机系　６　Ｇｒａｖａｎｏ　Ｌ．Ｉｅｐｉｒｏｔｉｓ　Ｐ　Ｇ　Ｕｓｉｎｇ　Ｑ—ｇｒａｍｓ　ｉｎ　ａ　ＤＢＭＳ　ｆｏｒ　Ａｐｐｒｏｘｉｍａｔｅ　Ｂ　＝辽宁师　大　计算机系　Ｓｔｉｒｎｇ　Ｐｒｏｃｅｓｓｉｎｇ［Ｊ］．Ｂｕｌｌｅｔｉｎ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｓｃｏｒｅ＝１　１　１—０．２　１—０．４　１　１　１　１　Ｔｅｃｈｎｉｃａｌ　Ｃｏｍｍｉｔｅｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００１，２４（４）：２８—３４．　Ｓｃｏｒｅ（Ａ，Ｂ）＝∑ｓ（Ａｉ，Ｂｉ）＝１＋１＋１—０．２＋１—０．４＋１＋１＋１＋１＝７．４　７　Ａｎａｎｔｈａｎｋｒｉｓｈｎａ　Ｒ．Ｃｈａｕｄｈｕｒｉ　Ｓ．Ｇａｎｔｉ　Ｖ　Ｅｌｉｍｉｎａｔｉｎｇ　Ｆｕｚｚｙ　Ｓｉｍ（Ａ，Ｂ）＝Ｓｃｏｒｅ（Ａ，Ｂ），ｌＡ＝７．４／１０＝０．７４　因为Ｓｉｍ（Ａ，Ｂ）＝０．７４＞Ｔ，所以可以认为Ａ和Ｂ是相似重　Ｄｕｐｌｉｃａｔｅｓ　ｉｎ　Ｄａｔａ　Ｗａｒｅｈｏｕｓｅｓ［Ｃ］Ｈ　Ｐｒｏｃｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２８　ＶＬＤＢ　复的。　Ｃｏｎｆｅｒｅｎｃｅ，Ｈｏｎｇ　Ｋｏｎｇ，Ｃｈｉｎａ，２００２．　８　Ｍａｓｅｋ　Ｗ　Ｐａｔｅｒｓｏｎ　Ｍ　Ａ．Ｆａｓｔｅｒ　Ａｌｇｏｒｉｔｈｍ　Ｃｏｍｐｕｔｉｎｇ　Ｓｔｉｒｎｇ　Ｅｄｉｔ　５结论　在数据仓库ＥＴＬ的构建中，由于存在着大量不完整的、　Ｄｉｓｔａｎｃｅ［Ｊ］．Ｊｏｕｍａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅ，１９８０，２Ｏ（６）：　ｌ８—３１．　含噪音的和不一致的数据，因此提高数据质量是关键，而检　测和消除数据仓库中的相似重复记录是数据清洗和提高数据　９陈细谦，迟忠先，昃宗亮，等．地理编码在空问数据仓库ＥＴＬ中的　质量要解决的关键问题之一。本文提出的算法尽管在时间复　应用【Ｊ】．小型微型计算机系统，２００５，ｌ６（４）：６２８—６３０．　（上接第４９页）　从图中可以看出，改进前系统是串行处理，其单位查询　４小结　平均处理时间随着查询数量的增加基本相差不大，而改进后　本文探讨的基于移动Ａｇｅｎｔ查询处理策略，能有效地提　的系统随着查询数量的增加有明显的下降，后来下降趋势渐　高查询处理效率和减少网络传输流量。但实验环境相对简单，　趋平缓。这是因为系统改进后，在查询数量不太大的情况下，　在实际的特定网络环境中，可能还会面临很多特殊的问题，　查询请求间相似或相同的情况极少，能合并的查询很少，查　需进一步研究。　询数量变化不大，相应的单位查询平均处理时间与原系统相　比相差较小。随着查询数量的增加，查询请求间相同或相似　参考文簟　的可能性极大，大多数的查询都能合并，查询Ａｇｅｎｔ处理的　ｌ　Ｇｒｙｚ　Ｊ．Ｑｕｅｒｙ　Ｒｅｗｒｉｉｔｎｇ　Ｕｓｉｎｇ　Ｖｉｅｗｓ　ｉｎ　Ｐｒｅｓｅｎｃｅ　ｏｆＦｕｎｃｔｉｏｎａｌ　ａｎｄ　查询数量大大减少，因此单位查询请求平均处理时间也随之　Ｉｎｃｌｕｓｉｏｎ　Ｄｅｐｅｎｄｅｎｃｉｅｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍ，１９９９，２４（７）：　下降；另一方面，分发Ａｇｅｎｔ在发送查询结果时，因采取上　５９７—６　１２．　述策略，网络流量大幅度减少，网络传输速度加快，也相对　２陶先平．基于Ｉｎｔｅｒｎｅｔ的移动Ａｇｅｎｔ技术和应用研究【Ｄ】．南京：南　减少了单位查询结果平均处理时间。当查询数量增加到一定　京大学，２００１．　数量时，合并后的查询数量变化不大，但单位查询平均处理　３洪　晓，光李晖．多查询之间的包含判断【Ｊ】．计算机工程与应用，　时间仍呈缓下降趋势。　２００３，３９（１９）：１９４—１９５．　从以上的测试结果可以看出，查询服务器应用上述策略　４张德，董逸生．多播环境下的增量式查询归并【Ｊ】．计算机学报，　后，能使服务器站点瓶颈状况得以缓解，并在一定程度上减　２０００，２３（４）：４０４－４０９．　轻网络负载。另外，因查询数量的减少还能简化并发控制与　５吴婷婷，周兴铭．基于语义缓存的移动查询导出【Ｊ】＿计算机学报，　数据一致性维护。　２００２．２５（１Ｏ１：１　１０４—１　１　１０．　一５２一