算法 -- IT技术博客大学习 -- 共学习共进步！

• 若无云，岂有风——词语语义相似度计算简介

诸多事物都要受到其周边事物的影响，进而改变自身的形态，甚至确立自己的存在——云动，方知风的存在。反映在人的眼中，则是云赋予了风的含义：若无云，岂有风？ 0. 动机武林高手经常从山川之间顿悟，并由山川之形变化出上乘武艺。风云之间的飘渺互动，实则也为实打实的科学、工程实践提供了指引。风是客观存在的，而只有籍由云，我们才能观察到它。在技术领域的日常工作中，诸如此类的例子数不胜数。而在自然语言语义的研究中，先驱者们把这个道理总结成了一条假设——上下文假设[i]： “实体的含义，以及实体之间语法关系的含义和这些实体与其他实体之间组合方式的限制有关。”

• 浅析PageRank算法

这篇文章是我对一些资料的归纳汇总，简单介绍了PageRank的背景、作用、计算方法、变种、Spam及反作弊等内容。为了突出重点我简化了搜索引擎的模型，当然在实际中搜索引擎远没有这么简单，真实算法也一定非常复杂。不过目前几乎所有现代搜索引擎页面权重的计算方法都基于PageRank及其变种。因为我没做过搜索引擎相关的开发，因此本文内容主要是基于现有文献的客观总结，稍加一点我的理解。

• 线性同余发生器的参数如何选取？（以JDK和leveldb的代码为例）

我们平时所用的伪随机数生成器(PRNGs)主要有两种：线性同余发生器(Linear Congruence Generator)和反馈位移寄存器法（Feedback Shift Register）。线性同余发生器是通过这样的递推函数产生随机序列： x=(a*x+c)%M （x,a,c,M都是非负整数）这样产生的随机数序列，一定是有周期的，且小于等于M。在实际应用中，当然希望周期越大越好。

• 相似度计算常用方法综述

引言相似度计算用于衡量对象之间的相似程度，在数据挖掘、自然语言处理中是一个基础性计算。其中的关键技术主要是两个部分，对象的特征表示，特征集合之间的相似关系。在信息检索、网页判重、推荐系统等，都涉及到对象之间或者对象和对象集合的相似性的计算。而针对不同的应用场景，受限于数据规模、时空开销等的限制，相似度计算方法的选择又会有所区别和不同。下面章节会针对不同特点的应用，进行一些常用的相似度计算方法进行介绍。 2向量空间模型向量空间模型（Vector space model）是应用最广泛的一个基础相似度计算模型，在该模型中，每个对象映射为一个特征向量: 作为一个应用广泛的模型，向量空间模型在现有的很多应用中仍然起着至关重要的作用，也是很多扩展方法的基础。

• 同义词反馈机制

1. 介绍由于搜索算法本身的局限性，对于用户的语义、意图等理解不够，而基于用户行为的点击调权，作为对传统搜索算法的补充，在搜索中扮演着重要的作用。尽管用户行为已经被证明在搜索中的效果，但是一直只是停留在query-url层面，或者ngram-url层面[1]，没有深入反馈到检索算法中的基础策略，比如：同义词、紧密度、省略等，这些策略影响了url与query之间的关系。本文以对同义词的反馈为例，提出一个通用的基于用户行为的基础策略反馈框架。由于同义词词典与线上应用算法的限制，检索系统中存在部分质量不好、或者本来质量好但是应用时错误降低了权值的同义词。在同义词召回出来结果后，呈现在用户面前，用户的行为数据可以帮助我们识别同义词的好坏。在计算出同义词的好坏后，就可以直接应用于同义词的退场或者调整应用的权值。

• 让搜索跨越语言的鸿沟——谈跨语言信息检索技术

跨语言信息检索，是信息检索领域中的一个研究课题。近10几年来，由于互联网的飞速发展，这方面的研究受到了学术界的广泛重视。将这项技术应用于搜索，可以帮助我们查找到更多的有用信息，例如外语相关页面、多语言页面以及语言无关的资源（如图片）等等。这些信息可以大大丰富搜索的结果，满足用户多样的需求。在跨语言信息检索的研究中，有一些研究成果已经趋于成熟，达到可以应用的状态。事实上，Yahoo和Google在5，6年前就已经开始提供多语言的搜索服务。毫无疑问，在这方面他们已经走在了世界的前列。目前，百度的各项国际化业务正在如火如荼的开展，对跨语言技术来说，正是用武之地。相信不久的将来，它将会在搜索国际化进程中扮演举足轻重的角色。来，就让我们一探究竟吧。

• 语音识别中声学模型得分计算优化方法

语音是人们沟通交流最直接、最自然的交互方式。自计算机问世以来，人们就一直希望可以通过语音实现人和计算机之间的交互，而语音识别技术，目标就是通过把人类的语音中的词汇内容转换为相应的文本，架起了人机交互的桥梁。对于一个语音识别系统，速度和精度是两个核心指标，直接决定着系统是否可用。其中，识别速度的提升意味着可以降低成本，同时提供更多的语音服务，一直是语音识别技术研究的重点方向。在语音识别系统中，声学模型得分的运算量一般会达到整个系统的40%-70%，因此也是识别速度优化的重点模块。本文就来讲讲如何优化声学模型得分计算。基本概念介绍特征向量：语音数据在识别前首先会被分成多帧数据，一般帧长为25毫秒，帧移为10毫秒。每一帧语音数据经过特征提取之后，会生成一帧特征，称之为一个特征向量或特征矢量，其中n为特征向量的维数。

• 关于PHP中配置文件的定义

关于PHP中配置文件的定义

• 浅析点对点(End-to-End)的场景文字识别

随着智能手机的广泛普及和移动互联网的迅速发展，通过手机等移动终端的摄像头获取、检索和分享资讯已经逐步成为一种生活方式。基于摄像头的(Camera-based)的应用更加强调对拍摄场景的理解。通常，在文字和其他物体并存的场景，用户往往首先更关注场景中的文字信息，因而如何能够正确识别场景中的文字，对用户拍摄意图会有更深入的理解。一般意义上，基于图像的文字识别包括基于扫描文字的光学字符识别(Optical Character Recognition, OCR) 和广泛用于网站注册验证的CAPTCHA (Completely Automated Public Turing Test to Tell Computers and Humans Apart,全自动区分计算机和人类的图灵测试)。

• Diffie-Hellman算法的效率

我之前一直有个误解,以为DH的私钥的长度必须跟公钥一样。今天调试flash的时候发现，它的DH算法用的私钥长度竟然是128位，虽然它采用的同余群的p是1024位的。我然后翻了些资料，看DH算法对私钥的长度有何要求。从Sun JDK的代码来看，对私钥x只有一个要求，1 <= x <= p-2，那么也就是说只要它的长度小于1024就没有问题。

• 几个精彩的数论问题

从同事那里借来了一本单墫教授主编的《初等数论》奥数书，看到很多精彩的问题，在这里做个笔记，与大家一同分享。不少问题和答案都有过重新叙述，个别问题有所改动。问题：找出所有使得 2n - 1 能被 7 整除的正整数 n 。答案：由于 2n 的二进制表达为 1000…00 （n 个 0），因此 2n - 1 的二进制表达为 111…11 （n 个 1）。而 7 的二进制表达是 111 ，要想让它整除 n 个 1 ，显然 n 必须是也只能是 3 的倍数。问题：是否存在 100 个数，使得它们的和等于它们的最小公倍数？答案...

• 有关Cache 2 - 基本结构

周末花了一个下午看了一下《计算机体系结构量化方法》的附录B，是有关Cache原理的介绍。这本书写的还真是好啊，看似一块大砖头，本以为废话很多，其实多数描述很简练，微言大义。例如前些日子写了一个带宽和时延的关系，这本书一句话就写明白了：“时延决定数据第一个接收Bit的时间，带宽决定接收剩余数据的时间”，真实很牛X啊。画了一张小图总结Cache的基本结构。 CPU的处理器地址(我理解就是经过转换后的最终的硬件地址了)被划分为三个部分，Tag，Index，Offset。寻址的时候，首先用Index寻址Cache Set(这个是Cache相关性的产物)。Tag用作Key在Cache Line Set之中匹配Cache Line。Offset用于得到最终对象地址。其他很多概念和Cache Policy就是基于这个简单的数据结构图演化出来的。

• 经典证明：几乎所有有理数都是无理数的无理数次方

一个无理数的无理数次方是否有可能是一个有理数？这是一个非常经典的老问题了。答案是肯定的，证明方法非常巧妙：考虑根号 2 的根号 2 次方。如果这个数是有理数，问题就已经解决了。如果这个数是无理数，那么就有：我们同样会得到一个无理数的无理数次方是有理数的例子。这是一个典型的非构造性证明的例子：我们证明了无理数的无理数次方有可能等于有理数，但却并没有给出一个确凿的例子。毕竟我们也不知道，真实情况究竟是上述推理中的哪一种。那么，真实情况究竟是上述推理中的哪一种呢？

• 趣题：构造多边形使得过边界上某一点的任意直线均能等分面积

这是 2008 年莫斯科数学竞赛中的一个问题。构造一个多边形，使得这个多边形的边界上存在这样的一个点 O ：经过点 O 的任意直线均会把该多边形分成面积相等的两份。这看起来不大可能对吧？但其实构造却并不困难。你能想出来吗？

• Huffman 编码压缩算法

前两天发布那个rsync算法后，想看看数据压缩的算法，知道一个经典的压缩算法Huffman算法。你应该听说过 David Huffman 和他的经典的压缩算法—— Huffman Code，这是一种通过字符出现频率，Priority Queue，和二叉树来进行的一种压缩算法，这种二叉树又叫Huffman二叉树 —— 一种带权重的树。但是网上查了一下，中文社区内好像没有把这个算法说得很清楚的文章，尤其是树的构造，而正好看到一篇国外的文章《A Simple Example of Huffman Code on a String》，其中的例子浅显易懂，相当不错，我就转了过来。注意，我没有对此文完全翻译。

• MySQL数据库InnoDB存储引擎 innodb_buffer_pool_size初始化详解

InnoDB Buffer Pool，可以说是InnoDB系统内部最重要的模块之一。通过系统参数innodb_buffer_pool_size，用户可以设置几G，几十G，乃至上百G的内存空间。那么，InnoDB存储引擎系统是如何管理这么大一片内存空间的呢？

• 趣题：把矩形分割为面积相同但形状各不相同的小矩形

数学谜题站的主持人 Michael Brand 某日收到了来自 R. Nandakumar 的一个谜题：是否有可能把一个矩形剖分成若干个小矩形，使得每个小矩形的形状互不相同，但它们的面积都一样？没有想到，从这个问题出发，加上一些非常机智巧妙的分析与构造，我们能得到越来越多有意思的东西。于是，它就变成了 Using your Head is Permitted 今年 3 月的谜题。看了谜题的答案后，我也被彻底折服，决定把这一系列的思考重述在此，和大家一同分享。为了简便起见，下面的“矩形剖分方案”一律指的是把一个大矩形分割成若干个小矩形的方案。

• 浅谈网页搜索排序中的投票模型

国选举制度，美国的总统选举是一种“赢者通吃”的方式，每个州根据其人口多少，有几十或几百的“州票”，州里的人对总统候选人进行选举，在某个州获得票最多的那个候选人，获得这个州所有的“州票”，然后统计所有候选人的“州票”多少，获得最多“州票”的候选人获胜。如果放在算法领域，可以看出这里的问题在于，为了统计结果R(最适合的总统人选)，找到了一个特征A(每个民众的投票)，而决定结果R的，却不是特征A，而是由特征A推导出来的特征B(州票)，在特征A向特征B的推导过程中，信息丢失了(每个洲的支持百分比不一样)。

• C函数串接的几种手法

经常会有这样的需求，一组处理业务逻辑的并列函数要串行调用，可以有下面的方法将其串接起来。例如我们有函数fa(), fb(), fc() 1.最简单就是顺序调用了 fa(); fb(); fc(); 2.上述调用在需要判断返回值的时候写起来有些冗余，于是可以这样写：假设返回非零表示错误 if (!fa()&&!fb()&&!fc()) …… 3.使用逻辑如下的调用方式 fa() return fb() return fc() 前述有写过一篇Nginx的filter，就是这么组织的。

• 基于综合兴趣度的协同过滤推荐算法

1 概述电子商务推荐系统最大的优点在于它能收集用户的兴趣资料和个人信息，根据用户兴趣偏好主动为用户做出个性化推荐。推荐技术指的是如何找出用户感兴趣的商品并列出推荐清单，在用户信息获取差别不大的情况下，推荐技术成为决定一个推荐系统性能的关键，其中推荐算法是推荐技术的核心[1]。协同过滤技术是实际应用中使用最广泛的推荐技术，包括Amazon.com 在内许多网上书店都在使用协同过滤技术。协同过滤是一种基于用户间关联性的推荐算法，该推荐方法将购买习惯或兴趣相同的用户归类在同一个群体中，同群体内的用户彼此之间可以分享信息，互相推荐商品。应用协同过滤技术的著名的推荐系统包括GroupLens/NetPerceptions[2], Ringo/Firefly[3], Tapestry[4]等。