Heim >Datenbank >MySQL-Tutorial >倒排索引构建算法BSBI和SPIMI
倒排索引构建算法BSBI和SPIMI
- WBOYOriginal
- 2016-06-07 16:13:142647Durchsuche
算法介绍 在信息搜索领域，构建索引一直是是一种非常有效的方式，但是当搜索引擎面对的是海量数据的时候，你如果要从茫茫人海的数据中去找出数据，显然这不是一个很好的办法。于是倒排索引这个概念就被提了出来。再说倒排索引概念之前，先要理解一下，一般的
算法介绍
在信息搜索领域，构建索引一直是是一种非常有效的方式，但是当搜索引擎面对的是海量数据的时候，你如果要从茫茫人海的数据中去找出数据，显然这不是一个很好的办法。于是倒排索引这个概念就被提了出来。再说倒排索引概念之前，先要理解一下，一般的索引检索信息的方式。比如原始的数据源假设都是以文档的形式被分开，文档1拥有一段内容，文档2也富含一段内容，文档3同样如此。然后给定一个关键词，要搜索出与此关键词相关的文档，自然而然我们联想到的办法就是一个个文档的内容去比较，判断是否含有此关键词，如果含有则返回这个文档的索引地址，如果不是接着用后面的文档去比，这就有点类似于字符串的匹配类似。很显然，当数据量非常巨大的时候，这种方式并不适用。原来的这种方式可以理解为是索引-->关键词，而倒排索引的形式则是关键词--->索引位置，也就是说，给出一个关键词信息，我能立马根据倒排索引的信息得出他的位置。当然，这里说的是倒排索引最后要达到的效果，至于是用什么方式实现，就不止一种了，本文所述的就是其中比较出名的BSBI和SPIMI算法。
算法的原理
这里首先给出一个具体的实例来了解一般的构造过程，先避开具体的实现方式，给定下面一组词句。
Doc1：Mike spoken English Frequently at home.And he can write English every day.
Doc2:：Mike plays football very well.
首先我们必须知道，我们需要的是一些关键的信息，诸如一些修饰词等等都需要省略，动词的时态变化等都需要还原，如果代词指的是同个人也能够省略，于是上面的句子可以简化成
Doc1：Mike spoken English home.write English.
Doc2：Mike play football.
下面进行索引的倒排构建，因为Mike出现在文档1和文档2 中，所以Mike:{1, 2}后面的词的构造同样的道理。最后的关系就会构成词对应于索引位置的映射关系。理解了这个过程之后呢，可以介绍一下本文主要要说的BSBI(基于磁盘的外部排序构建索引)和SPIMI(内存单遍扫描构建索引)算法了，一般来说，后者比前者常用。
BSBI
此算法的主要步骤如下：
1、将文档中的词进行id的映射，这里可以用hash的方法去构造
2、将文档分割成大小相等的部分。
3、将每部分按照词ID对上文档ID的方式进行排序
4、将每部分排序好后的结果进行合并，最后写出到磁盘中。
5、然后递归的执行，直到文档内容全部完成这一系列操作。
这里有一张示意图:
在算法的过程中会用到读缓冲区和写缓冲区，至于期间的大小多少如何配置都是看个人的，我在后面的代码实现中也有进行设置。至于其中的排序算法的选择，一般建议使用效果比较好的快速排序算法，但是我在后面为了方便，直接用了自己更熟悉的冒泡排序算法，这个也看个人。
SPIMI
接下来说说SPIMI算法，就是内存单遍扫描算法，这个算法与上面的算法一上来就有直接不同的特点就是他无须做id的转换，还是采用了词对索引的直接关联。还有1个比较大的特点是他不经过排序，直接按照先后顺序构建索引，算法的主要步骤如下：
1、对每个块构造一个独立的倒排索引。
2、最后将所有独立的倒排索引进行合并就OK了。
本人为了方便就把这个算法的实现简洁化了，直接在内存中完成所有的构建工作。望读者稍加注意。SPIMI相对比较的简单，这里就不给出截图了。
算法的代码实现
首先是文档的输入数据，采用了2个一样的文档，我也是实在想不出有更好的测试数据了
doc1.txt:
Mike studyed English hardly yesterday He got the 100 at the last exam He thinks English is very interesting
doc2.txt:
Mike studyed English hardly yesterday He got the 100 at the last exam He thinks English is very interesting下面是文档信息预处理类PreTreatTool.java:
package InvertedIndex;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* 文档预处理工具类
*
* @author lyq
*
*/
public class PreTreatTool {
// 一些无具体意义的过滤词
public static String[] FILTER_WORDS = new String[] { "at", "At", "The",
"the", "is", "very" };
// 批量文档的文件地址
private ArrayList<String> docFilePaths;
// 输出的有效词的存放路径
private ArrayList<String> effectWordPaths;
public PreTreatTool(ArrayList<String> docFilePaths) {
this.docFilePaths = docFilePaths;
}
/**
* 获取文档有效词文件路径
*
* @return
*/
public ArrayList<String> getEFWPaths() {
return this.effectWordPaths;
}
/**
* 从文件中读取数据
*
* @param filePath
* 单个文件
*/
private ArrayList<String> readDataFile(String filePath) {
File file = new File(filePath);
ArrayList<String[]> dataArray = new ArrayList<String[]>();
ArrayList<String> words = new ArrayList<>();
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] tempArray;
while ((str = in.readLine()) != null) {
tempArray = str.split(" ");
dataArray.add(tempArray);
}
in.close();
} catch (IOException e) {
e.getStackTrace();
}
// 将每行词做拆分加入到总列表容器中
for (String[] array : dataArray) {
for (String word : array) {
words.add(word);
}
}
return words;
}
/**
* 对文档内容词汇进行预处理
*/
public void preTreatWords() {
String baseOutputPath = "";
int endPos = 0;
ArrayList<String> tempWords = null;
effectWordPaths = new ArrayList<>();
for (String filePath : docFilePaths) {
tempWords = readDataFile(filePath);
filterWords(tempWords, true);
// 重新组装出新的输出路径
endPos = filePath.lastIndexOf(".");
baseOutputPath = filePath.substring(0, endPos);
writeOutOperation(tempWords, baseOutputPath + "-efword.txt");
effectWordPaths.add(baseOutputPath + "-efword.txt");
}
}
/**
*
* 对文档中的词语进行过滤操作
*
* @param words
* 待处理文档词语
* @param canRepeated
* 有效词是否可以重复
*/
private void filterWords(ArrayList<String> words, boolean canRepeated) {
boolean isFilterWord;
// 做形容词匹配
Pattern adjPattern;
// 做动词时态的匹配
Pattern formerPattern;
// 数字匹配
Pattern numberPattern;
Matcher adjMatcher;
Matcher formerMatcher;
Matcher numberMatcher;
ArrayList<String> deleteWords = new ArrayList<>();
adjPattern = Pattern.compile(".*(ly$|ful$|ing$)");
formerPattern = Pattern.compile(".*ed$");
numberPattern = Pattern.compile("[0-9]+(.[0-9]+)?");
String w;
for (int i = 0; i < words.size(); i++) {
w = words.get(i);
isFilterWord = false;
for (String fw : FILTER_WORDS) {
if (fw.equals(w)) {
deleteWords.add(w);
isFilterWord = true;
break;
}
}
if (isFilterWord) {
continue;
}
adjMatcher = adjPattern.matcher(w);
formerMatcher = formerPattern.matcher(w);
numberMatcher = numberPattern.matcher(w);
// 将词语统一小写字母化
w = w.toLowerCase();
// 如果是形容词,副词形式的或是纯数字的词，则进行过滤
if (adjMatcher.matches() || numberMatcher.matches()) {
deleteWords.add(w);
} else if (formerMatcher.matches()) {
// 如果是ed结尾表明是动词的在时态方面的变化，进行变化，转为原有动词的形式，截去最末尾2个额外添加的后缀词
w = w.substring(0, w.length() - 2);
}
words.set(i, w);
}
// 进行无效词的过滤
words.removeAll(deleteWords);
deleteWords.clear();
String s1;
String s2;
// 进行词语的去重
for (int i = 0; i < words.size() - 1; i++) {
s1 = words.get(i);
for (int j = i + 1; j < words.size(); j++) {
s2 = words.get(j);
// 找到存在相同的词了，就挑出循环
if (s1.equals(s2)) {
deleteWords.add(s1);
break;
}
}
}
// 删除多余重复的词语
words.removeAll(deleteWords);
words.addAll(deleteWords);
}
/**
* 将数据写出到磁盘文件操作，如果文件已经存在，则在文件尾部进行内容追加
*
* @param buffer
* 当前写缓冲中的数据
* @param filePath
* 输出地址
*/
private void writeOutOperation(ArrayList<String> buffer, String filePath) {
StringBuilder strBuilder = new StringBuilder();
// 将缓冲中的数据组成字符写入到文件中
for (String word : buffer) {
strBuilder.append(word);
strBuilder.append("\n");
}
try {
File file = new File(filePath);
PrintStream ps = new PrintStream(new FileOutputStream(file));
ps.print(strBuilder.toString());// 往文件里写入字符串
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
文档类Document.java:
package InvertedIndex;
import java.util.ArrayList;
/**
* 文档类
* @author lyq
*
*/
public class Document {
//文档的唯一标识
int docId;
//文档的文件地址
String filePath;
//文档中的有效词
ArrayList<String> effectWords;
public Document(ArrayList<String> effectWords, String filePath){
this.effectWords = effectWords;
this.filePath = filePath;
}
public Document(ArrayList<String> effectWords, String filePath, int docId){
this(effectWords, filePath);
this.docId = docId;
}
}
BSBI算法工具类BSBITool.java:
package InvertedIndex;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
/**
* BSBI基于磁盘的外部排序算法
*
* @author lyq
*
*/
public class BSBITool {
// 文档唯一标识ID
public static int DOC_ID = 0;
// 读缓冲区的大小
private int readBufferSize;
// 写缓冲区的大小
private int writeBufferSize;
// 读入的文档的有效词文件地址
private ArrayList<String> effectiveWordFiles;
// 倒排索引输出文件地址
private String outputFilePath;
// 读缓冲 1
private String[][] readBuffer1;
// 读缓冲2
private String[][] readBuffer2;
// 写缓冲区
private String[][] writeBuffer;
// 有效词与hashcode的映射
private Map<String, String> code2word;
public BSBITool(ArrayList<String> effectiveWordFiles, int readBufferSize,
int writeBufferSize) {
this.effectiveWordFiles = effectiveWordFiles;
this.readBufferSize = readBufferSize;
this.writeBufferSize = writeBufferSize;
initBuffers();
}
/**
* 初始化缓冲区的设置
*/
private void initBuffers() {
readBuffer1 = new String[readBufferSize][2];
readBuffer2 = new String[readBufferSize][2];
writeBuffer = new String[writeBufferSize][2];
}
/**
* 从文件中读取有效词并进行编码替换
*
* @param filePath
* 返回文档
*/
private Document readEffectWords(String filePath) {
long hashcode = 0;
String w;
Document document;
code2word = new HashMap<String, String>();
ArrayList<String> words;
words = readDataFile(filePath);
for (int i = 0; i < words.size(); i++) {
w = words.get(i);
hashcode = BKDRHash(w);
hashcode = hashcode % 10000;
// 将有效词的hashcode取模值作为对应的代表
code2word.put(hashcode + "", w);
w = hashcode + "";
words.set(i, w);
}
document = new Document(words, filePath, DOC_ID);
DOC_ID++;
return document;
}
/**
* 将字符做哈希值的转换
*
* @param str
* 待转换字符
* @return
*/
private long BKDRHash(String str) {
int seed = 31; /* 31 131 1313 13131 131313 etc.. */
long hash = 0;
int i = 0;
for (i = 0; i < str.length(); i++) {
hash = (hash * seed) + (str.charAt(i));
}
return hash;
}
/**
* 根据输入的有效词输出倒排索引文件
*/
public void outputInvertedFiles() {
int index = 0;
String baseFilePath = "";
outputFilePath = "";
Document doc;
ArrayList<String> tempPaths;
ArrayList<String[]> invertedData1;
ArrayList<String[]> invertedData2;
tempPaths = new ArrayList<>();
for (String filePath : effectiveWordFiles) {
doc = readEffectWords(filePath);
writeOutFile(doc);
index = doc.filePath.lastIndexOf(".");
baseFilePath = doc.filePath.substring(0, index);
writeOutOperation(writeBuffer, baseFilePath + "-temp.txt");
tempPaths.add(baseFilePath + "-temp.txt");
}
outputFilePath = baseFilePath + "-bsbi-inverted.txt";
// 将中间产生的倒排索引数据进行总的合并并输出到一个文件中
for (int i = 1; i < tempPaths.size(); i++) {
if (i == 1) {
invertedData1 = readInvertedFile(tempPaths.get(0));
} else {
invertedData1 = readInvertedFile(outputFilePath);
}
invertedData2 = readInvertedFile(tempPaths.get(i));
mergeInvertedData(invertedData1, invertedData2, false,
outputFilePath);
writeOutOperation(writeBuffer, outputFilePath, false);
}
}
/**
* 将文档的最终的倒排索引结果写出到文件
*
* @param doc
* 待处理文档
*/
private void writeOutFile(Document doc) {
// 在读缓冲区中是否需要再排序
boolean ifSort = true;
int index = 0;
String baseFilePath;
String[] temp;
ArrayList<String> tempWords = (ArrayList<String>) doc.effectWords
.clone();
ArrayList<String[]> invertedData1;
ArrayList<String[]> invertedData2;
invertedData1 = new ArrayList<>();
invertedData2 = new ArrayList<>();
// 将文档的数据平均拆分成2份，用于读入后面的2个缓冲区中
for (int i = 0; i < tempWords.size() / 2; i++) {
temp = new String[2];
temp[0] = tempWords.get(i);
temp[1] = doc.docId + "";
invertedData1.add(temp);
temp = new String[2];
temp[0] = tempWords.get(i + tempWords.size() / 2);
temp[1] = doc.docId + "";
invertedData2.add(temp);
}
// 如果是奇数个，则将最后一个补入
if (tempWords.size() % 2 == 1) {
temp = new String[2];
temp[0] = tempWords.get(tempWords.size() - 1);
temp[1] = doc.docId + "";
invertedData2.add(temp);
}
index = doc.filePath.lastIndexOf(".");
baseFilePath = doc.filePath.substring(0, index);
mergeInvertedData(invertedData1, invertedData2, ifSort, baseFilePath
+ "-temp.txt");
}
/**
* 合并读缓冲区数据写到写缓冲区中，用到了归并排序算法
*
* @param outputPath
* 写缓冲区的写出的路径
*/
private void mergeWordBuffers(String outputPath) {
int i = 0;
int j = 0;
int num1 = 0;
int num2 = 0;
// 写缓冲区下标
int writeIndex = 0;
while (readBuffer1[i][0] != null && readBuffer2[j][0] != null) {
num1 = Integer.parseInt(readBuffer1[i][0]);
num2 = Integer.parseInt(readBuffer2[j][0]);
// 如果缓冲1小，则优先存缓冲1到写缓冲区中
if (num1 < num2) {
writeBuffer[writeIndex][0] = num1 + "";
writeBuffer[writeIndex][1] = readBuffer1[i][1];
i++;
} else if (num2 < num1) {
writeBuffer[writeIndex][0] = num2 + "";
writeBuffer[writeIndex][1] = readBuffer1[j][1];
j++;
} else if (num1 == num2) {
// 如果两个缓冲区中的数字一样，说明是同个有效词，先进行合并再写入
writeBuffer[writeIndex][0] = num1 + "";
writeBuffer[writeIndex][1] = readBuffer1[i][1] + ":"
+ readBuffer2[j][1];
i++;
j++;
}
// 写的指针往后挪一位
writeIndex++;
// 如果写满写缓冲区时，进行写出到文件操作
if (writeIndex >= writeBufferSize) {
writeOutOperation(writeBuffer, outputPath);
writeIndex = 0;
}
}
if (readBuffer1[i][0] == null) {
writeRemainReadBuffer(readBuffer2, j, outputPath);
}
if (readBuffer2[j][0] == null) {
writeRemainReadBuffer(readBuffer1, j, outputPath);
}
}
/**
* 将数据写出到磁盘文件操作，如果文件已经存在，则在文件尾部进行内容追加
*
* @param buffer
* 当前写缓冲中的数据
* @param filePath
* 输出地址
*/
private void writeOutOperation(String[][] buffer, String filePath) {
String word;
StringBuilder strBuilder = new StringBuilder();
// 将缓冲中的数据组成字符写入到文件中
for (String[] array : buffer) {
if (array[0] == null) {
continue;
}
word = array[0];
strBuilder.append(word);
strBuilder.append(" ");
strBuilder.append(array[1]);
strBuilder.append("\n");
}
try {
File file = new File(filePath);
PrintStream ps = new PrintStream(new FileOutputStream(file));
ps.print(strBuilder.toString());// 往文件里写入字符串
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* 将数据写出到磁盘文件操作，如果文件已经存在，则在文件尾部进行内容追加
*
* @param buffer
* 当前写缓冲中的数据
* @param filePath
* 输出地址
* @param isCoded
* 是否以编码的方式输出
*/
private void writeOutOperation(String[][] buffer, String filePath, boolean isCoded) {
String word;
StringBuilder strBuilder = new StringBuilder();
// 将缓冲中的数据组成字符写入到文件中
for (String[] array : buffer) {
if (array[0] == null) {
continue;
}
if(!isCoded){
word = code2word.get(array[0]);
}else{
word = array[0];
}
strBuilder.append(word);
strBuilder.append(" ");
strBuilder.append(array[1]);
strBuilder.append("\n");
}
try {
File file = new File(filePath);
PrintStream ps = new PrintStream(new FileOutputStream(file));
ps.print(strBuilder.toString());// 往文件里写入字符串
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* 将剩余的读缓冲区中的数据读入写缓冲区中
*
* @param remainBuffer
* 读缓冲区的剩余缓冲
* @param currentReadPos
* 当前的读取位置
* @param outputPath
* 写缓冲区的写出文件路径
*/
private void writeRemainReadBuffer(String[][] remainBuffer,
int currentReadPos, String outputPath) {
while (remainBuffer[currentReadPos][0] != null
&& currentReadPos < readBufferSize) {
removeRBToWB(remainBuffer[currentReadPos]);
currentReadPos++;
// 如果写满写缓冲区时，进行写出到文件操作
if (writeBuffer[writeBufferSize - 1][0] != null) {
writeOutOperation(writeBuffer, outputPath);
}
}
}
/**
* 将剩余读缓冲区中的数据通过插入排序的方式插入写缓冲区
*
* @param record
*/
private void removeRBToWB(String[] record) {
int insertIndex = 0;
int endIndex = 0;
long num1;
long num2;
long code = Long.parseLong(record[0]);
// 如果写缓冲区目前为空，则直接加入
if (writeBuffer[0][0] == null) {
writeBuffer[0] = record;
return;
}
// 寻找待插入的位置
for (int i = 0; i < writeBufferSize - 1; i++) {
if (writeBuffer[i][0] == null) {
endIndex = i;
break;
}
num1 = Long.parseLong(writeBuffer[i][0]);
if (writeBuffer[i + 1][0] == null) {
if (code > num1) {
endIndex = i + 1;
insertIndex = i + 1;
}
} else {
num2 = Long.parseLong(writeBuffer[i + 1][0]);
if (code > num1 && code < num2) {
insertIndex = i + 1;
}
}
}
// 进行插入操作，相关数据进行位置迁移
for (int i = endIndex; i > insertIndex; i--) {
writeBuffer[i] = writeBuffer[i - 1];
}
writeBuffer[insertIndex] = record;
}
/**
* 将磁盘中的2个倒排索引数据进行合并
*
* @param invertedData1
* 倒排索引为文件数据1
* @param invertedData2
* 倒排索引文件数据2
* @param isSort
* 是否需要对缓冲区中的数据进行排序
* @param outputPath
* 倒排索引输出文件地址
*/
private void mergeInvertedData(ArrayList<String[]> invertedData1,
ArrayList<String[]> invertedData2, boolean ifSort, String outputPath) {
int rIndex1 = 0;
int rIndex2 = 0;
// 重新初始化缓冲区
initBuffers();
while (invertedData1.size() > 0 && invertedData2.size() > 0) {
readBuffer1[rIndex1][0] = invertedData1.get(0)[0];
readBuffer1[rIndex1][1] = invertedData1.get(0)[1];
readBuffer2[rIndex2][0] = invertedData2.get(0)[0];
readBuffer2[rIndex2][1] = invertedData2.get(0)[1];
invertedData1.remove(0);
invertedData2.remove(0);
rIndex1++;
rIndex2++;
if (rIndex1 == readBufferSize) {
if (ifSort) {
wordBufferSort(readBuffer1);
wordBufferSort(readBuffer2);
}
mergeWordBuffers(outputPath);
initBuffers();
}
}
if (ifSort) {
wordBufferSort(readBuffer1);
wordBufferSort(readBuffer2);
}
mergeWordBuffers(outputPath);
readBuffer1 = new String[readBufferSize][2];
readBuffer2 = new String[readBufferSize][2];
if (invertedData1.size() == 0 && invertedData2.size() > 0) {
readRemainDataToRB(invertedData2, outputPath);
} else if (invertedData1.size() > 0 && invertedData2.size() == 0) {
readRemainDataToRB(invertedData1, outputPath);
}
}
/**
* 剩余的有效词数据读入读缓冲区
*
* @param remainData
* 剩余数据
* @param outputPath
* 输出文件路径
*/
private void readRemainDataToRB(ArrayList<String[]> remainData,
String outputPath) {
int rIndex = 0;
while (remainData.size() > 0) {
readBuffer1[rIndex][0] = remainData.get(0)[0];
readBuffer1[rIndex][1] = remainData.get(0)[1];
remainData.remove(0);
rIndex++;
// 读缓冲 区写满，进行写入到写缓冲区中
if (readBuffer1[readBufferSize - 1][0] != null) {
wordBufferSort(readBuffer1);
writeRemainReadBuffer(readBuffer1, 0, outputPath);
initBuffers();
}
}
wordBufferSort(readBuffer1);
writeRemainReadBuffer(readBuffer1, 0, outputPath);
}
/**
* 缓冲区数据进行排序
*
* @param buffer
* 缓冲空间
*/
【本文来自鸿网互联 (http://www.68idc.cn)】 private void wordBufferSort(String[][] buffer) {
String[] temp;
int k = 0;
long num1 = 0;
long num2 = 0;
for (int i = 0; i < buffer.length - 1; i++) {
// 缓冲区可能没填满
if (buffer[i][0] == null) {
continue;
}
k = i;
for (int j = i + 1; j < buffer.length; j++) {
// 缓冲区可能没填满
if (buffer[j][0] == null) {
continue;
}
// 获取2个缓冲区小块的起始编号值
num1 = Long.parseLong(buffer[k][0]);
num2 = Long.parseLong(buffer[j][0]);
if (num2 < num1) {
k = j;
}
}
if (k != i) {
temp = buffer[k];
buffer[k] = buffer[i];
buffer[i] = temp;
}
}
}
/**
* 从文件中读取倒排索引数据
*
* @param filePath
* 单个文件
*/
private ArrayList<String[]> readInvertedFile(String filePath) {
File file = new File(filePath);
ArrayList<String[]> dataArray = new ArrayList<String[]>();
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] tempArray;
while ((str = in.readLine()) != null) {
tempArray = str.split(" ");
dataArray.add(tempArray);
}
in.close();
} catch (IOException e) {
e.getStackTrace();
}
return dataArray;
}
/**
* 从文件中读取数据
*
* @param filePath
* 单个文件
*/
private ArrayList<String> readDataFile(String filePath) {
File file = new File(filePath);
ArrayList<String[]> dataArray = new ArrayList<String[]>();
ArrayList<String> words = new ArrayList<>();
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] tempArray;
while ((str = in.readLine()) != null) {
tempArray = str.split(" ");
dataArray.add(tempArray);
}
in.close();
} catch (IOException e) {
e.getStackTrace();
}
// 将每行词做拆分加入到总列表容器中
for (String[] array : dataArray) {
for (String word : array) {
if (!word.equals("")) {
words.add(word);
}
}
}
return words;
}
}
SPIMI算法工具类SPIMITool.java:
package InvertedIndex;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
/**
* SPIMI内存式单边扫描构建算法
* @author lyq
*
*/
public class SPIMITool {
//倒排索引输出文件地址
private String outputFilePath;
// 读入的文档的有效词文件地址
private ArrayList<String> effectiveWordFiles;
// 内存缓冲区，不够还能够在增加空间
private ArrayList<String[]> buffers;
public SPIMITool(ArrayList<String> effectiveWordFiles){
this.effectiveWordFiles = effectiveWordFiles;
}
/**
* 从文件中读取数据
*
* @param filePath
* 单个文件
*/
private ArrayList<String> readDataFile(String filePath) {
File file = new File(filePath);
ArrayList<String[]> dataArray = new ArrayList<String[]>();
ArrayList<String> words = new ArrayList<>();
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] tempArray;
while ((str = in.readLine()) != null) {
tempArray = str.split(" ");
dataArray.add(tempArray);
}
in.close();
} catch (IOException e) {
e.getStackTrace();
}
// 将每行词做拆分加入到总列表容器中
for (String[] array : dataArray) {
for (String word : array) {
words.add(word);
}
}
return words;
}
/**
* 根据已有的文档数据进行倒排索引文件的构建
* @param docs
* 文档集合
*/
private void writeInvertedIndex(ArrayList<Document> docs){
ArrayList<String> datas;
String[] recordData;
buffers = new ArrayList<>();
for(Document tempDoc: docs){
datas = tempDoc.effectWords;
for(String word: datas){
recordData = new String[2];
recordData[0] = word;
recordData[1] = tempDoc.docId + "";
addRecordToBuffer(recordData);
}
}
//最后将数据写出到磁盘中
writeOutOperation(buffers, outputFilePath);
}
/**
* 将新读入的数据记录读入到内存缓冲中，如果存在则加入到倒排记录表中
* @param insertedData
* 待插入的数据
*/
private void addRecordToBuffer(String[] insertedData){
boolean isContained = false;
String wordName;
wordName = insertedData[0];
for(String[] array: buffers){
if(array[0].equals(wordName)){
isContained = true;
//添加倒排索引记录，以：隔开
array[1] += ":" + insertedData[1];
break;
}
}
//如果没有包含，则说明是新的数据,直接添加
if(!isContained){
buffers.add(insertedData);
}
}
/**
* 将数据写出到磁盘文件操作，如果文件已经存在，则在文件尾部进行内容追加
* @param buffer
* 当前写缓冲中的数据
* @param filePath
* 输出地址
*/
private void writeOutOperation(ArrayList<String[]> buffer, String filePath) {
StringBuilder strBuilder = new StringBuilder();
//将缓冲中的数据组成字符写入到文件中
for(String[] array: buffer){
strBuilder.append(array[0]);
strBuilder.append(" ");
strBuilder.append(array[1]);
strBuilder.append("\n");
}
try {
File file = new File(filePath);
PrintStream ps = new PrintStream(new FileOutputStream(file));
ps.println(strBuilder.toString());// 往文件里写入字符串
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* 构造倒排索引文件
*/
public void createInvertedIndexFile(){
int docId = 1;
String baseFilePath;
String fileName;
String p;
int index1 = 0;
int index2 = 0;
Document tempDoc;
ArrayList<String> words;
ArrayList<Document> docs;
outputFilePath = "spimi";
docs = new ArrayList<>();
p = effectiveWordFiles.get(0);
//提取文件名称
index1 = p.lastIndexOf("\\");
baseFilePath = p.substring(0, index1+1);
outputFilePath = baseFilePath + "spimi";
for(String path: effectiveWordFiles){
//获取文档有效词
words = readDataFile(path);
tempDoc = new Document(words, path, docId);
docId++;
docs.add(tempDoc);
//提取文件名称
index1 = path.lastIndexOf("\\");
index2 = path.lastIndexOf(".");
fileName = path.substring(index1+1, index2);
outputFilePath += "-" + fileName;
}
outputFilePath += ".txt";
//根据文档数据进行倒排索引文件的创建
writeInvertedIndex(docs);
}
}
算法测试类Client.java:
package InvertedIndex;
import java.util.ArrayList;
/**
* 倒排索引测试类
* @author lyq
*
*/
public class Client {
public static void main(String[] args){
//读写缓冲区的大小
int readBufferSize;
int writeBufferSize;
String baseFilePath;
PreTreatTool preTool;
//BSBI基于磁盘的外部排序算法
BSBITool bTool;
//SPIMI内存式单边扫描构建算法
SPIMITool sTool;
//有效词文件路径
ArrayList<String> efwFilePaths;
ArrayList<String> docFilePaths;
readBufferSize = 10;
writeBufferSize = 20;
baseFilePath = "C:\\Users\\lyq\\Desktop\\icon\\";
docFilePaths = new ArrayList<>();
docFilePaths.add(baseFilePath + "doc1.txt");
docFilePaths.add(baseFilePath + "doc2.txt");
//文档预处理工具类
preTool = new PreTreatTool(docFilePaths);
preTool.preTreatWords();
//预处理完获取有效词文件路径
efwFilePaths = preTool.getEFWPaths();
bTool = new BSBITool(efwFilePaths, readBufferSize, writeBufferSize);
bTool.outputInvertedFiles();
sTool = new SPIMITool(efwFilePaths);
sTool.createInvertedIndexFile();
}
}
算法的输出：
为了模拟出真实性，算法的输出都是以文件的形式。
首先是预处理类处理之后的有效词文件doc1-efword.txt和doc2-efword.txt:
mike study yesterday got last exam thinks english he可以看见，一些修饰词什么的已经被我过滤掉了。
下面是BSBI算法生成的中间文件，就是映射成编码的文件，也许你看了这些数值真实表示的是什么词语：
1426 0 1542 0 2540 0 3056 0 3325 0 4326 0 4897 0 6329 0 7327 0还有文档2的临时文件：
1426 1 1542 1 2540 1 3056 1 3325 1 4326 1 4897 1 6329 1 7327 1将这2个文档的信息进行合并最终输出的倒排索引文件为：
yesterday 0:1 mike 0:1 got 0:1 english 0:1 he 0:1 last 0:1 thinks 0:1 study 0:1 exam 0:1同样的SPIMI算法输出的结果：
mike 1:2 study 1:2 yesterday 1:2 got 1:2 last 1:2 exam 1:2 thinks 1:2 english 1:2 he 1:2
算法小结
我在实现算法的过程中无疑低估了此算法的难度，尤其是BSBI的实现，因为中间读写缓冲区在做数据操作的时候，各种情况需要判断，诸如写缓冲区满了的时候要刷出到磁盘上，读缓冲区满的时候要通过归并排序移入读缓冲区中，这里面的判断实在过多，加上之前早期没有想到这个问题，导致算法可读性不是很好，就索性把缓冲区设大，先走通这个流程，所以这个算法大家还是以理解为主，就不要拿来实际运用了，同样对于SPIMI算法一样的道理，算法实现在这里帮助大家更好的理解吧，还有很多不足的地方。还有1点是文档内容预处理的时候，我只是象征性的进行过滤，真实的信息过滤实现复杂程度远远超过我所写的，这里包括了修饰词，时态词的变化，副词等等，这些有时还需要语义挖掘的一些知识来解决，大家意会即可。
Stellungnahme：
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel：助记码的全部更新Nächster Artikel：Hibernate为表字段添加备注信息，便于理解数据库设计