作者mander (阿平)
看板Perl
标题[讨论] 检查任意的字母组合能拼成哪些字
时间Fri Apr 11 10:49:21 2008
各位好,第一次发文
这个问题有一些基本的想法提出来与大家讨论效果的优劣
我想要输入一组任意的字母组合(想是 C L E A R E H )
字母组合中不考虑顺序、大小写,字母可能出现多次(E出现两次)
程式检查有哪些单字能用上面列出的字母组合拼出来
例如以上的组合可能会跑出如clear,hear,reel,real,heal,rec...的列表
现在已经产生一个字典档dic.txt了
请问各位会怎麽考虑写这个查询的程式呢?
现把小弟粗略的想法提出来
想法挺简单的,就先建一个可供查询的索引,再查是否单字在其中
A.建索引
1.字典档中每个单字都建编号
2.对每个字母(a-z),建一个参照表
检查单字中出现了哪些字母,在参照表中加入有出现单字的整数编号W(k)
B.查询
1.查询的时候把输入字串中包含哪些字母,将字母参照表中的W(k)
放到一个array A或hash H中,
是在hash中的话key-valur pair的key是W(k),value则每符合一个字母就加一
2.对hash H依照value排序(这里会有问题value值可能不唯一)
然後照value值大小输出W(k)
3.印出W(k)对应的单字
以上想法实在始有够简单,感觉在查询的时候效率会很差
hash H在遇到字母AEIOU这种的时候会变大很多
边写的时候发现以上其实就是invertd file & boolean search的做法 XD
只是是字母版的
希望能够抛砖引玉,有更好的想法一起讨论
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.104.108.136
1F:推 threecia:已经有字典档, 直接对档案内容做过滤不是更快吗? 04/11 22:23
2F:→ threecia:反正你会产生的单字也逃不出这个字典档的范围 04/11 22:24
3F:→ mander:的确 因为母音的重叠范围过大 直接扫瞄所有内容会比 04/22 11:47
4F:→ mander:较快 预先做索引的好处便消失了 04/22 11:50