请教算法和php扩展的相关疑问
本帖最后由 ShadowSniper 于 2012-11-27 23:30:22 编辑 我有个需求，想用php扩展实现：
搜索一个字符串中包含在词表中搜索到的词。
比如词表如下:
---------------
你
他
我
他们
你们
我们
---------------
输入一句话:你、我与他们都是好朋友。
需求为：
1 找出包含在词表中的词。
2 可以通过参数控制
(1)长词优先(找到“他们”了，就不需要再找“他”)
(2)全部返回(“他”和“他们”都找出来)
(3)只找短词(只找“他”)
3 可以通过参数控制
(1)按词表顺序返回
(2)按词序返回(词在句中顺序)
4 可以通过参数控制在需求3的基础上增加个维度，正序或倒序返回
问题一：请问使用何种算法会比较高效？
如果按词表顺序返回，那么就逐行扫描词表，然后使用kmp算法去句中取词，这比较好办。
如果按句中词序返回，先用按词表顺序的方案找一遍，并且记录下每个找到的词在句子中的位置索引，然后再根据索引排序。
但这一步多了个排序，如何不用去排序？我一开始想到先用标准分词，把句子分成词，然后反着去词表查，但有个问题很难保证，就是标准分词我们可能要去使用第三方的，分出的词不一定符合我们词表中的词的规则。因为词表是我们人为手工录入的。有可能会造成这种问题。词表中有一个词是：“屌丝”，但标准分词法会把“屌”和“丝”当成两个词来分。这样反着查就查不到了。
不知有什么更好的方法，请指教。
问题二：词表提体积目前大概有20000左右，不是很大。我想全部放进内存里。但是使用zend提供的emalloc来申请内存或是使用c原生的malloc申请内存还是使用第三方内存数据库系统？
使用emalloc申请内存的优点为php的内存管理可以帮忙管理内存。但缺点为需要占用php本身的大量内存。
使用malloc申请内存的优点我不太清楚，不过貌似缺点是其也会占用php本身的内存，并且很难对内存进行管理，因为可能会造成php本身内存溢出。
使用第三方内存数据库的优点为不会占用php本身的内存，但可能效率上会稍差一些。比如使用redis。需要在php扩展中实现对redis的连接，关闭。
------解决方案--------------------
我猜是一个php-fpm进程一次?
------解决方案--------------------
这样的小规模应用，直接用php代码就可实现。
给一个php代码的测试数据
字典中共有 52938 个词（现代汉语常用词表en.txt）
待匹配文件长度 19415 字节（话说长江解说词(删去html成分)）
匹配到词 2300 个
耗时 146.212 毫秒
其中字典加载耗时 146.172 毫秒
折算速度 15,730 词/秒
算法采用 单数组trie
虽然不算很快，但已经是可以接受的了
当然写成扩展更好，速度应该更高
既然是扩展当然就是动态链接库了，加载了就驻留内存。所以你的第二个问题不是问题
像你这样的应用的开发过程大致是这样的：
1、以c/c++完成全部功能模块，配上io就是独立软件
2、书写php扩展函数去调用需要暴露的接口
搜索一个字符串中包含在词表中搜索到的词。
比如词表如下:
---------------
你
他
我
他们
你们
我们
---------------
输入一句话:你、我与他们都是好朋友。
需求为：
1 找出包含在词表中的词。
2 可以通过参数控制
(1)长词优先(找到“他们”了，就不需要再找“他”)
(2)全部返回(“他”和“他们”都找出来)
(3)只找短词(只找“他”)
3 可以通过参数控制
(1)按词表顺序返回
(2)按词序返回(词在句中顺序)
4 可以通过参数控制在需求3的基础上增加个维度，正序或倒序返回
问题一：请问使用何种算法会比较高效？
如果按词表顺序返回，那么就逐行扫描词表，然后使用kmp算法去句中取词，这比较好办。
如果按句中词序返回，先用按词表顺序的方案找一遍，并且记录下每个找到的词在句子中的位置索引，然后再根据索引排序。
但这一步多了个排序，如何不用去排序？我一开始想到先用标准分词，把句子分成词，然后反着去词表查，但有个问题很难保证，就是标准分词我们可能要去使用第三方的，分出的词不一定符合我们词表中的词的规则。因为词表是我们人为手工录入的。有可能会造成这种问题。词表中有一个词是：“屌丝”，但标准分词法会把“屌”和“丝”当成两个词来分。这样反着查就查不到了。
不知有什么更好的方法，请指教。
问题二：词表提体积目前大概有20000左右，不是很大。我想全部放进内存里。但是使用zend提供的emalloc来申请内存或是使用c原生的malloc申请内存还是使用第三方内存数据库系统？
使用emalloc申请内存的优点为php的内存管理可以帮忙管理内存。但缺点为需要占用php本身的大量内存。
使用malloc申请内存的优点我不太清楚，不过貌似缺点是其也会占用php本身的内存，并且很难对内存进行管理，因为可能会造成php本身内存溢出。
使用第三方内存数据库的优点为不会占用php本身的内存，但可能效率上会稍差一些。比如使用redis。需要在php扩展中实现对redis的连接，关闭。
------解决方案--------------------
我猜是一个php-fpm进程一次?
------解决方案--------------------
这样的小规模应用，直接用php代码就可实现。
给一个php代码的测试数据
字典中共有 52938 个词（现代汉语常用词表en.txt）
待匹配文件长度 19415 字节（话说长江解说词(删去html成分)）
匹配到词 2300 个
耗时 146.212 毫秒
其中字典加载耗时 146.172 毫秒
折算速度 15,730 词/秒
算法采用 单数组trie
虽然不算很快，但已经是可以接受的了
当然写成扩展更好，速度应该更高
既然是扩展当然就是动态链接库了，加载了就驻留内存。所以你的第二个问题不是问题
像你这样的应用的开发过程大致是这样的：
1、以c/c++完成全部功能模块，配上io就是独立软件
2、书写php扩展函数去调用需要暴露的接口
