1
jfcherng 2016-02-19 14:54:31 +08:00 1
xian 是不是雙拼呢,應該有不少這種例子
|
3
JiShuTui 2016-02-19 14:59:15 +08:00 1
你是想用 PHP 实现这个功能吗?
其实相当于用词典做中文分词,我讲一个简单思路。 你先把所有的单拼分下类,按照长度分为 1 位、 2 位、 3 位、 4 位、 5 位、 6 位等几类。 然后对于任意一个拼音字符串,举例 alie ,先看他的长度,是 4 位,看看是否是 4 位的单拼,如果不是,继续。 取 alie 的第一个字符 a ,判断是否在 1 位单拼里,如果在的话,判断剩下的 3 位 lie 是否在 3 位单拼里,刚好在,所以是双拼。 |
4
crystom 2016-02-19 15:00:05 +08:00 1
最简单的方法,所有双拼的总数是有限的
|
5
yumijie OP @JiShuTui 这个思路不错,但是如果判断几十万条记录是不是有个效率问题,
我的意思是,每天 com 域名可能有上百万条删除记录,这样判断是不是效率有点低. |
6
gimp 2016-02-19 15:19:23 +08:00 1
比如输入这个“ yolai ”
做一个函数,将其分割为如下形式 # "y" "olai" # "yo" "lai" # "yol" "ai" # "yola" "i" 然后再写一个函数判断他们是否在单拼列表中,如果存在一对都在单拼列表,则返回 true |
7
terence4444 2016-02-19 15:22:45 +08:00 1
这个感觉和编绎原理很像
|
8
JiShuTui 2016-02-19 15:23:48 +08:00 1
@yumijie 你一开始并没有说要高效率
你要高效最简单的就是按照 4 楼说的,把 16 万个双拼域名全部事先生成出来,也按照长度和首字符分类,每来一个要判断的,先看长度,再看首字母,然后直接判断是否在列表中(可以 in_array 也可以 array_key_exists ) |
9
jfcherng 2016-02-19 15:23:57 +08:00 1
如果你追求極限速度,我覺得 crystom 的方法靠譜。
```php function isShuangPing ($str) { static $danPing = [ 'a', 'ai', 'an', 'ang', 'ao', ...... , 'zuo', ]; static $shuangPing = []; // build dictionary if (empty($shuangPing)) { foreach ($danPing as &$first) { foreach ($danPing as &$second) { $shuangPing["{$first}{$second}"] = 1; } } } return array_key_exists($str, $shuangPing); } ``` |
10
yumijie OP |
12
kaiju 2016-02-19 15:26:38 +08:00 1
这个应该是一个很简单的动态规划吧
|
14
cppgohan 2016-02-19 16:02:22 +08:00 1
这个问题有点意思, 不过双拼的数据也分一些双拼表, 比如我用的小鹤双拼, eilo 也属于双拼
|
15
raysonx 2016-02-19 16:08:33 +08:00 via iPad 1
@yumijie 16 万个这种字符串对计算机来说是小数字,现在内存充裕,全部放在内存中使用二分查找或者 trie 树速度非常快
|
16
alioth310 2016-02-19 16:22:26 +08:00
@yumijie gimp 的意思应该是逐位把字符串分割成两段,如果两段内容都在单拼数组里的话,就是双拼。这个开销比 16 万的双拼数组要小。
当然,还可以先判断下: 1) 首尾字母是否满足需求。(首字母不是 iuv ,尾字母应该只能是 aeioung ) 2) 长度是否满足两个双拼的长度要求。(>=2 ,<=12 ) 不过判断这个可能反而增大开销。 |
17
liberize 2016-02-19 16:24:29 +08:00
生成全部双拼存哈希表
|
18
hitmanx 2016-02-19 16:27:33 +08:00
想了一下.假设输入的字符串长度为 n,如果预先穷举好所有的双拼组合 cache 起来,最快用 O(1)的时间就能找到,即一次查表就可以;如果是在 runtime 进行进算,一共有 n - 1 种可能的分割方法,每种分割方法查单拼表也是 O(1)时间,这样最坏情况下是 2(n-1)次查表,相当与复杂度是 O(n).不过由于最长的双拼也就是 6 * 2 = 12 个字符,所以不考虑查表速度的差异\以及表的大小带来的 cache 的 miss rate 等等等各种因素,大概估算起来会慢 20 来倍.不知道有没有算对
|
19
WhoMercy 2016-02-19 16:39:36 +08:00
算法问题,有意思。有点像编译原理中的语法分析。
我的思路是: 一、找出固定出现后必定双拼的词组,如“ yolai ”中的“ ol ”,出现后断定为双拼。 这样的组合理论数量会<<(远小于)列出所有双拼的数量。 二、如果不能保证“一、”中能过滤出所有双拼(或单拼)的话, 可以通过“再过滤”, 将可以预见的特殊字符放入内存,然后逐一对比...对比的方法较多,不一一列举了。 我的方法缺点很明显:前期探索投入的工作量较大。 但是能提高一定的效率,是否值得投入,得看你的任务要求了。 |
20
byron 2016-02-19 16:44:33 +08:00 1
你要考虑双拼有不同的键位
比如我用的就是小鹤双拼,和搜狗双拼、微软等等键位都不一样。 |
21
minongbang 2016-02-19 16:54:22 +08:00 1
|
23
jsq2627 2016-02-19 16:58:07 +08:00 2
一个正则就能搞定的事情,楼上想太多
^((a)|(ai)|(an)|(ang)|(ao)|(ba)|(bai)|(ban)|(bang)|(bao)|(bei)|(ben)|(beng)|(bi)|(bian)|(biao)|(bie)|(bin)|(bing)|(bo)|(bu)|(ca)|(cai)|(can)|(cang)|(cao)|(ce)|(cen)|(ceng)|(cha)|(chai)|(chan)|(chang)|(chao)|(che)|(chen)|(cheng)|(chi)|(chong)|(chou)|(chu)|(chua)|(chuai)|(chuan)|(chuang)|(chui)|(chun)|(chuo)|(ci)|(cong)|(cou)|(cu)|(cuan)|(cui)|(cun)|(cuo)|(da)|(dai)|(dan)|(dang)|(dao)|(de)|(den)|(dei)|(deng)|(di)|(dia)|(dian)|(diao)|(die)|(ding)|(diu)|(dong)|(dou)|(du)|(duan)|(dui)|(dun)|(duo)|(e)|(ei)|(en)|(eng)|(er)|(fa)|(fan)|(fang)|(fei)|(fen)|(feng)|(fo)|(fou)|(fu)|(ga)|(gai)|(gan)|(gang)|(gao)|(ge)|(gei)|(gen)|(geng)|(gong)|(gou)|(gu)|(gua)|(guai)|(guan)|(guang)|(gui)|(gun)|(guo)|(ha)|(hai)|(han)|(hang)|(hao)|(he)|(hei)|(hen)|(heng)|(hong)|(hou)|(hu)|(hua)|(huai)|(huan)|(huang)|(hui)|(hun)|(huo)|(ji)|(jia)|(jian)|(jiang)|(jiao)|(jie)|(jin)|(jing)|(jiong)|(jiu)|(ju)|(juan)|(jue)|(jun)|(ka)|(kai)|(kan)|(kang)|(kao)|(ke)|(ken)|(keng)|(kong)|(kou)|(ku)|(kua)|(kuai)|(kuan)|(kuang)|(kui)|(kun)|(kuo)|(la)|(lai)|(lan)|(lang)|(lao)|(le)|(lei)|(leng)|(li)|(lia)|(lian)|(liang)|(liao)|(lie)|(lin)|(ling)|(liu)|(long)|(lou)|(lu)|(luan)|(lue)|(lun)|(luo)|(ma)|(mai)|(man)|(mang)|(mao)|(me)|(mei)|(men)|(meng)|(mi)|(mian)|(miao)|(mie)|(min)|(ming)|(miu)|(mo)|(mou)|(mu)|(na)|(nai)|(nan)|(nang)|(nao)|(ne)|(nei)|(nen)|(neng)|(ni)|(nian)|(niang)|(niao)|(nie)|(nin)|(ning)|(niu)|(nong)|(nou)|(nu)|(nuan)|(nuo)|(nun)|(o)|(ou)|(pa)|(pai)|(pan)|(pang)|(pao)|(pei)|(pen)|(peng)|(pi)|(pian)|(piao)|(pie)|(pin)|(ping)|(po)|(pou)|(pu)|(qi)|(qia)|(qian)|(qiang)|(qiao)|(qie)|(qin)|(qing)|(qiong)|(qiu)|(qu)|(quan)|(que)|(qun)|(ran)|(rang)|(rao)|(re)|(ren)|(reng)|(ri)|(rong)|(rou)|(ru)|(ruan)|(rui)|(run)|(ruo)|(sa)|(sai)|(san)|(sang)|(sao)|(se)|(sen)|(seng)|(sha)|(shai)|(shan)|(shang)|(shao)|(she)|(shei)|(shen)|(sheng)|(shi)|(shou)|(shu)|(shua)|(shuai)|(shuan)|(shuang)|(shui)|(shun)|(shuo)|(si)|(song)|(sou)|(su)|(suan)|(sui)|(sun)|(suo)|(ta)|(tai)|(tan)|(tang)|(tao)|(te)|(teng)|(ti)|(tian)|(tiao)|(tie)|(ting)|(tong)|(tou)|(tu)|(tuan)|(tui)|(tun)|(tuo)|(wa)|(wai)|(wan)|(wang)|(wei)|(wen)|(weng)|(wo)|(wu)|(xi)|(xia)|(xian)|(xiang)|(xiao)|(xie)|(xin)|(xing)|(xiong)|(xiu)|(xu)|(xuan)|(xue)|(xun)|(ya)|(yan)|(yang)|(yao)|(ye)|(yi)|(yin)|(ying)|(yo)|(yong)|(you)|(yu)|(yuan)|(yue)|(yun)|(za)|(zai)|(zan)|(zang)|(zao)|(ze)|(zei)|(zen)|(zeng)|(zha)|(zhai)|(zhan)|(zhang)|(zhao)|(zhe)|(zhei)|(zhen)|(zheng)|(zhi)|(zhong)|(zhou)|(zhu)|(zhua)|(zhuai)|(zhuan)|(zhuang)|(zhui)|(zhun)|(zhuo)|(zi)|(zong)|(zou)|(zu)|(zuan)|(zui)|(zun)|(zuo)){2}$ 别看这么长,这东西并没有你想象的那么慢。 (试验还不严格,有 random 的影响) |
26
yumijie OP 筛选
|
27
jsq2627 2016-02-19 17:15:31 +08:00
@yumijie 好吧...
$pattern = "^((a)|(ai)|(an)|(ang)|(ao)|(ba)|(bai)|(ban)|(bang)|(bao)|(bei)|(ben)|(beng)|(bi)|(bian)|(biao)|(bie)|(bin)|(bing)|(bo)|(bu)|(ca)|(cai)|(can)|(cang)|(cao)|(ce)|(cen)|(ceng)|(cha)|(chai)|(chan)|(chang)|(chao)|(che)|(chen)|(cheng)|(chi)|(chong)|(chou)|(chu)|(chua)|(chuai)|(chuan)|(chuang)|(chui)|(chun)|(chuo)|(ci)|(cong)|(cou)|(cu)|(cuan)|(cui)|(cun)|(cuo)|(da)|(dai)|(dan)|(dang)|(dao)|(de)|(den)|(dei)|(deng)|(di)|(dia)|(dian)|(diao)|(die)|(ding)|(diu)|(dong)|(dou)|(du)|(duan)|(dui)|(dun)|(duo)|(e)|(ei)|(en)|(eng)|(er)|(fa)|(fan)|(fang)|(fei)|(fen)|(feng)|(fo)|(fou)|(fu)|(ga)|(gai)|(gan)|(gang)|(gao)|(ge)|(gei)|(gen)|(geng)|(gong)|(gou)|(gu)|(gua)|(guai)|(guan)|(guang)|(gui)|(gun)|(guo)|(ha)|(hai)|(han)|(hang)|(hao)|(he)|(hei)|(hen)|(heng)|(hong)|(hou)|(hu)|(hua)|(huai)|(huan)|(huang)|(hui)|(hun)|(huo)|(ji)|(jia)|(jian)|(jiang)|(jiao)|(jie)|(jin)|(jing)|(jiong)|(jiu)|(ju)|(juan)|(jue)|(jun)|(ka)|(kai)|(kan)|(kang)|(kao)|(ke)|(ken)|(keng)|(kong)|(kou)|(ku)|(kua)|(kuai)|(kuan)|(kuang)|(kui)|(kun)|(kuo)|(la)|(lai)|(lan)|(lang)|(lao)|(le)|(lei)|(leng)|(li)|(lia)|(lian)|(liang)|(liao)|(lie)|(lin)|(ling)|(liu)|(long)|(lou)|(lu)|(luan)|(lue)|(lun)|(luo)|(ma)|(mai)|(man)|(mang)|(mao)|(me)|(mei)|(men)|(meng)|(mi)|(mian)|(miao)|(mie)|(min)|(ming)|(miu)|(mo)|(mou)|(mu)|(na)|(nai)|(nan)|(nang)|(nao)|(ne)|(nei)|(nen)|(neng)|(ni)|(nian)|(niang)|(niao)|(nie)|(nin)|(ning)|(niu)|(nong)|(nou)|(nu)|(nuan)|(nuo)|(nun)|(o)|(ou)|(pa)|(pai)|(pan)|(pang)|(pao)|(pei)|(pen)|(peng)|(pi)|(pian)|(piao)|(pie)|(pin)|(ping)|(po)|(pou)|(pu)|(qi)|(qia)|(qian)|(qiang)|(qiao)|(qie)|(qin)|(qing)|(qiong)|(qiu)|(qu)|(quan)|(que)|(qun)|(ran)|(rang)|(rao)|(re)|(ren)|(reng)|(ri)|(rong)|(rou)|(ru)|(ruan)|(rui)|(run)|(ruo)|(sa)|(sai)|(san)|(sang)|(sao)|(se)|(sen)|(seng)|(sha)|(shai)|(shan)|(shang)|(shao)|(she)|(shei)|(shen)|(sheng)|(shi)|(shou)|(shu)|(shua)|(shuai)|(shuan)|(shuang)|(shui)|(shun)|(shuo)|(si)|(song)|(sou)|(su)|(suan)|(sui)|(sun)|(suo)|(ta)|(tai)|(tan)|(tang)|(tao)|(te)|(teng)|(ti)|(tian)|(tiao)|(tie)|(ting)|(tong)|(tou)|(tu)|(tuan)|(tui)|(tun)|(tuo)|(wa)|(wai)|(wan)|(wang)|(wei)|(wen)|(weng)|(wo)|(wu)|(xi)|(xia)|(xian)|(xiang)|(xiao)|(xie)|(xin)|(xing)|(xiong)|(xiu)|(xu)|(xuan)|(xue)|(xun)|(ya)|(yan)|(yang)|(yao)|(ye)|(yi)|(yin)|(ying)|(yo)|(yong)|(you)|(yu)|(yuan)|(yue)|(yun)|(za)|(zai)|(zan)|(zang)|(zao)|(ze)|(zei)|(zen)|(zeng)|(zha)|(zhai)|(zhan)|(zhang)|(zhao)|(zhe)|(zhei)|(zhen)|(zheng)|(zhi)|(zhong)|(zhou)|(zhu)|(zhua)|(zhuai)|(zhuan)|(zhuang)|(zhui)|(zhun)|(zhuo)|(zi)|(zong)|(zou)|(zu)|(zuan)|(zui)|(zun)|(zuo)){2}$"; if (preg_match($pattern, "xian")) { echo "匹配"; } 打算付费多少 |
32
yumijie OP @jsq2627 刚才调试了下,可以用了.
<?php $pattern = '/^((a)|(ai)|(an)|(ang)|(ao)|(ba)|(bai)|(ban)|(bang)|(bao)|(bei)|(ben)|(beng)|(bi)|(bian)|(biao)|(bie)|(bin)|(bing)|(bo)|(bu)|(ca)|(cai)|(can)|(cang)|(cao)|(ce)|(cen)|(ceng)|(cha)|(chai)|(chan)|(chang)|(chao)|(che)|(chen)|(cheng)|(chi)|(chong)|(chou)|(chu)|(chua)|(chuai)|(chuan)|(chuang)|(chui)|(chun)|(chuo)|(ci)|(cong)|(cou)|(cu)|(cuan)|(cui)|(cun)|(cuo)|(da)|(dai)|(dan)|(dang)|(dao)|(de)|(den)|(dei)|(deng)|(di)|(dia)|(dian)|(diao)|(die)|(ding)|(diu)|(dong)|(dou)|(du)|(duan)|(dui)|(dun)|(duo)|(e)|(ei)|(en)|(eng)|(er)|(fa)|(fan)|(fang)|(fei)|(fen)|(feng)|(fo)|(fou)|(fu)|(ga)|(gai)|(gan)|(gang)|(gao)|(ge)|(gei)|(gen)|(geng)|(gong)|(gou)|(gu)|(gua)|(guai)|(guan)|(guang)|(gui)|(gun)|(guo)|(ha)|(hai)|(han)|(hang)|(hao)|(he)|(hei)|(hen)|(heng)|(hong)|(hou)|(hu)|(hua)|(huai)|(huan)|(huang)|(hui)|(hun)|(huo)|(ji)|(jia)|(jian)|(jiang)|(jiao)|(jie)|(jin)|(jing)|(jiong)|(jiu)|(ju)|(juan)|(jue)|(jun)|(ka)|(kai)|(kan)|(kang)|(kao)|(ke)|(ken)|(keng)|(kong)|(kou)|(ku)|(kua)|(kuai)|(kuan)|(kuang)|(kui)|(kun)|(kuo)|(la)|(lai)|(lan)|(lang)|(lao)|(le)|(lei)|(leng)|(li)|(lia)|(lian)|(liang)|(liao)|(lie)|(lin)|(ling)|(liu)|(long)|(lou)|(lu)|(luan)|(lue)|(lun)|(luo)|(ma)|(mai)|(man)|(mang)|(mao)|(me)|(mei)|(men)|(meng)|(mi)|(mian)|(miao)|(mie)|(min)|(ming)|(miu)|(mo)|(mou)|(mu)|(na)|(nai)|(nan)|(nang)|(nao)|(ne)|(nei)|(nen)|(neng)|(ni)|(nian)|(niang)|(niao)|(nie)|(nin)|(ning)|(niu)|(nong)|(nou)|(nu)|(nuan)|(nuo)|(nun)|(o)|(ou)|(pa)|(pai)|(pan)|(pang)|(pao)|(pei)|(pen)|(peng)|(pi)|(pian)|(piao)|(pie)|(pin)|(ping)|(po)|(pou)|(pu)|(qi)|(qia)|(qian)|(qiang)|(qiao)|(qie)|(qin)|(qing)|(qiong)|(qiu)|(qu)|(quan)|(que)|(qun)|(ran)|(rang)|(rao)|(re)|(ren)|(reng)|(ri)|(rong)|(rou)|(ru)|(ruan)|(rui)|(run)|(ruo)|(sa)|(sai)|(san)|(sang)|(sao)|(se)|(sen)|(seng)|(sha)|(shai)|(shan)|(shang)|(shao)|(she)|(shei)|(shen)|(sheng)|(shi)|(shou)|(shu)|(shua)|(shuai)|(shuan)|(shuang)|(shui)|(shun)|(shuo)|(si)|(song)|(sou)|(su)|(suan)|(sui)|(sun)|(suo)|(ta)|(tai)|(tan)|(tang)|(tao)|(te)|(teng)|(ti)|(tian)|(tiao)|(tie)|(ting)|(tong)|(tou)|(tu)|(tuan)|(tui)|(tun)|(tuo)|(wa)|(wai)|(wan)|(wang)|(wei)|(wen)|(weng)|(wo)|(wu)|(xi)|(xia)|(xian)|(xiang)|(xiao)|(xie)|(xin)|(xing)|(xiong)|(xiu)|(xu)|(xuan)|(xue)|(xun)|(ya)|(yan)|(yang)|(yao)|(ye)|(yi)|(yin)|(ying)|(yo)|(yong)|(you)|(yu)|(yuan)|(yue)|(yun)|(za)|(zai)|(zan)|(zang)|(zao)|(ze)|(zei)|(zen)|(zeng)|(zha)|(zhai)|(zhan)|(zhang)|(zhao)|(zhe)|(zhei)|(zhen)|(zheng)|(zhi)|(zhong)|(zhou)|(zhu)|(zhua)|(zhuai)|(zhuan)|(zhuang)|(zhui)|(zhun)|(zhuo)|(zi)|(zong)|(zou)|(zu)|(zuan)|(zui)|(zun)|(zuo)){2}$/'; $file = file_get_contents("domain.txt","r"); $shuangpin =array(); $qita =array(); $lines = explode("\n", $file); foreach ($lines as $values) { if (preg_match($pattern, $values)) { $shuangpin[] = $values; } else { $qita[] = $values; } } $shuangpin = implode("\n", $shuangpin); $qita = implode("\n", $qita); file_put_contents('shuangpin.txt', $shuangpin); file_put_contents('qita.txt', $qita); ?> |
33
v3aqb 2016-02-20 02:52:09 +08:00 via Android
{声母: set([声母可对应的韵母])}, O(n)
|