文章目录
  1. 1. 倒排索引
  2. 2. TF-IDF
  3. 3. java实现

倒排索引

这里先简单介绍一下倒排索引的概念。

这里举一个简单的例子,如上图所示,我们有 100 个文档,每个文档里包含很多个单词,倒排索引的原理是为每个单词及其每个单词出现的次数建立关系,每个单词可能会出现多次,这样在索引表里的每一项就会是单词和文档链表的集合。

左边保存的是一系列字符串,称为词典。每个字符串都指向包含此字符串的文档(Document)链表,此文档链表称为倒排表(Posting List)。
有了索引,便使保存的信息和要搜索的信息一致,可以大大加快搜索的速度。
比如说,我们要寻找既包含字符串“lucene”又包含字符串“solr”的文档,我们只需要以下几步:

1、找出包含“lucene”的文档链表

2、找出包含“solr”的文档链表

3、合并链表,找出既包含“lucene”又包含“solr”的文档。

如下图所示:

全文检索在建立索引的过程会耗费一定的时间,但它的优势为一次索引,多次使用。

TF-IDF

TF-IDF 由两部分组成,TF 是单词的频率,IDF 是逆文档频率,用来反映单词的重要程度。计算公示如下:

TF计算公式如下:

IDF计算公式如下:

TF-IDF计算公式如下

这里推荐阮一峰的两篇博客:

TF-IDF与余弦相似性的应用(一):自动提取关键词

TF-IDF与余弦相似性的应用(二):找出相似文章

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.BufferedReader;  
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class IntertedIndex {
private Map<String, ArrayList<String>> map=new HashMap<>();
private ArrayList<String> list;
private Map<String, Integer> nums=new HashMap<>();

public void CreateIndex(String filepath){
String[] words = null;
try {
File file=new File(filepath);
BufferedReader reader=new BufferedReader(new FileReader(file));
String s=null;
while((s=reader.readLine())!=null){
//获取单词
words=s.split(" ");
}

for (String string : words) {
if (!map.containsKey(string)) {
list=new ArrayList<String>();
list.add(filepath);
map.put(string, list);
nums.put(string, 1);
}else {
list=map.get(string);
//如果没有包含过此文件名,则把文件名放入
if (!list.contains(filepath)) {
list.add(filepath);
}
//文件总词频数目
int count=nums.get(string)+1;
nums.put(string, count);
}
}
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}

public static void main(String[] args) {
IntertedIndex index=new IntertedIndex();
for(int i=1;i<=3;i++){
String path="E:\\data\\"+i+".txt";
index.CreateIndex(path);
}
for (Map.Entry<String, ArrayList<String>> map : index.map.entrySet()) {
System.out.println(map.getKey()+":"+map.getValue());
}

for (Map.Entry<String, Integer> num : index.nums.entrySet()) {
System.out.println(num.getKey()+":"+num.getValue());
}
}
}

该实现参考:java实现倒排索引

文章目录
  1. 1. 倒排索引
  2. 2. TF-IDF
  3. 3. java实现