CWYAlpha

Just another WordPress.com site

Archive for 十一月 2011

Thought this was cool: Linux面试时遇到的问题

leave a comment »

平时用的不多的或者确实本身就有点模糊的,非常感谢面试官的解释,这里记录下:

 

文件权限 4755的涵义 = 文件权限中s/S的意义?

chmod是Linux下设置文件权限的命令,后面的数字表示不同用户或用户组的权限。

一般是三个数字:

第一个数字表示文件所有者的权限

第二个数字表示与文件所有者同属一个用户组的其他用户的权限

第三个数字表示其它用户组的权限

权限分为三种:读(r=4),写(w=2),执行(x=1)。综合起来还有可读可执行(rx=5=4+1)、可读可写(rw=6=4+2)、可读可写可执行(rwx=7=4+2+1)。

所以,chmod 755 设置用户的权限为:

1.文件所有者可读可写可执行

2.与文件所有者同属一个用户组的其他用户可读可执行

3.其它用户组可读可执行

chmod 4755与chmod 755 的区别在于开头多了一位,这个4表示其他用户执行文件时,具有与所有者相当的权限。

 

文章Linux中的文件特殊权限中通过实例很好地解释了这里的4的含义:

先看个实例,查看你的/usr/bin/passwd 与/etc/passwd文件的权限

[root@MyLinux ~]# ls -l /usr/bin/passwd /etc/passwd

rwrr1 root root 1549081913:54/etc/passwd

rwsrxrx 1 root root 2298420070107/usr/bin/passwd

众所周知,/etc/passwd文件存放的各个用户的账号与密码信息,/usr/bin/passwd是执行修改和查看此文件的程序,但从权限上看,/etc/passwd仅有root权限的写(w)权,可是为什么每个用户都可以直接调用/usr/bin/passwd来写/etc/passwd从而达到修改自己的密码呢?注意这里的s代替了x(rwsrxrx 1 root root 2298420070107/usr/bin/passwd) , 这里的s使得其他的用户执行/usr/bin/passwd时具有与owner root相当的权限。

 

这里的4或s是特殊的文件权限,其他s可以用在user或group,还有另一种特殊权限t:

再看个实例,查看你的/tmp目录的权限

[root@MyLinux ~]# ls -dl /tmp
drwxrwxrwt 6 root root 4096 08-22 11:37 /tmp

 tmp目录是所有用户共有的临时文件夹,所有用户都拥有读写权限,这就必然出现一个问题,A用户在/tmp里创建了文件a.file,此时B用户看了不爽,在/tmp里把它给删了(因为拥有读写权限),那肯定是不行的。

 

有t特权的目录下的文件或目录只有owner和root才可以删除和修改,其他的人即使有写权限也不能删除。 

 

如何设置以上特殊权限:
setuid:chmod u+s xxx
setgid: chmod g+s xxx
stick bit : chmod o+t xxx

或者使用八进制方式,在原先的数字前加一个数字,三个权限所代表的进制数与一般权限的方式类似,如下:

suid   guid    stick bit
  1        1          1

所以:
suid的二进制串为:100,换算十进制为:4
guid的二进制串为:010,换算十进制:2
stick bit 二进制串:001,换算十进制:1

于是也可以这样设:
setuid:chmod 4755 xxx
setgid:chmod 2755 xxx
stick bit:chmod 1755 xxx

最后,在一些文件设置了特殊权限后,字母不是小写的s或者t,而是大写的S和T,那代表此文件的特殊权限没有生效,是因为你尚未给它对应用户的x权限.

 

硬链接和软连接的大小?

通过下面的测试,硬链接与源文件是相同的inode节点,指向相同的文件,肯定是相同的大小;软连接可以理解为文件内容中存储了源文件的地址或路径,所以有自己的大小。

[aaa@myvm ~]$ mkdir mytest
[aaa@myvm ~]$ cd mytest
[aaa@myvm mytest]$ echo “AAAAAAAAAAAAAAAAA” >hello
[aaa@myvm mytest]$ ln hello hello2
[aaa@myvm mytest]$ ln -s hello hello3
[aaa@myvm mytest]$ ls -lia
总计 16
5764989 drwxrwxr-x  2 aaa aaa 4096 11-25 16:03 .
5566272 drwx—— 23 aaa aaa 4096 11-25 16:02 ..
5765068 -rw-rw-r–  2 aaa aaa   18 11-25 16:03 hello
5765068 -rw-rw-r–  2 aaa aaa   18 11-25 16:03 hello2
5765116 lrwxrwxrwx  1 aaa aaa    5 11-25 16:03 hello3 -> hello
[aaa@myvm mytest]$ echo “BBBBBBBBBBB” >>hello
[aaa@myvm mytest]$ ls -lia
总计 16
5764989 drwxrwxr-x  2 aaa aaa 4096 11-25 16:03 .
5566272 drwx—— 23 aaa aaa 4096 11-25 16:02 ..
5765068 -rw-rw-r–  2 aaa aaa   30 11-25 16:04 hello
5765068 -rw-rw-r–  2 aaa aaa   30 11-25 16:04 hello2
5765116 lrwxrwxrwx  1 aaa aaa    5 11-25 16:03 hello3 -> hello

 

如何设置当前用户新建文件或目录的默认权限?

umask用来定义新建文件或目录的默认权限,新的目录的权限为777-umask设置的值,新建文件的权限为666-umask设置的值。若要长期修改umask的值,可以把它写进/etc/profile或~/.profile或~/.bash_profile中。

[aaa@myvm mytest]$ umask
0002
[aaa@myvm mytest]$ umask -S
u=rwx,g=rwx,o=rx
[aaa@myvm mytest]$ mkdir aa
[aaa@myvm mytest]$ touch bb
[aaa@myvm mytest]$ ls -la
总计 12
drwxrwxr-x  3 aaa aaa 4096 11-25 16:20 .
drwx—— 23 aaa aaa 4096 11-25 16:20 ..
drwxrwxr-x  2 aaa aaa 4096 11-25 16:20 aa
-rw-rw-r–  1 aaa aaa    0 11-25 16:20 bb
[aaa@myvm mytest]$ umask 022
[aaa@myvm mytest]$ mkdir aa2
[aaa@myvm mytest]$ touch bb2
[aaa@myvm mytest]$ ls -la
总计 16
drwxrwxr-x  4 aaa aaa 4096 11-25 16:29 .
drwx—— 23 aaa aaa 4096 11-25 16:20 ..
drwxrwxr-x  2 aaa aaa 4096 11-25 16:20 aa
drwxr-xr-x  2 aaa aaa 4096 11-25 16:29 aa2
-rw-rw-r–  1 aaa aaa    0 11-25 16:20 bb
-rw-r–r–  1 aaa aaa    0 11-25 16:29 bb2

find . -name “filename” 中的filename为啥必须加引号?但是ls中不需要?

find [-H] [-L] [-P] [path…] [expression]

ls [OPTION]… [FILE]…

 

因为这里的”filename”其实是表达式中的一个pattern,所以必须要加“”来组织shell的解析。 例如find . -name “aa*” -exec rm {}。

 

如何快速地将远程机器上的共享目录下的所有文件拷贝到本地供只读使用?

如果不拷贝,简单地mount到本地目录。但是这里是要求拷贝到本地,所以这里可以使用softlink来将对文件的拷贝时间变为固定值。具体可以使用cp的-s参数。

 

Linux中文件路劲可以用空格吗?

windows中用双引号就可以了,linux中用\加空格来表示。

mkdir my\ \ folder  (中间有2个空格)

cd my\ \ folder/

kill -9中的-9啥意思?

强行kill。

 

 完! 

 

作者: iTech 发表于 2011-11-28 11:18 原文链接

评论: 0 查看评论 发表评论


最新新闻:
· eBay将再次提请美国国会降低网络营业税(2011-11-30 22:24)
· Google地图伸入室内(2011-11-30 22:06)
· 贪婪的股东和1000亿美元的估值可能会伤害Facebook(2011-11-30 22:04)
· 新浪微博推出“身份信息注册”打击恶毒人身攻击(2011-11-30 21:42)
· 乔布斯一生中不为人知的片段(2011-11-30 21:39)

编辑推荐:一个月掌握VC++2010?

网站导航:博客园首页  我的园子  新闻  闪存  博问  知识库

from 博客园-iTech's Blog: http://www.cnblogs.com/itech/archive/2011/11/28/2263088.html

Advertisements

Written by cwyalpha

十一月 30, 2011 at 3:08 下午

发表在 Uncategorized

Thought this was cool: 新浪微博不是Twitter

leave a comment »

Twitter是互联网短信,新浪微博以微博客Twitter式弱关系切入,正在转型SNS。转型的挑战在于:1.如何融合弱关系和强关系?2.如何用弱关系倒逼中国社会的强关系和潜关系?3.找到新浪自己的核心竞争力。4.如何与竞争对手差异化定位?

国内有一些Twitter的拥趸,认为微博抄Twitter都抄不到点子上

  • “Twitter 是四两拨千斤的艺术。他不动博客 ,不动媒体,不动图片社区,甚至不动社交网络。他绕开了几乎所有现存网络巨头的 Stronghold 。
  • “帮助 Twitter 绕开这些的,是短链接。网络上,引用和传播总是受欢迎的。而 Twitter 的大多数竞争者则不同:他们更热衷于富媒体。(就这一点,大把的对手出局了。)
  • “Twitter 就是在长期竞争中慢慢脱颖而出的。他们的眼光,对新时代的理解,甚至到细小但重要的规则,都经过了时间考验。
  • 新浪微博不是个经得起推敲的产品。开发时间很短,把握好大方向已经不容易,剩下的只能拷贝,组装和拼凑。所以,对产品追问的深些,就会发现他既微又薄。”

在“Facebook、Twitter:未来的王者?”中,珍妮特·卡尔森说Twitter是“互联网上的短信服务” (“SMS of the internet”),“Twitter的差异化在于它让全世界通过不到140字来进行实时通讯。”

她对Twitter的这个定位或定义很准确,即:Twitter = 文字化的miniblog + 集成简化的RSS订阅 + @ 和转发 + 展示订阅和被订阅关系。

新浪微博不是Twitter

在我看来,这是Twitter被SMS捆住了手脚!放弃了富媒体或融媒体的广阔世界。当然也是因为Twitter是小团队创业,没有资源,只能单点突破。从这点上看,如果新浪微博照搬Twitter,无异于划地为牢。

以图片为例,一图胜过千言万语,第一时间看到缩小图、而不是点击短链接再看到图,更加直指人心。

Slashdot介绍说:国外媒体也开始讨论微博的优点,认为新浪微博不是简单的Facebook和Twitter杂交,而是胜过两者,理由是:嵌入多媒体和照片,用户可以直接在微博上播放和打开,无需跳转到视频网站;奖励系统;广场;线上经济。

他们说微博 = Twitter + 评论 + 富媒体。

新浪微博不是Twitter

这就是我说的【微博融媒体】:在一条微博里直接展示图片、播放视频/声音,是新浪微博的关键创新。这使得微博“吞噬”了图片、视频/声音,这种融合也大大提高了微博的“镜像”能力、表现力和传播速度,微博成为新的融合媒介的核心。(关于传播速度,有条件的研究者可以分析对比一下,在微博和Twitter上,大事件的爆发时间和衰减时间。我的直觉是微博上大事件爆发快、也衰减快。)

新浪微博不是Twitter

也许这种“融合媒体”设计并不是有意识的创新,而是新浪微博团队在新浪边界条件下的自然选择。比如新浪博客的经验会告诉他们:要有评论,有评论才能抢沙发;图片博客最受欢迎…

当然新浪微博采用了Twitter的Follow机制,即单向关注的弱关系。这样一张弱关系网构成人际传播媒体,已经爆发了巨大力量–“围观改变中国”。

新浪微博不是Twitter

这张弱关系网建立了竞争壁垒,其他门户网站应该发现以前可以“博客搬家”,现在“微博搬家”不灵了。因为关系已经被固化在新浪微博,以前博客的散落在外面的RSS订阅关系和浏览器收藏关系、已经被聚合在新浪微博的弱关系网中。

微博的未来是什么?转型SNS?!

微博转型Weibook?

①强关系,实时私信聊天+个人中心;②微应用中枢,相册/游戏/微群/其他应用+统一消息机制;③互动融媒体,微博中微投票,拓展微电商/微游戏;④微信用,“认证用户”搜索过滤…⑤微电商中枢,微币+微柜台/微团购/微秒杀;⑥微游戏,游戏碎片化;⑦开放平台

 

新浪微博不是Twitter

新浪微博转型SNS的挑战:

1.如何融合弱关系和强关系?能否构建无关系->弱关系->强关系的和谐并存格局?我注意到许多QQ用户说新浪微博的好处是“想说就说,不用担心熟人看见”。

2.如何用弱关系倒逼中国社会的强关系和潜关系?能否最大程度消除潜规则运行的强关系?能否把潜关系变成阳光下的关系?

3.找到新浪自己的核心竞争力,想清楚什么该新浪做、什么该由产业链合作完成。这点上,的确应该学习Twitter和Facebook。

4.如何与竞争对手差异化定位?新浪IM对抗腾讯QQ?新浪微群对抗百度贴吧?新浪微电商对抗社会化的淘宝?

来源:郑治投稿,原文链接

 


© 推荐 for 互联网的那点事, 2011. |
Permalink |
No comment |
Add to
del.icio.us

Post tags: ,

你可能也喜欢:


微博到底是该“增肥”还是“减肥” ? (@tech2ipo)


我的新浪微博被删了 (@sigma)


【连载一】twitter的新浪微博式创新系列之注册篇


“新浪微博”试用感受与猜想


新浪微博遭遇微博拍照谣言袭击 新浪一夜蒸发10亿美元

无觅

Feed enhanced by Better Feed from Ozh

from 互联网的那点事: http://www.alibuybuy.com/posts/67930.html

Written by cwyalpha

十一月 30, 2011 at 2:54 下午

发表在 Uncategorized

Thought this was cool: 爬网站的一些经验

leave a comment »

以前曾经做过一个收集各大OJ近期比赛的小工具,挂在NKOJ上:http://acm.nankai.edu.cn/recent_contests.php,添加过一些小创新,今年也被杭电OJ抄走了,不过还没有我的版本功能完善,主要原因还是因为我做的早一些,遇到过一些BUG,思考过怎么去绕过他们。之后我又因为各种原因爬过几个网站,稍微有一点经验,简单总结一下。
PHP是我最熟悉的脚本语言,我爬网站基本就靠他了。这里主要借助了几个工具,挨个介绍一下:
1,cURL库——这是用来获取网页的函数库,他支持了丰富的特性,包括模拟浏览器,post数据,cookie,网页转向,甚至代理服务器等。在大多数情况下,利用他可以轻松模拟浏览器做的事情,获得想要的网页。唯一美中不足的是,cURL不可以将网页中的a标签的相对链接转换成绝对链接。所以我有时候会使用linux的wget来抓网页。只不过混合语言写起来会不太爽。
2,simplehtmldom——这是用来解析HTML DOM树的库。他用起来很爽,和jQuery的接口很相似。利用他可以轻松找到想要的DOM节点,获取属性或者内容。这样就可以根据网页内容定位到自己想要的部分。
3,preg_match_all——用正则表达式取出想要的内容。他是php带的一个函数,因为simplehtmldom只能找到想要的节点,但是节点的内容并不一定完全都是想要的,所以还需要用这个函数再进一步选取想要的部分。其实很多网站只用他也就足够了,但是以过去的经验来看,用他和simplehtmldom配合使用会更稳定,当网页有一些小变化的时候,simplehtmldom一般能更稳定的找到想要的部分,而preg_match_all通常更容易因为网页的变动而失败,所以定位到想要的节点后再使用就会精确不少。
现在需要爬网站的例子随处可见,新兴起来的一淘网等比价网站就是天天去各大电子商务网站爬,团购聚合网也越来越多,百度谷歌都掺和进来了。个人认为,随着信息量的增大,以后爬网站、提取聚合信息的用处会更广泛,这也可以促进很多数据挖掘工作。

from Dora Blog: http://diaorui.net/?p=252

Written by cwyalpha

十一月 30, 2011 at 2:54 下午

发表在 Uncategorized

Thought this was cool: 基于主特征空间相似度计算的切分算法及切分框架

leave a comment »

摘要: 本文从切分的需求、作用、难点等方面谈起,介绍分析了目前主流的各种切分方法以及其优缺点,并介绍了一个新型的无监督切分方法,并在此基础上对切分在工程需求上进行了相应的分析和讨论,在最后在此算法基础上给出一个融合各种优点的切分框架。

关键词: 中文分词, Query Segmentation,无监督

技术领域: 自然语言处理

我们为什么要切分?

说到切分(segmentation),大多数人最容易想到的就是中文分词。作为没有天然空格区分的语言,切词可以帮助计算机去索引文章,从而便于信息检索等方面。该部分主要用到了分词的一个方面:降低搜索引擎的性能消耗。我们常用的汉字有5000多个,常用词组是几十万个。在倒排索引中,如果用每个字做索引的话,那么会造成每个字对应的拉链非常长。所以我们一般会用词组来代替单个汉字建立索引。除此,切词更重要的一个功能是帮助计算机理解文字,在这个层次上,切词是不分语言的,任何一个语言,涉及到计算机去“理解”的时候,首先要做的,就是先去切分并在一定程度上消除歧义。这是因为,我们知道计算机本身擅长做的工作就是匹配计算。假设我们可以把每个字词都指向一个语义,当输入一个句子的时候,每个字对应语义的累加要弱于词组语义的累加(因为单独用字语义累加的时候,有个潜在的假设是字和字之间是独立的),现在引入切分目的就是勾勒出字与字之间的关系,从而让计算机更好的理解。

切分的难点在哪里?

简单的讲,评价切分效果可以从三个层次来判定:切分边界,切分片段,整个句子切分结果是否正确。切分边界是指:相邻的token(在中文切分中token可以认为是汉字,在英文中可以认为是单词)之间是否应该被切开;句子级别是指,整个句子的切分结果是不是完全准确。切分片段是介于二者之间一种评估策略: 1. 切分结果片段中是否召回了需要切出的片段(recall); 2. 切分的结果中是否有错误的切分结果(precision)。下面我们从切分算法两个重要的考量标准来阐述切分的难点,即新词识别和歧义性的处理。

新词:
切分算法在召回方向上的难题主要为歧义现象和新词的出现。如果一个切分算法无法识别新词从而导致其未召回,最后会影响计算机对该切分句子的理解。前面我们有讲,字到词的过程可以让计算机“假装”理解这个词的意思。比如最近的一个人名新词“位菊月”,如果被切分算法切散后,计算机很难理解这个片段的含义,从而导致在诸如机器翻译等应用中无法准确进行处理。

歧义性:
切分算法要求解决切分片段歧义性,切分结果合理。汉字作为表示中文信息的载体,假设每个字/词表示的信息有个上限,假设每种语言总体的信息量接近,由于常用字数有限,这些汉字之间就要有较多的组合形式来成词并表达不同的语义。如果一个汉字可以同时作为2个词的部分,当这2个词按序出现时,就潜在包含了歧义。目前歧义主要分为2种:交叉型歧义,即相邻歧义片段之间有若干token重复,比如“长春市长春药店”,“长春市”与“市长”“长春”与“春药”都是交叉型歧义片段。该歧义现象存在于任何语言的切分过程,比如针对英文,“new york times square”中的”new york times” 和”times square”;还有一种歧义为覆盖型歧义,即token序列在不同语义下需要拆分开或合并在一起,比如“他马上就来”和“他从马上下来”,对后者来讲,切分为“马上”时则导致“从马背上”的意思被“立刻的”意思所覆盖。

除此,切分算法在应用中还要具备不错的性能,在引入统计学习算法时,还要考虑人力在标注语料上面的成本。随着时间的发展,语言也会进行相应的变化,只是在不同的领域会按照不同的速度演变着。因此,切分算法同样需要与时俱进的优化。比如添加更多的词进入词典,更新重建语言模型(Language Model), 对于某些基于判别式(Discriminative model)切分的方法,比如CRFs,需要不定期更新人工标注语料来使得切分算法适应处理当前语料等等。

切分算法作为一个基础的研究方向一直是很多科研人员努力奋斗方向,并产生出大量优秀的算法。在下面的章节中,我们简单的介绍一些主流的、在工程中有着一定应用的切分方法。

切分的主流方法简介

在介绍我们的切分方法之前,我们先从2个方面来简单介绍现有主流切分算法:即基于规则的切分方法和一些统计切分模型。

1.基于规则的切分方法。

基于规则的的切分方法主要表现为基于词典匹配,如:正向最大匹配(Forward Maximum Matching, FMM),逆向最大匹配,最少切分(使每一句中切出的词数最小)等等。

以正向最大匹配为例,其基本思想是:对于待处理文本,从左到右尽量匹配词典中的最长词,匹配到的词即该处理文本的一个切分片段。假设词典中有{百度,百度公司,中文,切分,算法}5个词,则句子“百度公司的中文分词算法”的正确切分结果为“百度公司|的|中文|分词|算法”。

基于规则匹配的切分算法,缺点主要有2点:(1).无法很好的解决切分歧义问题。上述提到的三种方法都是从不同的角度尝试去解决歧义问题,但是它们对于歧义消除的效果不显著,特别当词典词增多的时候,词与词之间交叉现象加剧,该方法的歧义处理能力就会相应的减弱。(2).该方法无法识别新词。在该方法下,线下挖掘大量的新词加入词典的收益和整体效果并非线性关系,词典膨胀的同时,切分的歧义现象会更加严重。

由于该方法简单快捷,因此针对上述缺点也有一些工作是将统计方法用在FMM上,该类方法主要运用贝叶斯模型(Naïve Bayes)、互信息(Mutual Information)以及t-test chi-2等检验手段对有切分歧义的相邻片段进行消岐。这方面可以参考“基于无指导学习策略的无词表条件下的汉语自动分词”等文献。

2.统计切分模型

统计切分算法主要利用语言模型、标注数据等资源,根据切分假设建立模型并利用其对应的资源进行模型参数优化,借助模型代替规则完成切分。

2.1
基于语言模型、Markov
链的切分方法

对于一个待处理的句子其每个处理的token(t_i,在中文分词中可以认为是汉字,在英文中可以认为是单词等)构成一个观察序列,各种可能的切分片段即为隐含的状态。该方法的目的即为观察序列找一个最有可能发生的隐含状态序列其中每个状态status(s_i)即为词典词。整个切分过程即为了寻找一个可行的切分结果利用markov假设,使得达到maximum likelihood:



如果有了词典词的各种概率分布(可以通过利用语言模型进行极大似然估计,利用EM算法进行参数优化等得到),根据viterbi解码算法,很容易就得到了切分结果。随着语言模型的广泛应用,以及各种learning算法的发展,该方法也具有广泛的应用场景。深入阅读的可以参考以下两篇文章:《Self-supervised Chinese word segmentation》,《unsupervised query segmentation using generative language models and wikipedia》。

现在说说该方法的不足:1. 在计算序列的概率时,我们依据markov假设,即:当前状态仅仅和前面一个状态相关。而在我们实际应用中,当前的状态可以和前面状态有关系,也可以和前面的前面状态有关系,也可以不和前面的状态有关系等等(这里面的是否有关系是在一定阀值条件下说的)。2. 在估算词典词之间的概率分布时,EM作为一个常用的算法也有自身的不足。

2.2.
条件随机场模型(Conditional Random Fields )

CRFs是一个无向图模型,它的目标是寻在在条件概率最大情况下的一种组合[Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data.]。在NLP技术领域中主要用于文本标注,应用场景主要为:分词(标注字的词位信息,由字构词),词性标注(Pos-Tagging,标注分词的词性,例如:名词,动词,助词),命名实体识别(Named Entities Recognition,识别人名,地名,机构名,商品名等具有一定内在规律的实体名词)。

它把切分的过程看作一个标注的过程,即对一个观察序列中的token进行标注,比如标记为4中状态:词首(Begin), 词中间部分(Middle),词尾(End)和单独存在(Single)。对于一个输入序列其标注序列为在输入序列下的条件概率:



其中Z为归一化函数,它等于所有可行标注序列条件概率的总和。为特征函数(feature function),是其对应的权重。该特征函数用来在观察序列T下,当前计算阶段i下状态序列的情况。我们的目标是找到一个标注序列,使得上式达到最大值:



如果我们有了可以用于计算的各种概率分布,利用viterbi算法,不难获得该序列的标注情况。再根据每个token的标注状态(BMES)来进行切分。具体可以阅读这篇文章《Chinese Segmentation and New Word Detection using Conditional Random Fields》。

CRFs模型中文分词在一些封闭测试的语料中达到了非常可观的准确率,在工业应用中,效果也是可圈可点。同时在中文分词中,CRF分词是基于汉字的构词法进行,它可以有效地识别具有结构特征的新词,而不在乎这个“新词”是否在互联网中出现过。CRF在分词里面有2个明显的不足:性能和代价。性能是在解码阶段需要耗费大量的计算量,代价是指,作为有监督学习,CRF模型的训练需要大量的标注语料,同时,互联网语料急剧增长和变化,CRF模型的更新也需要较多的人力。在后续我们会讨论如何有效地将CRF模型融入工业化切分应用中以及如何引入语言模型来更新统计切分模型。

除此,CRF模型在中文分词上取得不错的成绩,能否直接移植到其它语言呢?语言特征和training语料间有怎样的关系时整个切分算法才能出色的运行?有兴趣的读者可以思考这个问题。

在该节中,我们主要介绍了各种切分模型的原理,分析了他们的应用场景。在下面一节中,我们介绍一种新型的算法,它利用语言模型进行切分,它的假设是:如果两个词应该切分在一起,那么这两个词,在一定的条件下分布是接近的。

基于统计语言模型的无监督切分

在本节中,我们会介绍一种新型的无监督切分算法(Query Segmentation Based on Eigenspace Similarity),相对于基于HMM的方法来讲,他充分考虑了切分片段整体信息,并且在后面的章节中,我们会介绍该方法有很好的拓展性,从各个角度来讲都符合我们在最初提出的切分难点的解决。

在介绍具体算法之前,我们说说该算法的假设。对于A B两个token,他们可以切分在一起就说明他俩在一定条件下紧挨着出现,换句话说,在一定条件下(即整个待切分句子的上下文环境),他俩的数据分布是比较相似的,如果我们可以获得其数据分布(vector),再计算这两个vector之间的相似度,就可以决定这两个token是否应该合并在一起。这个方法听起来似乎和互信息(Mutual Information)有点像,但是互信息并没有考虑我们前面说的一定条件下,不过也有一些工作针对MI这点引入了cosine of point-wise mutual information。即便考虑了上下文信息,还有个问题比较棘手:判断两个token是否应该合并在一起的阀值应该是多少?在有些工作中[Generating query substitutions],这个阀值被经验地设置为一个定值,事实上,这样做可能是不大合理的。在各种各种下,我们构建了这样一个切分的上下文环境,并且巧妙地把统计特征投影到其主特征空间(principal eigenspace,在线性代数中,特征空间是由一个矩阵的所有特征向量张成的空间,主特征空间是有该矩阵的主要特征向量张成的空间。相比较特征空间,主特征空间可以覆盖特征空间大部分信息,并且可以辅助相关应用进行有效的降维、除噪和数据变换等),计算相似度,配合主特征空间的维度进行切分。

1.算法流程:

我们以一个例子来讲述该算法是如何工作的,有兴趣的读者可以阅读该文[Query Segmentation Based on Eigenspace Similarity]。(点击查看大图)

2.算法分析:

该算法一个核心的要点为主特征空间维度k的确定。换个角度讲,对于给定一个待处理串,如果事先知道切分的片段数,利用一些简单的统计策略如MI已经可以较好的做切分。

关于参数k的确定,论文中给出一种简单的判断方法。这方面也有相关的一些研究方法,有兴趣可以深入阅读谱聚类(spectral clustering)以及Principal Component Analysis, Springer (2002)一书中的第六章” Choosing a Subset of Principal Components or Variables”。

该切分算法根据数据分布入手,由切分片段特征展开假设,通过基本token在一定相关语义下统计分布而进行切分。相对基于EM/HMM等模型的无监督切分算法,该方法一个明显的优点是充分考虑了整个切分片段的信息,而不是相邻token之间的统计量;同时,该方法通过空间变换等手段,有效的进行数据除燥等策略,从而是数据分布更趋于真实情况。

同CRF等有监督学习相比,该方法的输入为ngram语言模型,不需人工标注数据 ,同时本方法可以识别新词,这在互联网应用中极具优势。同时针对不同语言不通领域,我们只要提供足够可靠的语言模型就可以在很大程度上解决他们的切分需求。

当然本方法(or无监督切分方法)在切分的准确率上和基于有监督的模型相比仍有差距,我们在下节会阐述这个问题,并给出一个我们勾画的切分体系。

如何打造一个好的切分框架?

简单的说:1. 词典是需要的,并且有有效的手段源源不断的更新词典词,在不同的应用需求下,这些词典词在切分体系中的位置和作用可能不一样。2. 强大的语言模型是需要的。原因是:如果A B两个token应该切分在一起,那么“AB”这个组合就应该在互联网中大量出现。3. 人工标注的数据也是必要的,这是因为,切分作为人们对句子一个主观的认识,这个和数据在语料中的分布不是完全一致的。

先说说有监督和无监督两种方法的差异。如果无监督的效果可以赶得上有监督的方法,那么有监督方法就可以彻底和分词说拜拜了。那么无监督方法切分效果瓶颈来源于哪里呢?这里用一个例子来解释。很多用户在在遇到不认识的字时候,会通过如下手段去搜索学习,query“**头上加一??”,如“旦头上加一横是什么字”等等,由于无监督学习是根据数据的分布出发,在这样的case中“头上加一”或者“加一”就会被切分出来。事实上,这种切分方式和人们的认识是不一样的。这是一个极端的例子,数据分布和人们主观认识不一致有很多因素。

我们在使用有监督的方法解决问题是,主要着眼点在考虑local consistency,也就是说,所有的工作是基于已经标注的数据进行开展,标注语料决定了最后的算法效果;而无监督方法更多的是从全局的数据分布(global consistency)来看,如果某个需求下数据具备全局的结构特征,则无监督模型也可以很好的对其进行解决。

那么在这里我们就有个设想,引入部分的标注数据来改变数据的原始分布,最后优化切分效果。半监督学习(semi-supervised learning)的引入即可以在很大程度上提升无监督切分的效果。我们之所以引入介绍无监督切分算法,是因为该方法可以和现有的半监督学习算法相结合。

结合上面所说的,描述一下我认为一个好的切分体系应该是什么样子。

1.我们需要词典。词典的来源有很多,比如专名挖掘(NE mining), 词组挖掘(Phrase Extraction)。同时我们还要有个模块对这些资源进行不同程度的加工,最后提供一个词典给正向最大匹配(FMM)切分使用。我们会在后续的章节中,介绍新词挖掘,资源抽取等技术。

2.我们之所以使用FMM是因为本算法可以完美地处理很多待处理语句。只有在FMM无法解决的时候,我们才会引入统计切分算法。这个时候,我们需要一个trigger来负责这件事,就如上图中的Ambiguity Detection模块。这个模块可以把一个句子分成2种形式,可以通过FMM处理的简单句,需要统计模型处理的复杂句。对于复杂句采用统计切分,最后把二者结果merge起来。

3.统计模型的方法有很多,在这里自然要推荐文中所述的模型。该模块输入为ngram语言模型。统计切分算法的优化过程是引入标注数据来改变ngram中token之间的分布。在这里,我们推荐使用metric learning的方法,直接对frequencies matrix进行改动。切分的bad case也可以通过标注数据来修复。

在这种体系下,我们很好地解决了切分过程中存在的一致性、歧义处理、新词、可持续提升、可扩展性、性能等因素。

切分作为自然语言处理中一个最底层的工作,有大量的学者在这方面进行不断的研究。在中文分词方面,清华大学的自然语言处理同学收集了这方面的论文:http://nlp.csai.tsinghua.edu.cn/~zkx/cws/bib.html,有兴趣的读者可以根据需要进行相应的扩展阅读。

百度自然语言处理在中文分词上做了相当多的工作,在后续,我们会从切词中遇到的技术和资源进行展开讨论。

by Super.Jiju


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0

from IT牛人博客聚合网站: http://www.udpwork.com/item/6430.html

Written by cwyalpha

十一月 30, 2011 at 2:53 下午

发表在 Uncategorized

Thought this was cool: 【Chrome】最快的Google搜索设置

leave a comment »

最近在v2ex上看到篇帖子

估计很多人也对 google.com/url?sa=t& 这种搜索结果页面链接强制跳转烦死了。

我觉得用userscript都是治标不治本的,因为我以前也写过。Google改版这个脚本就废了。而且Chrome每一个Extension开一个进程有点划不来。

Google Instant也是一个垃圾设计,有的时候输入了一个空格才发现想点击下面一个搜索结果,结果backspace回去就找不到了。烦啊。

所以搞了个办法治一治Google,Chrome专用!

  1. 修改Chrome的默认搜索引擎为:。http://64.233.183.132/search?gbv=1&tbo=1&as_qdr=all&hl=en&num=50&q=%s
  2. 选项 – 高级 – 内容设置 (chrome://settings/content) 里禁用掉 64.233.183.132 这个域名的javascript运行权限。
  3. ???
  4. Profit!

我来解释下位什么那个搜索URL很好用。

64.233.183.132 这个IP速度基本是最快的了。内地电信到美国西岸180ms
/search
?gbv=1&tbo=1 开启左边工具栏
&as_qdr=all 关闭Google Instant,使得下一个每页50条参数才能生效。[感谢]((http://cinderwick.ca/blog/2010/11/disable-google-instant-and-show-more-than-10-results-without-saving-cookies/))
&num=50 每页50条结果
&hl=en 强制英文界面
&q=%s

把最后的 &q=%s 替换成 &query=%s 就可以任意搜索敏感词了。但是SERP内容有敏感词还是会RST。

最后祝愿Google早日把核心业务搜索做烂做倒闭。

from hUrR DuRr: http://blog.est.im/archives/4343

Written by cwyalpha

十一月 29, 2011 at 7:39 上午

发表在 Uncategorized

Thought this was cool: python中dict的插入复杂度估算和排重复杂度估算

leave a comment »

    在做分词核心词典数据结构分析的时候需要,就先写一篇吧。

    具体可以参考python源码解析读书笔记(一)——内置对象,这里面有说:

7.dict对象的索引方案
dict对象的索引方案使用的是哈希表,而且是开放地址法的哈希表。当装载率达到一定规模后,会新申请一块内存,将有效数据复制过去。最小的表空间为8个对象,当装载率超过2/3时,会扩大规模到当前active的4倍(超过50000个对象为2倍)。目前为止,在对象被删除后,其表空间并不释放。因此曾经增长的非常大的dict对象,可以定期复制以回收空间。

    最初的表项空间为6个以内,满了之后,会自动扩张到24个,有效16个。从大致来说,如果要放下N个表项,大概就要扩张T次,他们满足以下关系。
A0*(8/3)^(T-1)<N<A0*(8/3)^T
    而每次扩张,就要进行全表项复制,因此复杂度大约是O(N)量级。当扩张到放下N个表项时,就需要进行的复制的总数是:
sum(i, 0, T-1){A0*(8/3)^i}
    这是一个典型的等比数列求和问题,我们知道问题的答案应当是:
A0*3*((8/3)^T-1)/5=A0*(3/5)*(8/3)^T-(3/5)*A0
    因此,(3/5)(N-A0)<O<(3/5)*((8/3)*N-A0)。如果只考虑数量级的话,插入的复杂度量级为O(n),即哈希表的平均插入复杂度为n级。
    也许有人奇怪,哈希表的插入复杂度为1级阿,怎么得到n级的结论的?看上面,都说是放下N个表项时的总复杂度了。
    我们可以和红黑树对比一下,红黑树的平均插入复杂度为logn级,平均查找复杂度为logn级。哈希表的平均插入复杂度为1级,查找复杂度为1级。但是红黑树在一点上比hash优秀——他的插入时间基本稳定,hash table的插入时间有可能会暴长。
    于是,当我们有N个元素,需要进行排重的时候,我们可以set化。假定set和dict基于一样原理运作,我们的时间复杂度为O(n+m)级,m为排重后元素个数。其实按照最差情况来说,也可以认为是O(n)级。

from shell's home: http://shell909090.com/blog/2011/11/python%e4%b8%addict%e7%9a%84%e6%8f%92%e5%85%a5%e5%a4%8d%e6%9d%82%e5%ba%a6%e4%bc%b0%e7%ae%97%e5%92%8c%e6%8e%92%e9%87%8d%e5%a4%8d%e6%9d%82%e5%ba%a6%e4%bc%b0%e7%ae%97/

Written by cwyalpha

十一月 29, 2011 at 7:39 上午

发表在 Uncategorized

Thought this was cool: 中国移动无线试题【有详细答案】zz

leave a comment »

发信人: daocaoren(daocaoren), 信区: JobForum
标  题: 中国移动无线试题【有详细答案】zz
发信站: 饮水思源 (2011年11月29日12:36:16 星期二)

中国移动无线试题【有详细答案】zz


无线试题
一、 填空
1) 目前,GSM频段是从_____ 到_______ (手机发射),_______到______(手机接收),
相对应的频点号从   到    。
2) DCS1800频段是从_______到_______(手机发射),______到______(手机接收),相
对应的频点号从    到    。
3) 0dB的含义是 __________?1W= ______dBm。
4) GSM系统使用的多址方式为 _______ 。
答案:1.890MHZ、915MHZ、935MHZ、960MHZ、1、124。
      2.1710MHZ、1785MHZ、1805MHZ、1880MHZ、512、885。
      3.无增益、30。bbs.hiall.com.cn; ^)
      4.FDMA+TDMA。
二、 选择
1) 处于空闲模式下的手机所需的大量网络信息来自()信道。
A、BCCH
B、CBCH
C、RACH
D、SDCCH
答案:(A)
2) 关于Um接口说法错误的是:
A、又称空中接口,用于手机与GSM系统固定部分之间的互通
B、是手机与BTS间的通信接口
C、其物理连接通过PCM链路实现
D、传递的信息包括无线资源管理、移动性管理和接续管理
答案:(C)
3) 未使用扩展范围(Extended Range)的GSM小区的最大半径为() 。
A、35km
B、50km
C、70km
D、129km
答案:(A)
4) 关于位置区的说法错误的是:
A、一个位置区可以属于多个BSC
B、一个位置区可以属于几个MSC
C、一个位置区只能由一个MSC处理
D、一个位置区有一个特定的识别码
答案:(B)
5) 使用combiner的原因是:
A、最多可以有4个Site使用同一PCM链路
B、多个TRXs可以使用同一天线系统
C、手机可以同进收听2个基站的信息 
D、发射和传送均由同一天线完成
答案:(B)
6) 手机使用DTX的好处是()。
A、延长电池寿命
B、增加接收信号强度
C、降低比特误码率! 
D、提高通话质量
答案:(A)
7) 当SACCH测量报告伴随TCH信道时,它的测量周期为 () 。
A、480毫秒
B、1秒
C、2048毫秒
D、1分钟
答案:(A)
8) 在手机通话过程中,用来传递切换命令消息的逻辑信道是 ()。
A、SACCH
B、SDCCH
C、SCH
D、FACCH
答案:(D)
9) 全速率业务信道和半速率业务信道传送数据最快速度为 ()和  () 。
A、13kbit/s、6.5 kbit/s
B、11.2kbit/s、5.6 kbit/s
C、9.6kbit/s、4.8 kbit/s
D、4.8kbit/s、2.4 kbit/s
答案:(C)
10) 发生Intra-cell切换的可能原因为 ()  
A、服务小区信号强度突然降低
B、服务小区信号质量急剧恶化
C、服务小区信号质量差而信号强度较强
D、服务小区信号质量和强度同时恶化
答案:(C)
11) 当一个小区的参数T3212值设为25时,表示周期性位置更新时长为   ()   。
A、25分钟
B、2.5小时
C、25个SACCH周期
D、25000秒
答案:(B)
12) 整个切换过程由   ()     共同完成。
A、MS、BTS、BSC、MSC
B、BTS、BSC、MSC
C、BTS、BSC
D、MS、BTS、BSC
 答案:(A)
13) 由于阴影效应引起的衰落称为   ()   。
A、多径衰落
B、瑞利衰落
C、对数正态衰落
D、路径损耗
答案:(C)
14) 用来防止乒乓切换的办法是:()
A、动态功率控制
B、跳频
C、不连续发射
D、迟滞
答案:(D)
15) 在GSM无线网络中 ()     逻辑信道携带用于校正手机频率的消息。
A、BCCH
B、FCCH
C、SCH
D、AGCH
答案:(B)
16) 支持  ()    的信道不跳频。
A.SDCCH  
B.  BCCH   
C.  TCH   
D.  CCCH
答案:(B)
17) 在MOTOROLA基站设备系统一个BSC最多可控制  ()    个BTS。
A.40
B. 89
C. 99
D. 120  
答案:(C)
18) 使用combiner的原因是:
A、最多可以有4个Site使用同一PCM链路
B、多个TRX可以使用同一天线系统
C、手机可以同进收听2个基站的信息
D、发射和传送均由同一天线完成
答案:(B)
19) TA对小区的      属性进行限制。
A、同时发生呼叫的数量)
B、呼叫建立的频率
C、半径
D、天线长度
答案:(C)
20) 一个用户在忙时的一小时内先后进行了2分钟和4分钟的通话,那么这个用户产生的话
务量为:
A、33毫爱尔兰
B、66毫爱尔兰
C、100毫爱尔兰
D、10毫爱尔兰
答案:(C)
三、 简答
1) 无线信号在空中传播时会出现一些问题,如:路径衰耗(Path Loss)、多径衰落(Mu
ltipath Fading)、阴影效应(Shadowing)等,请回答如何解决或尽可能将这些因素带
来的负面影响降到最低?
答案:采用信道编码、交织、分级接收、加均衡器、跳频、时间提前量等手段。
2) 请分别说出26帧复帧和51帧复帧分别承载哪些逻辑信道?
答案:26帧复帧承载TCH、SACCH、FACCH,51帧复帧承载FCCH、SCH、BCCH、CCCH、SDCCH、
SACCH、CBCH,其中CCCH包括PCH、AGCH和RACH。
3) 发射驻波比大于规定值会造成什么后果?
答案:小区覆盖较差、掉话率、切换成功率降低。
4) 减小T3212后对网络会产生一些什么影响?
答案:减小T3212后会使周期性位置更新时间变短,提高paging的成功率,但同时会增加SD
CCH的负荷,易出现SDCCH的拥塞。
5) 简述一下波瓣宽度定义
答案:波瓣宽度定义为天线波瓣的主方向和辐射功率低于主方向3dB的点之间的张角。
6) 列出SDCCH掉话的原因(三种以上)
答案:1)低接收电平(差覆盖)
2)差质量(低C/I)
3) TCH拥塞
四、 论述
1) GSM系统中定义了哪些逻辑信道?
答案:频率校正信道(FCCH)、同步信道(SCH)、广播控制信道(BCCH)、寻呼信道(P
CH)、准许接入信道(AGCH)、小区广播控制信道(CBCH)、随机接入信道(RACH)、独
立专用控制信道(SDCCH)、慢速随路控制信道(SACCH)、快速随路控制信道(FACCH)、
全速率话音信道(TCH/FS)、半速率话音信道(TCH/HS)。
2) 频率多重复用的特点有那些?
答案:主要有以下几个特点:
⑴提高容量,提高频率的利用率;
⑵信道分配灵活,可根据实际情况增减TRX;
⑶可释放出一些频率用于微蜂窝; 
⑷采用基带跳频,易实现;
⑸需要采用基于质量的功率控制技术以及不连续发射技术来降低干扰。
3) 请描述FCCH、SCH、BCCH、AGCH、PCH、RACH、SDCCH、SACCH、FACCH信道的作用。
答:FCCH—传送全0信息,其作用为标识BCCH载频和允许MS同步到这个频率上。
    SCH—传送BSIC和TDMA帧号,从而标识这是一个GSM网络。
    BCCH—传送用于漫游、建立呼叫的广播信息,如LAI、小区最大允许输出功率的信息。
AGCH—利用它分配SDCCH给MS。
    PCH—通知MS是否有此MS的语音呼叫或者**息。
    RACH—当MS有同网络连接的必要时,MS会利用它去申请一个信令信道。
    
SDCCH—MS利用此信道进行呼叫建立,处于IDLE状态的MS利用它接收**息。
    SACCH—伴随SDCCH或TCH存在,其上行链路接收MS发来的关于当前服务小区和邻小区的
测量报告,如信号强度和信号质量。其下行链路上传送指导MS应该使用的功率和TA信息。
处于BUSY状态的MS利用它接收**息。
    FACCH—利用偷帧模式工作,做切换时用到它。
4) 说出几种切换失败的原因。
答案:
1.设备的性能问题(包括天馈部分),主要是设备的射频部分。
2.邻小区设置不当。
3.覆盖不够。
4.干扰较大。
 zz
更丰富的中国移动笔试题汇总:http://bbs.aftjob.com/group-92-1.html


更多名企2012年校园招聘动态,请关注:http://www.aftjob.com/personal.php
阿凡提求职交流群,申请加入时请注明学校和姓名,谢谢!
1.2012-金融求职交流③:95371773
  2012-金融求职交流④:95371919
2.2012-会计求职交流①:7098899
  2012-会计求职交流③:21754384
  2012-会计求职交流②:1289940
3.2012-IT求职交流③:1289905
  2012-IT求职交流④:94628451
4.2012-通信求职交流③:95372037
5.2012-硬件求职交流②:1213195
6.2012-快消求职交流②:71333482

--
http://job.aftjob.com/job阿凡提招聘
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 61.135.194.121]
				

from JobForum: http://bbs.sjtu.edu.cn/bbstcon,board,JobForum,reid,1322541376.html

Written by cwyalpha

十一月 29, 2011 at 6:53 上午

发表在 Uncategorized