算法

A collection of 6 posts
算法

倒排索引

世界上最伟大的互联网产品,说是搜索引擎,绝对没有别的产品可以替代,尤其是伟大的先在市场占用率最高的搜索引擎,Google Search. 还有很多差一大截的,比如 Bing, Yahoo 和 YANDEX. 什么是搜索引擎 所谓搜索引擎,就是根据用户需求与一定算法,运用特定策略从互联网检索出制定信息反馈给用户的一门检索技术。 搜索引擎技术的核心模块一般包括爬虫、索引、检索和排序等,同时可添加其他一系列辅助模块,以为用户创造更好的网络使用环境。 搜索引擎干了些什么 简单的说搜索引擎从网络上爬取网页,然后对网页信息进行提取,构建正排索引,然后分析网页内容,建立倒排文件. 接下来我将依次介绍 正排索引、 倒排索引 等知识点. 正排索引 正排索引通常是 id-document 的键值对 id name context eng_context 1 小明 今天吃了 3 个包子 today eating 3 baozi 2
4 min read
算法

KMP 算法

在计算机科学中,Knuth-Morris-Pratt 字符串查找算法(简称为 KMP 算法)可在一个主文本字符串 S 内查找一个词 W 的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现,从而避免重新检查先前匹配的字符。 这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在 1974 年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终由三人于 1977 年联合发表。 原理 将待匹配字符串命名为 m 源字符串命名为 S 。本算法对待匹配字符串做处理之后,找到他的真前缀和真后缀。并通过真前缀与后缀重合的数量的值,这个值是在匹配状态中发生矢配时,位于原始字符串上 S 的指针移动的方向与距离。 简单的说就是匹配失败时。通过之前的真前缀和后缀表,直接移动在匹配字符串上的指针,达到减少无用匹配的效果。 优点 节约时间,相比于朴素的匹配方式,新的匹配算法只需要 O(m + n)
2 min read
算法

编辑距离

编辑距离是针对二个字符串(例如英文字)的差异程度的量化量测,量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中,例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离,判断哪一个(或哪几个)是比较可能的字。DNA 也可以视为用 A、C、G 和 T 组成的字符串,因此编辑距离也用在生物信息学中,判断二个 DNA 的类似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。 编辑距离有几种不同的定义,差异在可以对字符串进行的处理。 在莱文斯坦距离中,可以删除、加入、取代字符串中的任何一个字元,也是较常用的编辑距离定义,常常提到编辑距离时,指的就是莱文斯坦距离。 也存在其他编辑距离的定义方式,例如 Damerau-Levenshtein 距离是一种莱文斯坦距离的变种,但允许以单一操作交换相邻的两个字符(称为字符转置),如 AB→BA 的距离是 1(交换)而非 2(
3 min read
算法

Tree in Python

树是计算机科学中常用的数据结构之一,常见的地方有,Java 的继承树等。 还有一些基于树的特殊数据结构,比如二叉树,B 树,等等。 本篇会讲述一些关于简单关于树的操作。 树的定义 树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由 n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点: * 每个节点有零个或多个子节点 * 没有父节点的节点称为根节点 * 每一个非根节点有且只有一个父节点 * 除了根节点外,每个子节点可以分为多个不相交的子树 节选自 树(数据结构) 定义数据结构 class TreeNode(object): """ 一个树节点 """ def
5 min read
算法

基本排序算法的 Python 实现

本篇主要实现九(八)大排序算法,分别是冒泡排序,插入排序,选择排序,希尔排序,归并排序,快速排序,堆排序,计数排序。希望大家回顾知识的时候也能从我的这篇文章得到帮助。 为了防止误导读者,本文所有概念性内容均截取自对应 Wiki 冒泡排序 原理 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 步骤 冒泡排序算法的运作如下: 1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 3. 针对所有的元素重复以上的步骤,除了最后一个。 4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 代码 def bubble_sort(
11 min read
算法

基本线性数据结构的 Python 实现

本篇主要实现四种数据结构,分别是数组、堆栈、队列、链表。我不知道我为什么要用 Python 来干 C 干的事情,总之 Python 就是可以干。 所有概念性内容可以在参考资料中找到出处 数组 数组的设计 数组设计之初是在形式上依赖内存分配而成的,所以必须在使用前预先请求空间。这使得数组有以下特性: 1. 请求空间以后大小固定,不能再改变(数据溢出问题); 2. 在内存中有空间连续性的表现,中间不会存在其他程序需要调用的数据,为此数组的专用内存空间; 3. 在旧式编程语言中(如有中阶语言之称的 C),程序不会对数组的操作做下界判断,也就有潜在的越界操作的风险(比如会把数据写在运行中程序需要调用的核心部分的内存上)。 因为简单数组强烈倚赖电脑硬件之内存,所以不适用于现代的程序设计。欲使用可变大小、硬件无关性的数据类型,Java 等程序设计语言均提供了更高级的数据结构:ArrayList、Vector 等动态数组。 Python 的数组 从严格意义上来说:Python 里没有严格意义上的数组。 List可以说是 Python
6 min read