在爬虫的过程中，我们常常会遇到主题内容相同的网页，例如转载网页等等。由于标题不一样，内容有细微的偏差，也许我们的爬虫会误认为两个网页是不同的。这个时候，我们就必须对网页内容过滤消重。几乎所有的消重技术都基于这样一个基本思想：为每个文档计算出一组指纹（fingerprint），若两个文档拥有一定数量的相同指纹，则认为这两个文档的内容重叠性较高，也即二者是内容转载的。（具体详细内容在搜 索 引 擎 — 原理、技术与系统一书中有详细介绍）。
根据书中的算法描述，简单写了一个，网页消重的java代码，做一下代码笔记。
以下是算法中的主要部分：具体算法，在搜 索 引 擎 — 原理、技术与系统一书中有详细介绍。
public class FileSimCal {
private static final int N = 10;//取得特征词项的个数
public FileSimCal() {
}
/**
* 获取由n个关键词组成的特征项集合
*
* @param filepath
* @return Map<String, Integer>
*/
public Map<String, Integer> getTerms(String filepath) {
FileReader fr = null;
Map<String, Integer> map = new HashMap<String, Integer>();
try {
fr = new FileReader(filepath);
IKSegmentation iks = new IKSegmentation(fr, true);
Lexeme lexeme = null;
while ((lexeme = iks.next()) != null) {
String term = lexeme.getLexemeText();
if (map.containsKey(term)) {
int count = map.get(term) + 1;
map.put(term, count);
} else {
map.put(term, 1);
}
}
return map;
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
fr.close();
} catch (IOException e) {
e.printStackTrace();
}
}
return null;
}
/**
* 排序特征项集，取前10项
*
* @param words_T
* @return
*/
public String[] topTen(Map<String, Integer> words_T) {
PriorityQueue<Entry<String, Integer>> queue = new PriorityQueue<Entry<String, Integer>>(1000, new Comparator<Entry<String, Integer>>() {
public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
if (o1.getValue() > o2.getValue()) {
return -1;
}
if (o1.getValue() < o2.getValue()) {
return 1;
}
return 0;
};
});
String[] words = new String[N];
Iterator<Entry<String, Integer>> it = words_T.entrySet().iterator();
while (it.hasNext()) {
Entry<String, Integer> entry = it.next();
queue.add(entry);
}
int i = 0;
while(!queue.isEmpty()) {
Entry<String, Integer> entry = queue.poll();
if(entry.getKey().length() < 2) {//取出的特征项，应为一个词，所以string的长度必须大于等于2
continue;
}
words[i] = entry.getKey();
i++;
if(i == N) {//当取得头前十个词后跳出
break;
}
}
return words;
}
/**
* 重新组合前10位特征项词组
* @param tenFrontWords
* @return
*/
public String concatenate(String[] tenFrontWords) {
int i = 0;
if(tenFrontWords.length < N) {
return null;
}
StringBuilder sb = new StringBuilder();
while (i < N) {
System.out.print(tenFrontWords[i] + " ");
sb.append(tenFrontWords[i]);
i++;
}
System.out.println();
if(sb != null && sb.length() > 0) {
return sb.toString();
}
return null;
}
/**
* 生成特征字符串的md5码
* @param words
* @return
*/
public String md5(String words) {
MessageDigest digest = null;
StringBuffer sb = new StringBuffer();
try {
digest = MessageDigest.getInstance("MD5");
digest.update(words.getBytes(), 0, words.length());
byte[] tmp = digest.digest();
BigInteger bigint = new BigInteger(1, tmp);
sb.append(String.format("%1$016X", bigint));
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
return sb.toString();
}
/**
* 比较md5编码是否相同
* @param p1
* @param p2
* @return
*/
public boolean mirror(String p1, String p2) {
String p1_md5 = md5(p1).trim();
String p2_md5 = md5(p2).trim();
if(p1_md5.equals(p2_md5)) {
return true;
}
return false;
}
public static void main(String[] args) {
FileSimCal cal = new FileSimCal();
PingYinCompare pingYinCompare = new PingYinCompare();
//提取文档特征词项
Map<String, Integer> fwmap = cal.getTerms("./txt/fzfenghuang.txt");
Map<String, Integer> qqmap = cal.getTerms("./txt/fzqq.txt");
//排序词项
String[] topTenwords_fw = cal.topTen(fwmap);
String[] topTenwords_qq = cal.topTen(qqmap);
try {
String[] pinyinarr_fw = pingYinCompare.pinYinArr(topTenwords_fw);
String[] pinyinarr_qq = pingYinCompare.pinYinArr(topTenwords_qq);
//按照拼音字母顺序，对字符串数组排序
pingYinCompare.quickSort(pinyinarr_fw, 0, pinyinarr_fw.length - 1, topTenwords_fw);
pingYinCompare.quickSort(pinyinarr_qq, 0, pinyinarr_qq.length - 1, topTenwords_qq);
//合并排序后的词项
String con_fw = cal.concatenate(topTenwords_fw);
String con_qq = cal.concatenate(topTenwords_qq);
//比较连个字符串是否互为转载文章
if(cal.mirror(con_fw, con_qq)) {
System.out.println("fzfenghuang.txt和fzqq.txt为互为转载文章！");
} else {
System.out.println("fzfenghuang.txt和fzqq.txt不是互为转载文章！");
}
} catch (BadHanyuPinyinOutputFormatCombination e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
拼音识别及排序比较：
import java.text.Collator;
import java.util.Comparator;
import java.util.Locale;
import net.sourceforge.pinyin4j.PinyinHelper;
import net.sourceforge.pinyin4j.format.HanyuPinyinCaseType;
import net.sourceforge.pinyin4j.format.HanyuPinyinOutputFormat;
import net.sourceforge.pinyin4j.format.HanyuPinyinToneType;
import net.sourceforge.pinyin4j.format.HanyuPinyinVCharType;
import net.sourceforge.pinyin4j.format.exception.BadHanyuPinyinOutputFormatCombination;
public class PingYinCompare implements Comparator<String> {
//定义拼音输出格式
private HanyuPinyinOutputFormat format;
public PingYinCompare() {
this.format = new HanyuPinyinOutputFormat();
format.setCaseType(HanyuPinyinCaseType.LOWERCASE);
format.setToneType(HanyuPinyinToneType.WITHOUT_TONE);
format.setVCharType(HanyuPinyinVCharType.WITH_V);
}
/**
* 比较两个字符串的大小
*/
public int compare(String o1, String o2) {
return Collator.getInstance(Locale.ENGLISH).compare(o1, o2);
}
/**
* 把中文转换为字符串
* @param src
* @return
* @throws BadHanyuPinyinOutputFormatCombination
*/
public String str2PingYin(String src) throws BadHanyuPinyinOutputFormatCombination {
char[] chararr = src.toCharArray();
StringBuffer sb = new StringBuffer();
for(char c : chararr) {
String[] pinyin = PinyinHelper.toHanyuPinyinStringArray(c, this.format);
sb.append(pinyin[0]);
}
return sb.toString();
}
/**
* 快速排序
*
* @param arr
* 拼音字符串数组
* @param left
* 拼音字符串左起点
* @param right
* 拼音字符串的右起点
* @param src
* 源字符串数组
*/
public void quickSort(String[] arr, int left, int right, String[] src) {
String middle, tmp, tmp2;
int i = left;
int j = right;
middle = arr[(left + right) / 2];
do {
while ((compare(arr[i], middle) < 0) && i < right) {// 找出比middle大的数
i++;
}
while ((compare(arr[j], middle) > 0) && j > left) {// 找出比middle小的数
j--;
}
if (i <= j) {// 如果找出数值的位置下标符合条件，则两数组调换
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
//源字符串对调
tmp2 = src[i];
src[i] = src[j];
src[j] = tmp2;
i++;// i下标右移
j--;// j下标左移
}
} while (i < j);
if (left < j) {
quickSort(arr, left, j, src);
}
if (right > i) {
quickSort(arr, i, right, src);
}
}
/**
* 把字符串数组，转换成拼音数组
* @param src
* @return
* @throws BadHanyuPinyinOutputFormatCombination
*/
public String[] pinYinArr(String[] src) throws BadHanyuPinyinOutputFormatCombination {
if(src.length <= 0) {
return null;
}
String[] temp = new String[src.length];
for(int i = 0; i < temp.length; i++) {
temp[i] = str2PingYin(src[i]);
}
return temp;
}
public static void main(String[] args) {
PingYinCompare compare = new PingYinCompare();
try {
String p1 = compare.str2PingYin("我是一个兵");
String p2 = compare.str2PingYin("来自老百姓");
System.out.println(p1);
System.out.println(p2);
System.out.println(compare.compare(p2, p1));
} catch (BadHanyuPinyinOutputFormatCombination e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
参考文献：
一种适合java环境的中文快速排序和模糊检索方法--刘焕焕陆锋，赵云山
注：附件是三篇转载的文章
分享到：
相关推荐
【JAVA特效烟花绽放】是一种利用Java编程语言实现的视觉效果，它通过精心设计的算法模拟出烟花升空、绽放和熄灭的过程，为用户呈现一场精彩的视觉盛宴。这个特效通常包含多个元素，如烟花发射、颜色变化、爆炸扩散...
7. 常用算法模板：比如快速排序、归并排序、广度优先搜索(BFS)、深度优先搜索(DFS)、KMP算法、AC自动机、高斯消元法、二分图匹配、欧拉路径和欧拉回路、二分搜索等。 8. 竞赛策略：比如如何在竞赛中进行时间分配，...
6. **游戏逻辑**：《开心消消乐》的规则包括但不限于：三个相同颜色的元素相邻可以消除，连消有额外奖励等。这些规则的实现涉及复杂的条件判断和状态机设计。 7. **音频处理**：游戏音效增强了用户体验，源码中会有...
- **链接过滤消重算法**：避免重复抓取同一网页，减少存储空间和提高效率。 #### 3. **有色Petri网（CPN）在爬虫系统建模中的应用** 有色Petri网（Colored Petri Net, CPN）是一种高级的Petri网模型，常用于分布式...
碰撞检测是俄罗斯方块中的关键算法。当方块下落时，需要检查其与已有的方块或游戏区域底部是否有重叠。这通常通过比较每个单元格的位置来实现，一旦发现碰撞，方块就会停止下落并固定在当前位置。 消行计分是另一个...
在游戏、动画、网页设计或者应用程序中，这种效果可以营造出冬季或节日氛围，给用户带来愉悦的感受。 首先，我们要理解"雪花"效果是如何实现的。在编程中，这通常涉及到粒子系统（Particle System）的概念。粒子...
虽然具体的烟花渲染算法没有完全展示出来，但可以推测其基本逻辑是利用粒子系统来模拟烟花升空、绽放和消散的过程。由于Java Applet已不再被广泛支持，现代网页开发通常会使用HTML5的Canvas或者WebGL等技术来实现...
- JSP是动态网页技术，用于生成HTML或其他类型的文档。登录界面通常由一个JSP文件（如`login.jsp`）构成，包含HTML、CSS以及嵌入的Java代码，用于展示登录表单，并处理用户提交的数据。 3. **HTML/CSS/JavaScript*...
- **物理模拟**：简单地模拟重力和速度，让烟花根据物理规则上升、绽放和消散。 - **颜色过渡**：烟花在空中绽放时，颜色可以逐渐变化，这可以通过色彩渐变算法实现。 3. **图形渲染** - **粒子系统**：烟花效果...
而Java和JavaScript则广泛用于跨平台的桌面和网页应用。 在源代码中，我们可能会看到以下几个关键部分： 1. **游戏循环**：这是游戏的核心，负责处理每一帧的更新，包括方块的下落、旋转、移动以及检测消除行的...