Hov's Blog

To code, To record, To recall.

谈谈全文检索

作者注:最近,实验室有一个关于大数据全文检索的项目,主要架构采用了 Elasticsearch + Lucene ,并修改了部分源码,通过后缀数组代替 Lucene 原有的索引方式。因此,接触了一些全文检索相关的内容。偶然的机会,我在网络上看到 forfuture1978 关于 Lucene 的文章,觉得很受启发,深感有必要记录下来。我相信,本文也能很好地帮助您理解全文检索。本文部分内容出自 Lucene 原理与代码分析 ,感谢原作者的贡献。 0 写在前面 大数据时代,人们愈加重视数据的价值。在此之前,我们将数据存放在传统的关系型数据库(一个个数据表,由行列组成,格式固定),关系型数据库存储的是结构化数据,我们无法“用活”这些数据。事实上,绝大多数的数据都是以非结构化数据的形式存在的,比如邮件、图像、视频等等。这些大量的非结构化数据的价值是巨大的,但在关系型数据库下显然不好处理。 全文检索提供了对非结构化数据的信息搜索,使我们获得了处理这些数据的能力,我们可以在此基础上进一步提取这些数据的价值。 1 预备知识 1.1 数据分类 我们平时所说的数据,可分为结构化数据、半结构化数据和非结构化数据。 结构化数据:具有既定格式的实体化数据,如 XML 文档或满足特定预定义格式的数据库表; 半结构化数据:虽然可能有格式,但经常被忽略,所以只能作为对数据结构的一般性指导。如电子表格,它在结构上是由单元格组成的网格,但是每个单元格内可以保存任何形式的数据; 非结构化数据:无固定格式或不定长的数据,如纯文本、图像数据、邮件内容等。 1.2 数据搜索 数据的搜索根据数据的不同分类有所区别: 对结构化数据的搜索:如通过 SQL 语句对数据库的搜索等。 对非结构化数据的搜索:如 Linux 环境下的 grep 命令、 Google 搜索大量的内容数据等。 注:半结构化数据在本文将等同非结构化数据考虑。 2 什么是全文检索? 非结构化数据也可称为全文数据,对全文数据的搜索主要有两种方法。 (1)顺序扫描法(Serial scanning) 顺序扫描比较好理解,比如我们想在图书馆找某本书,那么我们就将整个图书馆的书一个一个比较,直到找到我们要找的书(当然现实中我们不会这么做)。 (2)全文检索(Full-text search) 全文检索的基本思路:将非结构化数据中的一部分信息提取出来,重新组织,使其变得有一定的结构,然后再对其进行搜索。也就是,将非结构化数据转化为结构化数据。 从非结构化数据中提取并重新组织的信息就叫做索引。索引其实我们早有接触,比如图书馆的图书索引,通过索引我们可根据图书的不同分类去特定的书架寻找,这样就无需寻找整个图书馆的所有书架。再比如,字典里通过汉字拼音的首字母分类,我们要在字典中寻找关于“搜索”的条目,只需找到首字母为 “S” 的分类即可。可见,索引可大大加快我们搜索的速度。 综上,对数据先建立索引,再通过索引搜索数据的过程就叫做全文检索。 下图为 Lucene 的检索原理,这其实也是全文检索的基本思路。通过对元数据建立索引信息,然后根据索引信息搜索数据。 3 索引应该存放哪些信息? 非结构化数据存放的是每个文件包含哪些字符串,这是从文件到字符串的映射。搜索的过程恰恰相反,我们想通过字符串搜索文件,也就是从字符串到文件的映射。 索引保存的正是从字符串到文件的映射,这也为什么是其能加快搜索速度的原因。

【LeetCode】292. Nim Game

题目描述: You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones. Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

【LeetCode】59. Spiral Matrix II

题目描述: Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 思路: 题意要求根据 n ,创建一个 n*n 的回旋矩阵。 设置 direction ,表示构造方向(向右,向下,向左,向上); 设置 left、right、top、buttom ,分别指示矩阵左边界、右边界、上边界、下边界; 设置 count 指示当前的数值; 按右-下-左-上的顺序不断循环构造,直至 left>right 或 top>buttom 。

【LeetCode】54. Spiral Matrix

题目描述: Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. 思路: 给定一个矩阵,以回旋形式以此遍历矩阵中的每个元素。 设置 direction ,表示遍历方向(向右,向下,向左,向上); 设置 left、right、top、buttom ,分别指示矩阵左边界、右边界、上边界、下边界; 每遍历一个元素将其添加到 ret 中,直至 left>right 或 top>buttom 。

【LeetCode】328. Odd Even Linked List

题目描述: Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL. Note: The relative order inside both the even and odd groups should remain as it was in the input.