欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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

程序员文章站 2022-04-21 20:56:26
...
请教算法和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扩展函数去调用需要暴露的接口
请问算法和php扩展的相关疑问

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

相关文章

相关视频


网友评论

文明上网理性发言,请遵守 新闻评论服务协议

我要评论
  • 请问算法和php扩展的相关疑问
  • 专题推荐