存档

‘技术相关’ 分类的存档

Siri背后的技术

2011年10月23日 1,824 条评论 114,814 views

今年10月,Apple发布了iphone 4S with IOS 5,其中最大的亮点就是一个语音搜索软件-Siri。一时间,各种geek,伪geek,码农,非码农都流行起调戏siri,各种调戏视频,音频大量出现。不过,常言道“外行看热闹,内行看门道”,作为一个“伪内行”,或者“欲做内行而不得”的人,根据自己的知识,以及一些搜索工具,尝试了解了一下Siri的“门道”,在这里做个总结,列出siri所可能用到的技术(所谓可能,是因为很多是我猜测,或者没有准确的来源的资料)。

Siri是IOS上的个人助理应用:此软件使用到自然语言处理技术,使用者可以使用自然的对话与手机进行互动,完成搜寻资料、查询天气、设定手机日历、设定闹铃等服务。(来自维基百科

Siri所用到的技术,很多人会回答,人工智能以及云计算,的确,总体来说,是这两样技术,不过,这种概述感觉几乎没有任何意义,和不直接说“计算技术”(注意,不是计算机技术)呢。因此,在本文,我将介绍下我了解Siri可能采用的技术(由于有个人猜测,不一定准确)。

首先,在前端方面,即面向用户,和用户交互(User Interface,UI)的技术,主要是语音识别以及语音合成技术。语音识别技术是把用户的口语转化成文字,其中需要强大的语音知识库,因此需要用到所谓的“云计算”技术。而语音合成则是把返回的文字结果转化成语音输出,这个技术理论上本地就能完成(以前用过科大讯飞的在windows mobile上的本地语音阅读软件,软件很小,但能读的很好,还支持方言),但不知道Siri是否如此,当然,在云端完成也并无不可,在当前无线带宽下,那点语音流量根本不算什么。

其次,后台技术,这些其实才是真正的大角色(当然,普通用户是不会在意的,他们只会觉得前端很炫,哎,这就是做后端的悲哀,小小感叹一下)。这些技术的目的就是处理用户的请求,并返回最匹配的结果,这些请求类型很多,千奇百怪,要处理好并不简单。基本的结构猜测可能是分析用户的输入(已经通过语音转化),根据输入类型,分别采用合适的技术(合适的技术后面)进行处理。这些合适的后台技术包括,①以Google为代表的网页搜索技术;②以Wolfram Alpha为代表的知识搜索技术(或者知识计算技术);③以Wikipedia为代表的知识库(和Wolfram Alpha不同的是,这些知识来自人类的手工编辑)技术(包括其他百科,如电影百科等);④以Yelp为代表的问答以及推荐技术

下面,对上面提到的各种技术进行简要介绍(如有空,后面的博文可能会对某些技术详细的介绍,大家耳熟能详的就免了),强调下,介绍的有些参考来源是维基百科相关词条,下面不一一列出:

阅读全文…

C语言逗号运算符的一些问题

2011年10月16日 1,858 条评论 17,487 views

前段时间,某童鞋碰到一个和逗号运算符相关的诡异问题,当时我也查了下运算符优先级,仔细想了半天才想明白,当时就想把关于逗号运算符的一些东西写一下,但由于比较忙,一直没写,现在补上。

在这里,为了省事,直接把邮件内容附上(假如那位童鞋你看到了,侵犯了你的版权,别生气哈~),我承认我真的很懒。。。

===============================================

对了能解释下这个问题么?

 void main ()
{
    bool test=false;
    int a = 1;

    test == true ? printf("hello\t"), printf("world\n"),a++ :
    printf("Ha\t"), a++, a++;

    printf("%d", a);
}

Test = false 的时候 a = 3;

Test = true 的时候 a = 4;

阅读全文…

Hash和Bloom Filter

这几天的“科研”中涉及到了一个概念,Bloom Filter(有的中文翻译为布隆过滤器,不知道正确否),今天看了下相关的资料,发现这东西和Hash还挺有关系的,在这里一并讲下。

Hash(函数/表)

Hash (中译为哈希,或者散列)函数在计算机领域,尤其是数据快速查找领域,加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面(这些小的数据集叫做哈希值,或者散列值)。Hash table(散列表,也叫哈希表),是根据哈希值(Key value)而直接进行访问的数据结构。也就是说,它通过把哈希值映射到表中一个位置来访问记录,以加快查找的速度。下面是一个典型的hash函数/表示意图:

哈希函数有以下两个特点:

  • 如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。
  • 散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的。但也可能不同,这种情况称为“散列碰撞”(或者“散列冲突”)。上图中,John Smith和Sandra Dee就存在hash冲突。

Hash一个应用就是对数据集分类,比如上图,Hash值为0的表示可能在A集合中,Hash值为2的表示B集合中,依次类推,值为15的表示F集合中。但Hash冲突会在这里会导致严重的问题,对于一个未知的新值,其可能不属于上面任何一个集合,但由于冲突,其Hash值和上面的某一个相同,导致误报(因为事先我们不可能做一个含有无限多项输入的完整的Hash表,也就是原来的Hash函数不可能是完美的)。并且,hash冲突也会导致查找效率低下。

Bloom Filter

Bloom Filter是1970年由Bloom提出的。它实际上是一个很长的二进制向量和一系列随机映射函数(Hash函数)。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。Bloom Filter广泛的应用于各种需要查询的场合中,如Orocle的数据库,Google的BitTable也用了此技术。

如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。

这时候就可以利用哈希表这个数据结构(它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点)。这样一来,我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是Bloom Filter的基本思想。

但这时,哈希冲突会是一个问题:假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m/100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们都在说谎,不过直觉上判断这种事情的概率是比较低的。这种多个Hash组成的数据结构就叫Bloom Filter。

一个Bloom Filter是基于一个m位的位向量(b1,…bm),这些位向量的初始值为0。另外,还有一系列的hash函数(h1,…hk),这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图:

 

上图中,m=18,k=3;插入x是,三个hash函数分别得到蓝线对应的三个值,并将对应的位向量改为1,插入y,z时,类似的,分别将红线,紫线对应的位向量改为1。查找时,当查找x时,三个hash值对应的位向量都为1,因此判断x在此数据集中。y,z也是如此。但是查找w时,w有个hash值对应的位向量为0,因此可以判断不在此集合中。但是,假如w的最后那个hash值比上图中的大1,这是就会认为w在此集合中,而事实上,w可能不在此集合中,因此可能出现误报。显然的,插入数据越多,1的位数越多,误报的概率越大。

Wiki的Bloom Filter词条有关于误报的概率的详细分析:Probability of false positives。从分析可以看出,当k比较大时,误报概率还是比较小的,因此这存储还是很空间有效滴。

Bloom Filter有以下几个特点:

  1. 不存在漏报(False Negative),即某个元素在某个集合中,肯定能报出来。
  2. 可能存在误报(False Positive),即某个元素不在某个集合中,可能也被爆出来。
  3. 确定某个元素是否在某个集合中的代价和总的元素数目无关。

优点:

相比于其它的数据结构,Bloom Filter在空间和时间方面都有巨大的优势。Bloom Filter存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系,方便由硬件并行实现。Bloom Filter不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

缺点:

另外,一般情况下不能从Bloom Filter中删除元素. 我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在Bloom Filter里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

参考资料:

  1. http://en.wikipedia.org/wiki/Hash_function
  2. http://en.wikipedia.org/wiki/Bloom_filter
  3. http://antognini.ch/papers/BloomFilters20080620.pdf

程序的正确性的一些理解–再谈一致性协议

这几天,看论文,有个东西一直困惑我。那就是,如何判断程序是正确的,又如何判断程序的执行是正确的。下面谈谈我个人很直白,很初级的理解

个人以为,简单直白讲,程序正确,就是程序能做程序员预期希望做的事;程序执行正确,就是程序能够在一定输入下,输出程序员(设计者)所希望的输出。

个人以为,对于冯诺依曼机器,程序的输入包括:

整个程序空间的内存初始值以及任何改变程序空间内存的事件。

    对串行程序,上面的输入很好理解,其实就是内存初始值,以及各种外部改变内存的IO事件。一句话,串行程序的输入,其实就是内存输入(包括初始值以及外部改变的值)。并且,前述的输入可以确定地决定程序的输出。
    对串行程序,正确的程序,个人以为,就是能够处理程序员所定义的所有输入并得到期望的输出;程序的正确执行,也就是计算机能够将正确的程序得到期望的输出。其实,这里的正确,是基于程序员和计算机的一种协定,即计算机的指令集及每条指令的功能;正确的程序强调的是,程序元能用这套指令集实现所期望的功能;正确的执行,强调的是,计算机能够按指令定义及规范正确的执行每一条指令。
    而对于并行程序,理论上输入也只有这些,但是,现代的并行机器(多核,多处理机),由于同一份内存有多个备份,这时候,程序内部的内存改变,也是影响程序最终的输出。因为,不同备份的内存会出现不一致的情况,而消除不一致的值传播却不是瞬间的,甚至不是固定时间的。也就是说,不同备份内存值改变(包括因为其他备份传播导致的值更新)的时间也能成为一个伪输入,影响最终的结果。
    这时候,程序员和计算机,除了指令集约定,就需要新的约定,那就是一致性约定。对于计算机(或者对于计算机设计者)来说,希望这个值传播能够随意传播,时间没有限制,顺序也没有限制,因为,这样可以乱序执行,可以不用等待,可以提高计算机性能。而对于程序员,希望这个值传播是瞬间的,每个线程,只需要一改写内存,其他的内存备份,马上得到更新。

程序员所希望的一致性协议,叫做严格一致性,但是,这是这从物理上都是不可实现的,计算机肯定更无法实现。而计算机希望的一致性,则是不靠谱的,因为,那种情况下,程序员无法写出具有确定性输出的程序,因为很可能,在程序执行完毕后,同一地址对应不同的内存备份不一样,这时候,到底取哪个值,是一个问题。对于这种计算机来说,并行程序已经无所谓正确与否了。

阅读全文…

漫谈Google的Native Client(NaCl)技术(二)–技术篇(兼谈LLVM)

上一篇文章介绍Google的Native Client技术的渊源及动力,解释了为什么Google要做这样一个技术。在这篇文章中,将介绍Native Client的一些技术概要。

Native Client简介

Native Client是Google在浏览器领域推出的一个开源技术,它允许在浏览器内编译Web应用程序,并执行原生的编译好的代码。Native Client有以下几个优势(参考Google官方英文介绍):

  • 为Web提供更多的图形,音频以及其他功能:可以直接在web上执行了原生的2D,3D图形渲染程序(对Web游戏很有用),播放音视频,响应鼠标键盘事件,多线程执行代码等等,而这一切,不需要浏览器安装任何插件。
  • 良好的可移植性:一个Web程序,只需要开发一份代码,即可以在所有平台(包括Windows,linux,Mac等)运行。
  • 高安全性:安装不被信任的桌面程序一级浏览器插件,可能带来很高的安全风险(如程序携带木马,病毒)。而Native client使用了双层沙盒(sandbox)设计来保护用户的本地资源。Native Client的架构可以保证web要应用的安全性,并且取得和原声代码相同或相近的性能。
  • 方便从桌面迁移:很多开发厂商之前花了大力气开发桌面程序,随着云计算的到来,越来越多的程序会被移植到互联网上,由于NaCl支持直接执行C/C++/Java等代码,Native Client技术可以简化移植过程,减少移植成本。
  • 高性能:Native Client可以让web应用已接近桌面程序的性能运行,这就为在浏览器内运行性能苛刻的程序提供了基础,如大型3D游戏。

Native Client技术概要

有人说,Native Client技术是抄袭ActiveX的,个人不以为然,ActiveX主要是基于COM的,是操作系统提供一套可重用的接口给web应用,而NaCl则是独立于操作系统的。说实话,感觉这技术更像是抄袭Adobe的Alchemy技术,Achemy技术主要目的是解决Flash的低性能,这和Native Client是接近的,并且,这两种技术都采用了LLVM技术,具体可以看这篇文章http://yjrl.iteye.com/blog/320665

LLVM 是 Low Level Virtual Machine 的简称,这个库提供了与编译器相关的支持,能够进行程序语言的编译期优化、链接优化、在线编译优化、代码生成。简而言之,可以作为多种语言编译器的后端来使用。而基于LLVM ,开源社区开发出了Clang,一个C++ 编写、基于 LLVM、发布于 LLVM BSD 许可证下的 C/C++/Objective C/Objective C++ 编译器,其目标(之一)就是超越 GCC。

Google 的Native Client的关键技术就是PNaCl(Portable Native Client Executables),而PNaCl实现的一个关键就是LLVM。下面是整个PNaCl结构示意图:
PNaCl示意图

在PNaCl中,开发者通过一些前端编译器将C/C++/Fortan源代码用对应的编译器前端编译成LLVM的中间字节码,并且进行优化以及链接(这一整套流程可以在Google提供的SDK中完成)。之后,服务器将链接好的字节码进行分发,在客户端,通过LLVM的后端将字节码翻译成本地的二进制对象文件,并且和本地的相关库链接,最终执行完成(这些功能应该是集成在浏览器中的)。

另外,为了保证安全性,NaCl采用了沙盒技术,具体可以看这篇论文:《Native Client: A Sandbox for Portable, Untrusted x86 Native Code》。

参考:

http://www.lingcc.com/2010/06/02/10955/

http://nativeclient.googlecode.com/svn/data/site/pnacl.pdf

无觅相关文章插件,快速提升流量