| 字串去重的快速算法研究 |
| |
| 引用本文： | 陈桂林,王永成.字串去重的快速算法研究[J].情报学报,2000,19(3):254-258. |
| |
| 作者姓名： | 陈桂林 王永成 |
| |
| 作者单位： | 上海交通大学网络信息中心,上海200030 |
| |
| 基金项目： | 国家 8 6 3计划资助!合同号 :86 3 30 6 ZD0 3 0 4 1 |
| |
| 摘 要： | 针对文本处理中的字串去重问题 ,本文提出了四种有效的快速算法 ,其平均时间复杂度为O(nlogn) ,空间复杂度为O(n)。其中利用首字hash方法的去重算法比直接利用快速排序算法具有更好的性能 ,其思想可用于改进快速排序算法。
|
| 关 键 词： | 字串去重 Hash 快速排序 时间复杂度 |
| 修稿时间： | 1999年6月21日 |
Research on Fast Algorithms for Removing Redundant Strings in a String Set |
| |
| Chen Guilin,Wang Yongcheng.Research on Fast Algorithms for Removing Redundant Strings in a String Set[J].Journal of the China Society for Scientific andTechnical Information,2000,19(3):254-258. |
| |
| Authors: | Chen Guilin Wang Yongcheng |
| |
| Abstract: | In this paper,we suggest several fast algorithms for removing redundant strings in a string set,their time complexity is O(n log n ) and space complexity is O(n). When processing Chinese strings,we first utilize hashing operation with the first Chinese character,then sort the string subset and remove redundant strings,which is superior to sorting by using quicksort directly.We spend only 50ms in removing 194 redundant items in a Chinese Biology Electronic Thesaurus including 11008 items. |
| |
| Keywords: | removing redundant strings hash quicksort time complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
