文档章节

利用前缀树处理数据重复出现的问题

penngo
 penngo
发布于 2011/01/17 22:48
字数 1200
阅读 216
收藏 2
点赞 0
评论 0

之前在做网页采集时,需要检查网址是否已经访问过,当时做这个功能时,考虑到只是字符串的搜索功能,第一想到的是用前缀树来处理,并找到了一个叫SimpleStringSearch字符串搜索组件,这个组件的文本搜索实现也是类似前缀树(大概浏览了下源码),关于前缀词的内容有兴趣的可以自己上网搜索下。下面看测试代码,例子是用jsoup抓取网页的链接,并把链接记录下来,如果链接重复,则不记录。

import  java.io.StringReader;
import  java.util.LinkedList;
import  java.util.List;
import  net.sourceforge.sstringsearch.StringSearchFactory;
import  net.sourceforge.sstringsearch.search.Searcher;
import  net.sourceforge.sstringsearch.search.SearchingHitListener;
import  org.jsoup.Jsoup;
import  org.jsoup.nodes.Document;
import  org.jsoup.nodes.Element;
import  org.jsoup.select.Elements;

public   class  WebSearch {
    
public   static   void  main(String[] args) {
        
try  {
            String url 
=   " http://www.163.com/ " ;
            Document doc 
=  Jsoup.connect(url).get();
            Elements links 
=  doc.select( " a[href] " );
            
            
long  start1  =  System.currentTimeMillis();
            Searcher s 
=  StringSearchFactory.getSearcher();
            MyExampleHitListener listener 
=   new  MyExampleHitListener();
            s.addSearchTerm(url, listener);
            
for  (Element link : links) {
                String l 
=  link.attr( " abs:href " );
                s.search(
new  StringReader(l));
                
if  (listener.getCount()  ==   0 ) {
                    s.addSearchTerm(l, listener);
                }
            }
            start1 
=  System.currentTimeMillis()  -  start1;
            
            
long  start2  =  System.currentTimeMillis();
            List
< String >  list  =   new  LinkedList < String > ();
            
for  (Element link : links) {
                String l 
=  link.attr( " abs:href " );
                
boolean  b  =  list.contains(l);
                
if (b  ==   false ){
                    list.add(l);
                }
            }
            start2 
=  System.currentTimeMillis()  -  start2;
            
            
long  start3  =  System.currentTimeMillis();
            StringBuffer sff 
=   new  StringBuffer();
            
for  (Element link : links) {
                String l 
=  link.attr( " abs:href " );
                
int  i  =  sff.toString().indexOf(l);
                
if (i  >   - 1 ){
                    sff.append(l);
                }
            }
            start3 
=  System.currentTimeMillis()  -  start3;
            System.out.println(
" start1: "   +  start1  +   "   start2: "   +  start2  +   "   start3: "   +  start3);
        } 
catch  (Exception e) {
            e.printStackTrace();
        }
    }
}

class  MyExampleHitListener  implements  SearchingHitListener {
    
private   int  count;
    
public  MyExampleHitListener() {
        count 
=   0 ;
    }
    
public   boolean  foundAt( long  startIndex,  long  endIndex, String term,
            Object callbackArgs) {
        count
++ ;
        
return   true ;
    }
    
public   int  getCount() {
        
if (count  >   0  ){
            count 
=   0 ;
            
return   1 ;
        }
        
return   0 ;
    }
}


在我本机运行3次的输出结果:
start1:201  start2:50  start3:59
start1:172  start2:40  start3:50
start1:160  start2:40  start3:40

运行结果一出来,发现用SimpleStringSearch的方法,效率最差,忘记了SimpleStringSearch只适合大量的搜索条件下的查找,而且它需要先把查询条件建成树,在建树时比较耗时间。最后决定用链表来实现该功能。

SimpleStringSearch在有大量搜索条件的情况下进行文本查找和过滤是比较不错的,下面贴两个例子出来给大家看下。
文本查找例子

import  java.io.IOException;
import  java.io.StringReader;

import  net.sourceforge.sstringsearch.StringSearchFactory;
import  net.sourceforge.sstringsearch.search.Searcher;
import  net.sourceforge.sstringsearch.search.SearchingHitListener;

public   class  ExampleSearch {
    
public   static   void  main(String[] args) {
        
try  {
            Searcher s 
=  StringSearchFactory.getSearcher();
            ExampleHitListener1 listener 
=   new  ExampleHitListener1();
            s.addSearchTerm(
" 姚明 " , listener);
            s.addSearchTerm(
" 姚明离队 " , listener);
            s.addSearchTerm(
" 火箭队 " , listener);
            s.search(
new  StringReader(
                    
" 海耶斯意外受伤,看似将加速姚明离队,毕竟现在火箭队在5号位的用人上已经是捉襟见肘,他们急需一位防守能力出众的纯正中锋。不过,现在似乎并不是交易姚明的最佳时机,莫雷没有必要那么早的亮出底牌。美国《篮圈世界》专栏作家阿莱克斯-肯尼迪今日撰文“火箭正在等待重磅交易”,透露火箭不会立刻着急送走姚明,他们期待一笔更一鸣惊人的交易,预计要等到2月份左右,才会用姚明换取一位全明星。 " ));
            System.out.println(
" Count1 is:  "   +  listener.getCount());
        } 
catch  (IOException ex) {
            ex.printStackTrace();
        }
    }
}
class  ExampleHitListener1  implements  SearchingHitListener {
    
private   int  count;
    
public  ExampleHitListener1() {
        count 
=   0 ;
    }
    
public   boolean  foundAt( long  startIndex,  long  endIndex, String term,
            Object callbackArgs) {
        count
++ ;
        
return   true ;
    }
    
public   int  getCount() {
        
return  count;
    }
}

运行结果:
Count1 is: 6

文本过滤例子

import  java.io.IOException;
import  java.io.StringReader;
import  java.io.StringWriter;

import  net.sourceforge.sstringsearch.StringSearchFactory;
import  net.sourceforge.sstringsearch.replace.Replacer;
import  net.sourceforge.sstringsearch.replace.ReplacingHitListener;

public   class  ExampleSearchAndReplace {
    
public   static   void  main(String[] args) {
        Replacer r 
=  StringSearchFactory.getReplacer();
        StringWriter result 
=   new  StringWriter();
        ExampleReplacingHitListener listener 
=   new  ExampleReplacingHitListener();
        r.addSearchTerm(
" 防守能力出众 " , listener);
        r.addSearchTerm(
" 全明星 " , listener);
        
try  {
            r.searchAndReplace(
                    
new  StringReader(
                            
" 海耶斯意外受伤,看似将加速姚明离队,毕竟现在火箭队在5号位的用人上已经是捉襟见肘,他们急需一位防守能力出众的纯正中锋。不过,现在似乎并不是交易姚明的最佳时机,莫雷没有必要那么早的亮出底牌。美国《篮圈世界》专栏作家阿莱克斯-肯尼迪今日撰文“火箭正在等待重磅交易”,透露火箭不会立刻着急送走姚明,他们期待一笔更一鸣惊人的交易,预计要等到2月份左右,才会用姚明换取一位全明星。 " ),
                    result);
            System.out.println(result.toString());
        } 
catch  (IOException ex) {
            ex.printStackTrace();
        }
    }
}

class  ExampleReplacingHitListener  implements  ReplacingHitListener {
    
public  String replace(String stringToReplace, Object callbackArguments) {
        
char [] ch  =   new   char [stringToReplace.length()];
         
for  ( int  i  =   0 ; i  <  ch.length; i ++ ) {
         ch[i] 
=   ' * ' ;
         }
        
return   new  String(ch);
    }
}

运行结果:
海耶斯意外受伤,看似将加速姚明离队,毕竟现在火箭队在5号位的用人上已经是捉襟见肘,他们急需一位******的纯正中锋。不过,现在似乎并不是交易姚明的最佳时机,莫雷没有必要那么早的亮出底牌。美国《篮圈世界》专栏作家阿莱克斯-肯尼迪今日撰文“火箭正在等待重磅交易”,透露火箭不会立刻着急送走姚明,他们期待一笔更一鸣惊人的交易,预计要等到2月份左右,才会用姚明换取一位***。






pengo 2011-01-01 22:11 发表评论

本文转载自:http://www.blogjava.net/pengo/archive/2011/01/01/342129.html

共有 人打赏支持
penngo
粉丝 76
博文 98
码字总数 55112
作品 2
广州
程序员
频繁项集与关联规则 FP-growth 的原理和实现

机器学习之手把手实现,第 2 部分 频繁项集与关联规则 FP-growth 的原理和实现 韩笑琳 2017 年 11 月 21 日发布 系列内容: 此内容是该系列 10 部分中的第 # 部分: 机器学习之手把手实现,第...

韩笑琳
2017/11/21
0
0
数据结构与算法之9(哈夫曼编解码与广度优先搜索)

》哈夫曼编码 在二叉树最后的例子里的最后提到了哈夫曼树,个人感觉不是很好理解,为大家找到了一个篇讲的比较简洁明了的http://blog.csdn.net/jinixin/article/details/52142352,就不再造轮...

kkae8643150
2017/11/27
0
0
99%海量数据处理

http://blog.csdn.net/vjulyv/article/details/7382693 前言 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,...

tantexian
01/15
0
0
由浅入深探究mysql索引结构原理、性能分析与优化

摘要: 第一部分:基础知识 第二部分:MYISAM和INNODB索引结构 1、 简单介绍B-tree B+ tree树 2、 MyisAM索引结构 3、 Annode索引结构 4、 MyisAM索引与InnoDB索引相比较 第三部分:MYSQL优化...

大数据之路
2012/08/21
0
0
由浅入深探究mysql索引结构原理、性能分析与优化

摘要: 第一部分:基础知识 第二部分:MYISAM和INNODB索引结构 1、 简单介绍B-tree B+ tree树 2、 MyisAM索引结构 3、 Annode索引结构 4、 MyisAM索引与InnoDB索引相比较 第三部分:MYSQL优化...

蓝狐乐队
2014/07/08
0
0
由浅入深探究mysql索引结构原理、性能分析与优化

摘要: 第一部分:基础知识: 索引 官方介绍索引是帮助MySQL高效获取数据的数据结构。笔者理解索引相当于一本书的目录,通过目录就知道要的资料在哪里,不用一页一页查阅找出需要的资料。关键...

chape
2013/04/15
0
1
由浅入深探究 MySQL索引结构原理、性能分析与优化

欢迎关注微信号:neihanrukou 第一部分:基础知识: 索引 官方介绍索引是帮助MySQL高效获取数据的数据结构。笔者理解索引相当于一本书的目录,通过目录就知道要的资料在哪里,不用一页一页查阅...

fzxu_05
2015/10/15
170
0
搜索引擎关键字智能提示的一种实现

搜索引擎关键字智能提示的一种实现 美团技术团队 问题背景 搜索关键字智能提示是一个搜索应用的标配,主要作用是避免用户输入错误的搜索词,并将用户引导到相应的关键词上,以提升用户搜索体...

宇智波带土
2014/06/06
0
1
Trie树(c++实现)

原理 先看个例子,存储字符串abc、ab、abm、abcde、pm可以利用以下方式存储 上边就是Trie树的基本原理:利用字串的公共前缀来节省存储空间,最大限度的减少无谓的字串比较。 应用 Trie树又称...

技术mix呢
2017/11/09
0
0
零基础学贪心算法

本文在写作过程中参考了大量资料,不能一一列举,还请见谅。 贪心算法的定义: 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,只做出在某...

angel_kitty
2017/02/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式 Factory工厂模式 Singleton单例模式 Delegate委派模式 Strategy策略模式 Prototype原型模式 Template模板模式 Spring5 beans 接口实例化 代理Bean操作 ...

小致dad
15分钟前
0
0
SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
9
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
12
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
203
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0
python里求解物理学上的双弹簧质能系统

物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定。假定没有外力时,两个弹簧的长度为L1和L2。 由于两物体有重力,那么...

wangxuwei
昨天
0
0
apolloxlua 介绍

##项目介绍 apolloxlua 目前支持javascript到lua的翻译。可以在openresty和luajit里使用。这个工具分为两种模式, 一种是web模式,可以通过网页使用。另外一种是tool模式, 通常作为大规模翻...

钟元OSS
昨天
2
0
Mybatis入门

简介: 定义:Mybatis是一个支持普通SQL查询、存储过程和高级映射的持久层框架。 途径:MyBatis通过XML文件或者注解的形式配置映射,实现数据库查询。 特性:动态SQL语句。 文件结构:Mybat...

霍淇滨
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部