根据用户指定的关键字查询记录并分发给相应用户的问题
在设计中遇到一个问题, 可以抽象为如下模型:
某数码产品网站有若干个(设为M个)注册用户,注册用户可从该网站定期收到按其个人喜好定制的某种数码产品(比如手机)的最新信息.个人喜好是指用户在注册时填写的对于产品某种属性的特别偏好,这些属性都有有限个取值,比如手机可分为 品牌:NOKIA,MOTO,SE; 价格:1000元以下,1000元~2000元,2000元~4000元,4000元以上; 支持蓝牙: 是, 否 ... 等等若干种属性. 某个注册用户所填写的个人喜好可以是如上属性的各种可能的逻辑组合,例如:
用户1 :(品牌=NOKIA & 价格=1000元至2000元) ¦ (品牌=MOTO & 价格=1000元以下);
用户2 :(品牌=NOKIA & 价格=1000元至2000元) ¦ (支持蓝牙=是 & 价格=2000元至4000元) ¦ 价格=1000元以下;
用户3 :品牌=SE.
... ...
这里先不用去考虑以什么方式输入,表示,解析和判断这些逻辑关系的问题,假设这已经不是问题了.
那么我们要将获得的每一条最新的数码产品信息送到与其个人偏好相符的用户那里. 每条信息都已经注明了如上各属性的取值(品牌是什么,价位如何,支持蓝牙与否,等).
现在的问题就是应该使用怎样的数据结构和相关算法来进行信息的分拣递送呢? 假如每收到一条信息,就遍历所有注册用户,逐个判断其属性是否与其要求相符,显然效率太低; 另一种做法是,假如有N种属性,那么就建立一个庞大的N维数据表,其中每一项对应着一种可能的属性组合(如Table[0][2][0]对应着2000~4000元的NOKIA支持蓝牙的手机),里面的内容是该属性组合所满足的所有用户的ID号, 每当一个用户注册时,根据其偏好往所有满足其偏好的条目里都添加进其ID,这样虽然注册用户时效率很低,但可以增加分拣时的速度(我只关心分拣投送时的空时复杂度), 然而这又需要浪费大量的存储空间.
我数据结构学得不够好, 还得请教大家,有什么在空间时间上都比较高效的方法能解决我的问题?
声明一下:举这个网站的例子只是为了说明我的问题,但事实上我要做的并不是网站程序,而是完全从最底层实现这种数据查找分发的工作,所以不能用到数据库.
[解决办法]
好长，坐沙发
[解决办法]
用户按喜好信息排序,
比如先按品牌排序,在相同的品牌里再按价格排序,这样一级一级排序下去
搜索的时候便可很快定位
[解决办法]
数据库里面建立几个索引。在查找的时候会自动优化的。
不过最好不是一条更新就这么找一次。规定的时间或者批量更新后再做了。
我也不懂，
[解决办法]
对于lz的问题，个人认为：为便于信息匹配，首先应该对用户偏好进行“分解”，并在此基础上采用BitSet的方法实现。基本思路说明如下：
** 用户偏好的“分解”
在LZ的举例中用户1的偏好如下：
用户1 :(品牌=NOKIA & 价格=1000元至2000元) ¦ (品牌=MOTO & 价格=1000元以下);
对于该用户的偏好，可以分解为2个”子偏好“：
子偏好1：(品牌=NOKIA & 价格=1000元至2000元)
子偏好2：(品牌=MOTO & 价格=1000元以下)
偏好分解的主要目的是满足快速匹配的基本要求。用户偏好的分解最好在用户注册时完成。
** 基于BitSet的产品/用户偏好编码
属性编码：将每个属性的可选项分别用一个bit位来表示，该属性可选项的数量决定该属性的“编码空间”。例如"品牌“属性有3个可选项，那么该属性的编码空间就是3。
产品编码：产品编码实际上就是该产品所有属性编码的”联加“
用户子偏好编码：首先将用户子偏好分别针对不同的产品属性进行编码，然后将这些编码进行”联加“，就得到一个子偏好的编码。
采用基于BitSet的产品/用户偏好编码方案的最大好处是高效率：最终的匹配操作被简化为位操作。如果属性及各属性可选项的总数不太多，一次匹配甚至可以被简化为一次整数位与操作。
** 举例说明
品牌:NOKIA,MOTO,SE; ### 共有3个可选项，则该属性的编码空间为 3bits
价格:1000元以下,1000元~2000元,2000元~4000元,4000元以上; ### 共有4个可选项，则该属性的编码空间为 4bits
支持蓝牙: 是, 否 ### 共有2个可选项，则该属性的编码空间为 2bits
假设用户偏好如下：
用户1 :(品牌=NOKIA & 价格=1000元至2000元) ¦ (品牌=MOTO & 价格=1000元以下);
用户2 :(品牌=NOKIA & 价格=1000元至2000元) ¦ (支持蓝牙=是 & 价格=2000元至4000元) ¦ 价格=1000元以下;
用户3 :品牌=SE.
分解后的用户子偏好如下：
用户1 :
子偏好1：(品牌=NOKIA & 价格=1000元至2000元)
子偏好2：(品牌=MOTO & 价格=1000元以下)
用户2 :
子偏好1：(品牌=NOKIA & 价格=1000元至2000元)
子偏好2：(支持蓝牙=是 & 价格=2000元至4000元)
子偏好3：价格=1000元以下
用户3 :
子偏好1：品牌=SE.
则这3个用户的偏好可编码如下（各可选项分别占据其相应编码空间的0~n-1 bit位）：
用户1：
子偏好1：001（品牌） + 0010（价格） + 11 (蓝牙)
子偏好2：010（品牌） + 0001（价格） + 11 (蓝牙)
用户2：
子偏好1：001（品牌） + 0010（价格） + 11 (蓝牙)
子偏好2：111（品牌） + 0100（价格） + 01 (蓝牙)
子偏好3：111（品牌） + 0001（价格） + 11 (蓝牙)
用户3：
子偏好1：100（品牌） + 1111（价格） + 11 (蓝牙)
** 用户偏好匹配
经过前面的偏好分解和偏好编码后，就为每个用户建立了一个“偏好链”。当有新的信息输入时，首先对信息进行编码，然后用信息编码与用户偏好链中的节点作“位与”运算，结果与信息编码一致则表明匹配成功。
例如，对于新的信息“NOKIA/1000~2000/支持蓝牙”，可以得到信息编码“001 + 0010 + 01”。通过匹配操作，可以得到：用户1-子偏好1，用户2-子偏好1 匹配成功。
** 实现
基于BitSet的编码方式可以采用C++ bitset<> 实现。bitset支持各种位操作，是用来实现该方案的首选。
** 优化
一种可能的优化方案是：就某一个或多个重要属性（例如品牌）对所有用户子偏好进行分类，从而达到通过重要属性的一次匹配达到大幅缩减搜索空间的效果。
