java实现简单的搜索引擎

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 details = new HashMap();

//对于参与搜索的关键词，这里采用的稀疏数组存储，也可以采用HashMap来存储，定义格式如下

//private static HashMap> keySearch = new HashMap>();

//HashMap中额key值相当于稀疏数组中的下标，value相当于稀疏数组在该位置的值

private final static int maxLength = Character.MAX_VALUE;

@SuppressWarnings("unchecked")

private HashSet[] 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

if (ids == null || "".equals(ids)) {

return null;

}

List

String[] idArray = ids.split(",");

for (String id : idArray) {

objs.add(getObjecJzMAHt(id));

}

return objs;

}

/**

* @param key

* @return

* @Description: 根据搜索词查找对应的id，id之间用","分割

*/

public String getIds(String key) {

if (key == null || "".equals(key)) {

return null;

}

//查找

//idTimes存储搜索词每个字符在id中是否出现

HashMap idTimes = new HashMap();

//ids存储出现搜索词中的字符的id

HashSet ids = new HashSet();

//从搜索库中去查找

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 sortBeans = new ArrayList();

for (String id : ids) {

SortBean sortBean = new SortBean();

sortBeans.add(sortBean);

sortBean.setId(id);

sortBean.setTimes(idTimes.get(id));

http:// }

Collections.sort(sortBeans, new Comparator(){

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 value = new HashSet();

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

if (objs != null) {

for (Object obj : objs) {

System.out.println((String) obj);

}

}

}

}

测试输出结果如下：

5,3,2,1,4,

高数确实很难。

今天的天气挺好的。

你好！我是张三。

你好！

你是谁？

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

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

改进方法：采用现在成熟的分词方法，比如IKAnalyzer、StandardAnalyzer等，这样修改，keySearch的数据结构就需要做下修改，可以修改为 private HashMap[] 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 idTimes = new HashMap();idTimes 变量用来存储搜索词中的词元有多少个在keySearch中出现，key值为唯一标识id，value为出现的词元个数。HashSet ids = new HashSet(); ids变量用来存储出现的词元的ids。这样搜索的复杂度就是搜索词的词元个数n。获得包含词元的ids，构造SortBean数组，对其排序，排序规则是出现词元个数的降序排列。最后返回ids字符串，每个id用"，"分割。如要获取详细信息

再使用getObjects方法即可。

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。