6.5 jmu-Java-05集合-4-倒排索引 题解

• 一、题目描述
• • 1、输入说明
  • 2、输出说明
  • 3、输入样例
  • 4、输入样例
• 二、解题思路
• • 1.采用treemap的原因
  • 2.处理输入数据，并建立好倒排索引
  • 3.处理查询数据
• 三、完整代码
• • 提交截图

对若干行文字建立倒排索引(根据单词找到所在行号)。
然后根据关键字，在倒排索引查找进行查找，找到包含所有该关键字所在的行数并输出。

若干行英文，以!!!为结束。
输入一行查询关键字，以1个空格为分隔

输出所创建倒排索引。索引的key按照字母升序，索引的value按照行号升序
输出查询结果。如果找到，输出行集与行集内每一行的内容，如果没找到输出found 0 results：

where are you from are you ok
this is a test 
that is an apple
there are lots of apples you eat it
who are you
!!!!!
you are
eat
you test
abc

a=[2]
an=[3]
apple=[3]
apples=[4]
are=[1, 4, 5]
eat=[4]
from=[1]
is=[2, 3]
it=[4]
lots=[4]
of=[4]
ok=[1]
test=[2]
that=[3]
there=[4]
this=[2]
where=[1]
who=[5]
you=[1, 4, 5]
[1, 4, 5]
line 1:where are you from are you ok
line 4:there are lots of apples you eat it
line 5:who are you
[4]
line 4:there are lots of apples you eat it
found 0 results
found 0 results

关于题意不难看出这适合于用treeMap 求解
因为这个6.X的题集都是map的题
观察输出样例我们可以发现

所以使用的collection 框架，基本是想好了

		ArrayList strList=new ArrayList();
		//用于存储每一行的内容
		Map>m=new TreeMap>();
		//用于存储单词对应行号的倒排索引

我的读取思路是先一整行一整行的读取，存入每一行的数据，然后换一个输入流，一个单词一个单词的读取完一整行的数据

		int h=0;//用于记录行号
		while(true) {
			h++;
			String s = null;
			s=in.nextLine();//读取一整行的内容
			if(s.equals("!!!!!"))break;
			strList.add(s);//将一行的内容存储起来
			Scanner sc=new Scanner(s);
			while(sc.hasNext()) { //分别处理每一行里面的各个单词
				String word=sc.next();
				if(m.containsKey(word)) //如果map已经有对应的单词关键字了，直接将行号存入到value（treeset)当中
				m.get(word).add(h);
				else m.put(word, new TreeSet(Arrays.asList(h)));//如果没有，向map当中同时存入key 和value;
			}
		}

思路同样是是先一整行一整行的读取，存入每一行的数据，然后换一个输入流，一个单词一个单词的读取完一整行的数据。
题目查询要求“ 找到包含所有该关键字所在的行数并输出”
因为建立了每一个单词对应行号的set ，所以求个交集就完事了，关于set自带求交集的方法我还并不是很能熟练运用，所以换个思路，用一个数组类似于桶排序的办法求交集 如题中样例查询 you,are,其中
you=[1, 4, 5]
are=[1, 4, 5]
定义数组an，当读到后面的行号的时候 就让an[行号]++；
最后遍历数组，如果an[i]==前面一整行的单词个数，那么就说明 ，第i行包含了所有的查询单词

	while(in.hasNext()){
			int cnt=0;
			String s = null;
			s=in.nextLine();
			Scanner sc=new Scanner(s);
			Set set=new TreeSet<>();
			int [] an=new int[5000];//用于求交集
			while(sc.hasNext()){
				cnt++;//记录单词个数
				String a=sc.next();
				if(m.containsKey(a))
				for (Integer e : m.get(a)) {
					an[e]++;//对应的行号位置++
				}
			}
			for (int i = 0; i < an.length; i++) {
				if(an[i]==cnt) set.add(i);//i位置满足单词数（cnt)==an[i] 存入容器中输出
			}

import java.lang.reflect.Array;
import java.net.Inet4Address;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		ArrayList strList=new ArrayList();//用于存储每一行的内容
		Map>m=new TreeMap>();//用于存储单词对应行号的倒排索引
		int h=0;//用于记录行号
		while(true) {
			h++;
			String s = null;
			s=in.nextLine();//读取一整行的内容
			if(s.equals("!!!!!"))break;
			strList.add(s);//将一行的内容存储起来
			Scanner sc=new Scanner(s);
			while(sc.hasNext()) { //分别处理每一行里面的各个单词
				String word=sc.next();
				if(m.containsKey(word)) //如果map已经有对应的单词关键字了，直接将行号存入到value（treeset)当中
				m.get(word).add(h);
				else m.put(word, new TreeSet(Arrays.asList(h)));//如果没有，向map当中同时存入key 和value;
			}
		}
		for (Entry> e : m.entrySet()) {
			System.out.println(e);
		}
		while(in.hasNext()){
			int cnt=0;
			String s = null;
			s=in.nextLine();
			Scanner sc=new Scanner(s);
			Set set=new TreeSet<>();
			int [] an=new int[5000];//用于求交集
			while(sc.hasNext()){
				cnt++;//记录单词个数
				String a=sc.next();
				if(m.containsKey(a))
				for (Integer e : m.get(a)) {
					an[e]++;//对应的行号位置++
				}
			}
			for (int i = 0; i < an.length; i++) {
				if(an[i]==cnt) set.add(i);//i位置满足单词数（cnt)==an[i] 存入容器中输出
			}
			if(set.isEmpty()) System.out.println("found 0 results");
			else {
				System.out.println(set);
				for (Integer e : set) {
					System.out.println("line "+e+":"+strList.get(e-1));
				}
			}
		
		}
	}

}