徐国华

(太原大学 计算机中心,山西 太原 030032)

拓展的LCS算法展开的网页关键词挖掘研究*

徐国华*

(太原大学 计算机中心,山西 太原 030032)

以经典的LCS算法为基础，通过对其进行分析，确定其不足之处，从而对其进行适度拓展，使其协同运算能力得到提升.在此基础上，利用拓展的LCS算法对网页关键词快速挖掘展开分析，通过具体实例确定其有效性.

LCS；拓展；网页；关键词;挖掘

网页信息的挖掘在互联网时代的重要性越来越重要，实现网页信息挖掘的快速、高效仍然是目前需要很好解决的一大问题[1～4].本文利用LCS算法，尝试进行网页关键词的挖掘研究.对LCS算法进行了拓展，以此对网页关键词快速挖掘展开具体分析，通过具体实例确定其有效性.

1 LCS算法论述与问题描述

1.1 LCS算法论述

LCS是英文单词Longest Common Subsequence的缩写，其意是指最长的公共子序列.举例而言，对于两个序列x1x2…xi…xn和y1y2…yj…ym而言，如果存在序列z1z2…zl…zq，使得序列z1z2…zl…zq中的每一个元素zl不仅包含在序列x1x2…xi…xn中，而且还包含在序列y1y2…yj…ym中.另外，不仅有z1=xi1，z2=xi2，…，zl=xi,l，…，zq=xi,q成立，还有z1=yj1，z2=yj2，…，zl=yj,l，…，zq=yj,q成立(其中，xis∈x1x2…xi…xn，yjt∈y1y2…yj…ym),则称序列z1z2…zl…zq为序列x1x2…xi…xn和y1y2…yj…ym的公共子序列.如果不存在长度超过序列z1z2…zl…zq长度的序列，则称序列z1z2…zl…zq为序列x1x2…xi…xn和y1y2…yj…ym的最长公共子序列，即我们所说的LCS.

1.2 研究问题描述

本文的主要问题是如何利用LCS的特性进行网页关键词的挖掘.具体说来，就是在不同的网页内容中寻找到最适合其特色的关键词.对于该问题，我们可以将其转换为两个字符序列的最长公共子序列问题，即LCS问题.以字符序列w1w2…wi…wn代表长度为n的网……