燕山大学学报
燕山大學學報
연산대학학보
JOURNAL OF YANSHAN UNIVERSITY
2014年
1期
49-56
,共8页
王燕%周军锋%汤显%陈子阳%郭景峰
王燕%週軍鋒%湯顯%陳子暘%郭景峰
왕연%주군봉%탕현%진자양%곽경봉
字符串相似性%trie树%编辑距离%Trie-TSS%优化技术
字符串相似性%trie樹%編輯距離%Trie-TSS%優化技術
자부천상사성%trie수%편집거리%Trie-TSS%우화기술
string similarity%trie%edit distance%Trie-TSS%pruning technique
对于给定的两个字符串集合,基于相似度的连接操作可用于从中找出相似的字符串对,该操作是数据清洗、数据集成以及协同过滤等应用中的核心操作之一,其执行效率直接影响系统的整体性能。本文提出一种高效计算字符串集合间连接操作的算法Trie-TSS,该方法基于trie树进行处理,利用对称性来减少冗余计算。提出一种旨在减少冗余编辑距离计算操作的优化技术来进一步提升系统性能。最后通过实验验证了Trie-TSS算法的高效性。
對于給定的兩箇字符串集閤,基于相似度的連接操作可用于從中找齣相似的字符串對,該操作是數據清洗、數據集成以及協同過濾等應用中的覈心操作之一,其執行效率直接影響繫統的整體性能。本文提齣一種高效計算字符串集閤間連接操作的算法Trie-TSS,該方法基于trie樹進行處理,利用對稱性來減少冗餘計算。提齣一種旨在減少冗餘編輯距離計算操作的優化技術來進一步提升繫統性能。最後通過實驗驗證瞭Trie-TSS算法的高效性。
대우급정적량개자부천집합,기우상사도적련접조작가용우종중조출상사적자부천대,해조작시수거청세、수거집성이급협동과려등응용중적핵심조작지일,기집행효솔직접영향계통적정체성능。본문제출일충고효계산자부천집합간련접조작적산법Trie-TSS,해방법기우trie수진행처리,이용대칭성래감소용여계산。제출일충지재감소용여편집거리계산조작적우화기술래진일보제승계통성능。최후통과실험험증료Trie-TSS산법적고효성。
For two given sets of strings, join operation is used to find similar string pairs based on string similarity. It is one of the essential operations in many applications, such as data integration, data cleaning, and collaborative filtering. A new trie-based al-gorithm, namely Trie-TSS, which uses the symmetry of edit distance to reduce redundant computation, is proposed. Then a new pruning technique is suggested to further reduce the unnecessary computation so as to improve the overall performance. The ex-perimental results show the efficiency of our method according to various metrics.