【从0做项目】Java搜索引擎（2）图解索引结构

三三是该溜子

发布于 2025-02-16 19:19:20

16600

代码可运行

文章被收录于专栏：该溜子的专栏该溜子的专栏

运行总次数：0

代码可运行

文章导读

阿华将发布项目复盘系列的文章，旨在：

1：手把手细致带大家从0到1做一个完整的项目，保证每2~3行代码都有详细的注解

2：通过文字+画图的方式，对项目进行整个复盘，更好的理解以及优化项目

3：总结自己的优缺点，扎实java相关技术栈，增强文档编写能力

零：项目结果展示

简述：在我的搜索引擎网站，用户进行关键字搜索，就可以查询到与这个关键字相关的java在线文档，（包含标题，关键字附近的简述，url），用户点击标题，即可跳转到相关在线文档，适用于JDK17版本。

一：功能实现准备

导入：搜索引擎（1）文章中我们在Parse类中实现了枚举文件，和解析文件的接口现在我们要考虑把解析出来的结果构建到正排索引和倒排索引结构中了

二：实体类

1：DocInfo

DocInfo对象用于记录文档相关的信息，这里引入了lombok依赖，自动会生成get和set方法

@Data
public class DocInfo {
    private int docId;
    private String title;
    private String url;
    private String content;
}

<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok</artifactId>
    <optional>true</optional>
</dependency>

2：Weight

//权重：文档id   和   文档和词语的相关性   建立联系
@Data
public class Weight {
    private int docId;
    //weight的值越大，相关性越强
    private int weight;
}

三：具体功能实现

index类中进行完善

1：构建索引结构

优点：查正排和查倒排时间复杂度都是O1，数据都是放在内存当中的，所以读写速度更快

 //使用数组下标来表示docId,（前置索引）
    private ArrayList<DocInfo> forwardIndex = new ArrayList<>();

    //使用哈希表来表示倒排索引，key是词，value是一组跟这个词相关联的文章（倒排索引）
    private HashMap<String,ArrayList<Weight>> invertedIndex = new HashMap<>();

2：添加文档

新增一个文档的时候，正排和倒排索引都要更新


//3：新增文档
    public void addDoc(String title , String url , String content){
        //新增文档操作，正排、倒排索引都需要更新
        //1：构建正排索引
        DocInfo docInfo = buildForward(title,url,content);
        //2：构建倒排索引
        buildInverted(docInfo);
    }

（1）往正排索引中添加

实现buildForWard方法，加锁这里大家先忽略，我将在性能优化篇重点介绍

这里实现的逻辑很简单，构建一个DocInfo对象，把它加入正排索引即可。

注意一点：新加入的文档id就是正排索引的长度，比如第一个加入的文档DocId = 0 ，因为此时正排索引的长度为0.

    private DocInfo buildForward(String title , String url , String content){
        DocInfo docInfo = new DocInfo();
        docInfo.setTitle(title);
        docInfo.setUrl(url);
        docInfo.setContent(content);
        synchronized(locker1){//对index加锁
            docInfo.setDocId(forwardIndex.size());//新加入的文档id就是正排索引集合的长度
            forwardIndex.add(docInfo);
        }
        return docInfo;
    }

（2）往倒排索引中添加

实现buildInverted方法，这里逻辑是不是看着就头大，（大家结合代码和注释看会更清晰）待我慢慢分析

①标题和正文词频统计

首先我们对一个文档的标题和正文分别进行词频统计，不难理解标题中出现的词，它的权重更大，更能概括整篇文章的意思。

（像大家在高中写作文，得取一个能概括本篇文章中心主题的标题嘛，这样别人一看，就知道了你这篇文章大概要讲啥）

②创建词频对象

这里创建一个词频对象，对象中包含标题中出现的次数和正文中出现的次数

注意，这里一个词在标题中出现了，它的权重相当于在正文中出现10次，简单策略，实际我们常用的搜狗啊百度啊这一块的逻辑算法肯定是更加复杂的。（比如多个公式的迭代，荒泷一斗把一堆蛐蛐放到一起打，最后胜者为蛐蛐王）

③步骤

步骤一：对标题进行分词，统计词频

步骤二：对正文进行分词，统计词频

（3）注意点

这里我们使用三方库后的分词结果中，三方库已经自动帮我们把大写英语字母转化为了小写，大家如果使用别的三方库，一定要测试一下，是否大小写转化了，不然统计就会有问题

不多bb直接上图

    private void buildInverted(DocInfo docInfo){
        class WordCnt{
            //统计这个词在标题和正文中出现的次数，标题权重大
            public int titleCount;
            public int contentCount;
        }
        //map来统计词频
        HashMap<String,WordCnt> wordCntHashMap = new HashMap<>();

        //1:对标题分词
        List<Term> terms = ToAnalysis.parse(docInfo.getTitle()).getTerms();
        //2:遍历，统计词频
        for(Term term : terms){
            String word = term.getName();
            WordCnt wordCnt = wordCntHashMap.get(word);//map中不存在这个key，就返回null

            if(wordCnt == null){
                WordCnt newWordCnt = new WordCnt();
                newWordCnt.titleCount = 1;
                newWordCnt.contentCount = 0;
                wordCntHashMap.put(word,newWordCnt);
            }else {
                wordCnt.titleCount += 1;
            }
        }
        //3：对正文进行词频统计
        terms = ToAnalysis.parse(docInfo.getContent()).getTerms();//集合重复利用
        for(Term term : terms){
            String word = term.getName();
            WordCnt wordCnt = wordCntHashMap.get(word);
            if(wordCnt == null){
                WordCnt newWordCnt = new WordCnt();
                newWordCnt.titleCount = 0;
                newWordCnt.contentCount = 1;
                wordCntHashMap.put(word,newWordCnt);
            }else {
                wordCnt.contentCount += 1;
            }
        }
        //把wordCntHashMap中存储的结果汇总到一个Map中
        //文档的权重 =  标题中出现的次数 * 10 + 正文中出现的次数
        //在遍历这个Map，更新倒排索引中的结构
        for(Map.Entry<String,WordCnt> entry : wordCntHashMap.entrySet()){
            synchronized (locker2){
                List<Weight> invertedList = invertedIndex.get(entry.getKey());//去倒排索引中看是否已经存在当前词
                if(invertedList == null){
                    ArrayList<Weight> newInvertedList = new ArrayList<>();
                    Weight weight = new Weight();
                    weight.setDocId(docInfo.getDocId());
                    weight.setWeight(entry.getValue().titleCount * 10 + entry.getValue().contentCount);
                    newInvertedList.add(weight);
                    invertedIndex.put(entry.getKey(),newInvertedList);
                }else {
                    Weight weight = new Weight();
                    weight.setDocId(docInfo.getDocId());
                    weight.setWeight(entry.getValue().titleCount * 10 + entry.getValue().contentCount);
                    invertedList.add(weight);//倒排索引中已经出现了这个词的话，就直接添加到value（集合）中去
                }
            }
        }
    }

这里是一张流程的调用执行图，因为太大了，可能会比较糊，大家保存下来，放大看

3：根据docId返回文档

给一个docId，从正排索引中获取文档

    //1：给定docId，在正排索引中，查询文档详细信息
    public DocInfo getDocInfo(int docId){
        return forwardIndex.get(docId);//docId就对应集合中元素的下标
    }

4：根据词返回Weight集合

给一个词，从倒排索引中获取一堆Weight对象

    //2：在倒排索引中，查询哪些文档和这个词相关联，
    // 不同文档，相关联的程度是不一样的，所以我们用集合来作为返回值
    public List<Weight> getInverted(String term){
        return invertedIndex.get(term);
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-15，如有侵权请联系 cloudcommunity@tencent.com 删除

索引