词语匹配
设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，
则中国人民 人民中国都有效
1 php
2 /**
3 *设计一个系统处理词语搭配问题，比如说中国和人民可以搭配，
4 *则中国人民人民中国都有效。要求： 5 *系统每秒的查询数量可能上千次；
6 *词语的数量级为10W；
7 *每个词至多可以与1W 个词搭配
8 *当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。
9 **/
10
11 /**
12 *解决思路
13 *假设10W的词语都是二字词语，UTF8存储，则每个词语占 2*3 bytes = 6 bytes
14 *现在先对10W个词语建一棵二叉查找树，树节点存储词语内容和一个指向词语匹配表的指针，忽略左右孩子指针和指向词语匹配表的指针大小
15 *10W个词语组成的树大小是 100,000 * 6 bytes = 600 Kbytes，即使加上各种指针也不大
16 *每个词语的匹配表对应1W个单词，这1W个单词使用数组存储，并排序，则每个数组大小为10,000 * 6bytes = 60 Kbytes
17 *10W个单词的匹配数组就是 100,000 * 60 Kbytes = 6 Gbytes，应该来说大多数服务器内存都够
18 *然后查找的时候先通过查找树找到关键词，然后去匹配数组用二分查找找到匹配词即可
19 **/
20 ?>
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/29012686/viewspace-1161624/ ，如需转载，请注明出处，否则将追究法律责任。
