怎样判断字符串是否是双拼？

[yumijie]

比如说：

alie //是
aliex //不是

olai //是
olain //不是

oupai //是
onpai //不是

eiyuan //是
eilo //不是

yolai //是
yoei //是

当然我有单拼列表，问题是怎样筛选。不懂编程的人没思路更不懂下手，可以付费.......
单拼列表:
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

[jfcherng]

xian 是不是雙拼呢，應該有不少這種例子

[yumijie]

@jfcherng 是双拼的，当然也是单拼

[JiShuTui]

你是想用 PHP 实现这个功能吗？
其实相当于用词典做中文分词，我讲一个简单思路。

你先把所有的单拼分下类，按照长度分为 1 位、 2 位、 3 位、 4 位、 5 位、 6 位等几类。

然后对于任意一个拼音字符串，举例 alie ，先看他的长度，是 4 位，看看是否是 4 位的单拼，如果不是，继续。
取 alie 的第一个字符 a ，判断是否在 1 位单拼里，如果在的话，判断剩下的 3 位 lie 是否在 3 位单拼里，刚好在，所以是双拼。

[crystom]

最简单的方法，所有双拼的总数是有限的

[yumijie]

@JiShuTui 这个思路不错，但是如果判断几十万条记录是不是有个效率问题，
我的意思是，每天 com 域名可能有上百万条删除记录，这样判断是不是效率有点低.

[gimp]

比如输入这个“ yolai ”
做一个函数，将其分割为如下形式

# "y" "olai"
# "yo" "lai"
# "yol" "ai"
# "yola" "i"

然后再写一个函数判断他们是否在单拼列表中，如果存在一对都在单拼列表，则返回 true

[terence4444]

这个感觉和编绎原理很像

[JiShuTui]

@yumijie 你一开始并没有说要高效率
你要高效最简单的就是按照 4 楼说的，把 16 万个双拼域名全部事先生成出来，也按照长度和首字符分类，每来一个要判断的，先看长度，再看首字母，然后直接判断是否在列表中（可以 in_array 也可以 array_key_exists ）

[jfcherng]

如果你追求極限速度，我覺得 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);
}
```

[yumijie]

@gimp 哦我理解你的意思，就是把双拼组合做成一个数组，然后看要检验的字符串是否在数组中，在就是双拼，不再就不是。

问题是双拼有 16 万多个啊，我想提高点效率

[yumijie]

@jfcherng 没有好的方法就用这个方法了，

[kaiju]

这个应该是一个很简单的动态规划吧

[kaiju]

@kaiju oops 看成如何判断是否是拼音了

[cppgohan]

这个问题有点意思, 不过双拼的数据也分一些双拼表, 比如我用的小鹤双拼, eilo 也属于双拼

[raysonx]

@yumijie 16 万个这种字符串对计算机来说是小数字，现在内存充裕，全部放在内存中使用二分查找或者 trie 树速度非常快

[alioth310]

@yumijie gimp 的意思应该是逐位把字符串分割成两段，如果两段内容都在单拼数组里的话，就是双拼。这个开销比 16 万的双拼数组要小。

当然，还可以先判断下：
1) 首尾字母是否满足需求。（首字母不是 iuv ，尾字母应该只能是 aeioung ）
2) 长度是否满足两个双拼的长度要求。（>=2 ，<=12 ）
不过判断这个可能反而增大开销。

[liberize]

生成全部双拼存哈希表

[hitmanx]

想了一下.假设输入的字符串长度为 n,如果预先穷举好所有的双拼组合 cache 起来,最快用 O(1)的时间就能找到,即一次查表就可以;如果是在 runtime 进行进算,一共有 n - 1 种可能的分割方法,每种分割方法查单拼表也是 O(1)时间,这样最坏情况下是 2(n-1)次查表,相当与复杂度是 O(n).不过由于最长的双拼也就是 6 * 2 = 12 个字符,所以不考虑查表速度的差异\以及表的大小带来的 cache 的 miss rate 等等等各种因素,大概估算起来会慢 20 来倍.不知道有没有算对

[WhoMercy]

算法问题，有意思。有点像编译原理中的语法分析。
我的思路是：
一、找出固定出现后必定双拼的词组，如“ yolai ”中的“ ol ”，出现后断定为双拼。
这样的组合理论数量会<<（远小于）列出所有双拼的数量。

二、如果不能保证“一、”中能过滤出所有双拼（或单拼）的话，
可以通过“再过滤”，
将可以预见的特殊字符放入内存，然后逐一对比...对比的方法较多，不一一列举了。

我的方法缺点很明显：前期探索投入的工作量较大。
但是能提高一定的效率，是否值得投入，得看你的任务要求了。

[byron]

你要考虑双拼有不同的键位
比如我用的就是小鹤双拼，和搜狗双拼、微软等等键位都不一样。

[minongbang]

一看就知道楼主是想用来找域名。
有的看起来不是双拼，但是那确实是，只是那些音用的极少。
http://minongbang.com/?jipin=2

[JiShuTui]

@byron @cppgohan 楼主的双拼是指双拼域名，也就是两个汉字的拼音组成的两（双）拼

[jsq2627]

一个正则就能搞定的事情，楼上想太多

^((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 的影响）

[yumijie]

@jsq2627 内什么，我只看得懂 PHP,js 都看不懂，悲剧

[yumijie]

@byron 不用考虑什么键位，我是晒现双拼域名

[yumijie]

筛选

[jsq2627]

@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 "匹配";
}

打算付费多少

[yumijie]

@jsq2627 哈哈，你要多少红包？！！！

[byron]

@yumijie 噗，我以为是双拼输入法。

[yumijie]

@jsq2627 兄弟,这个不行的，直接报错了，

[jsq2627]

@yumijie 把 if 里面的改成
preg_match("/".$pattern."/", "xian")

[yumijie]

@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);
?>

[v3aqb]

{声母: set([声母可对应的韵母])}， O(n)