| cover | https://images.squarespace-cdn.com/content/v1/5daddb33ee92bf44231c2fef/1593634997762-75P05A5AKO859N5G9OMU/medical-algorithms.gif |
|---|---|
| coverY | 0 |
（搜索引擎工作原理
简单来说，正向索引是通过key找value，反向索引是通过value来找key
文档是有许多的单词组成的，其中每个单词也可以在同一个文档中重复出现很多次，当然，同一个单词也可以出现在不同的文档中。
正向索引(forward index)：从文档角度看其中的单词，表示每个文档（用文档ID标识）都含有哪些单词，以及每个单词出现了多少次（词频/TF：terms frequency）及其出现位置（相对于文档首部的偏移量）。
反向索引(inverted index)：从单词角度看文档，标识每个单词分别在那些文档中出现(文档ID)，以及在各自的文档中每个单词分别出现了多少次（词频/TF：terms frequency）及其出现位置（相对于该文档首部的偏移量）
An inverted index is just a dictionary, where the keys are the words found in the corpus and the value for a key is a list of all the documents that have that word in them.
当我们把反向索引当成一个字典的时候，key是用户输入的单词，value是数据库中含有关键字的所有文档
TF-IDF(term frequency–inverse document frequency)是一种用于信息检索与数据挖掘的常用加权技术，常用于挖掘文章中的关键词。
TF-IDF有两层意思，一层是**"词频"（Term Frequency，缩写为TF），另一层是"逆文档频率"**（Inverse Document Frequency，缩写为IDF）。
假设我们现在有一片长文，词频高在文章中往往是停用词，“的”，“是”，“了”等，这些在文档中最常见但对结果毫无帮助、需要过滤掉的词，用TF可以统计到这些停用词并把它们过滤。当高频词过滤后就只需考虑剩下的有实际意义的词。
但这样又会遇到了另一个问题，我们可能发现有些词的出现次数一样多。这是不是意味着，作为关键词，它们的重要性是一样的？
所以在关键词排序上，需要IDF给常见的词较小的权重，它的大小与一个词的常见程度成反比。
一个词预测主题的能力越强，权重越大，反之，权重越小。
当有TF(词频)和IDF(逆文档频率)后，将这两个词相乘，就能得到一个词的TF-IDF的值。某个词在文章中的TF-IDF越大，那么一般而言这个词在这篇文章的重要性会越高，所以通过计算文章中各个词的TF-IDF，由大到小排序，排在最前面的几个词，就是该文章的关键词
第一步，计算词频
第二步，计算逆文档频率：
这时，需要一个语料库（corpus），用来模拟语言的使用环境
如果一个词越常见，那么分母就越大，逆文档频率就越小越接近0。分母之所以要加1，是为了避免分母为0（即所有文档都不包含该词）。log表示对得到的值取对数。
第三步，计算TF-IDF：
TF-IDF与一个词在文档中的出现次数成正比，与该词在整个语言中的出现次数成反比。所以，自动提取关键词的算法就很清楚了，就是计算出文档的每个词的TF-IDF值，然后按降序排列，取排在最前面的几个词
优缺点：
TF-IDF的优点是简单快速，而且容易理解。缺点是有时候用词频来衡量文章中的一个词的重要性不够全面，有时候重要的词出现的可能不够多，而且这种计算无法体现位置信息，无法体现词在上下文的重要性。还有是没有考虑语序，武松打虎 ， 虎打武松，这种统计是一样的特征表示。
散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。
哈希函数（散列函数）能够将任意长度的输入值转变成固定长度的值输出，该值称为散列值，输出值通常为字母与数字组合。
属性：
- 定义里面讲的是哈希函数接收任意长度的输入，但在实际实现中，大家都会指明一个具体可接收的阈值，例如SHA-2最高接受(2^64-1)/8长度的字节字符串。此处需要理解的是哈希函数拥有较为庞大的输入值域，它接受长度非常长的输入值。
- 产生固定长度的输出值。
- 不可逆性，已知哈希函数fn与x的哈希值无法反向求出x，当然这里的不可逆是指计算上行不通，正着算很好算，反着算在当前的计算机计算能力条件下做不到。
- 对于特定的哈希函数，只要输入值不变，那么输出的值也是唯一不变的。
- 哈希函数的计算时间不应过长，即通过输入值求出输出值的时间不宜过长。
- 无冲突性，即对于输入值x，与哈希函数fn，无法求出一个值y，使得x与y的哈希值相等。但是由于上文我们知道，由于哈希函数实际上代表着一种映射（对应关系），将一个大区间上的数值映射到一个小区间上，它一定是有冲突的，这里的无冲突同样是指“求冲突在计算上行不通”，正向地计算很容易，但是反向的计算在当前的计算机能力条件下做不到，但是这种冲突的概率发生了怎么办我们后面再说。
- 即使修改了输入值的一个比特位，也会使得输出值发送巨大的变化。
- 哈希函数产生的映射应当保持均匀，即不要使得映射结果堆积在小区间的某一块区域。
通俗易懂的例子：
手机通讯录里面的人名依据首字母从a-z的顺序排列着的，这种排列方式能让我们快速地找到某个人。
我们不妨认定这种映射过程为一个简陋的哈希函数，并称这个简陋的哈希函数为“电话簿哈希”。我们可以看到，“电话簿哈希”的运行机制很简单：对于任意输入值，“电话簿哈希”都取第一个字的拼音首字母输出。
这个哈希函数实际上满足我们在上方列举的8条属性中的前5条的。但是从第6条开始，我们定义的这个电话簿哈希就不满足了。
我们来分析一下，由于这个这个函数过于简陋，它的冲突概率是较高的，比如我们分别输入“张三”、“章五”，“电话簿哈希”都输出了“z”。
回到我们的电话簿哈希中，针对此处的冲突我们修改一下哈希函数：“将取第一个字的首字母改为取每个字的首字母”。也就是说输入“张三”与“章五”输出值变成了“zs”与“zw”，之后我们再来通过输出值执行名字到电话簿位置的映射。
存放到具体位置遵循以下规则，定位依然遵循从a到z的顺序，但是出现冲突后取第二个字的首字母再排序。那么咱们这个升级后的“电话簿哈希”对于上方的输入，就有了更为具体的电话簿位置映射。
此时，“张三”与“章五”无需冲突在位置“z”上，而是在位置“z”上冲突后，执行了冲突解决方法，即以第二个字首字母对冲突对象再排序，“s”排在“w”之前，因此，“张三”与“章五”应当排在电话簿的“z”下，且“张三”的位置在“章五”前面。
但是这个升级后的哈希函数依然有漏洞，它还有冲突未解决。
即使我们已完美解决了冲突的问题，但是回顾“电话簿哈希”这个哈希函数的设计原理，咱们的电话簿哈希依然存在问题——假设我姓“刘”，那么由于我会保存很多姓“刘”的亲戚，电话簿中大量的联系人都映射在了“L”这个地址下。
即使我们有了升级版的解决办法，能解决冲突的问题，但是由于映射的不均匀，大量的数据堆积在了一块区域，那么冲突发生的概率顿时就高了许多。由此导致本来查找速度极快的哈希函数速度降下来许多了——因为它需要继续执行冲突之后的遍历。这个与现实生活中的体验是一致的：我们能通过一次查找定位人名在“L”下，但是我们要具体找到目标甚至需要遍历“L”下挂着的所有对象，这是一个优秀的哈希函数所难以容忍的。
我们的哈希函数“电话簿哈希”还需要升级，使得映射能够更均匀一些。这里就不再继续开脑洞如何升级“电话簿哈希”这个函数了。但是需要说明的是，就算我们将来能解决这个映射不均匀的问题，我们也会引入一个新的问题：这个哈希函数计算起来变复杂了，它为了兼顾前文我们列举的种种要求种种属性，函数考虑的东西越来越多应对的情况越来越丰富，以至于函数本身体积膨胀，计算哈希值（输出值）变的很耗费CPU（脑细胞）。
试想，我们发明这个哈希函数目的就是为了快点找到目标人名，但是在找到这个人名之前我们得经过一系列的计算，那岂不是违背设计这个函数以达到“快速查找”的初衷。所以这里往往要做一个权衡，实际上很多类似的函数设计都有这个权衡在里面。
手机中的电话簿实现到了这一步基本就停止了，没有再去解决映射不均匀的情况实际上也是权衡的结果。人脑根据拼音首字母来定位到特定字母目录下，而不用遍历一整个电话簿已经帮了很大忙了，而且人脑完成这一映射的速度也非常快（计算简单），所需要的仅仅是费些时间遍历某个字母下挂靠着的节点而已。
哈希函数十分强大，除了上文的“快速查找”场景以外，还有许多经典的场景。
- 保护数据，散列值可用于唯一地识别机密信息，这个应用场景是基于属性“无冲突”的特性，但是本文关于无冲突还是太浅显，实际上各种散列函数为了实现更强的抗碰撞，都有各自更加复杂的设计。
- 确保传递真实的消息，这个实际上是“数字签名”的内容。人们通过哈希函数获得“指纹”（摘要），打包原文与“摘要”一同发送，接收者只需要将原文进行一次哈希后与“摘要”进行匹配即可。
- 散列表，这应当是最经典的用法了，散列表是数组加链表的组成，上文我们举的关于“电话簿”的例子其实就类似于散列表的定义。
性能不佳的散列函数表意味着查找操作会退化为费时的线性搜索。
上方引用来自维基百科下的最后一句，对于这句引用代入到例子中同样好理解，在我们所举的“电话簿”例子中，假设电话簿中所存名字都是“刘”姓，那么所有的映射都集中到了“L”地址下了，所有的姓名挂靠在“L”地址节点下，整个哈希表退化成了一个链表，那么链表的查询能力大家是有目共睹。因此，一个优秀的散列函数对于查询是至关重要的。
\