IT牛人博客聚合

多模式匹配在这里指的是在一个字符串中寻找多个模式字符字串的问题。一般来说，给出一个长字符串和很多短模式字符串，如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有Trie树，AC算法，WM算法等等。我们将首先介绍这些常见算法。

1.hash

可以单字、双字、全字、首尾字hash。

优点：简单、通常有效

缺点：受最坏情况制约，空间消耗大，需要回朔。

2.Trie树

改进：进行穿线，参考KMP的算法，进行相同前缀匹配，建立跳转路径，避免回朔。

跳转路径建立的算法思想：

如果要建立节点 A -> A’ 的 跳转路径需要满足：

查看全文: http://www.udpwork.com/item/6036.html

Unrolled linked list被翻译成松散链表，是传统链表的一种改进。

传统链表中的每个node存储一个元素，而松散链表的每个node中存储一个数组。特点：

插入数据：找一个节点，插入其数组。如果节点固定长度的数组已满，则在周围新建一个节点，将原来节点中一半的数据移到新节点。

删除数据：找到节点和数组的相应下标，将数据从数组中删除。如果节点中的数据太少，将当前节点与周围的节点合并。

这样做在某些场景下有不少优点：

由于每个节点能够存储多个元素（用数组存储），减少了每个节点的额外开销。如果数组中所存储的数据太小，显然比用普通链表存储更好。因为普通链表光额外开销就比所存储的数据量大。

比数组更节省空间，要多少分配多

查看全文: http://www.udpwork.com/item/5769.html

如何计算树的直径？

1. 二叉树：计算左子树的高度，计算右子树的高度，两者相加。

2. 多叉树：计算所有子树的高度，取两个最大值相加。

 

Ikbear 猜您也喜欢：

DBank数据银行登录失败 (@fengxiangba)

数据恢复工具：Boomerang Data Recovery绿色版 (@portablesoft)

google宣布搜索方面算法的重大改进

Get Many Persimmon Trees

Unrolled linked list（松散链表）

无觅

查看全文: http://www.udpwork.com/item/5767.html

本文介绍一种生成新闻事件脉络的方法，该方法已经应用于百度新闻的新闻事件专题页中。

前言

对于一些延续时间较长的新闻事件，我们希望通过机器挖掘的手段，抽取出事件发展的重要阶段，称为事件的脉络信息；使得用户能够通过脉络信息，直观的了解该事件发展的过程。比如：在中国协助智利解救被困矿工一事的专题页中，展现如下的事件回顾信息，能够帮助用户迅速的领略该事件的来龙去脉。

图1：事件专题页

图2：事件的脉络信息

问题描述

输入：关于某一事件的相关新闻集合，包含的新闻量最好多于10篇；我们实验用的数据，是利用文本聚类得到的新闻簇，新闻簇的大小从几十到几百篇都有。（得到事件新闻集合的方法，还可以通过事件检测与跟踪的办法，或者通过获取搜索引

查看全文: http://www.udpwork.com/item/5168.html

1.   Hellow hadoop~~!

Hadoop（某人儿子的一只虚拟大象的名字）是一个复杂到极致，又简单到极致的东西。

说它复杂，是因为一个hadoop集群往往有几十台甚至成百上千台low cost的计算机组成，你运行的每一个任务都要在这些计算机上做任务的分发，执行中间数据排序以及最后的汇总，期间还包含节点发现，任务的重试，故障节点替换等等等等的维护以及异常情况处理。谁叫hadoop集群往往都是由一些平民计算机组成，没事儿罢个工什么的，实在是再寻常不过的事情。

而说其简单，则是因为，上面说到的那些，你通通不用管，你所需要做的，就是写一个程序，当然也可以是脚本，从标准输入读入一条数据，处理完之后，把结果输出到标准输出。

查看全文: http://www.udpwork.com/item/4938.html

 

发信人: draculalord ( 嗯？), 信区: Python

标 题: 也谈链表及其他Re: python标准库貌似没有实现链表？

发信站: 水木社区 (Mon Mar 21 18:49:46 2011), 转信

实际上刚开始学习一些高级语言的时候我也有同样的疑问，而且即使有链表对应物的语言，链表常常也很少被实际使用。

如果是在国外听数据结构的课，老师一般会警告你这只是一个理论概念，实际应用应该实际考察，在通常情况下链表不是一个很好的结构。

通常链表会作为一个很好的反例，告诉大家脱离实际硬件环境来谈论所谓算法复杂度是没有任何意义的。

这是因为，链表已经不适合当今的计算机硬件发展。当今

查看全文: http://www.udpwork.com/item/4791.html

常用的数据结构包括：数组，队列，堆栈，链表，树（平衡二叉树，B树，Trie树，堆），哈希表，图，后缀数组，等等。其中，堆，图结构，Trie树及后缀数组解决特定问题，其它数据结构解决通用的查找，更新，删除操作。

查找，更新和删除操作一般是O(1)，O(logN)或者O(N)，通用的数据结果大致可分为如下三种：

1, 极端型；某些操作的算法复杂度为O(1)，另外一些算法复杂度为O(N)，比如有序链表查找复杂度为O(N)，更新和删除为O(1)；

2, 平衡型：主要操作的复杂度为O(logN)，比如平衡二叉树及各种变种，B树的查找，更新和删除操作的复杂度都为O(logN)；

3, 取巧型：主要指哈希表，最差情况下的算法复杂度虽然很高

查看全文: http://www.udpwork.com/item/4079.html

[摘 要] 本文通过工业界世界级人脸测试，说明人脸识别发展现状，分别从二维、三维角度，阐述了人脸识别算法现状，并对人脸识别算法发展趋势予以说明。

[关键词] 人脸识别 二维识别算法 三维识别算法

 

一、引言

 

1.人脸识别概述。人脸识别由于可接受性好，在生物识别领域得到较快的发展。人脸识别的研究范围广义上来讲大致包括以下五个方面的内容：人脸定位和检测、人脸表征（人脸特征抽取）、人脸鉴别、表情/姿态分析、生理分类五方面内容。

2.人脸识别现状。目前有世界级的人脸检测算法测试项目，它的结论完全可以揭示人脸识别现状。最早是1993年，美国国防部高级研究项目署和美国陆军研究实验室FERET项目组，建立了F

查看全文: http://www.udpwork.com/item/4602.html

[摘 要] 本文通过工业界世界级人脸测试，说明人脸识别发展现状，分别从二维、三维角度，阐述了人脸识别算法现状，并对人脸识别算法发展趋势予以说明。
[关键词] 人脸识别 二维识别算法 三维识别算法

一、引言

1.人脸识别概述。人脸识别由于可接受性好，在生物识别领域得到较快的发展。人脸识别的研究范围广义上来讲大致包括以下五个方面的内容：人脸定位和检测、人脸表征（人脸特征抽取）、人脸鉴别、表情/姿态分析、生理分类五方面内容。
2.人脸识别现状。目前有世界级的人脸检测算法测试项目，它的结论完全可以揭示人脸识别现状。最早是1993年，美国国防部高级研究项目署和美国陆军研究实验室FERET项目组，建立了FERE

查看全文: http://www.udpwork.com/item/3965.html

[摘 要] 本文通过工业界世界级人脸测试，说明人脸识别发展现状，分别从二维、三维角度，阐述了人脸识别算法现状，并对人脸识别算法发展趋势予以说明。

[关键词] 人脸识别 二维识别算法 三维识别算法

 

一、引言

 

1.人脸识别概述。人脸识别由于可接受性好，在生物识别领域得到较快的发展。人脸识别的研究范围广义上来讲大致包括以下五个方面的内容：人脸定位和检测、人脸表征（人脸特征抽取）、人脸鉴别、表情/姿态分析、生理分类五方面内容。

2.人脸识别现状。目前有世界级的人脸检测算法测试项目，它的结论完全可以揭示人脸识别现状。最早是1993年，美国国防部高级研究项目署和美国陆军研究实验室FERET项目组，建立了F

查看全文: http://www.udpwork.com/item/4398.html

[摘 要] 本文通过工业界世界级人脸测试，说明人脸识别发展现状，分别从二维、三维角度，阐述了人脸识别算法现状，并对人脸识别算法发展趋势予以说明。

[关键词] 人脸识别 二维识别算法 三维识别算法

 

一、引言

 

1.人脸识别概述。人脸识别由于可接受性好，在生物识别领域得到较快的发展。人脸识别的研究范围广义上来讲大致包括以下五个方面的内容：人脸定位和检测、人脸表征（人脸特征抽取）、人脸鉴别、表情/姿态分析、生理分类五方面内容。

2.人脸识别现状。目前有世界级的人脸检测算法测试项目，它的结论完全可以揭示人脸识别现状。最早是1993年，美国国防部高级研究项目署和美国陆军研究实验室FERET项目组，建立了F

查看全文: http://www.udpwork.com/item/4431.html

这种题也是一道经典的面试题，主要考察进制转换细想，Coding质量等。

当我们把十进制转成二进制的时候，我们通过辗转相除，取余，逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。

如下是C的详细的实现方法

void m2n(int m, char* mNum, int n, char* nNum)
{
int i = 0;
char c, *p = nNum;

//这是一个考察地方，是否能用最少乘法次数。
while (*mNum != '\0')
i = i*m + *mNum++ - '0';

//辗转取余
while (i) {
*p++ = i % n +

查看全文: http://www.udpwork.com/item/4608.html

这种题也是一道经典的面试题，主要考察进制转换细想，Coding质量等。

当我们把十进制转成二进制的时候，我们通过辗转相除，取余，逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。

如下是C的详细的实现方法

void m2n(int m, char* mNum, int n, char* nNum)
{
int i = 0;
char c, *p = nNum;

//这是一个考察地方，是否能用最少乘法次数。
while (*mNum != '\0')
i = i*m + *mNum++ - '0';

//辗转取余
while (i) {
*p++ = i % n +

查看全文: http://www.udpwork.com/item/3759.html

这种题也是一道经典的面试题，主要考察进制转换细想，Coding质量等。

当我们把十进制转成二进制的时候，我们通过辗转相除，取余，逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。

如下是C的详细的实现方法

void m2n(int m, char* mNum, int n, char* nNum)
{
int i = 0;
char c, *p = nNum;

//这是一个考察地方，是否能用最少乘法次数。
while (*mNum != '\0')
i = i*m + *mNum++ - '0';

//辗转取余
while (i) {
*p++ = i % n +

查看全文: http://www.udpwork.com/item/4438.html

【什么是双层桶】 
事实上，与其说双层桶划分是一种数据结构，不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候，我们可以将其分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的。

【适用范围】
第k大，中位数，不重复或重复的数字

【基本原理及要点】
因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子，分治才是其根本（只是“只分不治”）。

【扩展】
当有时候需要用一个小范围的数据来构造一个大数据，也是可以利用这种思想，相比之下不

查看全文: http://www.udpwork.com/item/4609.html

【什么是双层桶】 
事实上，与其说双层桶划分是一种数据结构，不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候，我们可以将其分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的。
【适用范围】
第k大，中位数，不重复或重复的数字
【基本原理及要点】
因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子，分治才是其根本（只是“只分不治”）。
【扩展】
当有时候需要用一个小范围的数据来构造一个大数据，也是可以利用这种思想，相比之下不同的，只是其

查看全文: http://www.udpwork.com/item/3760.html