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

五个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篇文章//初始化都为Falsefor(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   想法不错。不过还需要多完善！

查看更多 下一篇