V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
supersheep
V2EX  ›  Node.js

一个简单的穷举

  •  
  •   supersheep · 2013-06-30 11:53:10 +08:00 · 3307 次点击
    这是一个创建于 4176 天前的主题,其中的信息可能已经有所发展或是发生改变。
    最近疯狂猜图很火,于是想有没有办法通过穷举自动识别出可能的组合。写的时候发现算法什么的都还给老师了,比如有n个可选字,组成一个m位数的词,当中不能有重复,感觉有点像n皇后问题,反正倒腾了半天没搞定,弱爆了。今天早上想到拿进制来做,其实道理一样的,不过代码会变得简单清晰很多,简单讲就是把递增的i转成一个m位的n进制数。

    大致就是这样:

    http://gist.github.com/supersheep/5893777.js

    现在觉得数量还是太大了,无从判断,拿来发douban api一下子access rate limit就爆掉了,所以有必要有个本地词库拿来扫一下,可以组成词组的字占一半以上才列入考虑。有兴趣的同学可以继续尝试一下看看咯。
    5 条回复    1970-01-01 08:00:00 +08:00
    csx163
        1
    csx163  
       2013-06-30 13:18:57 +08:00
    感觉还是要词库,里面大部分都是能连接的字符
    Golevka
        2
    Golevka  
       2013-06-30 15:02:29 +08:00
    把字典组织成trie的形式, 把待匹配的字符集中取出一个元素作为首字母然后用类似递归下降的方式匹配剩余的部分. 目测剪枝能力还是可以的, 至少比穷举要好得多
    Ricepig
        3
    Ricepig  
       2013-06-30 19:11:52 +08:00 via iPhone
    字根表就行了
    supersheep
        4
    supersheep  
    OP
       2013-06-30 20:33:42 +08:00
    @Golevka 嗯,多谢,回头试试看。
    @Ricepig 字根表是什么意思?google搜到的都是五笔相关的内容。和Golevka是一个意思么?
    Ricepig
        5
    Ricepig  
       2013-06-30 23:14:30 +08:00
    @supersheep 额,不好意思我词不达意了,我当时的意思是词根。英文里用的比较多,比如说什么前缀,什么后缀大概能表达一个什么意思。这样不用多大的库,剪枝效果就很好了。

    字典当然更好,不过对字典的要求比较高,另外就是高质量的字典可能本身也不小了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3594 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 04:41 · PVG 12:41 · LAX 20:41 · JFK 23:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.