• 文档矩阵
• 倒排索引基本概念
  • 文档(Document)
  • 文档集合(Document Collection)
  • 文档编号(Document ID)
  • 单词编号(Word ID)
  • 倒排索引(Inverted Index)
  • 单词词典(Lexicon)
  • 倒排列表(PostingList)
  • 倒排文件(Inverted File)
• 倒排索引
• 倒排列表
• 倒排索引简单实例
• 单词词典
  • 哈希加链表
  • 树形结构
• 索引更新
  • 完全重建策略
  • 再合并策略
  • 原地更新策略
  • 混合策略

文档矩阵

单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型。图的每列代表一个文档，每行代表一个单词，打对勾的位置代表包含关系。

从纵向即文档这个维度来看，每列代表文档包含了哪些单词，比如文档1包含了词汇1和词汇4，而不包含其它单词。从横向即单词这个维度来看，每行代表了哪些文档包含了某个单词。比如对于词汇1来说，文档1和文档4中出现过单词1，而其它文档不包含词汇1。矩阵中其它的行列也可作此种解读。
搜索引擎的索引其实就是实现“单词-文档矩阵”的具体数据结构。可以有不同的方式来实现上述概念模型，比如“倒排索引”、“签名文件”、“后缀树”等方式。但是各项实验数据表明，“倒排索引”是实现单词到文档映射关系的最佳实现方式。

• 直接寻址
• 散列表
  • 链接法
  • 开放寻址法
• 散列函数的设计
  • 散列函数的需求
  • 常见的散列函数
    • 除法散列函数
    • 乘法散列函数

转帖:散列表

直接寻址

使用散列的目的是能够快速取得某个元素，那么如果能够保证每个元素都存在一个“槽”的话（类似于数组），就能够完成在O(1)的时间内完成取元素的工作。如果一个集合的元素都是取自全域U={1, 2, ... m}，那么通过使用数组T[1,...m]来保证每个元素都存在与之对应的”槽“。

• 跳表介绍
  • 跳表核心思想
• 存储模式
  • 性质
  • 结构设计
• 操作
  • 搜索
  • 插入
    • K取值
    • 高度
    • 空间复杂度
  • 删除
• 代码
  • Java
  • C++
    • 初始化
    • 插入
    • 删除

跳表介绍

目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。
跳表是一种随机化的数据结构，目前开源软件Redis和LevelDB都有用到它，它的效率和红黑树以及AVL树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。
这是跳表的作者，上面介绍的William Pugh给出的解释。

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

跳表核心思想

从该有序表中搜索元素“23,43,59”，需要比较的次数分别为<2, 4, 6>，总共比较的次数为2 + 4 + 6 = 12次。有没有优化的算法吗? 链表是有序的，但不能使用二分查找。类似二叉搜索树，把一些节点提取出来，作为索引。得到如下结构。

把“14,34,50,72”提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构。

如果是说链表是排序的，并且节点中还存储指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。

• 算法
• Java

算法

中缀表达式转后缀表达式的方法：

1. 遇到操作数：直接输出（添加到后缀表达式中）
2. 栈为空时，遇到运算符，直接入栈
3. 遇到左括号：将其入栈
4. 遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
5. 遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素【栈内的栈顶运算符>=遇到的运算符，就弹出】，然后将该运算符入栈
6. 最终将栈中的元素依次出栈，输出。

实现中缀表达式转换为后缀表达式主要包含三个类，一个主函数，一个自定义栈的类，还有一个就是核心类，实现其转换。

• 概念
  • 时间复杂度
  • 空间复杂度
• 示例
  • 时间复杂度
    • $n^3$
    • O(n)：
    • O(1)：
    • O($log_{2}n$)：
    • O($n^2$)
    • O($nlog_{2}n$)
  • 时间复杂度
    • O(1)

概念

时间复杂度

是度量算法执行的时间长短，时间复杂度是指他运行时计算的次数。
一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算法的时间复杂度记做：T(n)=O(f(n))
随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。
在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T(n)的同数量级（它的同数量级有以下：1，$log_{2}n$，n，$nlog_{2}n$，n的平方，n的三次方，2的n次方），找出后，f(n) = 该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T(n) = O(f(n)。
按数量级递增排列，常见的时间复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O($n^2$)，立方阶O($n^3$),…，k次方阶O($n^k$)，指数阶O($2^n$)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

空间复杂度

是度量算法所需存储空间的大小，空间复杂度是指运行完一个程序所需内存的大小。在算法中所谓的空间复杂度为O(1)并不是说只使用一个空间，而是说在待处理的数据量变化的情况下使用的空间量是不变的。空间复杂度一般算的是辅助空间的大小，如果这个辅助空间的大小不随元素N变化那么就是O(1)。
例如：冒泡排序，需要的辅助空间是一个作交换用的临时变量，而且无论任何情况下都只要这一个，所以空间复杂度就是O(1)。但桶排序就不同了，本身需要M个桶，桶的数量是人为决定的，然后需要N个结点，去装原本的N个元素，所以空间复杂度就是O(M+N)。
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。
程序执行时所需存储空间包括以下两部分。
固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示：S(n)=O(f(n))，其中n为问题的规模，S(n)表示空间复杂度。

示例

时间复杂度

$n^3$

1
2
3
4
5
6
7
8
9

for(i=1; i<=n; ++i)
{
    for(j=1; j<=n; ++j)
    {
        c[i][j] = 0;//该步骤属于基本操作执行次数：n的平方次
        for(k=1; k<=n; ++k)
            c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数：n的三次方次
    }
}

则有T(n) = n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定n的三次方为T(n)的同数量级，则有f(n) = n的三次方，然后根据T(n)/f(n)求极限可得到常数c，则该算法的时间复杂度：T(n) = O($n^3$) 。注：$n^3$即是n的3次方。

O(n)：

1
2
3
4

int x = 1;//时间复杂度为O(1)  
for(int i=0; i<n; i++) {  
    System.out.println(i);  
}//时间复杂度为O(n)

O(1)：

1

int x = 1;

O($log_{2}n$)：

1
2
3
4

int n = 8, count = 0;;  
for(int i=1; i<=n; i *= 2) {  
    count++;  
}

O($n^2$)

1
2
3
4
5
6

int n = 8, count = 0;;  
for(int i=1; i<=n; i++) {  
    for(int j=1; j<=n; j++) {  
        count++;  
    }  
}

O($nlog_{2}n$)

1
2
3
4
5
6

int n = 8, count = 0;;  
for(int i=1; i<=n; i *= 2) {  
    for(int j=1; j<=n; j++) {  
        count++;  
    }  
}

时间复杂度

O(1)

一个临时变量temp，所以空间复杂度为O(1)

1
2
3
4

int x=1, y=2;  
int temp = x;  
x = y;  
y = temp;