干货分享:站内搜索引擎的分词算法的数据库设计方案

王志勇 发表于 2019年11月03日 11:48

在程序开发之前,脑中需要有一个主线的方案,整个程序都是在围绕这个方案。就在前天写《网络创业的几个新思考》到昨晚,共经历了30多个小时,突然有了一个新的方案。

这个方案,虽然还不能完全实现巨量数据的标题关键词任意快速搜索,但是可以实现带有空格的分词快速搜索,因此基本上已经可以实现类似淘宝的产品快速搜索,这适用于产品类、关键词分类的搜索站点或平台。

这样的站内搜索引擎,其实大约在2011年我开发Orshu帐号新程序的时候,设计了一个新的算法方案。

2008、2009年我开发帐号程序时,是一个用户名为一个数据库文件(称为“索引文件”),登录时可以以最节约资源、最快的速度找到该索引文件。但这样有个弊端,当时很多主机商要求每个目录下只能放1024个文件,所以必须突破这个1024的限制。

2011年时,设计了新的方案,将用户名的每个字符变为查询编码,之后再将查询编码通过一定的规则转化成数字,例如汉字“我”在UTF-8下的查询编码为%E6%88%91,“我们出发了”这样的ID转化成数字后是5646498489462546这样的代码,该索引文件的存储路径为:005/646/498/489/462/546.x,类似于这样。

实际是提取前12、或前15位数字,把前12、或前15位数字相同的ID放在同一组数据库里,例如564/649/848/946.x这样的索引路径,最终的索引用户名写在946.x数据库里。

这个方案一直沿用直今,比如半年前新开发的Eonval帐号。虽然这个方案能够以最快的速度从上百万、十亿条数据中瞬间搜索到,但是也稍微有个弊端,创建的目录太多(对象太多),不利于定期备份。

尤其是站内搜索引擎的分词,则不适用这个方案,因为创建的目录太多,目录还可以再减少。

站内搜索引擎的分词思路
比如用户需要搜索的“洗脸池水龙头”关键词。最理想的方案是商家在创建该产品时,已经将关键词做了切分,使用空格切分,即“洗脸池 水龙头”。(或者由网站编辑进行审核,审核时创建切分关键词。)

这时,创建2组关键词的数据库。用户搜索这些关键词,搜索结果里都会包含该产品,只是排名不一定靠前:洗脸、洗脸池、水龙头。

而用户如果搜索“洗脸池 水龙头”,则优先把这个搜索结果靠前。

算法步骤:
写入数据时,创建这样的数据索引:
数据库1:洗
下一级的数据库2:脸
下一级的数据库3:洗脸池

这里,将数据库索引的文件分为3级。也可以分为2级,各有好处(后面讨论)。

数据库3存储的是产品ID,产品ID再为分为2-3级的目录,1级目录可放1024个产品,2级是1024×1024,3级是1024×1024×1024。

如果用户搜索“脸池”,则无法搜索到这个产品,因为这个算法是从关键词的开头进行索引的。

在上述的数据库1,记录了以“洗”字开头的下一级数据库名称;
数据库2,记录了记录了以“洗脸”开头的下一级数据库名称,和“洗脸”开头的所有产品ID;
数据库3,则记录了记录了以“洗脸池”开头的所有产品ID。

用户搜索、调取数据库时的算法步骤:
例如用户搜索“洗脸池 水龙头”,优先直接找到“洗脸池”的数据库,会显示“洗脸池”开头的所有产品ID。如果该数据库不存在,则向上找“洗脸”开头的所有产品ID。

同理,如果用户搜索“水龙头”,搜索结果也会包含该产品的ID。

假如某一个产品发布时,同时包含“洗脸池”“水龙头”的关键词,产品发布时的ID是3356,用户搜索“洗脸池 水龙头”时,“洗脸池”和“水龙头”这2个关键词的搜索结果都包含3356,则3356这个产品的排名会在“洗脸池 水龙头”、或者“洗脸 水龙头”、或者“洗脸 水龙”里靠前。

搜索“洗脸池水龙头”
如果搜索“洗脸池水龙头”,这时情况就变得复杂许多。因为如果按照上述的算法,会找不到该产品。解决的办法暂时只能在搜索时,在机器里,将“洗脸池水龙头”这6个字进行组合,如:

洗 脸池水龙头
洗脸 池水龙头
洗脸池 水龙头
洗脸池水 龙头
洗脸池水龙 头

然后依次搜索数据库。由于上述的索引数据库是建立了3级,那么上述的5种组合,需要在内部搜索5×3×2=30次。如果之前建了2级,则内部搜索(内部寻址)5×2×2=20次。

索引数据库建立的级数越多,优点是单个数据库文件越小;但是缺点是内部搜索次数多。

MP3、歌名的服务器内的搜索引擎
和上述的搜索方案一样,搜一首歌内部寻址次数为5-8次。

简体中文/繁体中文关键词混用的解决方案
如果用户发布的信息含有繁体中文,则在发布程序里事先设计一个简体中文/繁体中文互转的程序。发布时,用户填写的内容保持不变,但是在创建索引数据库分类时,关键词统一转为简体中文、或者繁体中文。

用户搜索时,搜索程序里同样需要设计简体中文/繁体中文的互转程序,这样用户对同一产品,无论是输入简体、还是繁体中文,都能搜索到。

2008年时的一个方案
2008年时,我曾使用调用Windows服务器的DOS的查找命令,然后所有的关键词都放在一个目录,当时大约在几千个文件里搜索非常快。这个查找命令,基本上等同于Linux系统下的find命令。但是可想而知,当一个文件里的文件达到几十万个、几百万个,搜索速度会很慢,因为它是进行了几十万个、几百万个文件的搜索。所以,必须进行切分。

查找命令/或者传统的数据库查询语句,优点是算法非常简单,不需要上述的算法,用户搜索“洗脸池水龙头”这6个字当中的任意连续字符,都能搜索到该产品。但是缺点是无法实现巨量数据的快速搜索。

0条评论:

发表评论:
名字: (*必填)
博客: (可省)

正文:

  记住信息?

直接发送Trackback到此文章

说明:本评论系统不支持HTML代码。(您的留言需要审核,审核规则请见这里。)

王志勇:1980-09-26 (39周岁)
程序设计,前端设计。

版权声明:本博客所有文章,均符合原创的定义,禁止转载,违者将必究;正确的方法是贴原文的标题和网址即可。

与此相关的链接
自由勇专栏

Blog存档 Archives

2019年09月
2019年08月
2019年07月
2019年06月
2019年05月
2019年04月(30)
2019年03月(30)
2019年02月(30)
2019年01月(30)
2018年12月(30)
2018年11月(30)
2018年10月(30)
2018年09月(17)
2016年-2017年(9)
2014年06月-09月(10)
2013年 +

2012年 +
2011年 +
2010年 +
2009年 +
2008年 +
2007年 +
2006年 +
2005年09月(4)

Copyright © 2006-2019 auiou.com All rights reserved.
此Blog程序由王志勇编写 已经发布在Arsue