关于双数组trie树实现中汉字编码的问题

[liugang]

我想用双数组trie树实现ictclas4j的词典，首先碰到的问题的是如何给汉字生成相应的序列码，以便放到数组中去。

如果仅对常用的6737个汉字，很容易，这些汉字的GB2312编码都是连续的，直接映射到1-6737就可以。但我想支持非GB2312的汉字，如果用unicode编码的话，常用的6000多个汉字不是连续的，很浪费空间。

 

想问问这块大家都是怎么做的？提个建议，非常感谢！

--
Yours sincerely
liugang

[Dancefire]

我建议直接用Unicode，不必关心空间连续问题，那反而增加复杂度。UCS2中汉字包含了20000多个，占了3分之一的空间，这还不包含数字标点符号之类的。算不上太浪费空间。先做出来看看空间占用情况，我感觉不会很严重。如果真是不可接受，再进行优化。让一个正确的程序高效，比让一个高效的程序正确要简单的多。

2009/4/2 liugang <liug...@gmail.com>:

--
Tao Wang
Microsoft Certified Technology Specialist
CCNA

[liugang]

感觉ucs2里的汉字虽然有20000多个，但大部分都是不常用的，很少出现在词典中，所以感觉有可能浪费空间。不过也不一定，我先测试下看看

2009/4/2 Dancefire <danc...@gmail.com>

--
Yours sincerely
liugang

[Teng Ren]

unicode的汉字是连续的,0x4e00--0x9fa5,可以直接设一个数组大小是0x9fa5-0x4e00+1,设一个偏移量查询就可以了.

2009/4/2 liugang <liug...@gmail.com>

[Dancefire]

Unicode的汉字不是连续的。包括，

CJK Radicals Supplement (2E80-2EFF)
CJK Symbols and Punctuation (3000-303F)
Enclosed CJK Letters and Months (3200-32FF)
CJK Compatibility (3300-33FF)
CJK Unified Ideographs Extension A (3400-4DBF)
CJK Unified Ideographs (4E00-9FFF)
CJK Compatibility Ideographs (F900-FAFF)
CJK Compatibility Forms (FE30-FE4F)
CJK Unified Ideographs Extension B (20000-2A6DF)
CJK Compatibility Ideographs Supplement (2F800-2FA1F)

等等。请参看：

http://orwell.ru/test/Unicode/
http://blog.oasisfeng.com/2006/10/19/full-cjk-unicode-range/

2009/4/2 Teng Ren <sjtu.r...@gmail.com>:

[liugang]

关键是6768个常用汉字不是连续的，其实字典里其他汉字很少出现的。我现在采取的方法是采用GBK的编码。GBK/3对应的6768个汉字编码为从0~6767，GBK的其他汉字从6768往后排。

 

占用空间大小写好代码了测试看看

2009/4/2 Dancefire <danc...@gmail.com>

--
Yours sincerely
liugang

[Dancefire]

问题是你写的是字典索引结构，不能出现无法表现的字。几率虽然小，但是万一出现怎么办呢？比如说人名字典、地名字典都经常出现非常奇怪的字。既然是词典索引结构，就不能说出现用户输入的词，根本无法建立索引的情况。

而且，用Unicode真的很费空间么？根据DATrie的结构看，其本身就是有不少空洞的，另一方面它也是增长性的，因此如果词典中怪异字不怎么出现，也不会浪费很多空间。我是建议不要在这个上面浪费精力，确保实现是无bug的最重要。

不过做个测试，查看一下将几十万词建立DATrie索引后，不同的编码方式的大小绝对数值和相对数值是多少。内存中，对于几十万词来说，50MB以下应该不是太大的问题。如果使用Unicode超过了200MB，而使用GBK在50MB以内，这个优化才有意义。否则如果都在50MB以内，这不是什么问题。毕竟内存中只有一个词典，就算是多线程程序，词典由于是只读，那么多线程同时读取也不会有什么问题。

2009/4/3 liugang <liug...@gmail.com>: