|
|
By jeffye, on July 3rd, 2009
Thoughts on Lucene, Solr, Nutch and vertical search
Trie-based approximate autocomplete implementation with support for ranks and synonyms
Posted by Kelvin on 01 Jul 2009 at 02:30 am | Tagged as: programming
The problem of auto-completing user queries is a well-explored one.
For example,
Type less, find more: fast autocompletion search with a succinct index
http://stevedaskam.wordpress.com/2009/06/07/putting-autocomplete-data-structure-to-the-test/
http://suggesttree.sourceforge.net/
http://sujitpal.blogspot.com/2007/02/three-autocomplete-implementations.html
However, there’s been little written [...]
By jeffye, on March 28th, 2008
2.1 搜集的时机
一般来说，搜索引擎这样一个软件系统都是事先收集好网页，存储在本地硬盘上，然后再进行预处理、索引。可以想象如果等用户查询时再爬取成千上万的网页，再一个个分析处理，是不可能满足搜索引擎的响应时间要求的。[1]一般搜索引擎都是使用一种叫网络爬虫（也叫网络爬虫和网络机器人）的程序来完成这项工作，下面我们讲介绍这样一个程序的原理以及其实现。
2.2 网络爬虫介绍
互联网其实就是一张大图，我们可以把每一个网页当作一个节点，把那些超链接（Hyperlinks)当作连接网页的弧。网页中那些蓝色的、带有下划线的文字背后其实藏着对应的网址，当你点下去的的时候，浏览器是通过这些隐含的网址转到相应的网页中的。这些隐含在文字背后的网址称为“超链接”。有了超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫，或者在一些文献中称为“机器人“（Robot)。世界上第一个网络爬虫是由麻省理工学院 (MIT)的学生马休.格雷（Matthew Gray)在 1993 年写成的。他给他的程序起了个名字叫“互联网漫游者”(“www wanderer”)。以后的网络爬虫越写越复杂，但原理是一样的。
那么网络爬虫如何下载整个互联网。假定我们从一家门户网站的首页出发，先下载这个网页，然后通过分析这个网页，可以找到藏在它里面的所有超链接，也就等于知道了这家门户网站首页所直接连接的全部网页，诸如雅虎邮件、雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等网页，又能找到其他相连的网页。我们让计算机不停地做下去，就能下载整个的互联网。
2.2.1 搜集的策略
最长见一种方式就是所谓的“爬行”。我们在遍历互联网这张大图时，既可以从某个网页节点（或节点集）开始深度优先遍历，也可以广度优先遍历。由图论知识我们可以知道， 遍历时必须记录下已经访问过的节点（避免重复），在网络爬虫中，我们使用一个称为“哈希表”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。下面我们要介绍的爬虫WebLech就是采取这一策略。
By jeffye, on March 10th, 2008
目录 (详细见附件)下载：Nutch总结
试运行脚本说明――抓取全过程… 1
一、系统架构… 3
二、Nutch的安装测试… 6
关于 Nutch 的 segread TOOL. 7
关于 nutch analyze db. 9
Nutch中分词的嵌入… 11
Nutch中文问题… 11
Nutch中爬取网页过程中url的过滤问题… 12
Nutch中的插件结构… 12
类剖析… 15
UTF-8. 15
org.apache.nutch.io.DataOutputBuffer. 16
Segments数据的读取… 16
FetchedSegments类 – 通过hit读取所有数据… 16
NutchBean中索引加载顺序… 16
Nutch查询服务器配置方法… 17
Nutch中脚本命令与类的对应关系… 18
Nutch中查询处理… 18
SEWM评测跑程序参考步骤… 18
Incoming search terms for the article:读取nutch数据 [...]
By jeffye, on February 1st, 2008
Nutch/Lucene的存取机制与结构分析
2007-12-04 00:08
http://searcher.org.cn/html/lucene/20071011/291.htmlTEAM : I.S.T.OAUTHOR : SUMMER转载需注明出处,未经作者同意,不得用于任何形式的商业活动主题：解决nutch的segmens的拆分与nutch crawl的重载(重新构建)问题主要内容一、Lucene的索引机制与索引文件结构二、Nutch的爬虫分析与文件结构分析三、Nutch segments的拆分索引实现方案一、Lucene的索引机制与索引文件结构1、Lucene的索引机制2、Lucene文件格式_0.f0，_0.f1 文档文件_0.fnm域集合信息文件0.frq; 0.prx位置与频率文件*.fdt和*.fdx构成了域值/域索引文件segment1.nrm标准化因子- segments索引块文件- deletable保存已删除文件的记录-*.tii和*.tis构成了项字典-lock(无扩展名) 用来控制读写的同步二、Nutch的爬虫分析Nutch segments分析Nutch 的文件结构分析三、Nutch segments的拆分解决方案Lucene采取的是倒排索引结构存储结构建立反向索引。对爬取回来的信息通过Lucene Analyzer分词器提取出索引项以相关信息，如索引项的出现频率。然后分词器把这些信息写到索引文件中。其核心在于Lucene的索引文件结构（倒排索引结构），首先理解”反向索引”的概念。反向索引是一种以索引项为中心来组织文档的方式，每个索引项指向一个文档序列，这个序列中的文档都包含该索引项。相反，在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。你可以利用反向索引轻松的找到那些文档包含了特定的索引项。 Lucene使用了反向索引作为其基本的索引结构。Lucene索引index由若干段(segment)组成,每一段由若干的文档(document)组成,每一个文档由若干的域(field)组成,每一个域由若干的项(term)组成。项是最小的索引概念单位,它直接代表了一个字符串以及其在文件中的位置、出现次数等信息。域是一个关联的元组,由一个域名和一个域值组成,域名是一个字串,域值是一个项,比如将”标题”和实际标题的项组成的域。文档是提取了某个文件中的所有信息之后的结果,这些组成了段,或者称为一个子索引。子索引可以组合为索引,也可以合并为一个新的包含了所有合并项内部元素的子索引。Lucene采用倒排索引结构索引被处理为一个目录(文件夹),其中含有的所有文件即为其内容,这些文件按照所属的段不同分组存放,同组的文件拥有相同的文件名,不同的扩展名。此外还有三个文件,分别用来保存所有的段的记录、保存已删除文件的记录和控制读写的同步,它们分别是segments, deletable和lock文件,都没有扩展名。每个段包含一组文件,它们的文件扩展名不同,但是文件名均为记录在文件segments中段的名字每个 段的文件中。主要记录了两大类的信息：域集合与项集合。由于索引信息是静态存储的,域集合与项集合中的文件组采用了一种类似的存储办法：一个小型的索引文件,运行时载 入内存；一个对应于索引文件的实际信息文件,可以按照索引中指示的偏移量随机访问；索引文件与信息文件在记录的排列顺序上存在隐式的对应关系,即索引文件中按照”索引项1、索引项2…”排列,则信息文件则也按照”信息项1、信息项2…”排列。域集合与项集合之间则通过域的在域记录文件(比如segment1.fnm)中所记录的域记录号维持对应关系,segment1.fdx与segment1.tii中就是通过这种方式保持联系。这样,域集合和项集合不仅仅联系起来,而且其中的文件之间也相互联系起来。这样,整个段的索引信息就通过这些文档有机的组成。Lucene所采用的索引文件格式。基本上而言,它是一个倒排索引。,但是Lucene在文件的安排上做了一些努力,比如使用索引/信息文件的方式,从文件安排的形式上提高查找的效率。(_0.f0，_0.f1 文档文件)文档号（Document Number）编号方式：Lucene用一个整形（interger）的文档号来指示文档。第一个被加入到索引的文档就是0号，顺序加入的文档将得到一个由前一个号码递增而来的号码。标准的技术是根据每一段号码多少为每一段分配一个段号。将段内文档号转换到段外时，加上段号。将某段外的文档号转换到段内时，根据每段中可能的转换后号码范围来判断文档属于那一段，并减调这一段的段号。例如有两个含5个文档的段合并，那么第一段的段号就是0，第二段段号5。第二段中的第三个文档，在段外的号码就是8。(_0.fnm域集合信息)索引中的文档由一个或者多个域组成，这个文件包含了每个索引块中的域的信息。所有域名都存储在这个文件的域集合信息中文件中的域根据它们的次序编号。因此域0是文件中的第一个域，域1是接下来的 ，这个和文档号的编号方式相同。项频数 .frq文件包含每一项的文档的列表，还有该项在对应文档中出现的频数。项位置 .prx文件包含了某文档中某项出现的位置信息的列表。(0.frq; 0.prx位置与频率文件)项频数 .frq文件包含每一项的文档的列表，还有该项在对应文档中出现的频数。项位置 .prx文件包含了某文档中某项出现的位置信息的列表。(*.fdt和*.fdx构成了域值/域索引文件)域值存储表（Stored Fields）域值存储表使用域索引 .fdx与域值 .fdt两个文件表示。(segment1.nrm标准化因子).nrm文件包含了每个文档的标准化因子，其主要用在评分排序机制中。(segments索引块文件)Segments索引块又称segment段，这个文件包含了索引中的索引块信息，这个文件包含了每个索引块的名字以及大小等信息。(deletable保存已删除文件的记录)deletetable的文件包含了索引不再使用的文件的名字，这些文件可能并没有被实际的删除。.del文件是可选的，只有在某段中存在删除操作后才存在。(*.tii和*.tis构成了项字典 )项字典用项信息（.tis文件）和项信息索引（.tii文件） 两个文件表示。项信息索引（.tii文件）每个项信息索引文件包含.tis文件中的128个条目，依照条目在.tis文件中的顺序。这样设计是为了一次将索引信息读入内存能，然后使用它来随机的访问.tis文件。这个文件的结构和.tis文件非常类似，只在每个条目记录上增加了一个变量IndexDelta。(lock(无扩展名) 用来控制读写的同步)主要是用于防止进程在使用索引时，被其它文件操作修改索引。Nutch的爬虫分析1. 创建一个新的WebDb (admin db -create)；2. 将抓取起始URLs写入WebDB中 (inject)；3. 根据WebDB生成fetchlist并写入相应的segment(generate)；4. 根据fetchlist中的URL抓取网页 (fetch).；5. 根据抓取网页更新WebDb (updatedb).通过3―5这个循环就可以实现Nutch的深度抓取。Nutch segments分析对于segments/segment/下的文件以后分析）结构，在nutch爬虫运行后在webdb文件夹下一共产生如下五个文件：linksByMD5 linksByURL pagesByMD5 pagesByURL stats其中：Stats文件用来存放爬虫爬行后的版本信息，处理网页数量，连接数量；pagesByURL等其余四个文件夹下均有两个文件DDindex和data，其中data文件用来存放有序的key／value对，排序是通过选择不同的key和comparator来改变的，当然里面会有一些其他信息， 比如在pagesByURL中，就每隔一定长度的key／va
lue对放入一个用来定位的信息（syn）；index文件用来存放索引，但是这个索引文件也是一个有序的，这个里面存放的是key和位置信息，但是在data文件中出现的key在这个index中都能找到的，它为了节省空间，实施了每隔一段key／value建立一条索引，这样在查找的时候，因为是有序的，所以采用２分查找，如果找不到，则返回最后时候的最小的位置信息，这个位置离我们要找的目标是相当近的，然后在data文件的这个位置向前找就可以很快找到了！另外，nutch维持这个webdb的方式是，在填加，删除网页或者连接时，并不是直接向这个webdb中填加网页或者连接，而是在WebDBWriter 中的内部类PageInstructionWriter或者LinkInstructionWriter中填加一条对网页操作的命令，然后最后对存放的命令进行排序去重，最后将这个命令与现有的webdb中存放的网页数据进行合并；Fetcher类是进行实际网页抓取时候运行的类，爬虫产生的文件或文件夹都是由这个类产生的， Nutch提供了选项D是否对抓回的网页进行parse（解析），如果这个选项设置为false，将没有parseddata和parsedtext这两个文件夹。nutch爬虫产生的文件几乎都是key/value对，不同的只是key/value的种类和值不同，爬虫运行后在segments文件夹的子文件夹产生如下几个文件夹： content [...]
|
|
