五个Java类 揭秘 多关键字搜索 引擎

最近看了《数学之美系列五》-- 简单之美：布尔代数和搜索引擎的索引。

通过文章的介绍，了解了搜索引擎的原理，就动手尝试了一下。代码除了学习最基本原理外没有任何价值。所有的操作都是内存操作，与真实的商用搜索系统相差甚远。

首先创建一个索引器，这是最最简单的索引器。

package index;

import java.util.StringTokenizer;

import store.IndexMap;
import store.StoreMap;

/**
 * 建立文章倒排序的索引,一个最简单的索引器
 * @author zhangdp
 *
 */
public class SimpleIndex {

	/**
	 * 将value加入索引
	 * @param value
	 */
	public void index(int num,String value){
		//最简单的分词器
		StringTokenizer st = new StringTokenizer(value);
		while(st.hasMoreTokens()){
			String keyword =st.nextToken();
			IndexMap.index(keyword, num);
		}
	}
}

然后在创建一个存储系统，当然这个只是查找方便使用，也可以不用，直接用文件系统。
想相应的文章按编号索引

package store;

import java.util.HashMap;
import java.util.Map;

public class StoreMap {

	//key 为文章编号，Value 为文章内容
	private static Map<Integer,String> store = new HashMap<Integer,String>();
	
	public static  void put(Integer key,String value){
		store.put(key, value);
	}
	
	public static String get(Integer key){
		return store.get(key);
	}
}

然后创建最关键的部分了-索引

package store;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 倒排索引
 * @author zhangdp
 *
 */
public class IndexMap {

	/**
	 * 索引，key为关键字，value为文章列表向量，第i位的值为true表示
	 * 第i个文章中出现key这个关键词，否则没出现
	 * 
	 */
	private static Map<String,BitVector> indexMap = new HashMap<String,BitVector>();

	/**
	 * 创建索引
	 * @param key
	 * @param num
	 */
	public  static void  index(String key,int num){

		if(indexMap.containsKey(key)){
			BitVector bv = indexMap.get(key);
			bv.set(num);
			indexMap.put(key, bv);//更新
		}else{
			BitVector bv = new BitVector(10);//假设就10篇文章
			//初始化都为False
			for(int i = 0;i<10;i++){
				bv.clear(i);
			}
			bv.set(num);
			indexMap.put(key, bv);
		}
	}

	/***
	 * 在索引上进行搜索
	 * @param keyList 关键字列表
	 * @return 文章编号列表
	 */
	public static List search(List keyList){
		Set keySet = indexMap.keySet();
		BitVector bv = indexMap.get(keyList.get(0));
		for(int i =1;i<keyList.size();i++){
                //按位与结果中位图向量上为1的代表词文章出现了所有关键词
			bv=bv.comp(indexMap.get(keyList.get(i)));
		}
		List result = new ArrayList();
		for(int i = 0;i<bv.size();i++){
			if(bv.get(i)){
				result.add(Integer.valueOf(i));
			}
		}
		return result;
	}

}

索引中用到了一个位图向量，位图向量在解决存储空间压缩，整数排序等方面很有优势。

package store;

import java.io.IOException;

/**
 * 一个位图向量
 * @author zhangdp
 *
 */
public final class BitVector {

  private byte[] bits;
  private int size;
  private int count = -1;


  public BitVector(int n) {
    size = n;
    bits = new byte[(size >> 3) + 1];
  }


  /**
   * 将第bit位的值设置为1
   * @param bit
   */
  public final void set(int bit) {
    bits[bit >> 3] |= 1 << (bit & 7);
    count = -1;
  }


  /**
   * 将第bit位的值设置为0
   * @param bit
   */
  public final void clear(int bit) {
    bits[bit >> 3] &= ~(1 << (bit & 7));
    count = -1;
  }


  /**
   * 如果第i位的值为1返回True,否则返回False
   * @param bit
   * @return
   */
  public final boolean get(int bit) {
    return (bits[bit >> 3] & (1 << (bit & 7))) != 0;
  }

  public final int size() {
    return size;
  }

  /**
   * 按位&操作，两个关键词后的位图向量按位与操作，值为1位的话代表该编号
   * 文章同时出现这两个关键字，跟多关键字原理相同
   * @param bv
   * @return
   */
  public final BitVector comp(BitVector bv){
	  for(int i=0;i<bv.bits.length;i++){
		  bits[i]=(byte) (bits[i]&bv.bits[i]);
	  }
	  return this;
  }


}

创建完了索引系统了，应该再创建一个查询系统，不然就没有用了啊。

package search;

import java.util.List;

import store.IndexMap;
import store.StoreMap;

/**
 * 一个最简单的搜索类
 * @author zhangdp
 *
 */
public class SimpleSearch {

	/**
	 * 搜索并打印出来结果
	 * @param list 关键字列表
	 * @return 文件编号列表
	 */
	public void search(List list){
		//搜索到的文章编号
		List result = IndexMap.search(list);
		//显示搜索结果
		for(int i = 0;i<result.size();i++){
			Integer it = (Integer) result.get(i);
			System.out.println(StoreMap.get(it));
		}
	}
}

最后测试一下吧，是能做到多关键字搜索吧。

package test;

import java.util.List;
import java.util.ArrayList;

import search.SimpleSearch;
import store.StoreMap;
import index.SimpleIndex;

public class TestMain {

	public static void main(String args[]){
		String s1 = "Google is a engine";
		String s2 = "baidu is a engine";
		String s3 = "soso is a engine and javaeye is not";
		
		StoreMap.put(1, s1);
		StoreMap.put(2, s2);
		StoreMap.put(3, s3);
		SimpleIndex si = new SimpleIndex();
		
		si.index(1, s1);
		si.index(2, s2);
		si.index(3, s3);
		SimpleSearch ss = new SimpleSearch();
		List list = new ArrayList();
		list.add("is");//关键字列表
		list.add("javaeye");
		ss.search(list);
	}
}

评论

1 楼 jayje 2010-01-05  

想法不错。不过还需要多完善！