认识搜索引擎
像百度搜索这样，输入要搜索的内容，点击搜索，就会出现若干条结果，每条结果包含标题，内容描述，展示url，图片，图标等相关的内容。如下图输入"恰似故人归"点击百度一下，就会出现如下的页面。
搜索引擎的本质就是输入一个查询词，得到若干个搜索结果,其中包含了标题，描述，展示url和点击url。
搜索的核心思路
我们把每一个网页称为一个文档，每一次的搜索就是在所有文档中查找查询词，检查文档中是否包含要查询的词或字符串。但是细想这种方法直接暴力且开销巨大，随着文档的增多，搜索的时间也随之延长，而搜索引擎往往对效率要求非常高，试想如果你的每一次搜索都需要1分钟时间才会有相应的搜素结果你还会用这个搜索引擎吗？
因此我们想到倒排索引，这是一种专门针对搜素引擎场景而设计的数据结构。
倒排索引
文档:被检索的html页面
正排索引:一个文档中包含了那些词，描述一个文档的基本信息，将文档中的词进行分词处理并存储。
倒排索引:一个词被那些文档所引用，描述一个词的基本信息，存储了这个词都存在在那些文档中，这个词在文档中的重要程度。
项目介绍
下面我们对Java API文档实现一个搜索引擎。
首先我们需要在官方页面下载Java API文档到本地，此处附上下载地址:Java API 文档下载
主要实现下面三个模块:
- 索引模块:扫描下载的文档，分析数据内容构建正排索引和倒排索引，并保存到文件中。
- 搜索模块:加载索引，根据输入的查询词，基于正排+倒排索引进行检索得到检索结果。
- web模块:编写一个简单的页面，展示搜索结果。点击搜素结果跳转到对应的线上Java API文档页面
关于分词
上面我们提到的正排索引，倒排索引首先都需要对文档中的内容进行分词处理，下面我们使用现成的ansj分词库进行分词操作。
首先我们需要在所创建项目的pom.xml中插入如下代码。
<dependency>
<groupId>org.ansj</groupId>
<artifactId>ansj_seg</artifactId>
<version>5.1.6</version>
</dependency>
下面通过如下示例演示分词操作:
public class test1 {
public static void main(String[] args) {
String s="与君初相识恰是故人归";
List<Term> terms= ToAnalysis.parse(s).getTerms();
for (Term term:terms) {
System.out.print(term.getName()+" ");
}
}
}
输出:
实现索引模块
实现Parser类
- 根据指定路径枚举出路径中所有的文件，此过程要把所有子目录中的文件都获取到
- 针对获取到的文件路径，打开文件读取文件内容，并进行解析，构建索引
- 把在内存中构建好的索引数据结构保存的到指定的文件中
enumFile方法实现读文件
使用ArrayList< File > fileList用来存放所有文件的具体路径，封装enumFile方法递归读取文件,参数分别为读文件的根目录，存放所有文件路径的数组fileList。
首先将根目录的字符串转换为File类方便读取，通过file.ListFiles()方法获取当前目录下的文件，此方法获取到的是一个File类型的数组，通过遍历数组使用isDirectory判断其是否是目录，是目录就递归遍历下一次，否则就将其放入到fileList中
private void enumFile(String inputPath, ArrayList<File> result) {
//将目录字符串转为File类
File rootFile=new File(inputPath);
File[] files=rootFile.listFiles();
for (File f:files) {
if(f.isDirectory()) {
//当前是一个目录，递归往下继续读取
enumFile(f.getAbsolutePath(),result);
} else {
//判断其是否是以.html结尾的文件
if(f.getAbsolutePath().endsWith(".html")) {
result.add(f);
}
}
}
}
parseHTML方法实现解析文件
分别使用parseTitle()方法解析标题，parseUrl()方法解析url,parseContent()方法解析正文
private void parseHTML(File file) {
//1.解析HTML标题
String title=parseTitle(file);
//2.解析HTML对应的URL
String url=parseUrl(file);
//3.解析HTML对应的正文
String content=parseContent(file);
//4.将其添加到索引中
index.addDoc(title,url,content);
}
parseTitle方法实现
通过获取HTML文件名获取标题，通过File类中的getname方法获取文件名，但此时的文件名还包含.html后缀使用substring方法对字符串截取。
private String parseTitle(File file) {
String title=file.getName().substring(0,file.getName().length()-".html".length());
return title;
}
parseUrl方法实现
此处我们希望用户点击搜素结果能够跳转到对应的线上文档的页面，这里就需要我们获取的是一个线上的url，根据对线上和线下文档url的对比我们不难发现其后半部分是一致的内容，而线上文档的前半部分是固定不变的。所以我们根据本地文档路径获取其后半部分，并于其线上文档的前半部分固定字符串进行拼接以此获取线上文档对应的url。
private String parseUrl(File file) {
String s1=file.getAbsolutePath().substring(INPUT_PATH.length());
String s2="https://docs.oracle.com/javase/8/docs/api/";
return s2+s1;
}
parseContent方法实现
依次读取HTML中的每个字符，针对取出的字符进行判定。如果字符不是<,就直接把当前字符进行拷贝，如果字符是<,那么从<位置开始直到遇到>为止包含在内的所有字符都不进行拷贝。
private String parseContent(File file) {
try(FileReader fileReader=new FileReader(file)) {
//读取文件按字符读取
boolean isContent=true;
StringBuilder stringBuilder=new StringBuilder();
while (true) {
int ret=fileReader.read();
if(ret==-1) {
break;
}
char c= (char) ret;
if(isContent) {
if(c=='<') {
isContent=false;
continue;
}
if(c=='\n'||c=='\r') {
c=' ';
}
stringBuilder.append(c);
} else {
if(c=='>') {
isContent=true;
}
}
}
return stringBuilder.toString();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return "";
}
Paraer类整体代码
package com.example.searchengines;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class Parser {
private static final String INPUT_PATH = "D:/jdk-8/docs/api";
private Index index=new Index();
public static void main(String[] args) throws InterruptedException {
Parser parser=new Parser();
parser.run();
}
private void run() {
//1.根据指定路劲，枚举路劲中所有文件
ArrayList<File> result=new ArrayList<>();
enumFile(INPUT_PATH,result);
for (File file:result) {
System.out.println("解析 "+file.getAbsolutePath());
//2.读取文件并解析html
parseHTML(file);
}
System.out.println("解析完成");
//保存到文件中
index.save();
}
private void parseHTML(File file) {
//1.解析HTML标题
String title=parseTitle(file);
//2.解析HTML对应的URL
String url=parseUrl(file);
//3.解析HTML对应的正文
String content=parseContent(file);
//4.将其添加到索引中
index.addDoc(title,url,content);
}
private String parseContent(File file) {
try(FileReader fileReader=new FileReader(file)) {
//读取文件按字符读取
boolean isContent=true;
StringBuilder stringBuilder=new StringBuilder();
while (true) {
int ret=fileReader.read();
if(ret==-1) {
break;
}
char c= (char) ret;
if(isContent) {
if(c=='<') {
isContent=false;
continue;
}
if(c=='\n'||c=='\r') {
c=' ';
}
stringBuilder.append(c);
} else {
if(c=='>') {
isContent=true;
}
}
}
return stringBuilder.toString();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return "";
}
private String parseUrl(File file) {
String s1=file.getAbsolutePath().substring(INPUT_PATH.length());
String s2="https://docs.oracle.com/javase/8/docs/api/";
return s2+s1;
}
private String parseTitle(File file) {
String title=file.getName().substring(0,file.getName().length()-".html".length());
return title;
}
private void enumFile(String inputPath, ArrayList<File> result) {
//将目录字符串转为File类
File rootFile=new File(inputPath);
File[] files=rootFile.listFiles();
for (File f:files) {
if(f.isDirectory()) {
//当前是一个目录，递归往下继续读取
enumFile(f.getAbsolutePath(),result);
} else {
if(f.getAbsolutePath().endsWith(".html")) {
result.add(f);
}
}
}
}
}
实现Index类
- 给定一个docId，在正排索引中，查询文档的详细信息
- 给定一个词，在倒排索引中，查询那些文档和这个词关联
- 往正排索引和倒排索引中新增一个文档
- 把内存中的索引数据结构保存到磁盘中
- 把磁盘中的索引数据结构加载到内存中
public class Index {
private static final String INDEX_PATH="D:\\jdk-8";
// 正排索引,下标对应docId
private ArrayList<DocInfo> forwardIndex=new ArrayList<DocInfo>();
// 倒排索引 键为词，值为其权重
private HashMap<String,ArrayList<Weight>> invertedIndex=new HashMap<>();
//1.在正排索引中查询文档信息
public DocInfo getDocInfo(int docId) {
}
//2.给定一个词，在倒排索引中查找与那些文档关联
public ArrayList<Weight> getInverted(String term) {
}
//3.往索引中新增一个文档
public void addDoc(String title,String url,String content) {
}
//4.保存索引到文件中
public void save() {
}
//5.加载索引到内存
public void load() {
}
Weight类
创建Weight类，用来表示一个文档的权重信息。将文档id和文档与词的相关性权重进行的一个包装。
package com.example.searchengines;
import lombok.Data;
@Data
public class Weight {
private int DocId;
//weight值越大就认为相关性越强
private int weight;
}
DocInfo类
DocInfo类中主要包含了文档的id，标题，url，内容相关的信息。
package com.example.searchengines;
import lombok.Data;
@Data
public class DocInfo {
private int DocId;
private String title;
private String url;
private String content;
}
实现getDocInfo和getInverted方法
//1.在正排索引中查询文档信息
public DocInfo getDocInfo(int docId) {
return forwardIndex.get(docId);
}
//2.给定一个词，在倒排索引中查找与那些文档关联
public ArrayList<Weight> getInverted(String term) {
return invertedIndex.get(term);
}
实现addDoc方法
往索引中插入新文档，我们需要同时往正排索引和倒排索引中插入新文档，buildForward()方法实现往正排索引中插入，buildIndex()方法实现往倒排索引中插入。
public void addDoc(String title,String url,String content) {
//正排索引插入
DocInfo docInfo=buildForward(title,url,content);
//往倒排索引中插入文档
buildIndex(docInfo);
}
buildForward()方法实现
直接将其插入forwardIndex数组中即可，此时forwardIndex数组的长度就是DocId。
private DocInfo buildForward(String title,String url,String content) {
DocInfo docInfo=new DocInfo();
docInfo.setTitle(title);
docInfo.setUrl(url);
docInfo.setContent(content);
//此处插入的DocId是正排数组的插入，其插入是在最后插入
docInfo.setDocId(forwardIndex.size());
//往正排索引中插入文档
forwardIndex.add(docInfo);
}
return docInfo;
}
buildIndex()方法实现
使用buildIndex()方法进行倒排索引的插入，需要知道词与文档Id的映射，首先需要对文档标题和正文进行分词，结合分词结果计算其权重进行倒排索引的插入。其主要分为以下六个步骤
- 针对标题进行分词
- 遍历分词结果统计每个词出现的次数
- 针对正文进行分词
- 遍历分词结果统计每个词出现的次数
- 把上面结果汇总到一个HashMap中，权重=标题中出现的次数*10+正文中出现的次数(此处计算是一个拍脑门想法也可以自己设置)
- 遍历HashMap得到词和权重的映射关系，更新到倒排索引中
使用WordCnt内部类表示词在标题中出现的次数和在正文中出现的次数
private void buildIndex(DocInfo docInfo) {
class WordCnt {
public int titleCount;
public int contentCount;
public WordCnt(int titleCount,int contentCount) {
this.titleCount=titleCount;
this.contentCount=contentCount;
}
}
HashMap<String,WordCnt> wordCntMap=new HashMap<>();
//1.对标题进行分词
List<Term> terms= ToAnalysis.parse(docInfo.getTitle()).getTerms();
//2.遍历分词结果，统计标题中每个词出现的次数
for (Term term:terms) {
//获取词
String word=term.getName();
//在表中查找是否存在其键
WordCnt newWordCnt=wordCntMap.get(word);
if(newWordCnt==null) {
wordCntMap.put(word,new WordCnt(1,0));
} else {
newWordCnt.titleCount++;
}
}
//3.对正文进行解析
terms=ToAnalysis.parse(docInfo.getContent()).getTerms();
//4.遍历分词结果，统计正文中每个词出的次数
for (Term term:terms) {
String word=term.getName();
WordCnt wordCnt=wordCntMap.get(word);
if(wordCnt==null) {
wordCntMap.put(word,new WordCnt(0,1));
} else {
wordCnt.contentCount++;
}
}
//5.把以上内容整理到一个Hash Map中
for (Map.Entry<String,WordCnt> entry:wordCntMap.entrySet()) {
Weight weight=new Weight();
weight.setDocId(docInfo.getDocId());
//计算权重
weight.setWeight(entry.getValue().titleCount*10+entry.getValue().contentCount);
//在倒排索引中寻找是否存在当前词
ArrayList<Weight> invertedList=invertedIndex.get(entry.getKey());
//不存在就加入
if (invertedList==null) {
invertedList=new ArrayList<>();
invertedIndex.put(entry.getKey(),invertedList);
}
//存在当前词的键，就将其新的权重加入
invertedList.add(weight);
}
}
实现save方法 保存索引到文件
需要把内存中的索引结构变成一个"字符串"，然后写入文件 此操作称为序列化。使用JSON格式进行序列化。
首先在pom.xml中插入Jackson库
<!-- https://mvnrepository.com/artifact/com.fasterxml.jackson.core/jackson-databind -->
<dependency>
<groupId>com.fasterxml.jackson.core</groupId>
<artifactId>jackson-databind</artifactId>
<version>2.13.2.2</version>
</dependency>
保存索引到文件中，生成两个文件forward.txt和inverted.txt，通过JSON格式表示
public void save() {
System.out.println("保存索引开始");
//保存在当前目录下
File indexPathFile=new File(INDEX_PATH);
//目录为空进行创建
if(indexPathFile.exists()) {
indexPathFile.mkdirs();
}
//保存正排索引 使用JSON格式进行保存
File forwardIndexFile=new File(INDEX_PATH + "forward.txt");
//保存倒排索引
File invertedIndexFile=new File(INDEX_PATH + "inverted.txt");
try {
objectMapper.writeValue(forwardIndexFile,forwardIndex);
objectMapper.writeValue(invertedIndexFile,invertedIndex);
} catch (IOException e) {
e.printStackTrace();
}
}
实现load方法 加载索引到内存中
public void load() {
long beg=System.currentTimeMillis();
System.out.println("加载索引开始");
File forwardIndexFile=new File(INDEX_PATH+"forward.txt");
File invertedIndexFile=new File(INDEX_PATH+"inverted.txt");
try {
//读取对应文件中的内容并按照指定的格式进行解析
forwardIndex=objectMapper.readValue(forwardIndexFile, new TypeReference<ArrayList<DocInfo>>() {
});
invertedIndex=objectMapper.readValue(invertedIndexFile, new TypeReference<HashMap<String, ArrayList<Weight>>>() {
});
} catch (IOException e) {
e.printStackTrace();
}
long end=System.currentTimeMillis();
System.out.println("加载索引结束，消耗时间为: "+(end-beg)+"ms");
}
实现搜索模块
实现DocSearcher类，此类负责搜素功能，使用search方法进行根据查询词，完成搜素过程。使用Result类表示一次搜素的结果。
创建DocSearcher类
public class DocSearcher {
public List<Result> search(String query) {
}
}
创建Result类
表示搜素结果
package com.example.searchengines;
import lombok.Data;
@Data
public class Result {
private String title;
private String url;
//正文的摘要
private String desc;
}
实现search方法
参数是用户给出的查询词，返回值是搜素结果的集合
- 分词 针对查询词进行分词处理
- 针对分词结果查倒排
- 针对上面结果按照权重进行降序排序
- 针对排序的结果查正排构造出返回的结果
分词操作
//1.分词
List<Term> terms= ToAnalysis.parse(query).getTerms();
查倒排
Index index=new Index();
index.load();//加载索引
ArrayList<Weight> allResult=new ArrayList<>();
for (Term term:terms) {
String word=term.getName();
ArrayList<Weight> list=index.getInverted(word);
if(list==null) {
continue;
}
allResult.addAll(list);
}
根据权重进行降序
//3.针对结果进行排序按权重降序排列
allResult.sort(new Comparator<Weight>() {
@Override
public int compare(Weight o1, Weight o2) {
return o2.getWeight()-o1.getWeight();
}
});
返回结果
需要注意的是此时返回的内容是正文的一个描述，因此我们使用GenDesc方法对正文内容进行一个截取操作。
//4.返回结果
List<Result> results=new ArrayList<>();
for (Weight weight:allResult) {
DocInfo docInfo=index.getDocInfo(weight.getDocId());
Result result=new Result();
result.setTitle(docInfo.getTitle());
result.setUrl(docInfo.getUrl());
result.setDesc(GenDesc(docInfo.getContent(),terms));
results.add(result);
}
return results;
GenDesc实现
- 找到分词在正文中第一次出现的位置
- 进行截断操作，从第一次出现位置往前找90个字符作为起始位置，然后从起始位置往后找130位置作为终止位置，注意此处选取数字都是随意决定的自己可以按照喜好修改。
在查找位置时需要注意，经过分词结果都转换为小写字母了，所有需要将正文内容转换为小写后进行查询。
private String GenDesc(String content, List<Term> terms) {
//找出word在content中出现第一次的位置
int firsPos=-1;
for (Term term:terms) {
String firsWord=term.getName();
firsPos=content.toLowerCase().indexOf(" "+firsWord+" ");
if(firsPos>0) {
break;
}
}
//分词不存在直接返回空
if(firsPos==-1) {
return "";
}
//进行截断 从firsPos往前找90个字符作为描述的开始，然后从开始位置往后130个字符作为描述的结束
String desc="";
int descBeg=firsPos<90?0:firsPos-90;
if(descBeg+130>content.length()) {
desc=content.substring(descBeg,content.length());
} else {
desc=content.substring(descBeg,descBeg+130)+"...";
}
return desc;
}
验证DocSearcher
public static void main(String[] args) {
DocSearcher docSearcher=new DocSearcher();
List<Result> results=docSearcher.search("ArrayList");
for (Result result:results) {
System.out.println("================");
System.out.println(result);
System.out.println("=================");
}
}
观察结果我们发现如下图一些不符合要求的结果:
这是因为在Parser类中的parseHTML方法中解析HTML对应的正文时 只是去掉了标签本身, 而像 script 这种标签没去掉其中的内容.因此下面我们基于正则表达式去除script标签内容，HTML标签本身即多余的空格。
正则表达式中的特殊符号:
- .表示匹配一个非换行字符(不是\n,\r）
- *代表前面的字符可以不出现，也可以出现一次或者多次（0次、或1次、或多次）
- .*匹配非换行字符出现若干次
- ?表示“非贪婪匹配”匹配到一个符号条件的最短结果
- +代表前面的字符必须至少出现一次（1次或多次）
private String parseContentByRegular(File file) {
//1.将文件读到String中
String content=readFile(file);
//2.替换掉script标签
content=content.replaceAll("<script.*?>(.*?)</script>"," ");
//3.替换掉html标签
content=content.replaceAll("<.*?>"," ");
//4.替换掉多个空格
content=content.replaceAll("\\s+"," ");
return content;
}
private String readFile(File file) {
try(BufferedReader bufferedReader=new BufferedReader(new FileReader(file))) {
StringBuilder stringBuilder=new StringBuilder();
while (true) {
int ret=bufferedReader.read();
if(ret==-1) {
break;
}
char c= (char) ret;
if(c=='\n'||c=='\r') {
c=' ';
}
stringBuilder.append(c);
}
return stringBuilder.toString();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return "";
}
实现web模块
实现DescSearcherController
通过SpringBoot提供web服务，通过get方法提供web接口，返回json格式的数据.
请求:GET/searcher?query=[查询词] HTTP/1.1
相应:HTTP/1.1 200 OK
[
{
title:“这是标题”,
url：“这是url”,
desc：“这是描述”，
}
]
@RestController
@ResponseBody
public class DescSearcherController {
//查找类
private static DocSearcher searcher=new DocSearcher();
//构造Json格式
private ObjectMapper objectMapper=new ObjectMapper();
@RequestMapping("/searcher")
public String search(@RequestParam("query") String query) throws JsonProcessingException {
List<Result> results=searcher.search(query);
return objectMapper.writeValueAsString(results);
}
}
实现标红逻辑
显示搜索结果时，为了描述中关键词的方便查看，针对描述中的关键词进行标红处理。
主要思路是在服务器查询的时候，找到其中关键词，并在关键词上套上一层标签，并在前端设置一个红色的样式。
修改DocSeacher类下的GenDesc方法。
需要注意的是一个描述中可能存在多个关键词，需要使用replacAll来替换。
在GenDesc方法中加入下面代码。
// 实现标红逻辑，给关键词加上特殊标记
for (Term term:terms) {
String word=term.getName();
// 使用(?i)忽略大小写替换
desc=desc.replaceAll("(?i) "+word+" ","<i>"+word+"</i>");
}
处理暂停词
首先需要下载停用词表，网上一搜就可以搜到，然后将停用词表放到文件中，其中每个词占一行.
加载停用词
修改DocSearcher类，用HashSet存放停用词。
public class DocSearcher {
private static final String STOP_WORD="D:\\doc_searcher_index\\stop_word.txt";
private HashSet<String> stopWordDict=new HashSet<>();
}
创建loadStopWord方法，加载停用词
private void loadStopWord() {
try(InputStream inputStream=new FileInputStream(STOP_WORD)){
//将停用词加入到hashset中 按行读取
Scanner scanner=new Scanner(inputStream);
while (scanner.hasNextLine()) {
String line=scanner.nextLine();
stopWordDict.add(line);
}
} catch (IOException e) {
e.printStackTrace();
}
}
在DocSearcher中调用loadStopWord
public DocSearcher() {
index.load();
loadStopWord();
}
修改search方法，将分词结果存放在oldTerm中，遍历oldTerm，将不是停用词的其余所有词加入到terms中。只需要在search方法中新增如下代码。
//1.分词
List<Term> oldTerm=ToAnalysis.parse(query).getTerms();
List<Term> terms= new ArrayList<>();
for (Term term:oldTerm) {
if(stopWordDict.contains(term)) {
continue;
}
terms.add(term);
}
实现权重合并
当我们搜素的查询词包含多个单词时，我们希望同时包含多个单词的结果可以靠前展示，这时就需要对其权重进行调整。
首先把分词结果按照docId进行升序排序，将docId相等的进行权重相加。此处类似于合并两个链表的操作，但是要注意的是，分词结果不一定只分为两部分，有可能是很多部分，此时就是N个数组合并。
在search方法中排序之前，使用mergeResult方法进行合并，并将结果保存在allTokenResult中，后续的排序和返回操作的对象都为allTokenTesult。
mergeResult实现
- 针对每一行按照id进行升序排序
- 借助优先级队列，针对行进行合并。
// 描述一个元素在二维数组中的位置
static class Pos {
public int row;
public int col;
public Pos(int row,int col) {
this.row=row;
this.col=col;
}
}
private ArrayList<Weight> mergeResult(ArrayList<ArrayList<Weight>> allResult) {
//1.针对每一行进行排序按照DocId进行升序排序
for (ArrayList<Weight> list:allResult) {
list.sort(new Comparator<Weight>() {
@Override
public int compare(Weight o1, Weight o2) {
return o1.getDocId()-o2.getDocId();
}
});
}
//2.创建优先级队列，进行合并
//target存放合并后结果
ArrayList<Weight> target=new ArrayList<>();
//2.1创建优先级队列，并指定比价规则
PriorityQueue<Pos> queue=new PriorityQueue<>(new Comparator<Pos>() {
@Override
public int compare(Pos o1, Pos o2) {
//根据Pos值找到对应元素，按照DocId升序排序
Weight w1=allResult.get(o1.row).get(o1.col);
Weight w2=allResult.get(o2.row).get(o2.col);
return w1.getDocId()-w2.getDocId();
}
});
//2.2初始化队列将每一行的第一个元素放入队列中
for (int i = 0; i <allResult.size() ; i++) {
queue.offer(new Pos(i,0));
}
//2.3循环取队首元素
while (!queue.isEmpty()) {
Pos minPos=queue.poll();
Weight curWeight=allResult.get(minPos.row).get(minPos.col);
//看当前取到的Weight是否和前一个target中的docId是否相同
if(target.size()>0) {
Weight lastWeight=target.get(target.size()-1);
if(lastWeight.getDocId()==curWeight.getDocId()) {
//相同文档合并权重
lastWeight.setWeight(lastWeight.getWeight()+curWeight.getWeight());
} else {
//不相同 直接把curWeight插入到target末尾
target.add(curWeight);
}
} else {
target.add(curWeight);
}
//2.5把当前元素处理完后，把对应元素光标往后移动取当前行的下一个元素
Pos newPos=new Pos(minPos.row,minPos.col+1);
if(newPos.col>=allResult.get(newPos.row).size()) {
//光标到达末尾
continue;
}
queue.offer(newPos);
}
return target;
}
