设计一个系统处理词语搭配问题,比如说 中国 和人民可以搭配,则中国人民 人民中国都有效。要求:
** </span>***系统每秒的查询数量可能上千次;
** </span>***词语的数量级为10W;
** </span>***每个词至多可以与1W个词搭配
当用户输入中国人民的时候,要求返回与这个搭配词组相关的信息。
方案:
步骤:
分词.
判断是否搭配
一。分词的判断
如果不考虑歧义,可以用wm基于shift表的词表匹配方法,在O(length(input))时间内完成分词。
如果考虑歧义,用专用分词系统。时间复杂度待查。
暂时不考虑歧义。
wm表占用内存大概5M以内.
二。判断是否搭配
用二维向量表示10w个词之间的搭配信息。每个词-词搭配信息占用一个bit,共 10w * 10w bit,大概160MByte.
分词完成后,可以在O(1)时间内完成搭配信息的查询。
上述处理在普通PC(AMD 双核2.5G Hz,2G内存)上可以在一百-五百微秒时间范围内完成,即每秒至少可以处理两千次查询。