搜索中常见数据结构与算法探究（一）

原创郑冰潘坤京东技术

Tech

导读
本文介绍了算法和数据结构的基础概念和复杂度函数，并提供了一些评价算法和数据结构优劣的方法论，之后又重点介绍了几种工作中常见且重要的数据结构和算法。作为系列文章的开篇，希望读者能够在理解复杂度函数的基础上，重点关注每一种数据结构的优劣势分析。

前言

ES现在已经被广泛的使用在日常的搜索中，Lucene作为它的内核值得深入研究，比如FST，下面就用两篇分享来介绍一些本文的主题：

第一篇主要介绍数据结构和算法基础和分析方法，以及一些常用的典型的数据结构；
第二篇主要介绍图论，以及自动机，KMP，FST等算法；

下面开始第一篇：

提出问题

“算法是计算机科学领域最重要的基石之一“

“编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。“

——《算法的力量》

2.1.1 案例一

设有一组N个数而要确定其中第k个最大者，称之为选择问题。常规的解法如下：

该问题的一种解法就是将这N个数读进一个数组中，在通过某种简单的算法，比如冒泡排序法，以递减顺序将数组排序，然后返回位置k上的元素。
稍微好一点的算法可以先把前k个元素读入数组并对其排序。接着，将剩下的元素再逐个读入。当新元素被读到时，如果它小于数组中的第k个元素则忽略之，否则就将其放到数组中正确的位置上，同时将数组中的一个元素挤出数组。当算法终止时，位于第k个位置上的元素作为答案返回。

这两种算法编码都很简单，但是自然要问：哪个算法更好？哪个算法更重要？还是两个算法都足够好？使用N=30000000和k=15000000进行模拟将发现，两个算法在合理的时间量内均不能结束；每一种算法都需要计算机处理若干时间才能完成。

其实还有很多可以解决这个问题，比如二叉堆，归并算法等等。

2.2.2案例二

输入是由一些字母构成的一个二维数组以及一组单词组成。目标是要找出字谜中的单词，这些单词可能是水平、垂直、或沿对角线上任何方向放置。下图所示的字谜由单词this、two、fat和that组成。

图1 字谜单词字符排列示意图

现在至少也有两种直观的算法来求解这个问题：

对单词表中的每个单词，检查每一个有序三元组（行，列，方向）验证是否有单词存在。这需要大量嵌套的for循环，但它基本上是直观的算法。
对于每一个尚未越出迷板边缘的有序四元组（行，列，方向，字符数）可以测试是否所指的单词在单词表中。这也导致使用大量嵌套的for循环。

上述两种方法相对来说都不难编码，但如果增加行和列的数量，则上面提出的两种解法均需要相当长的时间。

以上两个案例中，可以看到要写一个工作程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要问题。

那么，使用自动机理论可以快速的解决这个问题，下一篇中给大家详细的分析。

03
数据结构与算法基础

3.1 数据结构基础

3.1.1 什么是数据结构
在计算机领域中，数据是信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号的总称。数据结构是指数据元素和数据元素之间的相互关系或数据的组织形式。数据元素是数据的的基本单位，数据元素有若干基本项组成。
3.1.2 数据之间的关系
数据之间的关系分为两类：
· 逻辑关系
表示数据之间的抽象关系，按每个元素可能具有的前趋数和直接后继数将逻辑结构分为线性结构和非线性结构。
逻辑关系或逻辑结构有如下特点：
只是描述数据结构中数据元素之间的联系规律；
是从具体问题中抽象出来的数学模型，是独立于计算机存储器的（与硬件无关）
逻辑结构的分类如下：
线性结构
树形结构
图状结构
其他结构
· 物理关系
逻辑关系在计算中的具体实现方法，分为顺序存储方法、链式存储方法、索引存储方法、散列存储方法。
物理关系或物理结构有如下特点：
是数据的逻辑结构在计算机存储其中的映像；
存储结构是通过计算机程序来实现，因而是依赖于具体的计算机语言的；
物理结构分类如下：
顺序结构
链式结构
索引结构

3.2 算法基础

3.2.1 基础概念
算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。对于一个问题，一旦某种算法给定并且被确定是正确的，那么重要的一步就是确定该算法将需要多少诸如时间或空间等资源量的问题。如果一个问题的求解算法竟然需要长达一年时间，那么这种算法就很难能有什么用处。同样，一个需要若干个GB的内存的算法在当前的大多数机器上也是无法使用的。

3.2.2 数学基础
一般来说，估算算法资源消耗所需的分析是一个理论问题，因此需要一套数学分析法，先从数学定义开始。

定理1：如果存在正常数c和n0，使得当N>= n0时，T(N) <= cf(N)，则记为T(N) = O(f(N))。

定理2：如果存在正常数c和n0，使得当N>=n0时，T(N) <= cg(N)，则记为T(N) = Ω(g(N))。

定理3：T(N) = θ(h(N))当且仅当T(N) = O(h(N)) 和 T(N) = Ω(h(N))。

定理4：如果对每一个正常数c都存在常数n0使得当N>n0时，T(N) < cp(N)，则T(N) = o(p(N))。

这些定义的目的是要在函数间建立一种相对的级别。给定两个函数，通常存在一些点，在这些点上一个函数的值小于另一个函数的值，因此，一般宣称f(N)<g(N)，是没有什么意义的。于是，比较他们的相对增长率。当将相对增长率应用到算法分析时，会明白它是重要的度量。

如果用传统的不等式来计算增长率，那么第一个定义T(N) = O(f(N))是说T(N)的增长率小于或者等于f(N)的增长率。第二个定义T(N) = Ω(g(N))是说T(N)增长率大于或者等于g(N)的增长率。第三个定义T(N) = θ(h(N))是说T(N)的增长率等于h(N)的增长率。最后一个定义T(N) = o(p(N))说的则是T(N)的增长率小于p(N)的增长率。他不同于大O，因为大O包含增长率相同的可能性。

要证明某个函数T(N) =O(f(N))，通常不是形式的使用这些定义，而是使用一些已知的结果（比如说T(N) = O(log(N))）。一般来说，这就意味着证明是非常简单的计算而不应涉及微积分，除非遇到特殊情况。如下是常见的已知函数结果
c（常数函数）
logN（对数函数）
logN^2（对数平方函数）
N（线性函数）
NlogN
N^2（二次函数）
N^3（三次函数）
2^N（指数函数）

在使用已知函数结果时，有几点需要注意：

首先，将常数或低阶项放进大O是非常坏的习惯。不要写成T(N) = O(2N^2)或T(N) = O(N^2 + N)。这两种情形下，正确的形式是T(N) = O(N^2)。也就是说低阶项一般可以被忽略，而常数也可以弃掉。
其次，总能够通过计算极限limN→∞f(N)/g(N)（极限公式）来确定两个函数f(N)和g(N)的相对增长率。该极限可以有四种可能的值：
极限是0：这意味着f(N) = o(g(N))。
极限是c != 0：这意味着f(N) = θ(g(N))。
极限是∞：这意味着g(N) = o(f(N))*。
极限摆动：二者无关。

3.2.3 复杂度函数
正常情况下的复杂度函数包含如下两种：
时间复杂度
空间复杂度
时间和空间的度量并没有一个固定的标准，但是在正常情况下，时间复杂度的单位基本上是以一次内存访问或者一次IO来决定。空间复杂度是指在算法执行过程中需要占用的存储空间。对于一个算法来说，时间复杂度和空间复杂度往往是相互影响，当追求一个好的时间复杂度时，可能会使空间复杂度变差，即可能占用更多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度变差，即可能占用较长的运算时间。

3.3 知识储备

3.3.1 质数分辨定理（HashTree的理论基础）
简单的说就是，n个不同的质数可以分辨的连续数的个数和他们的乘机相同。分辨是指这些连续的整数不可能有相同的余数序列。

3.3.2 Hash算法
1）Hash
Hash一般翻译成散列，也可以直接音译成哈希，就是把任意长度的输入，通过散列算法变换成固定长度的输出，该输入就是散列值。不同的输入可能散列成相同的值，确定的散列值不可能确定一个输入。
2）常见的Hash算法
MD4：消息摘要算法；
MD5：消息摘要算法，MD4的升级版本；
SHA-1：SHA-1的设计和MD4相同原理，并模仿该算法；
自定义HASH算法：程序设计者可以自定义HASH算法，比如java中重写的hashCode()方法。
3）Hash碰撞
解决Hash碰撞常见的方法有一下几种：
分离链接法（链表法）：做法是将散列到同一个值的所有元素保留在一个表中，例如JDK中的HashMap；
探测散列表：当发生Hash碰撞时，尝试寻找另外一个单元格，直到知道到空的单元为止。包括：线性探测法，平方探测法，双散列。
3.3.2树结构的基本概念

树的递归定义：一棵树是一些节点的集合。这个集合可以是空集；若不是空集，则树由根节点root以及0个或多个非空的子树组成，这些子树中每一棵的根都被来自根root的一条有向的边所连接；
树叶节点：没有儿子节点称为树叶；
深度：对于任意节点ni，ni的深度为从根到ni的唯一路径的长；
高度：对于任意节点ni，ni的高度为从ni到一片树叶的最长路径的长；
树的遍历：树的遍历分为两种，先序遍历和后续遍历。

3.3.4二叉搜索树

二叉搜索树是一棵二叉树，其中每个节点都不能有多于两个子节点。

对于二叉查找树的每一个节点X，它的左子树中所有项的值都小于X节点中的项，而它的右子树中所有项的值大于X中的项。