当前位置:Gxlcms > PHP教程 > 请问算法和php扩展的相关疑问

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

时间:2021-07-01 10:21:17 帮助过:14人阅读

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

人气教程排行