期刊文献+

基于字符串近似匹配的模式生成算法

下载PDF
导出
摘要 本文提出一种字符串之间的模式产生算法。算法的思想来源于一个新颖的想法:通过比较两个字符串,得到两个字符串的不同之处,并采用一套事先定义的规则来泛化这些不同之处,从而得到一个能够同时匹配这两个字符串的模式,我们使用正规表达式来表示这个模式。为了计算两个字符串的不同之处,本文使用了字符串近似匹配的方法,并提出了一种基于动态规划的改进算法,降低了已有算法的时空复杂度。
作者 孙进 龚沛曾
机构地区 同济大学
出处 《福建电脑》 2010年第2期59-61,共3页 Journal of Fujian Computer
  • 相关文献

参考文献12

  • 1G. Navarro. A guided tour to approximate string matching. ACM Computing surveys (CSUR), 33(1):31-88, 2001.
  • 2P. H. Sellers. The theory and computation of evolutionary distances: Pattern recognition. Journal of Algorithms, 1 (4):359-373,1980.
  • 3R. Baeza-Yates. A unified view of string matching algorithms. In Proceedings of the Theory, and Practice of Informatics(SOFSEM'96).LNCS,vol. 1175, Springer Verlag, 1996.
  • 4V. Crescenzi, G MeccaG, P. Merialdo. RoadRunner: Towards automatic data extraction from large Web sites. Proceedings of the26th International Conference on Very Large Database Systems (VLDB), Rome, Italy, pp. 109-118, 2001.
  • 5A. Arasu, and H. Garcia-Molina, Extracting structured data from Web pages. Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, California, pp. 337-348, 2003.
  • 6D. Reis, P. Golgher, A. Silva, A. Laender, A. Automatic Web news extraction using tree edit distance, WWW-04, 20040.
  • 7C. Chai-Hui, K. Mohanmmed . A Survey of Web Information Extraction Systems, IEEE Transactiom on Knowledge and Data Engineering, Vol .18, 2006.
  • 8G. Navarro, M. Raffinot. Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge Press, 2002.
  • 9V. I. Levenshtein. Binary codes capable of correcting spurious insertions and deletions of ones. Problems of Information Transmission, 1:8-17, 1965.
  • 10E. Ukkonen. Algorithms for approximate string matching. Information and Control 64,100-118. Preliminary version in Proceedings of the International Conference Foundations of Computation Theory (LNCS, vol. 158, 1983).

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部