文档章节

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

penngo
 penngo
发布于 2011/01/17 22:48
字数 1200
阅读 222
收藏 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

penngo

粉丝 84
博文 121
码字总数 71288
作品 3
广州
高级程序员
私信 提问
加载中

评论(0)

《机器学习实战》学习笔记第十二章 —— FP-growth算法

主要内容: 一. FP-growth算法简介 二.构建FP树 三.从一颗FP树中挖掘频繁项集 一. FP-growth算法简介 1.上次提到可以用Apriori算法来提取频繁项集,但是Apriori算法有个致命的缺点,那就是它...

osc_v22siqak
2018/08/25
2
0
降维打击!为什么我认为数据结构与算法对前端开发很重要

事情要从 GitHub 上的一个 issue 谈起:https://github.com/LeuisKen/leuisken.github.io/issues/2,需求里面的我指代为 issue 里面的我。 从一个需求谈起 在我之前的项目中,曾经遇到过这样...

osc_nd4uekgu
04/16
2
0
使用FP-growth算法高效发现频繁项集

FP-growth算法:将数据集存储在一个特定的称为FP树的结构之后发现频繁项集或者频繁项对,即常在一起出现的元素项的集合FP树。 工作流程: 1、构建FP树:需要扫描两遍数据集,第一遍对所有元素...

osc_yyhakgol
2018/11/20
2
0
Trie树(代码),后缀树(代码)

Trie树系列 Trie字典树 压缩的Trie 后缀树Suffix tree 后缀树--ukkonen算法 Trie是通过对字符串进行预先处理,达到加快搜索速度的算法。即把文本中的字符串转换为树结构,搜索字符串的速度提...

osc_jz8ypj6y
2019/09/27
4
0
可持久化线段树+主席树+动态主席树

可持久化线段树 整体还是很容易理解的,网上的教程都挺不错,所以只简单介绍下 可持久化的原理在于,借用已经建过的线段树的一部分 比如,我们有一个数列$a={12,23,34,45,56,67,78,89}$ 而我...

osc_ju7lpfoo
2019/02/01
2
0

没有更多内容

加载失败,请刷新页面

加载更多

mongodb CRUD以及Aggregation常用操作

CRUD操作集 1)查询只展示需要的列db.collection.find({age : {$gt : 30} }, {name: 1, age: 1, _id: 0})2)查询有name字段且值为null的记录db.collection.find({name : {$type : 10} })......

简到珍
40分钟前
23
0
wellcms2.0伪静态配置

目标格式 /user/login.html apache RewriteEngine on# Apache 2.4RewriteCond %{REQUEST_FILENAME} !-d RewriteCond %{REQUEST_FILENAME} !-f RewriteRule ^(.*?)([^/]*).html(.*)$ inde......

cs_sharp
42分钟前
8
0
部署异步下载服务

异步下载 一、背景 目前系统对于大文件的下载慢、导出慢、大量的接口占用服务器带宽等问题,严重影响用户的体验,基于此背景,开发并实现了异步下载功能。 二、项目结构 脑图思路 三、环境准...

荼靡旖旎
42分钟前
25
0
(转)Marathon私有镜像仓库用户名和密码方式

下载镜像需要输入用户名和密码的时候,marathon发布这样的images需要用这种方法。 首先需要手动登入镜像仓库。 docker login db-registry.inc-test.com Username: admin Password: D...

osc_5p8bxoq2
47分钟前
24
0
Kafka集群、目录与工具

@[TOC] Zookeeper集群配置 Kafka重度依赖Zookeeper,所以必须选安装Zookeeper,下面是本机安装简单配置,因为只有一台机器,也没有使用虚拟机,所以使用了不同端口。 详细内容可以参考Zooke...

trayvon
48分钟前
36
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部