：creation-zy, 时间：2001-5-3 18:33:12, ID：521534
我想到了一个主意，有可能在数量级上提高一般全文搜索的时间：
针对每个数据自动生成一个包含256个Boolean变量的数组，若数据的正文中含有ASCII码为i的字符，
则此数组的第i个元素的值为true，反之为false。如此一来，每次进行全文检索的时候，
先按顺序在每个数据项的数组表中查找，若发现其中包含查找目标的全部ASCII，则将其加入待查对象列表，
在针对数组表的搜索结束之后，再对待查对象列表中的对象进行真正的全文搜索，得到最终结果。
针对chm的"单词检索"功能，我认为还有一种方法，可以提高用e文单词作为关键字时的检索速度：
对每个数据进行分析，将遇到的单词（也就是连续的e文序列）提取出来，对其进行hash运算，
运算的结果范围控制在2^8到2^11以内，这样，若检索的对象是e文单词，就可以先在hash表里进行快速匹配，
据我的估计，平均可以过滤掉80%以上的数据。
如果使用我上面所说的两个方案，针对每个数据项只要增加2^9到2^11+2^8 Bit的信息（也就是300 Byte不到），就可以实现全文检索
速度的数量级上的提高。
：mikedeakins, 时间：2001-5-4 0:43:31, ID：521671
索引算法，Hash Table + B-Tree。其实 .chi 文件也是符合 .chm 格式的，不过每一页
的页面信息被替换成了指向 B-Tree 的 Root（瞎说的，不过没有第二种设计方案了，
对吗？），这样在进行全文检索的时候就可以很方便地定位检索结果在 .chm 中的位置。
这种算法应当和商用数据库中广泛使用的索引算法没有什么区别，只不过 Html Help 把
文档中的每一个单词（远东语言比如中文、日文、韩文这种不用空格区分单词的部分可能
是取几个字作为一个单词，反正是 Hash 算法，不成问题）。
以上内容均属瞎猜（".chi 文件也是符合 .chm 格式的"除外），如果我设计 Html Help
就只能这么干了，还要听一听诸位的高见。
：creation-zy, 时间：2001-5-5 13:46:08, ID：522481
to mikedeakins:
您能否把"指向 B-Tree 的 Root"说得更具体一点，我看不大明白。（我数据结构学得不好，见谅 :)）
我想过了，认为我的第一条方案不大可行，ASCII码重叠的几率太高了，估计只能过滤掉10%不到的贴子。
用过了JBuilder的Help以后，发现它的方法比较好--事先将所有关键词都列举出来，并且针对每个关键字
生成了一个表，存放含有此关键词的文章的ID号。我估算了一下，大约有32K个关键词，平均每个关键词关联
的文章大约为10篇，以每个ID占4Byte计算，占用空间为1280K--不是很大。
它的方案用于e文检索无疑是非常先进的，但我认为若将其运用于中文检索需要进行一些改进：
在e文中，提取单词时轻而易举的事情，但在中文里非常困难，因此，建议将每两个汉字作为一个单词
（两个以上的汉字可以被拆分为若干个两个汉字的组合），因为汉字（GB码）的ASCII码的分布范围是
160-255，因此两个汉字的可能组合约为8.5e+7，80多M！--而我估计实际上的组合数应该在1.0e+7左右
（3000个常用汉字的组合），甚至更小。为了使Hash表的大小可以为我们所接受，有必要对其进行hash
运算，但是hash运算存在着一个问题--值域越大hash表就越大，发生重叠的概率就越小；值域越小hash
表就越小，但发生重叠的机会就会大大增加。
在进行估算之前，让我们先估算一下一些要用到的参考数据：
现在大富翁论坛中大约有50000个问题贴子，根据离线数据库130M的大小看来，认为其中贴子的内容
所占空间大约为100M，这样，平均每个问题贴子（包括跟贴）占2k。假设平均在每个贴子中有200个汉字，
又设重复率为50%，则每篇文章（即问题贴子以及它的跟贴）中出现的两个汉字的组合数为200。又设这些
组合中80%属于常用组合，则总的组合数应该在600000个左右（包括约100000个常用组合），而平均每个
组合对应有20个贴子。（常用组合所对应文章的数量可能还要多出好几十倍！）。
根据以上计算的结果，若hash算法较为理想--即分布较为均匀，当值域为0-256时，重叠的率约为2000:1
--这显然是不行的；当值域为0-65535时，重叠率约为10:1。
根据上面的结论，即使将值域设为64K，还是很可能多搜索好几倍的文章！如果将值域再次增大，
就会造成hash表过大，不利于存储和传输。
为了解决这个矛盾，我认为应当采用多个hash表的方案：
先建立多个hash表，值域都为64k，但它们采用的hash算法不同。在具体搜索时将它们得到的结果
集合进行求交运算，就可以极大的降低无关文章所占的比例！
应用了多hash表的方案之后，可以在不在数量级上增加hash表的总体大小的情况下极大的减少
无关结果的出现率，如果使用得法，还可以同时减小hash表的大小和提高搜索精度（我认为用两个
值域为16k的hash表的搜索精度比单独的64k的hash表要高得多）。
下面是一个应用两个hash表搜索的例子：
搜索目标： 关系数据库
1.将汉字拆分成两个一组： 关系 系数 数据 据库
2.按顺序搜索汉字组合
2.1.1搜索目标： 关系
2.1.2在hash表1中搜索"关系"的hash1值，得到集合A1
2.1.3在hash表2中搜索"关系"的hash2值，得到集合B1
2.1.4"关系"的结果集合 R1=A1与B1的交集
2.2.1搜索目标： 系数
...
...
2.4.4"据库"的结果集合 R4=A4与B4的交集
3.搜索集合 R_=R1、R2、R3、R4的交集
4.在R_中搜索字符串"关系数据库"，得到最终结果集合R
5.End.
：mikedeakins, 时间：2001-5-5 14:58:17, ID：522527
B-Tree 是一种用在海量数据中的索引算法，类似于二分树。我觉得 hh 根据每一个网页
生成了一个 b-tree，b-tree 有一个根节点，从这里可以遍历整个树。
字符串全文检索没有多少算法，基本上就只有 hash-table 和 b(b+)-tree。实际上，如果
使用 hash-table 可以使用 64-bit 索引的表（值域 0 - 2 ^ 64 - 1）。远东语言可以
直接存储四个字，字母语言使用 hash 算法将值域落在非远东语言区间，并且存储采用类似
于稀疏数组的有序存储方式。压缩方法是将 hash-table 分块压缩。检索可以使用二分检索
或者跳跃检索。
b-tree 的特点是修改起来比较方便，不过对于 hh 不太适用。
：DoubleWood, 时间：2001-5-6 7:05:45, ID：522934
CHM快其实也就在于索引。
其实CHM的分词没有那么复杂，对于英文就是一个"Word"，Word
之间以空格分隔。对于中文一个汉字就是一个词，然后加上判断是否
连续。
试查一下"题问"和"题 问"就可以看出来乐。那么其实用到的
中文也就只是几千个而已。
其实在Delphi中，看看Memo吧，如果使用自动换行，换行的依据
是词，可以清楚的看到对于中文一个汉字就是一个词，而英文是以空
格作为词的分隔。CHM分词的原理也是如此。
Hash-Table是一定要用的，没什么好说，因为那是最快的检索办
法，具体就是实现的算法而已。据说好的算法可以实现GB级数据的秒
级检索。
：creation-zy, 时间：2001-5-6 10:35:58, ID：523036
to DoubleWood:
我试验了一下，的确，chm的分词是以单独的汉字为基础的，这个绝对没问题，但我并不认为它
仅限于此，我估计它将汉字的组合按长度1-4（再大的话我认为没有什么意义）取词，进行hash运算，
构成hash表（可能有不止一个hash表）。当查询"花开花落"时，用时不到0.2秒；而查询
"花 开 落"时，时间就要长得多--约一秒左右。
>GB级数据的秒级检索
我还没遇到过"GB级数据"，但据我估计，要达到那么快的速度，关键词的选取一定要有讲究，
在某些情况下，即使算法再好也不可能在"秒级"完成检索--光是把数以万计的结果标题读入内存
都不够。
to mikedeakins:
64-bit--太大了一点吧。根据我的估计，两个汉字的组合仅有约6e+5种，四个汉字的组合也就在
1e+9左右，32bit足够了吧... 不过，40M的索引表还是太大了吧（忘了算具体数据了--还要乘10）
关于B-tree：知道用处了，还是不知道原理--看来要看书了，不能再偷懒了。 :)
：DoubleWood, 时间：2001-5-6 13:57:16, ID：523205
TO creation-zy:
真的要研究吗?其实我认为CHM做得并非最好，如果是自己的格式自己做的话，
应该可以更快。而且自己做的话，做插入更新应该更方便，而不是重新编译。可惜
我不知道怎么写。
可能有不止一个hash表我同意。B-tree我不清楚，大学没有好好学习:p，不过
我觉得用处不大，B-tree的用途应该是排序数据的检索，这里好像没有什么排序。
查询"花 开 落"时，时间就要长得多，也有可能是检索结果太多，时间花在
数据解压上了。
有时间的话就做个很小的，比如只有一篇文章的CHM，研究一下它的索引怎么建
立的，只有几K的大小。所以我觉得CHM有可能先做了统计，先生成了一个词表，然
后根据词表来建立hash table，难道一篇文章也要建立几M的索引？MS还没有那么笨。
GB级数据的秒级索引我相信可以做到。比如Yahoo的数据库远不止GB级。好的算
法是关键( 哎，大学没有学好，当时还认为没多大用:( )。可能光索引都有GB级了。
所以一定还有索引的索引，甚至索引的索引的索引。索引的算法至关重要。
使用64bit索引没有必要，MS一定不会那么做，CHM应该是采用一种灵活的索引方
法。Hash的结果也不一定要唯一的阿，解决的办法很多，比如100万的关键字完全可以
采取16-Bit的索引，速度不会比32－Bit慢到哪里，关键是解决冲突的办法。
至于CHM的取词，我还是认为没有必要对1-4个汉字建立索引，没有太大意义的。
不然的话"花开花落"就得是10个索引，太浪费。完全可以用别的方法来实现，比如
判断连续，其实也是可以在索引里做的，只要有好的算法。我觉得判断连续是比较可
行的办法:p
：creation-zy, 时间：2001-5-6 14:21:49, ID：523227
to DoubleWood:
>自己的格式自己做的话，应该可以更快
我正是想通过研究chm的原理来编制一个更加高效的搜索工具。
>Yahoo的数据库远不止GB级
我只知道Yahoo的搜索引擎技术是google的，而google用了5000（6000？）台Linux服务器，还有负载
均衡技术。5000！ 还有一点--由于他们的设备好，完全可以建立超大的Hash表--每台机器负责一
小部分。
>判断连续
具体如何实现？请给出算法流程或思路。
其实我认为只要1-3个汉字组成的词就足够了，1-2个在技术上也是可行的，只是精确程度会下降，不过
还可以接受。如果只用一个汉字的话--我认为那样会大大增加搜索范围，很可能不是一倍两倍的问题。
（就盼着您的算法思路了 :) ）
：mikedeakins, 时间：2001-5-6 15:08:20, ID：523274
楼上的同志们，动态索引和静态索引不是同样的技术！！！！！！！！！！！！！！！！
什么 yahoo 之类的东西都是动态索引，必须使用 B+ 树。当然，B+ 树使用 hash 变换
倒是必要的。
另外，hash 变换与 hash table 是两个概念，不要没弄懂就混用。hash 算法指的是把
字符串变成定长整数。hash table 指的是一个数组表或者链表。
.chm 是在编译的时候就已经确定的全文检索的索引，属于静态索引算法，可以使用 B+
树或者 hash table。另外，hash table 也分为完全 hash table 和不完全两种，完全的
是在索引值域中的所有值都存在于表内。不完全的使用类似稀疏数组的实现方法，adt:
struct TIncompleteHashItem
{
THashIndex IndexValue;
THashLinkList *lpHashLinkList;
};
不完全的 hash table 必须排序存储实现基于 log2(n) 的速度，否则搜索速度为 n。
完全 hash table 可以直接根据索引换算出偏移量。
但是，hash table 有一个致命的问题：完全 hash table 占用大量的存储空间，不完全
表虽然空间占用相对较小，但是必须排序存储，那么，插入数据的效率就很低，在外存
储器几乎无法实现。
所以，动态索引（yahoo 的搜索技术以及 ms sql server 的索引技术）都要使用 B+ 树。