文档章节

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

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

之前在做网页采集时,需要检查网址是否已经访问过,当时做这个功能时,考虑到只是字符串的搜索功能,第一想到的是用前缀树来处理,并找到了一个叫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
粉丝 78
博文 100
码字总数 55704
作品 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
海量数据处理 - 教你如何迅速秒杀掉:99%的海量数据处理面试题

一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名 :-),同时,此文...

小王穷遊
09/02
0
0
Trie树(c++实现)

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

技术mix呢
2017/11/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Cointext在阿根廷和土耳其推出比特币现金短信钱包

Cointext于10月15日开始在土耳其和阿根廷提供新的基于SMS的比特币现金钱包服务,这两个国家的加密货币使用量急剧上升,以应对严峻的经济形势。 移动钱包 通过短信处理BCH交易 “比特币是更好...

lpy411
17分钟前
0
0
大数据早课-0918

9.18日早课 1.全局搜索含有abc的文件名称或文件夹的命令 2.当前目录一般用什么表示 3.切换到上一次和上一层命令分别是什么 4.pwd是查看当前目录的什么 5.隐藏文件或文件夹的标识是什么? 怎样...

hnairdb
18分钟前
0
0
mybatis学习笔记一

一、mybaits需要的项目依赖 <!-- https://mvnrepository.com/artifact/org.mybatis/mybatis --> <dependency> <groupId>org.mybatis</groupId> <artif......

wuyiyi
19分钟前
0
0
CentOS6 安装 GraphicsMagick

1.安装相关依赖: yum install -y gcc libpng libjpeg libpng-devel libjpeg-devel ghostscript libtiff libtiff-devel freetype freetype-devel 2.下载并解压到目录/usr/local/ wget ft......

凯文加内特
20分钟前
0
0
RabbitMq集群使用Nginx做负载均衡

1.配置rabbitmq集群(可以参考前一篇RabbitMq之部署集群) 2.Nginx做负载均衡 注意:Nginx1.90版本后 新增了stream 模块用于一般的 TCP 代理和负载均衡,之前版本不支持 修改Nginx配置文件ngi...

zhaochaochao
25分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部