Heart.X.Raid
- 浏览: 898291 次
- 性别:
- 来自: 武汉
-
最新评论
-
小宇宙_WZY：
膜拜一下大神，解决了我一个大问题，非常感谢 orz
【解惑】深入jar包：从jar包中读取资源文件 -
JKL852qaz：
感谢，遇到相同的问题！
【解惑】深入jar包：从jar包中读取资源文件 -
lgh1992314：
为什么java中调用final方法是用invokevirtua ...
【解惑】Java动态绑定机制的内幕 -
鲁曼1991：
说的都有道理，protected只能被同一级包的类所调用
【解惑】真正理解了protected的作用范围 -
鲁曼1991：
...
【总结】String in Java
文章列表
上接《索引创建(3)：DocumentWriter 处理流程二
》
1.3.3
第三车间——
TermsHashPerField &
FreqProxTermsWriterPerField
TermsHashPerField和FreqProxTermsWriterPerField负责将token信息(字符串内容termTest，所在文档编号docID，所在文档中的位置position，所在文档中的词频frequence)添加到索引的Hash表结构(postingsHash)中。事实上，这些信息并不是直接存放在Hash表中的，而是存放 ...
(1) 简单选择排序 O(N^2)
一趟简单选择排序的操作为：通过n-i 次关键字间的比较，从n-i+1 个记录中选择出关键字最小的记录，并和第 i (i<=i<=n)个记录交换之。
#include<iostream.h>
/***************************************
* 简单选择排序 Simple Selection Sort *
***************************************/
class SimpleSelectSort{
public:
//递增排序
...
1、起泡排序 O(N^2)
起泡排序的过程很简单，首先将第一个关键字和第二个关键字比较，若为逆序，则将两个记录交换。然后再用第二个关键字和第三个关键字比较，以此类推，知道第n-1个关键字和第n个比较完，这样最大 ...
1、基本概念介绍
(1) 如果待排序列中有两个相同的关键字 Ki = Kj，其顺序是Ki在Kj之前。如果经过排序之后，Ki 和 Kj的顺序颠倒了，则说明这个排序方法是不稳定
的。否则则是稳定
排序。
(2) 在内存中就可以完成的排序过程，称为内部排序
。如果待排数据量很大，内存不够容纳全部数据，在排序过程中必须对外存进行访问，则叫做外部排序
。
实际上，由于数据量级别不同。排序的方法会有很大的改变，思考排序效率的角度也不一样。这个专题系列未经特殊注明，都属于内部排序方法。
2、直接插入排序 O(N^2)
将一 ...
上接《索引创建
(2)：DocumentWriter处理流程三
》
1.4 索引数据池存储细节
倒排索引(token->posting list)表的数据信息在内存中并不是直接存储在postingsHash中的，而是存放在三大数据缓冲池中——CharBlockPool，ByteBlockPool，IntBlockPool
。
这三个池均都由若干个固定长度的buffer数组构成。DocumentsWriter对它们进行管理和维护(包括分配新的块或者回收不用的块的操作)，以达到节省内存和提高效率的作用。
◆ 三大索引数据池
1 ...
上接《索引创建(2)：DocumentWriter处理流程一
》
1.3.2 第二车间——DocInverterPerField
DocInverterPerField 负责对DocFieldProcessorPerThread对象的Fieldable[]数组的内容建立倒排索引，也就是处理同名字的所有Field。但实际上这个类主要解决的是前期工作，比如分词，统计位置信息等。倒排索引结构的核心的工作由TermsHashPerField和
FreqProxTermsWriterPerField
(第三车间
)
来完成。这两个类将在后面的专题中再提及。
...
上接《索引创建(1): IndexWriter索引器》
1.3 索引创建过程
DocumentsWriter是由IndexWriter调用来负责对多个document建立索引的核心类，但整个索引过程并不是由一个对象来完成的。而是有一系列的对象组成的处理链(IndexingChain)来完成的(这个过程就像流水线生产汽车)。
下面是DocumentWriter开始建立索引的源代码。
//由IndexWriter调用的方法
boolean addDocument(Document doc, Analyzer analyzer){
return ...
《Lucene索引创建》系列文章将从源代码出发，详细揭示Lucene两大功能之一的索引创建过程。并阐述其中所用到的信息检索的相关技术。由于Lucene是基于多线程的，为了能够简洁明了的说明Lucene索引创建的过程，我们尽量会绕开Lucene多线程机制的处理细节。
1.1 准备工作
我们对content目录中1.txt、2.txt、3.txt这三个英文文档的文件名，路径，内容建立索引。代码如下：
//索引文件存放的位置
File indexDir=new File(".\index");
//需要建立索引的文档集合的位置
File doc ...
在检索数据的时候，我们很希望可以检索出数据源的各种信息。就比如检索磁盘文件，可以检索出文件的路径，名字，
内容，修改时间等等。再比如检索图书的书号、书名、作者、出版时间.... Lucene是如何组织这些数据源的不同属性信息呢？
Lucene 数据源组织结构
org.apache.lucene.document包中有两个很重要的类：Document 和 Field。这两个类将杂乱无章的数据形式组织成可以被Lucene使用的内存数据结构。
Field类的作用主要是用来表示当前数据源的各种属性。
数据源的每种属性信息都可以组织 ...
一个优秀的IR system要做好的第一件事就是利用自然语言处理技术(NLP)对文本进行分析。其中分词是最基本的，其性能直接决定IR system的搜索精度和速度。因此，大型Web搜索引擎都有自己的分词工具。
Lucene3.0 的分析器由三个包组成：
(1)
org.apache.lucene.analysis 是Lucene分析器的基本结构包。包含了分析器最底层的结构(Analyzer、Tokenizer、TokenFilter接口和抽象类)，一些简单分析器的具体实现类(如SimpleAnayzer, StopAnalyzer)，一些常用的分词器和过滤器(如Lowe ...
该系列文章是《An Introduce to
Information Retrieval》Chapter 4 的读书笔记。
对于大规模数据的信息检索，倒排索引的建立其实并没有想象中的那么简单。在实际应用中，倒排索引的建立算法必须考虑到硬件的约束。可以这样说：计算机硬件的参数性能是促动IR系统的设计发展的决定因素。
索引创建(Index construction)
要点：(1) 介绍 BSBI 算法建立大规模数据的倒排索引
(2) 分布式索引的建立算法
4.1 硬件基础介绍
下图是2007 ...
计算机存储设备一般分为两种——内存储器(main memory)和外存储器。 内存存取速度快，但容量小，价格昂贵。而且不能长期保存数据(在不通电情况下数据会消失)。
外存储器——磁盘
磁盘时一种直接存取的存储设备(DASD)。它是以存取时间变化不大为特征的。可以直接存取任何字符组，且容量大、速度较其它外存设备更快。
磁盘的构造
磁盘时一个扁平的圆盘(与电唱机的唱片类似)。盘面 上有许多称为磁道 的圆圈，数据就记录在这些磁道上。磁盘可以是单片的，也可以是由若干盘片 组成的盘组 ，每一盘片上有两个面。如下图6片盘组为例，除去最顶端和最底端的外侧面不存储数据之外，一 ...
题目：有一个江洋大盗，他每次写信都是从一张报纸上剪下单词，再把单词贴在信上。假如某张报纸的单词保存在vector<string>paper 中，而信的单词保存在vector<string>letter 中，写一个算法程序判别该报纸可不可以生成该信？
对比一些方法： 这里假设paper:(m个单词，每个单词平均d个字母),letter:(n个单词，每个单词平均d个字母)。对于中文词语而言，一般2~4个字左右，对于英文单词，d就要大一点，但基本上也是常数。因此d远远小于m，下面比较的时候就不考虑单词中每个字符间的比较了。
(1) 蛮力匹配：
把n中 ...
LIS：
给定一个字符串序列S={x0,x1,x2,...,x(n-1)}，找出其中的最长子序列，而且这个序列必须递增存在。
下面给出解决这个问题的几种方法：
(1) 转化为LCS问题
思想：
将原序列S递增排序成序列T，然后利用动态规划算法取得S与T的公共最长子序列。具体算法详见《LCS最长公共子序列
》。
效率：
这个方法排序最好的是时间复杂度是O(n*logn)，动态规划解决LCS的时间复杂度是O(n^2)。因此总体时间复杂度是O(n*logn)+O(n^2)=O(n^2)
级别。
(2) 分治 ...
问题描述
：设T是长为n的文本串。描述一个找出T的最长前缀的O(n)时间的方法，该前缀也是T的逆串的一个子串。
(来自《Algorithm Design》(中文版：算法分析与设计) -
Chapter9 - 文本处理 - 创新题C-9.12）
分析：既然要在O(n)时间内完成，KMP算法是可以考虑的。根据题目要求我们发现要让T的前缀匹配到T的逆串。那么我们可以把T的逆串作为主串，T作为模式串。对KMP算法做如下修改：
(1) 在匹配逻辑中，主串指针 i 从T逆向开始查找，即i=(T.length-1) ——> 0。模式串指针 j 从T正向开始查找， ...