一种编辑距离算法及其在网页搜索中的应用

薛晔伟; 沈钧毅; 张云

您当前的位置：

首页 >

文章列表页 >

一种编辑距离算法及其在网页搜索中的应用

更新时间：2025-12-08

- 一种编辑距离算法及其在网页搜索中的应用
- Modified Edit Distance Algorithm and Its Application in Web Search
- 西安交通大学学报 2008年42卷第12期页码：1450-1454
- 作者机构：
  
  西安交通大学电子与信息工程学院,西安,710049
- 作者简介：
- 基金信息：
  
  : 2008-04-15. 作者简介: 薛晔伟(1980-),男,博士生;沈钧毅(联系人),男,教授,博士生导师. 基金项目: 国家自然科学基金资助项目(60673087)
- DOI：
  中图分类号： TP391
- 网络首发：2008-12-10，
  
  纸质出版：2008
- 稿件说明：
移动端阅览
薛晔伟, 沈钧毅, 张云. 一种编辑距离算法及其在网页搜索中的应用[J]. 西安交通大学学报, 2008,42(12):1450-1454.

薛晔伟, 沈钧毅, 张云. Modified Edit Distance Algorithm and Its Application in Web Search[J]. 2008, 42(12): 1450-1454.
薛晔伟, 沈钧毅, 张云. 一种编辑距离算法及其在网页搜索中的应用[J]. 西安交通大学学报, 2008,42(12):1450-1454. DOI：

薛晔伟, 沈钧毅, 张云. Modified Edit Distance Algorithm and Its Application in Web Search[J]. 2008, 42(12): 1450-1454. DOI：

摘要

针对传统方法不能很好地处理网页中简短域与用户查询之间的相关性排序问题

提出一种基于改进的编辑距离排序算法.将以词为单位的用户查询和简短网页域通过匹配编码转化为2个字符串

再利用改进的编辑距离计算2个字符串之间的相似性.由于在用户查询与待比较的简短网页域之间引入了查询词分布的位置、顺序和距离等

以及含有查询词修饰关系的重要信息

所以编码字符串之间的相似程度可以衡量对应的查询与简短网页域之间的相关性.经大规模真实搜索引擎实验表明

该算法较之传统的相关性排序算法

可以显著地提高网页搜索中的简短网页域相关性排序性能

尤其适用于简短域与用户查询之间的相关性比较.

Abstract

Focusing on the problem that the traditional methods cannot perform well on the short web page fields

a modified edit distance algorithm

referred as MED

is proposed. The proposed algorithm encodes the user query and the short web fields into two strings according to the word match

and then the MED is used to calculate the similarity between the two strings. Because the ‘position'

‘order'

and ‘distance' information that is very important in expressing the modification relationship between the query words are considered

the similarity between the encoding strings can be used to measure the relevance between the corresponding query and short field. Experimental results on large scale search engine data show that the proposed algorithm can significantly outperform the traditional algorithms for relevance ranking on short web fields

especially for very short fields.

关键词

Keywords

references

BRIN S, PAGE L. The anatomy of a large-scale hypertextual web search engine [J]. Computer Networks and ISDN Systems,1998, 30(1/7): 107-117.

OGILVIE P, CALLAN J. Combining structural information and the use of priors in mixed named-page and homepage finding [EB/OL]. [2006-10-11]. http:∥www. scils.rutgers.edu/～muresan/IR/TREC/Notebooks/t12_notebook/papers/cmu-dir.web.pdf.

BAEZA-YATES R A, RIBEIRO-NETO B A. Modern information retrieval [M]. Reading, MA, USA: Addison-Wesley Publishing Company, 1999.

ROBERTSON S E, WALKER S, HANCOCK-BEAULIEU M. Experimentation as a way of life: OKAPI at TREC [J]. Information Processing Management, 2000,36(1):95-108.

BUTTCHER S, CLARKE C L A, LUSHMAN B. Term proximity scoring for ad-hoc retrieval on very large text collections [C]∥Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA: ACM, 2006: 621-622.

MITTAL V, BALUJA S, SAHAMI M. The happy searcher: challenges in web information retrieval [EB/OL]. [2006-12-10]. http:∥www.cs.cmu.edu/～har/PRICAI-2004. pdf.

LEVENSHTEIN V I. Binary codes capable of correcting deletions, insertions, and reversals[J]. Soviet Physics Doklady, 1966,10(8):707-710.

车万翔, 刘挺, 秦兵, 等. 基于改进编辑距离的中文相似句子检索 [J]. 高技术通讯, 2004, 14(7):15.

CHE Wanxiang, LIU Ting, QIN Bing, et al. Similar Chinese sentence retrieval based on improved edit-distance [J]. High Technology Letters, 2004, 14(7):15.

CORMEN T H, LEISERSON C E, RIVEST R L, at el. Introduction to algorithms[M]. Beijing, China: China Machine Press, 2006.

CRASWELL N, HAWKING D. Overview of the TREC-2002 Web track [EB/OL]. [2006-09-22]. http:∥trec. nist. gov/pubs/trec11/papers/WEB.OVER. pdf.

JARVELIN K, KEKALAINEN J. IR evaluation methods for retrieving highly relevant documents [C]∥Proceedings of the 23rd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA: ACM,2000: 41-48.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

融合物理信息与深度算子网络的变压器绕组热-流场快速计算方法

EBSILON软件在热电联产系统优化中的应用综述

采用试验设计方法的第三代CO2气体箔轴承箔片几何参数敏感性分析

结构-语义-残差协同的图像压缩框架：面向隐私保护与高保真重建

离子液体改性燃料的电流体动力学效应研究