利用前缀树处理数据重复出现的问题
博客专区 > penngo 的博客 > 博客详情
利用前缀树处理数据重复出现的问题
penngo 发表于7年前
利用前缀树处理数据重复出现的问题
  • 发表于 7年前
  • 阅读 209
  • 收藏 2
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

之前在做网页采集时,需要检查网址是否已经访问过,当时做这个功能时,考虑到只是字符串的搜索功能,第一想到的是用前缀树来处理,并找到了一个叫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 发表评论

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 72
博文 83
码字总数 51490
作品 2
×
penngo
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: