posts - 59, comments - 244, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

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

Posted on 2011-01-01 22:11 penngo 阅读(2210) 评论(2)  编辑  收藏 所属分类: Java
之前在做网页采集时,需要检查网址是否已经访问过,当时做这个功能时,考虑到只是字符串的搜索功能,第一想到的是用前缀树来处理,并找到了一个叫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月份左右,才会用姚明换取一位***。





评论

# re: 利用前缀树处理数据重复出现的问题  回复  更多评论   

2011-01-02 18:16 by buy ugg boots
呃,一大串的,头疼勒,回家了

# re: 利用前缀树处理数据重复出现的问题  回复  更多评论   

2011-01-10 12:47 by 610622106
楼主,链表的功能实现了么? 方便的话,也贴出来,分享一下...........

只有注册用户登录后才能发表评论。


网站导航: