Archive for 搜索引擎

划词搜索

划词搜索,是中搜的专利。我仔细阅读过,觉得是一个非常小的小发明专利,我个人认为,可能还够不上“本专业人员,非显而易见”的创造性的标准。专利申请文件里,还有1,2个错别字,比较让人遗憾。

但就是这样的一个非常小的小发明,被中搜自豪地在各种媒体大肆宣扬。归根结底,有1个专利,总比没有好。

我看到在美国的专利判例,微软和一个小公司打专利官司,小公司赢了,微软支付了大笔赔偿费用。在美国的专利判例中,大公司往往输给小公司。

而在中国的判例中,个人和小公司却老是败北,比如某发明人和海尔公司关于手机的一个专利的纠纷。读者可以在网上找到相关报道,看后令人为中国的司法现实而叹息。

划词搜索的技术实现:

划词类似于鼠标取词,但比鼠标取词从技术上讲简单很多。

鼠标取词,早在95-97年,四通利方,英汉通,金山词霸等纷纷实现。技术难度是很大的。

我在1998年,写过一篇文章,首次公开了这个技术。http://www.18ie.com/index.php?option=com_content&task=view&id=23&Itemid=38

鼠标取词需要安装mouse hook,并拦截textout 等诸多api函数。编写程序是一个比较痛苦的过程。

划词就简单多了,只需要安装一个mouse hook就可以了。判断出划词动作结束,就可以调用被划软件的相关接口,来得到选择的词。

在ie中,借助com,有1个函数可以实现,很简单,就一句话。

http://www.codeproject.com/jscript/CopyasHTML.asp 

// Get the selected Html source of the window object
// where the context menu item was executed
     var selectedHtml=(document.selection.createRange()).htmlText;
在word中,我估计也是一句话。

在记事本中,我用spy看了一下,估计是用发消息 EM_GETSEL 来实现的。

http://msdn.microsoft.com/library/en-us/shellcc/platform/commctls/editcontrols/editcontrolreference/editcontrolmessages/em_getsel.asp?frame=true

The EM_GETSEL message retrieves the starting and ending character positions of the current selection in an edit control. You can send this message to either an edit control or a rich edit control.

中国互联网,流氓软件泛滥,我就自己写了一个小浏览器,调用ie webbrowser,默认禁止掉所有的activex 插件,这些年一直在用,所以很少见识到流氓软件的行踪。

以前也听说过网络猪,但是从来没有用过。其他的国内软件,对只留一个电子邮件地址,不敢署真名的软件,除非测试需要,也很少招惹。

前段时间见朋友安装了一个影子操作系统,http://www.powershadow.com ,我用了感觉很好,等于给操作系统安装了“金钟罩,铁布衫”,想装什么软件,只管装,再也不怕病毒、木马、流氓把系统搞乱了。 估计推广开后,杀病毒的,杀木马的,杀流氓的,耍流氓的,先耍流氓再杀流氓的,都要失业。

体验一下中搜的划词搜索,同时还发现了另外一个类似的小软件,00超级划词搜索

从起名,就看出作者很专业,00 ,在下载网站排名会很靠前。超级,是否暗示着:很可能出现在中搜的划词专利之后呢?

一般地说,软件总会有1个“关于我们”的版权标志,而这个软件没有。

一般地说,exe和dll总会有1个版权标志,而00search.exe 和 dllmouse.dll 也没有任何版权标记。

但是,划词之后,所有的搜索,都指向百度的搜索引擎。这点,就比较容易让人浮想联翩了。

 

马飞涛

 

Comments (1)

关于搜索引擎的倒排索引技术

为什么搜索引擎的查询速度这么快? 说明白了很简单,核心技术就是 “倒排索引”。

“倒排索引”这个名词很唬人,其实原理很简单。

假设有3篇文章,file1,file2,file3,文件内容如下: 

file1 (单词1,单词2,单词3,单词4....)

file2 (单词a,单词b,单词c,单词d....)

file3 (单词1,单词a,单词3,单词d....)

建立的倒排索引就是这个样子:

单词1 (file1,file3)

单词2 (file1)

单词3 (file1,file3)

单词a (file2, file3)

....

这就是倒排索引,很简单吧。

比如一个文件要建立索引,就先把它抽成纯文本的格式,然后把一个一个的单词切割出来,每个单词在数据库里是一条记录,单词作为关键字,后面跟着文件的标识ID,位置。

我写的桌面搜索引擎 ftfind, 内部也采用了倒排索引技术。http://www.18ie.com

倒排索引技术,点破了很简单,我想每个有兴趣的程序员,花点时间,都能写出来一个自己的桌面搜索引擎。

还用google desktop search 干什么?看着它右边不时冒出来的广告窗口,心里就不爽。

为什么不自己写一个呢,随心所欲,自由自在。

下面收集一些需要进一步了解的知识。 

在使用索引进行查找时,首先对需要索引的文档进行预处理,建立关于这些文档的索引结构。索引的技术主要有以下3种:倒排索引,后缀数组和签名文件。其中,倒排索引技术在当前大多数的信息检索系统中得到了广泛的应用,它对于关键词的搜索非常有效,在Lucene中也是使用的这种技术。后缀数组技术在短语查询中具有很快的速度,但是这样的数据结构在构造和维护时都比较复杂一些。签名文档技术在20世纪80年代时期比较流行,但是后来倒排索引技术逐渐超越了它。

 

Comments (2)

ftfind 桌面搜索引擎的设计文档 (2)

河南省青年创新软件设计大赛参赛作品说明书

飞涛本机搜索引擎

1.创意说明

       

    1. 背景介绍 

尽管从互联网上数以十亿计的文档中搜索信息已经变得相对简单,但在计算机的硬盘上查找一个Word文件仍然不是一件容易的事。

为了方便用户在越来越大硬盘里,从海量的资料中查找自己感兴趣的文档,我开发了本机搜索引擎,该软件能够以全文检索的方式,通过浏览器,让用户在自己的计算机的本地硬盘中,迅速找到Html网页、Word文档 、txt纯文本、或者c,cpp,pas,java,asp,php等程序的源代码文件。

撰写说明书的参考文献:

1)《软件工程》叶俊民 清华大学出版社 2006年

2) 《UML基础及Visio 建模》刘晓华 电子工业出版社 2004年

1.2 市场定位

相对网络搜索,桌面搜索的威力更大,市场更好。从技术来看,只有桌面搜索才算是全方位的搜索工具。它无所不能且方便快捷,从电脑到网络的每个角落都能找到你要找的东西。

日前,google, 微软,雅虎,百度等国际化大公司纷纷全力打造并推出了自己的桌面搜索软件,宣布进入桌面搜索市场。决心为之搏斗一番。

从市场发展来看,桌面搜索市场的发展潜力最大。尽管搜索市场竞争非常激烈,但这一市场的增长潜力被普遍看好。有关市场研究数据显示:中国的搜索引擎市场2003年达到了5.2亿元人民币,比2002年的2.3亿一年增长了127%,今后3年内还将每年增长60%至70%之间,而全球搜索引擎产业,3至5年后将有望达到70亿美元。事实上,各大搜索公司近来的业绩都在高速发展,百度最近的财报显示,其业绩已经上涨了两倍,雅虎的财报也在一路攀升,Google的业绩就更不用说了。

虽然桌面搜索市场,暂时还没有明显的赢利模式,但我们看到各大公司纷纷在桌面搜索市场,积极地进行战略布局。

在这大家都还没有赢利的看不见硝烟的战场上,对后来者而言,正是一个起步的绝好机会:能和巨人们站在同一起跑线上,进行同台竞技。

 

1.3 需求规格

1.3.1 一般性描述

本软件要提供的主要功能是:帮助用户在自己的计算机的本地硬盘中,迅速进行全文检索。

用户特征:

预期软件的主要用户为一般职员(主任/一般文职/业务/办事人员)、学生和专业人士。用户受到的教育水平较高,对计算机操作较为熟练。

限制与约束:

为了方便软件在网络上的传播,在设计时,需要尽量精减软件的尺寸:整个软件的安装包限制在1M字节之内。在一个安装包内,提供全文检索的完整功能,内含微型化的http 服务器,hash型文件数据库,中文分词模块,中文词汇表,doc解析模块,html解析模块,文件遍历模块,模版化人机界面等。

1.3.2 特殊需求

作品功能:

能够以全文检索的方式,通过浏览器,让用户在自己的计算机的本地硬盘中,迅速找到Html网页、Word文档 、txt纯文本、或者c,cpp,pas,java,asp,php等程序的源代码文件。

行为需求:

1)用户可以在自己的计算机中,进行全文检索。用户通过浏览器输入欲查询的关键词,软件进行中文分词和检索,以页面形式返回包含关键词的文件集合。

2)用户可以指定和添加要索引的范围,比如可以一次添加多个文件进行索引,可以添加某个目录,某个硬盘进行索引。软件可以按照用户的指定范围,自动遍历并索引该目录或该硬盘下所有的文件,及其子目录下的所有文件。

3)索引时,采用多线程技术,尽量降低对CPU和内存资源的消耗。当用户空闲时,(鼠标停止移动10秒后),软件才能进入索引状态。一旦用户移动鼠标,索引线程立即进入休眠状态。

性能需求:

1) 查询时,最长的响应时间:控制在800毫秒和1秒左右;平均响应时间:控制在200毫秒之内。

2)内存平均占用控制在4M-10M之间。

3)软件安装包的大小控制在1M之内,以方便下载。

4)倒排索引文件的占用随索引范围而变动,采用中文分词技术,以词汇为单位进行存储,以期减少对硬盘空间的消耗。

5)如果计算机死机或者突然断电后,软件重新启动时,应该具备自我修复功能,避免从头再次建立索引。

6)提供模版化人机界面,如果用户具备编写html的能力,可以灵活地自行修改查询结果的显示页面。

安全性需求:

只允许来自本地IP地址(127.0.0.1)的查询,拒绝来自局域网和互联网的其他IP地址的查询。

 

2.设计规格说明

2.1 背景介绍

2.1.1 作用范围

系统目标:设计一个轻量级的全文检索软件,可以让用户通过浏览器输入欲查询的关键词, 在用户自己的本地硬盘中,迅速查询并以页面形式返回:包含关键词的Html网页、Word文档 、txt纯文本、或者c,cpp,pas,java,asp,php等程序的源代码文件。

系统的运行环境

硬件环境:公知计算机。

软件环境:WINDONS 98/2000/XP操作系统。

人机界面:浏览器(比如ie, netscape,firefox等)

 

设计约束:

软件语言采用DELPHI和Vc 混合编程。使用Delphi 编写主程序ftfind.exe,包括http server、遍历模块和软件界面等模块。使用Vc编写动态连接库fullindex.dll, 包括全文检索和中文分词等模块,供主程序ftfind.exe调用。

 

2.1.2 文档

技术参考书:

《C++ 标准程序库》 侯捷/孟岩 华中科技大学出版社 2002年

《Delphi 4编程技术内幕》 Charlie Calvert 机械工业出版社 1999年

《Delphi 算法与数据结构》Julian Bucknall 中国电力出版社 2003年

《C++ 编程思想》Bruce Eckel 机械工业出版社 2003年

《编程珠玑》Jon Bentley 中国电力出版社 2004年

参考标准

Hypertext Transfer Protocol -- HTTP/1.1 (RFC 2616)

Hypertext Markup Language - 2.0 (RFC 1866)

 

2.2 软件功能设计

系统划分为以下子系统:http 服务器,hash型文件数据库,中文分词模块,中文词汇表,doc解析模块,html解析模块,文件遍历模块,模版化人机界面。

整体结构

2.3 软件逻辑设计

添加倒排索引文件的数据流图

倒排索引

 

查询句子的数据流图

关键词全文检索

 

添加索引的线程状态的控制流图

 

添加索引

查询时的UML活动图

查询uml的活动图

界面设计:

主程序的界面:

ftfind

 

查询的输入界面:

query keyword 

显示返回结果

find keyword

 

2.4 软件运行平台设计

开发平台:

Delphi 和 Visual C++

运行平台:

Windows XP, 2000,98。

 

2.5 部署与安装设计

运行安装包find.exe, 点击“下一步”。 安装完毕后,系统自动运行。

 

3.软件使用说明

3.1 系统安装说明

安装步骤:

运行安装包find.exe, 点击“下一步”。 安装完毕后,系统自动运行。

数据初始化过程:

第1次查询前,用户需要先指定索引的范围,比如输入c:\, 然后,软件会自动检测鼠标使用状态,如果鼠标停止移动10秒之上,索引模块就会开始工作,在用户指定的范围内建立索引文件。

3.2 系统使用说明

用户第1次运行本软件时,应该指定搜索范围,软件会在计算机空闲时,对指定范围内的文件进行分析并建立索引,以供用户日后快速进行全文检索。

索引建立完毕或者正在建立的过程中,用户可以用浏览器,输入关键字进行全文检索,比如输入“ 计算机 ”,软件会返回用户本机硬盘中包含该关键词的所有文件,高亮度标识该关键词,并以分页的html形式显示出来。

如果输入“ 计算机 电脑 ”, 软件会返回既包括“ 计算机 ”又包括“ 电脑 ”的文件。

如果输入“ 计算机 -电脑 ”, 软件会返回包括“ 计算机 ”但不包括“ 电脑 ”的文件。

 

3.3 疑难问题解答

>为什么第一次运行,什么文章也没有搜索到?

因为:需要用户先指定索引的范围,软件才开始工作,在该范围内建立索引文件。索引建立完毕后,用户才能进行检索。

>软件可以索引那些后缀的文件?

可以对网页文件(*.htm)、纯文本文件(*.txt)、word文件(*.doc)、和源代码 *.c,*.h,*.cpp,*.pas,*.asp,*.php,*.java 等文件建立索引。支持Gb2312,utf-8等编码方式。

>软件何时进入索引状态?

软件检测到用户停止使用鼠标10秒之后,自动进入索引状态;一但用户开始使用鼠标,软件立即暂停索引。

>是否需要安装word软件,才能检索doc文件?

本软件自带doc文件转换器,不用安装WORD软件,即可直接抽取并索引doc文档。

>用户是否可以自行修改查询的页面?

本软件采用灵活的模版化设计,稍具网页设计知识的用户,即可自行修改软件www目录下的搜索界面。

 

4.商业计划书

4.1 背景

尽管搜索市场竞争非常激烈,但这一市场的增长潜力被普遍看好。 有关市场研究数据显示:中国的搜索引擎市场2003年达到了5.2亿元人民币,比2002年的2.3亿一年增长了127%,今后3年内还将每年增长60%至70%之间,而全球搜索引擎产业,3至5年后将有望达到70亿美元。事实上,各大搜索公司近来的业绩都在高速发展,百度最近的财报显示,其业绩已经上涨了两倍,雅虎的财报也在一路攀升,Google的业绩就更不用说了。

从市场发展来看,桌面搜索市场的发展潜力最大。相对网络搜索,桌面搜索的威力更大。从技术来看,只有桌面搜索才算是全方位的搜索工具。它无所不能且方便快捷,从电脑到网络的每个角落都能找到你要找的东西。

虽然桌面搜索市场,暂时还没有明显的赢利模式,但我们看到各大公司纷纷在桌面搜索市场,积极地进行战略布局。

在这大家都还没有赢利的看不见硝烟的战场上,对后来者而言,正是一个起步的绝好机会:能和巨人们站在同一起跑线上,进行同台竞技。

4.2 创业思路

密切关注goolge在桌面搜索市场上的动向,在技术上步步紧追, 争取有所超越;在商业上,积极发现并模仿google desktop search未来可能出现的的赢利模式。

4.3 产品推广策略

推向市场的策略:

采用免费下载、免费使用的推广模式,通过在用户中建立良好的口碑,借助用户之间的传播,并积极在报刊杂志等传统媒体和网络媒体上,采用广告、博客、论坛、搜索引擎优化等多种方式,进行宣传推广。

为目标客户提供服务:

收集用户的需求,改善软件的结构,适应软件外部运行环境的发展变化,提高软件的可维护性和可靠性,为日后进一步改进软件打下基础,力争满足来自各方面用户的多种需求。

本文 doc格式 下载地址:

http://www.18ie.com/find/ftfind_doc.php

本软件可执行程序 下载地址

http://www.18ie.com/find/download.php

 

花了整整2个星期的时间,我才写完了这个文档。现在放在网络上,希望会给大家带来一些帮助: 

1)对于初学者,会对桌面搜索引擎的内部结构有所了解。

2)给以后参加此类软件大赛的选手一个参考例子。截至现在2006-10-9日,朝鲜的原子弹都爆炸了,网络上还没有一个参赛的文挡可供下载。那就让我来做第1人吧 。

 

 

Comments (2)

ftfind 桌面搜索引擎的设计文档 (1)

坦白地说,我设计软件时,和很多程序员一样,也不爱写文档。

后来,发觉如果按软件工程要求,不爱写文档的程序员,就是不成熟的程序员,就是游击队,即使你编程技艺高超,也是山顶洞的史前野人。

看看按软件工程的要求,都需要写些什么呢?

一、可行性研究报告.dot
二、项目开发计划.dot
三、需求规格说明书.dot
四、概要设计说明书.dot
五、详细设计说明书.dot
六、用户操作手册.dot
七、测试计划.dot
八、测试分析报告.dot
九、开发进度月报.dot
十、项目开发总结报告.dot
十一、程序维护手册.dot
十二、软件问题报告.dot
十三、软件修改报告.dot
 

和做智能狂拼的刘定西聊过天,他观察到:程序员的输入法一般都不太好。比如我就是这样,英文打得飞快,中文输入时,得选来选去,速度就慢多了。

我觉得:如果按这些列表把文档都写下来,手还不写软?哪里还有时间和心情写程序?

所以不写也罢,我就心甘情愿地做了十多年的山顶洞的史前野人。

后来,在一个互联网业界的牛烘烘的公司里面作驱动程序的开发,发现新来一个大牛级的人物,也做开发,第1件事情,就是埋头写文档。惹得二牛们满脸羡慕之情,看:别人一来就写文档,真专业。

这才发现,写文档还有这种好处。

那个时候,正兴起敏捷开发,就特意号称不写文档。

真让我思想解放!!! 原来,不写文档的程序员也大有人在,不光是我呀,还有好多人都不爱写呀。

怪不得有 SourceForge.net: Doxygen 这种能够自动把注释抽取成文挡的软件。

上半年,我写了一个桌面搜索引擎,类似于google desktop search 。

下载地址:http://www.18ie.com/find/download.php

9月18号那天,把它递交到河南省青年软件大赛,看看能得第几名。

这种青年软件大赛,特别麻烦。说明文挡里需要一大堆软件的设计说明。我也想偷懒,在网络找一个现成的例子,可是没有发现。

却通过网络搜索发现一个小秘密,原来全国各省的这种大赛的要求是一样的,用了一个模子刻出来的说明书。可叹,中国无人呀。不知道是请那个老教授写的,然后就全国通用了。那个老教授是参考哪本书写的呢?我很想知道,但不得而知了。知道这本书的名称,对理解他所说的技术术语很重要,如果谁知道是哪本书,请告诉我呀。

河南省青年创新软件设计大赛参赛作品说明书
(参考目录)
1.创意说明
1.1 背景介绍
介绍作者设计软件的创意背景、定义、名词解释、参考文献。
1.2 市场定位
主要介绍作者参赛作品的适用对象、应用前景和市场展望,可以从技术发展、行业应用、个人经历的方面来阐述。
1.3 需求规格
1.3.1 一般性描述
作品与环境之间的关系、作品要提供的功能、用户特征、限制与约束等。
1.3.2 特殊需求
包括参赛作品功能、行为需求、性能需求、安全性需求、设计约束和其他。
1.4 总结
2.设计规格说明
2.1 背景介绍
2.1.1 作用范围
包括系统目标、系统环境定义(硬件、软件和人机界面等)、主要设计约束和限制等。
2.1.2 文档
包括应用的技术参考书、参考标准、采用的技术或技术路线说明,以及在本软件设计工程中采用的项目管理方法、措施和规范制定。
2.2 软件功能设计
包括软件结构的功能、系统子系统划分以及公共构件的设计。
2.3 软件逻辑设计
可采用面向对象或面向过程的设计法中,设计软件数据流和控制流的任何方法或工具完成(如Rational Rose中的状态图、活动图、User case等),要求包括如下内容:
数据流设计
数据库设计(如软件中不涉及数据库管理,可省略)
控制流设计
用户界面设计
2.4 软件运行平台设计
对软件的开发平台、运行平台和使用场景进行设计,包括系统运行的操作系统、数据库系统及其他支撑环境等。
2.5 部署与安装设计
对系统的安装、部署的要求和实现方法进行说明。
2.6 小结
3.软件使用说明
3.1 系统安装说明
描述重要的安装步骤、脚本参数配置和数据初始化过程。
3.2 系统使用说明
说明系统的使用方法,描述主要的功能实现流程。
3.3 疑难问题解答
4.商业计划书
4.1 背景
进行创业或成果转化的背景介绍,可结合软件来介绍毕业后的职业选择或人生定位。
4.2 创业思路
如果你想创建你自己的软件公司,结合你设计的软件产品介绍你可能组建一个什么样的公司(可包括合伙人及股份结构,公司初创规模、雇员 ……)。
4.3 产品推广策略
如何把设计出来的软件或软件提供的服务推向市场,并对你的目标客户提供服务

仔细阅读该本《软件工程》,尽量把老教授的术语和这本书上的术语套在一起。

(说的好听点是术语,说不好听,就是方言)。现在,我仍然把握不准“控制流设计”是个什么方言,

我买的那本《软件工程》里,对“控制流设计”几乎没有解释,在网络上能找到好几种说法,到底应该采信谁的?我想应该不是指软件的流程图,也不太象是状态转化图。谁知道确切含义,请给我留言呀。

花了整整2个星期的时间,才写完了这个文档。现在放在网络上,希望会给大家带来一些帮助: 

1)对于初学者,会对桌面搜索引擎的内部结构有所了解。

2)给以后参加此类软件大赛的选手一个参考例子。截至现在2006-10-9日,朝鲜的原子弹都爆炸了,网络上还没有一个参赛的文档可供下载。那就让我来做第1人吧 。

下载地址:

参赛文档 doc格式 下载地址:

http://www.18ie.com/find/ftfind_doc.php

参赛文档的网页格式:

http://www.18ie.com/wordpress/?p=43 

本软件可执行程序 下载地址

http://www.18ie.com/find/download.php

 

再发几句戏言,以乐读者:

1)从来不写文档的程序员,是山顶洞人。(我当过10多年呢)

2)按照软件工程的要求写文档的程序员,是公元前人。

3)遵循敏捷开发的程序员,是公元后人。也许2,3的顺序有争议。

4)用数码相机,摄像机,扫描仪,录音笔、带摄像头的手机,纪录数码文档的程序员,是新人类。如果能有个PLMM把纪录下的视频、照片,录音带,MP3,AVI整理成软件工程要求的文挡,那就是新新人类了。
 

 

评论

字符串快速查询算法

字符串快速查询算法

  1. Knuth - Morris - Pratt 算法 http://barnyard.syr.edu/quickies/kmp.c
  2. Boyer-Moore fast string search 算法  http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html
  3. 比Boyer-Moore更快的字符串查找算法

号称快速的算法,也并不一定比strstr更快些,可能还要慢些。( strstr 经过手工汇编优化过的最原始的c语言的)。http://www.arstdesign.com/articles/fastsearch.html

评论

« Previous entries ·


0.033 sec