java实现简单的搜索引擎

记得java老师曾经说过百度的一个面试题目，大概意思是“有1w条无序的记录，如何从其中快速的查找到自己想要的记录”。这个就相当于一个简单的搜索引擎。最近在整理这一年的工作中，自己竟然已经把这个实现了，今天对其进一步的抽象，和大家分享下。

先写具体的实现代码，具体的实现思路和逻辑写在代码之后。

搜索时用于排序的bean

 /**  
 *@description:   
 */  
package cn.lulei.search.engine.model;  
  
public class sortbean { 
  private string id; 
  private int times; 
   
  public string getid() { 
    return id; 
  } 
  public void setid(string id) { 
    this.id = id; 
  } 
  public int gettimes() { 
    return times; 
  } 
  public void settimes(int times) { 
    this.times = times; 
  } 
} 

构造的搜索数据结构以及简单的搜索算法

 /**  
 *@description:   
 */  
package cn.lulei.search.engine;  
 
import java.util.arraylist; 
import java.util.collections; 
import java.util.comparator; 
import java.util.hashmap; 
import java.util.hashset; 
import java.util.list; 
 
import cn.lulei.search.engine.model.sortbean; 
  
public class serachbase { 
  //details 存储搜素对象的详细信息，其中key作为区分object的唯一标识 
  private hashmap<string, object> details = new hashmap<string, object>(); 
  //对于参与搜索的关键词，这里采用的稀疏数组存储，也可以采用hashmap来存储，定义格式如下 
  //private static hashmap<integer, hashset<string>> keysearch = new hashmap<integer, hashset<string>>(); 
  //hashmap中额key值相当于稀疏数组中的下标，value相当于稀疏数组在该位置的值 
  private final static int maxlength = character.max_value; 
  @suppresswarnings("unchecked") 
  private hashset<string>[] keysearch = new hashset[maxlength]; 
   
  /** 
   *@description: 实现单例模式，采用initialization on demand holder加载 
   *@version:1.1.0 
   */ 
  private static class lazyloadserachbase { 
    private static final serachbase serachbase = new serachbase(); 
  } 
   
  /** 
   * 这里把构造方法设置成私有为的是单例模式 
   */ 
  private serachbase() { 
     
  } 
   
  /** 
   * @return  
   * @description: 获取单例 
   */ 
  public static serachbase getserachbase() { 
    return lazyloadserachbase.serachbase; 
  } 
   
  /** 
   * @param id 
   * @return  
   * @description: 根据id获取详细 
   */ 
  public object getobject(string id) { 
    return details.get(id); 
  } 
   
  /** 
   * @param ids 
   * @return  
   * @description: 根据ids获取详细，id之间用","隔开 
   */ 
  public list<object> getobjects(string ids) { 
    if (ids == null || "".equals(ids)) { 
      return null; 
    } 
    list<object> objs = new arraylist<object>(); 
    string[] idarray = ids.split(","); 
    for (string id : idarray) { 
      objs.add(getobject(id)); 
    } 
    return objs; 
  } 
   
  /** 
   * @param key 
   * @return  
   * @description: 根据搜索词查找对应的id，id之间用","分割 
   */ 
  public string getids(string key) { 
    if (key == null || "".equals(key)) { 
      return null; 
    } 
    //查找 
    //idtimes存储搜索词每个字符在id中是否出现 
    hashmap<string, integer> idtimes = new hashmap<string, integer>(); 
    //ids存储出现搜索词中的字符的id 
    hashset<string> ids = new hashset<string>(); 
     
    //从搜索库中去查找 
    for (int i = 0; i < key.length(); i++) { 
      int at = key.charat(i); 
      //搜索词库中没有对应的字符，则进行下一个字符的匹配 
      if (keysearch[at] == null) { 
        continue; 
      } 
      for (object obj : keysearch[at].toarray()) { 
        string id = (string) obj; 
        int times = 1; 
        if (ids.contains(id)) { 
          times += idtimes.get(id); 
          idtimes.put(id, times); 
        } else { 
          ids.add(id); 
          idtimes.put(id, times); 
        } 
      } 
    } 
     
    //使用数组排序 
    list<sortbean> sortbeans = new arraylist<sortbean>(); 
    for (string id : ids) { 
      sortbean sortbean = new sortbean(); 
      sortbeans.add(sortbean); 
      sortbean.setid(id); 
      sortbean.settimes(idtimes.get(id)); 
    } 
    collections.sort(sortbeans, new comparator<sortbean>(){ 
      public int compare(sortbean o1, sortbean o2){ 
        return o2.gettimes() - o1.gettimes(); 
      } 
    }); 
     
    //构建返回字符串 
    stringbuffer sb = new stringbuffer(); 
    for (sortbean sortbean : sortbeans) { 
      sb.append(sortbean.getid()); 
      sb.append(","); 
    } 
     
    //释放资源 
    idtimes.clear(); 
    idtimes = null; 
    ids.clear(); 
    ids = null; 
    sortbeans.clear(); 
    sortbeans = null; 
     
    //返回 
    return sb.tostring(); 
  } 
   
  /** 
   * @param id 
   * @param searchkey 
   * @param obj 
   * @description: 添加搜索记录 
   */ 
  public void add(string id, string searchkey, object obj) { 
    //参数有部分为空，不加载 
    if (id == null || searchkey == null || obj == null) { 
      return; 
    } 
    //保存对象 
    details.put(id, obj); 
    //保存搜索词 
    addsearchkey(id, searchkey); 
  } 
   
  /** 
   * @param id 
   * @param searchkey 
   * @description: 将搜索词加入到搜索域中 
   */ 
  private void addsearchkey(string id, string searchkey) { 
    //参数有部分为空，不加载 
    //这里是私有方法，可以不做如下判断，但为了设计规范，还是加上 
    if (id == null || searchkey == null) { 
      return; 
    } 
    //下面采用的是字符分词，这里也可以使用现在成熟的其他分词器 
    for (int i = 0; i < searchkey.length(); i++) { 
      //at值相当于是数组的下标，id组成的hashset相当于数组的值 
      int at = searchkey.charat(i); 
      if (keysearch[at] == null) { 
        hashset<string> value = new hashset<string>(); 
        keysearch[at] = value; 
      } 
      keysearch[at].add(id); 
    } 
  } 
   
   
 
} 

测试用例：

 /**  
 *@description:   
 */  
package cn.lulei.search.engine.test;  
 
import java.util.list; 
 
import cn.lulei.search.engine.serachbase; 
  
public class test { 
  public static void main(string[] args) { 
    // todo auto-generated method stub  
    serachbase serachbase = serachbase.getserachbase(); 
    serachbase.add("1", "你好！", "你好！"); 
    serachbase.add("2", "你好！我是张三。", "你好！我是张三。"); 
    serachbase.add("3", "今天的天气挺好的。", "今天的天气挺好的。"); 
    serachbase.add("4", "你是谁？", "你是谁？"); 
    serachbase.add("5", "高数这门学科很难", "高数确实很难。"); 
    serachbase.add("6", "测试", "上面的只是测试"); 
    string ids = serachbase.getids("你的高数"); 
    system.out.println(ids); 
    list<object> objs = serachbase.getobjects(ids); 
    if (objs != null) { 
      for (object obj : objs) { 
        system.out.println((string) obj); 
      } 
    } 
  } 
 
} 

测试输出结果如下：

5,3,2,1,4,
高数确实很难。
今天的天气挺好的。
你好！我是张三。
你好！
你是谁？

这样一个简单的搜索引擎也就算是完成了。

问题一：这里面的分词采用的是字符分词，对汉语的处理还是挺不错的，但是对英文的处理就很弱。

改进方法：采用现在成熟的分词方法，比如ikanalyzer、standardanalyzer等，这样修改，keysearch的数据结构就需要做下修改，可以修改为 private hashmap<string, string>[] keysearch = new hashmap[maxlength]; 其中key存储分的词元，value存储唯一标识id。

问题二：本文实现的搜索引擎对词元并没有像lucene设置权重，只是简单的判断词元是否在对象中出现。

改进方法：暂无。添加权重处理，使数据结构更加复杂，所以暂时没有对其做处理，在今后的文章中会实现权重的处理。

下面就简单的介绍一下搜索引擎的实现思路。

在serachbase类中设置details和keysearch两个属性，details用于存储object的详细信息，keysearch用于对搜索域做索引。details数据格式为hashmap，keysearch的数据格式为稀疏数组（也可以为hashmap，hashmap中额key值相当于稀疏数组中的下标，value相当于稀疏数组在该位置的值）。

对于details我就不做太多的介绍。

keysearch中数组下标（如用hashmap就是key）的计算方法是获取词元的第一个字符int值（因为本文的分词采用的是字符分词，所以一个字符就是一个词元），该int值就是数组的下标，相应的数组值就是object的唯一标识。这样keysearch的数据结构就如下图

因此想添加新纪录的时候只需要调用add方法即可。

对于搜索的实现逻辑和上面的keysearch类似。对于id的搜索直接使用hashmap的get方法即可。对于搜索词的一个搜索，整体的过程也是采用先分词、其次查询、最后排序。当然这里面的分词要和创建采用的分词要一致（即创建的时候采用字符分词，查找的时候也采用字符分词）。

在getids方法中，hashmap<string, integer> idtimes = new hashmap<string, integer>();idtimes 变量用来存储搜索词中的词元有多少个在keysearch中出现，key值为唯一标识id，value为出现的词元个数。hashset<string> ids = new hashset<string>(); ids变量用来存储出现的词元的ids。这样搜索的复杂度就是搜索词的词元个数n。获得包含词元的ids，构造sortbean数组，对其排序，排序规则是出现词元个数的降序排列。最后返回ids字符串，每个id用"，"分割。如要获取详细信息
再使用getobjects方法即可。

上述的只是一个简单的搜索引擎，并没有设计太多的计算方法，希望对大家的学习有所启发。