Skip to content

{ Category Archives } 工作日志

转:一种语言/编码检测的复合方法

转自: http://blog.i5un.com/item/21 翻译自Mozilla的网站。 这篇论文讨论了组合三种不同的检测方法来实现自动字符集检测。 A composite approach to language/encoding detection) Shanjian Li (shanjian@netscape.com) Katsuhiko Momoi (momoi@netscape.com) Netscape Communications Corp. [ 注:这篇论文最初发表在19届国际Unicode会议(19th International Unicode Conference)(San Jose)。那以后,我们的实现经受住了时间和实际应用的检验,并且,我们还作了许多改进。一个主要的变化是我们现在使用正序列来检测单字节字符集,参见 4.7和4.7.1节。这篇论文写于通用字符集检测代码集成到Moailla主代码前(参见第8节)。自此以后,字符集检测代码被合并到了代码树中。如想 查看最新的实现,请在Mozilla的代码树中查看相应代码。作者 - 2002年11月25日。] 1.概要: 这篇论文提供三种自动检测的方法来判定无明显字符集声明的文档的编码。我们将分别讨论每种方法的优点和缺点,并且提供了一种复合后的,更有效的方法 来检测编码,这样,三种检测方法就可以互为补充。我们认为自动检测在使浏览器用户避免经常使用编码菜单手动选择编码上很有用,同时在编码菜单很少出现的情 况下,提供了更合理的处理方式。我们假设,文档转化到Unicode对用户是透明的。无论字符编码采用的是某种Unicode编码还是本地编码,用户仅需 知道字符最终显示是正确的就行。好的自动编码检测能有效的帮助用户处理大部分的编码事项,而无需用户手动参与。 2.背景: 自从进入计算机时代以来,人们创造了许多使用计算机数据表示的编码方案来表达不同的文字/字符集。随着全球化和Internet的发展,跨语言和区 域的信息交换越来越重要。但是现存的多种编码方案对此是一个屏障。Unicode提供了通用的编码解决方案,但是,迄今为止,各种各样的因素使它并没有代 替现存的区域编码方案。除了W3C和IETF建议使用UTF-8作为缺省编码,比如XML,XHTML,RDF。因此,现今的国际化软件不仅要处理 Unicode编码,还要处理其它多种不同的编码方式。 我们当前的工作是在开发Internet浏览器的环境中开展的。为了处理如今Web上使用不同编码的各种语言,我们做了许多努力。为了获取正确的显 示结果,浏览器需要利用HTTP服务器返回的编码信息,网页或者是最终用户通过选择编码菜单而得到的编码方式。此外,大部分用户没有能力手动的通过编码菜 单来进行操作。如果没有编码信息的话,网页有时就会显示为“垃圾”字符,用户就无法得到他们想要的信息。这最终会导致用户认为他们的浏览器有故障或有 Bug。 由于越来越多的Internet标准协议指定Unicode作为缺省的编码方式,网页将会不容置疑的转向使用Unicode来编码。好的通用自动检 测方法可以对这种转向提供重要的贡献,因为它们工作很自然,无需用户使用编码菜单。在这种情况下,渐进的转向将会以用户不易察觉的方式进行,这是由于,对 用户来说,网页总会显示正确,他们无需考虑使用编码菜单。这种平滑的转变将使编码对用户来说越来越不需要关注。自动检测在这种场景中将很关键。

转:Berkeley DB增加SQL功能

Oracle Berkeley DB将于2010年3月底发布最新版本Oracle Berkeley DB 11g release 2,具体版本号为 11.2.5.0.xx (xx代表具体的patch版本号)。 除了对原有Oracle Berkeley DB的功能进行了一定的改进和增强(比如提升了数据压缩功能、性能优化、C/C++中系统资源自动管理功能等等),本次发布的版本中最引人瞩目的变化是我们引入了一个有用的新特性——Oracle Berkeley DB SQL,简称BDBSQL。这是自Berkeley DB诞生20多年来第一次支持SQL接口。这无论是对开源社区,还是对嵌入式数据库行业来说,都将是一件喜事。在此也感谢整个Oracle Berkeley DB 研发团队的努力工作和大家的不断支持。 新的版本,新增的BDBSQL接口,值得期待。 Oracle Berkeley DB SQL接口简介 从Oracle Berkeley DB (简称BDB)诞生以来,它一直扮演着一个嵌入式、提供API调用的、高性能、非关系型的数据库引擎的角色, 被广泛应用于存储、金融、互联网、电子商务、汽车、消费电子、航空及国防等领域。简言之,它是一个1M大小的C语言类库,提供了基于键/值对(key/value pair)形式的并发和事务操作的API给C/C++/Java/C#/PHP等编程语言调用。由于BDB灵活高效的特点,它特别适合一些大数据量的、或者任务密集型的、或者硬件资源受限而性能要求高的嵌入式、跨平台等等的应用需求。 但我们发现,在很多场合对于关系数据库和SQL的需求是大量存在的。在 “edge”(如消费电子)或者一些大型的企业应用(如ERP)中,一个即时高效、并发的,支持SQL的、本地化嵌入式数据库通常是首选。因此,从 Oracle Berkeley DB 11g release 2开始,我们在保留原有基于key/value操作的API的同时,新增加了BDBSQL接口,实现了对SQL的支持。 BDBSQL完全兼容SQLite(著名的嵌入式开源关系数据库)原有的编程接口。以往运行在SQLite上的程序和应用都可以无缝的、方便的迁移到 Oracle Berkeley DB这个更加强大的引擎。并且,Oracle Berkeley DB和SQLite还将进行长期的官方层面的合作,保证了Oracle Berkeley DB的SQL接口和SQLite保持一致,免除了用户的后顾之忧。此外,Berkeley DB SQL完美支持很多第三方的SQLite工具,如JDBC,ODBC,FireFox 3及其SQLite Manager 插件等。 就具体实现来说,在BDBSQL中,我们将原SQLite的底层存储引擎替换为Berkeley DB的数据库引擎。如下图所示: Oracle [...]

音乐搜索系统部署说明

工作日志,转载请保留出处:唐福林 博客雨 音乐搜索系统部署说明 http://blog.fulin.org/2009/11/pcsearch_deploy.html PC 客户端搜索系统部署说明 唐福林 <tangfulin AT gmail.com> PC 客户端搜索系统主要由 负责建索引的 IndexServer 和负责提供搜索服务的 SearchServer 两部分组成。 IndexServer (目前是 98)负责接收资源库发过来的xml原始文件,解析原始文件,更新索引,并将更新后的索引推送到 SearchServer 上的指定目录供搜索使用。当前架构中,IndexServer 不支持分布式和负载均衡,只能部署在一台机器上。因为索引更新并不频繁,所以这里并不会带来性能瓶颈。如果是为了消除单点故障,可以在另外一台机器上起一个备份进程,当主 IndexServer 故障的时候接收资源库发过来的xml原始文件,但为了保持索引一致,建议不做实际的索引更新操作。这样 IndexServer 故障带来的唯一影响是索引更新延迟。只要做了必要的监控措施,延迟的时间是可以控制在可接受范围内的。IndexServer 主要消耗磁盘IO,也会有一些 cpu 和内存消耗。 SearchServer (目前是 221)负责对外提供搜索服务。SearchServer 当前使用 Resin 提供的 Servlet 环境,以 HTTP 协议提供 Rest 风格的服务。SearchServer 会定期查看工作目录下是否有新的索引到达,如果有,则打开新索引,关闭旧索引。已关闭的旧索引随后会被脚本删除。SearchServer 主要消耗内存和网络IO。 一。部署之前的服务器检查: 1. 确认操作系统发行版本: cat /etc/redhat-release Red Hat Enterprise Linux Server release [...]

音乐搜索的极致(续)

12530 PC客户端音乐搜索项目一期的总结和思考。 SlideShare 上的 pdf: 音乐搜索的极致 View more documents from fulin tang. PPT 的文字内容: 音乐搜索的极致 唐福林 tangfulin@gmail.com http://blog.fulin.org 目录  项目简介  需求描述  搜索实现  查询示例  持续改进 项目简介 (1/3)  中国移动  12530  咪咕  Miniportal  搜索  Out source : edadao 项目简介 (2/3)  时间: 2009 年 9 月 12 日到 10 月 [...]

音乐搜索的极致

12530 PC客户端 咪咕 (页面最下方有一个很不显眼的下载链接) 搜索 原本计划是今天上线内测,20号正是随资源库后台一起上线,其实昨晚就已经替换掉了正式服务器上原来的接口。正因为昨晚悄无声息的上线,原本已经下班走到 家门口的我们,又被电话叫回公司,来解决一个刚刚发现的bug。 音乐搜索,第一期还没有特别做歌词的搜索,只对歌手名,歌曲名,专辑名做优化,加上数据量本身就很小(一共才不到100万首歌),只好在查询上做文章。我们当前一共设置了十层查询 Query: 1。精确匹配:歌手,歌曲,专辑,不分词字段,去掉前后多余空格,精确匹配 2。过滤后的精确匹配:歌手,歌曲,专辑,过滤字段,去掉所有特殊字符,英文转成小写,精确匹配 3。拼音全量匹配:歌手,歌曲,专辑,拼音全量字段,去掉所有非英文字符,英文转成小写,精确匹配 4。同音纠错匹配:歌手,歌曲,专辑,拼音全量字段,只对含中文的搜索词使用,中文转拼音,英文转小写,去掉所有特殊字符,精确匹配 5。拼音首字母匹配:歌手,拼音首字母字段,中文转拼音首字母,英文转小写,去掉所有特殊字符,精确匹配 6。前缀匹配:歌手,歌曲,专辑,不分词字段,去掉前后多余空格,英文转小写,前缀匹配 7。分词Must匹配:歌手,歌曲,专辑,(歌词),分词字段,分词,词之间使用Must连接,分词匹配 8。分词Should匹配:歌手,歌曲,专辑,(歌词),分词字段,分词,词之间使用Should连接,分词匹配 9。合并分词匹配:歌手+歌曲+专辑 分词字段,分词,(当前使用 Should 连接),分词匹配 10。模糊匹配:歌手,歌曲,专辑,分词字段,去掉前后多余空格,英文转小写,模糊匹配, 包含中文时模糊度:0.65 全英文模糊度:0.85 其中模糊匹配还分了两级: a 拼音纠错 b 模糊查询,包括中文模糊和英文模糊(模糊度不一样) 当前拼音模糊是使用组合的办法来实现的: 1。建索引的时候,拼音全量字段里建的是字段的准确拼音,包括多音字的组合 2。搜索的时候,将用户输入的关键词转成拼音,在拼音全量字段里搜 3。模糊的时候,将用户输入关键词转成的拼音,按照模糊规则:n-l 互换,zh-z, ch-c, sh-s 互换,an-ang, en-eng, in-ing, on-ong 互换,每次只换一个(当前只支持模糊度为1的拼音模糊查询),如果有多个可以替换的点,则返回的结果为一个数组组合,然后使用 精确匹配在拼音全量字段进行查询 还有一种做法: 首先定义个所谓的拼音标准化过程: n->l,zh->z, ch->c, sh->s ,an->ang, en->eng, in->ing, on->ong 不是互换,而是单向替换。 将一个拼音串的所有可替换点都替换后,得到的一个串,称为标准化串。 1。建索引的时候,歌曲名,歌手名,专辑名各新增一个标准化串字段,按”,”分词(多音字),存储字段的拼音标准化串 2。搜索的时候,将用户输入的关键词转成拼音,在拼音全量里面搜索 [...]

关于音乐搜索

音乐搜索属于垂直搜索的一种,但它又有着自己独特的一些需求。 首先,几乎所有的音乐搜索都实现了用户输入时的关键词提示功能。但在网上搜索相关的技术文章,大多是讲如何用 Js 实现前台表现层的功能,少有的几篇关于后台技术实现的文章,也都太过简单。标准的办法是使用 Trie 树,但太过晦涩,不够直观。我们打算直接使用 Lucene 的前缀查询来实现,并且计划在项目上线后写一个比较详细的说明。 其次,很多的音乐搜索都提供了拼音查询的功能。比如说用户输入 “liudehua”,关键词提示里会给出 “刘德华”,但即使用户不理会提示,直接点击提交,在服务器端,还是可以查询到关于 “刘德华” 的条目。甚至,用户输入拼音首字母 “ldh”,都可以匹配到 “刘德华”。这主要是考虑到使用音乐搜索的用户群的特点(低龄?懒惰?互联网初级用户?),以及某些艺人的名字确实比较难拼写吧。技术上其实很简单,建索 引的时候,将歌曲名,歌手名等都转成拼音一并进行索引就可以了。唯一一点需要注意的地方在于,多音字的处理。 再次,有些搜索引擎,像 qq music,提供了同音字纠错的功能,可以在用户输入“周洁论”的时候,命中关于“周杰伦”的结果。有了上一步的拼音索引,这一步也很容易实现了。再多做 一步,考虑到南北方的口音差别,很多人 en 与 eng,zh 与 z,n 与 l 不分,在搜索过程中进行一些简单的替换,拼音模糊纠错功能也就水到渠成了。 最后,汉字的模糊搜索。我们常用的一个例子就是,用户输入“刘大华”,能否命中“刘德华”?技术上肯定是可以的,lucene 本身就提供这样的查询,只是在产品设计上,是否有代替用户思考的嫌疑呢?这就需要产品人员去仔细思量了。 前面说的是功能,后面说说排序。 最基础的排序当然是按文档匹配度,也就是 lucene 的 score 来排了。但是有时候编辑推荐的歌曲是一定要排前面的,这个比较好实现。可是点击率比较高的歌曲也要靠前排,这个就有点麻烦了,因为牵涉到频繁的字段更新,以及 boost 值的微调。 最麻烦的是上面说的那一堆的特殊处理。比如用户输入了一个词,精确匹配肯定应该排最前面了,没有精确匹配中文的,拼音全量匹配也可以,分词匹配,或 者部分匹配的结果次之,再接下来应该是前缀搜索,同音字纠错,模糊搜索的匹配条目。最开始的想法一直是多次搜索,可是在多次搜索里,一是无法控制所谓的精 确匹配;二是多次搜索打包的结果用于排序的时候,很麻烦;三则,多次搜索,本身的逻辑就非常复杂。不过今天学会一招,如果不考虑性能损耗,可以说是屠龙刀 级别的必杀技:打包多个 Query 对象,一次搜索!排序的问题,当然使用 Query.setBoost 解决了。至于精确匹配,冗余一个字段,不分词就行。 搭建好了 Hudson,写了一个看起来蛮复杂的 build.xml ,然后每天看着它自动的编译,测试,发布,还是有点成就感的。 开始写测试用例。一边写也一边在思考,搜索引擎项目该如何进行功能正确性的测试,又如何进行搜索结果好坏的评价呢?

当前几个主要的Lucene中文分词器的比较

1. 基本介绍: paoding :Lucene中文分词“庖丁解牛” Paoding Analysis imdict :imdict智能词典所采用的智能中文分词程序 mmseg4j : 用 Chih-Hao Tsai 的 MMSeg 算法 实现的中文分词器 ik :采用了特有的“正向迭代最细粒度切分算法“,多子处理器分析模式 2. 开发者及开发活跃度: paoding :qieqie.wang, google code 上最后一次代码提交:2008-06-12,svn 版本号 132 imdict :XiaoPingGao, 进入了 lucene contribute,lucene trunk 中 contrib/analyzers/smartcn/ 最后一次提交:2009-07-24, mmseg4j :chenlb2008,google code 中 2009-08-03 (昨天),版本号 57,log为:mmseg4j-1.7 创建分支 ik :linliangyi2005,google code 中 2009-07-31,版本号 41 3. 用户自定义词库: paoding :支持不限制个数的用户自定义词库,纯文本格式,一行一词,使用后台线程检测词库的更新,自动编译更新过的词库到二进制版本,并加载 [...]

关于行业相关的站内搜索分词的一些想法

最近在给一个类似 京东 和 新蛋 的3C类电子商城提供站内搜索。基本功能都是现成的,但部署上去以后,发现搜索结果比论坛,cms的搜索结果差远了。仔细的看了几个搜索记录的 debug log,才弄明白为什么: 所有的中文分词组件(paoding,imdict, mmseg4j, ik 等等等等), 都是为了应付日常使用的语言而设计的,特别是 imdict “基于自然语言处理领域的隐马尔科夫模型”,当前的实现还不支持用户自定义词库。其他几个支持用户自定义词库,paoding 甚至起了一个线程来扫描词库的变化,以达到动态更新词库的目的。但词库的维护还是需要使用者来做。mmseg4j 自带了一个 sogou 细胞词库,也都是日常生活用词。不论是基于语料库训练概率还是基于精巧的词库匹配算法,当需要分词的文档中,大部分词都是“未登录词”(行业相关性较强的时候就是这样,比如搜公司名,品牌名,甚至产品型号,配置等等),机器都是无可奈何的。 行业相关的词库因为用的少,关注的人也少,能使用的资源也就少的多了。在没有现成可用的词库的前提下,怎么样以最小的代价得到一个可以接受的搜索精度呢?想了一下,暂时只想到这么几点,欢迎大家补充: 根据行业特点修改分词算法的一些细节处理:比如大部分分词器实现,都会把 “A1600” 这种字母数字混合出现分解成 “A” 和 “1600” 两个词。在日常生活中,这样处理是有道理的。但在 3C 类的电子商城网站中,用户输入 “A1600” 进行搜索,与输入 “A   1600” 的意图肯定是不一样的:前者是想搜摩托罗拉的明手机,后者嘛,就很难揣测了。 站内搜索,一般来说是在一个比较小的有限集合中进行搜索,所以搜索结果集合也是比较小的,甚至经常没有完全命中用户所有的关键词的情况出现。提供给用户一些可能相关的内容总要比显示“对不起,没有搜到任何结果”要好。所以文档中 “摩托罗拉” 除了要分出一个 “摩托罗拉” 以外,“摩托” 也是一个可以接受的索引词,以防用户输入一个莫名其妙的 “摩托” 的时候,搜不到任何结果(我们这里是卖3C类产品的,不卖摩托车,也不卖摩托艇,谢谢!)。—— mmseg4j 的 max-word 算法。 方便的用户添加新词功能:这里的用户,既可以是网站管理员,也可以是最终用户,甚至是写一个程序去baidu,google或其他的什么数据源抓取过来的跟行业相关的词汇。新词经过清理,排重,验证,确认等预处理环节后,添加到词库里面去。如何吸引用户来为网站做有价值的贡献,永远是一个值得探讨的问题。 方便的重建索引功能:在词库的量变快要引起质变的时候,应该重建一下索引。在敏捷开发如日中天的现在,搜索功能也是在不断完善的。索引源数据是不变的,但索引,应该跟着搜索功能的完善而完善,搜索结果,也应该随之得到提升。 未完,待续。。。

Lucene 2.9 上实现 GroupBy 功能

Lucene 2.9 上,终于在 Searchable 接口中支持 search(weight, filter, collector) 了,而不是像 2.4 中那样,只在 IndexSearcher 中支持,而在 MultiSearcher 中,需要自己手工的添加 Collector。 把原来的非常丑陋的 HitCollector 换成了一般丑陋的 Collector ,本来觉得还挺高兴的,但仔细一看代码前的注释:“This API is experimental and might change in incompatible ways in the next release.” 无语了。 虽然 API 还是实验性的,但看起来已经到达了可用的阶段,所以 IMobile Search 2.0 中,还是使用 Lucene 2.9 的 API ,将原来临时性质的 groupby 功能实现重构了一下,大致思路是这样的: 使用 Collector 实现 实现一个 抽象类 o.a.l.search.Collector  [...]

beta技术沙龙 邀请

http://club.blogbeta.com/82.html beta技术沙龙·大型网站的lucene搜索实战 时间:7月26日14点30分开始 地点:奇遇花园咖啡馆 http://storygarden.me/cafe/map 主题:大型网站的lucene搜索实战 演讲简介:本次活动介绍基于Lucene的站内搜索的实践,后台技术层面的一些想法与实践,包括缩短更新周期,简化重建索引流程,支持大数据量频繁更新的索引,以及在性能和可用性方面作的努力。 主讲人:唐福林 (http://blog.fulin.org https://twitter.com/tangfl) 主讲人简介:从高中的 NOIP 到大学的ACM,是编程竞赛的参与者,也是算法的爱好者,以追求程序或系统的性能的极致为乐。 目前就职于手机之家,负责基于lucene的站内搜索的开发及持续改进。 参与人员:最大的前提是技术出身,第二个要求是写blog。积极参加现场沙龙聊天;如有可能对话题通过blog保持跟进关注。http://club.blogbeta.com/ 网上报名或直接现身沙龙,参与免费,点单另付。 关于沙龙:blogbeta技术沙龙由一群技术人员发起并参与,旨在以技术的视角看待社会、互联网和未来,以务实精神深化交流,促进创新。 update: 讲稿的最终版本下载: http://files.getdropbox.com/u/648709/%E5%9F%BA%E4%BA%8Elucene%E7%9A%84%E7%AB%99%E5%86%85%E6%90%9C%E7%B4%A2-beta.pdf https://docs.google.com/fileview?id=0By5e0-mxw7O0NWM5MzhhZTctZGEwOS00NzkzLTliMGYtY2U0ZjBlMDJhZjcy&hl=zh_CN