请问算法和php扩展的相关疑问

程序员文章站 2022-03-30 21:37:39

...

请教算法和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扩展函数去调用需要暴露的接口