字典搜索，急需，请尽快！
有一英文字典文件，单词按字母排序以纯文本方式储存，请问有什么好的方法，搜索到指定词条。请注意字典非常庞大——600万单词、每个单词一行，不能使用数据库。请提出详细算法，并比较若干算法优劣。急需，请尽快。 问题点数：300、回复次数：29Top
1 楼iamxia（）回复于 2001-07-11 10:52:27 得分 0
用二分查找试试Top
2 楼songhtao（三十年孤独）回复于 2001-07-11 10:53:13 得分 0
说过了，但经理不满意。要求节省内存，速度快。Top
3 楼wjzhuang（程序猪）回复于 2001-07-11 10:57:47 得分 150
分级存储Top
4 楼iamxia（）回复于 2001-07-11 10:58:57 得分 50
试试分块查找怎么样Top
5 楼songhtao（三十年孤独）回复于 2001-07-11 11:01:41 得分 0
分块多级索引查找提过了，但经理未置可否。
要求考虑到内存碎片，和速度，另外请注意词条很多，不能一次输入内存。Top
6 楼iamxia（）回复于 2001-07-11 11:05:52 得分 0
如果不行，那我得想想。Top
7 楼wjzhuang（程序猪）回复于 2001-07-11 11:14:13 得分 0
不用一次输入内存,分级的话还要有一个index文件,存储词条位置Top
8 楼iamxia（）回复于 2001-07-11 11:15:17 得分 0
wjzhuang(醉里挑灯看剑--程序猪,说的对Top
9 楼songhtao（三十年孤独）回复于 2001-07-11 11:20:46 得分 0
怎么分级呀？详细点好吗？Top
10 楼gqxs（我心㊣飞翔）回复于 2001-07-11 11:24:25 得分 0
关注Top
11 楼iamxia（）回复于 2001-07-11 11:24:58 得分 0
可以26字母分级，也可以按单词量来分级，方法很多。Top
12 楼iamxia（）回复于 2001-07-11 11:27:11 得分 0
只要保证后面分级的都比排在前面的小或大（指ASCII）Top
13 楼luhongjun（过江项羽）回复于 2001-07-11 11:29:21 得分 100
使用流的方式，然后建立索引。索引文件非常小，全部掉入掉入内存也不是很站地方。
Top
14 楼iamxia（）回复于 2001-07-11 11:32:56 得分 0
附，定义,希望对你有帮助。
分块查找是把表分成若干块，每块中的记录顺序是任意的，但块与块之间必须按照关键码有序，即第一块中任意一条记录的关键码都小于第二块中记录的关键码，而第三块中的小于第二......。
Top
15 楼songhtao（三十年孤独）回复于 2001-07-11 11:38:14 得分 0
单词长度不一致，建索引有困难。请教具体怎么建呀。Top
16 楼wjzhuang（程序猪）回复于 2001-07-11 11:53:17 得分 0
以字母分级,然后再比较多的字母,比如:a,b,c,d,e,p,这些字母还可以再次分级
具体要以何种标准来分级和分级的临界点你看看你的功能需要
使用链表或者哈希表可以解决长度问题
我以前好像有建过一个,就是几个数据结构的全套,具体的结构我现在记不得了Top
17 楼songhtao（三十年孤独）回复于 2001-07-14 14:42:46 得分 0
我是这样回答的，经理没说什么，要我参加项目，请大家帮我分析一下看看有什么问题。
字典搜索软件概要设计
1．引言
1.1 项目名称：
项目名称：字典搜索。
1.2 项目背景和内容概要：
1. 负 责 人：宋红涛
2. 内容概要：英文字典文件，单词按字母排序以纯文本方式储存。字典非常庞大——600
万单词、每个单词一行，不能使用数据库。
1.3 项目目的：
从大英文字典文件中快速搜索到指定单词
2.概要设计
2.1基本设计概念和处理流程
1.数据分块法。
1. 内存中建立若干固定大小数组，数组元素为指向单词字符串的指针。
2. 从文件拷贝单词到数组。
3. 采用分块查找法——块内无需有序，因为单词按字母排序，所以块内单词有序。块
内按二分法查找。
4. 块间有序，待查字符串与最后块最后一条记录比较，在块中，再匹配各块查找。否则，内存中无待查单词，从文件读入后续数据到内存。
5. 重复2-4直到单词查到或查找失败。
优点：算法简单，有一定效率。
缺点：可能造成内存碎片。但可通过定期内存重组解决。有一定磁盘访问次数，可能降低效率，但可通过调整分块数和分块大小优化。
2. 分级索引法
1. 为英文字典建立索引文件
2. 索引文件格式：
单词（定长字符串） 单词偏移量（长整数）
3. 读索引到内存一个表中
4. 查找索引，找到单词在文件中存在范围。
5. 直接在文件中查找单词是否存在。
6. 可采用多级索引，把索引存到内存，提高效率，尽量减少访问磁盘次数。
优点：效率高，速度快。
缺点：需要进行索引维护，索引的建立方式对性能影响较大，需要着重考虑。
3. 局部缓存法
1． 建立一小文件缓存经常访问的单词
2． 利用高速缓存匹配算法查找单词。
优点：20%的单词访问概率为80%极大的提高访问速度
缺点：高速缓存算法有多种，需要适当选择，建议采用自组织线性表法（1.移至顶端、2.交换、3.频率计数（不推荐）），实践证明简单、有效。
补充：最好和其他算法综合使用，以便一旦高速缓存未命中，也能较快的查找或证明查找失败。
4．查找树法
1. 建立B/B+树。
2. 叶为单词在文件中的偏移量，分子节点存储关键字。
优点：适合大量数据的快速查找，尤其是数据库。
缺点：算法较复杂，关键字的选择特别重要。
5．散列表法
优点：精确匹配效率高
缺点：不改变字典文件结构，我不知道实现。拟单词定长，因为是根据单词找地址，因此查找效率高，但插入删除涉及到大量磁盘i/o效率会极低，只能在后台进行。最后散列函数的选择是一个重点。
3.说明
时间仓促，来不及仔细考虑，也未涉及到具体实现。只是一个不完善的思路。
Top
18 楼songhtao（三十年孤独）回复于 2001-07-16 12:30:16 得分 0
请大家帮我看看呀。Top
19 楼wjzhuang（程序猪）回复于 2001-07-16 14:19:04 得分 0
写得很好呀~~~~~~~~
我乱说一些自己的看法,当成抛砖引玉就是了
方法1:我觉得比较笨重
方法2:应该和方法3结合使用
方法4:很不错的想法,关键字不知道使用字典的可以吗(就是出现在页右上角的那个)
方法5:文件存储结构就不能像你描述的那样了
大家快来看,这个题目很好的
Top
20 楼songhtao（三十年孤独）回复于 2001-07-16 15:24:44 得分 0
wjzhuang(醉里挑灯看剑--程序猪)
方法5:文件存储结构就不能像你描述的那样了
你是指我算法中的，还是指：
2. 内容概要：英文字典文件，单词按字母排序以纯文本方式储存。字典非常庞大——600 万单词、每个单词一行，不能使用数据库。
呀
Top
21 楼wjzhuang（程序猪）回复于 2001-07-16 15:37:44 得分 0
我是指
"英文字典文件，单词按字母排序以纯文本方式储存。字典非常庞大——600 万单词、每个单词一行"
这里内存结构应该是和文件一样的,不然又要建立一个index文件,这里用index不划算Top
22 楼sephil（NAILY Soft 【哈里波特大】）回复于 2001-07-16 15:48:07 得分 0
sephil无精打采的走了进来
有气无力的抬头看了看
又垂着头，无精打采的出去了
众人回头看时
依稀见他肩头扛着一块大木牌
上面似乎写着：
心情不好 无心答题Top
23 楼songhtao（三十年孤独）回复于 2001-07-16 16:18:41 得分 0
wjzhuang(醉里挑灯看剑--程序猪
同意Top
24 楼songhtao（三十年孤独）回复于 2001-07-18 20:40:18 得分 0
抛出了一块砖头，请大家来指正。Top
25 楼wjzhuang（程序猪）回复于 2001-07-19 09:29:46 得分 0
我来提提,这个问题很值得讨论Top
26 楼songhtao（三十年孤独）回复于 2001-07-20 20:58:30 得分 0
还请指点Top
27 楼wjzhuang（程序猪）回复于 2001-07-20 23:24:27 得分 0
up!Top
28 楼wjzhuang（程序猪）回复于 2001-07-20 23:25:36 得分 0
好的建议和说明我另加300分
另：孤独兄，刷新一下，有人找你Top
29 楼mailprint1（）回复于 2002-06-20 08:47:13 得分 0
每行定长
单词排序
用TFileStream
用 Position 2分查找Top
