第五章 文本索引和搜索

1、第五章:文本索引和搜索任飞亮东北大学自然语言处理实验室2010 大纲n索引和搜索的概念n倒排文件索引n后缀数组索引n签名文件索引n文本搜索技术大纲n索引和搜索的概念索引和搜索的概念n倒排文件索引n后缀数组索引n签名文件索引n文本搜索技术应用索引的例子n检索的目的是为了在一大堆的信息中发现自己感兴趣的信息;n但是,当有了一大堆资料之后,并不能立即开始搜索.n为什么?图书馆实例在检索前必须建立索引在检索前必须建立索引!索引的定义n所谓建立索引,是指将待搜索的信息进行一定的分析分析,并将分析的结果按照一定的组织一定的组织方式存储方式存储起来,通常是存储在文件中.n存储了分析结果的文件的集合就是所谓的

2、索引索引.n准确定义:索引索引（Index）是一种数据结构数据结构，其将关键词与包含该关键词的文档（或关键词在文档中的位置）建立了一种映射关系，以加快检索的速度。文本搜索的概念n不使用任何索引技术，而快速的在给定文本或文本集合中查找是否出现某一关键词，这种技术通常被称为单模式匹配单模式匹配n应用领域n信息过滤、检索结果后处理等n常用算法nBFnKMPnBM大纲n索引和搜索的概念n倒排文件索引倒排文件索引n后缀数组索引n签名文件索引n文本搜索技术倒排索引主要内容n倒排索引简介n倒排文件的使用n倒排文件的建立n倒排文件的维护n倒排文件的压缩n倒排文件的性能分析n词汇表的存取倒排索引主要内容n倒排索

3、引简介倒排索引简介n倒排文件的使用n倒排文件的建立n倒排文件的维护n倒排文件的压缩n倒排文件的性能分析n词汇表的存取倒排文件简介 n倒排文件 (Inverted File)n也称倒排索引，索引对象是文档或文档集合中的单词单词等，用来存储这些单词在一个文档或者一组文档中的存储位置存储位置，是对文档或文档集合的一种最常用的索引机制n倒如:有些书往往在最后提供的索引(单词页码列表表)就可以看成是一种倒排索引.即通过一些关键词,在全书中检索出与之相关的部分;n这种思想也被应用于数据库技术中,即对数据库中需要经常进行检索的域建立索引结构,从而实现快速查询.在关系数据库上建索引n如上图所示,对”姓名”字段

4、使用便于查找的数据结构(如排序数组、B树或散列等)建立索引，当查询某个名字时，就不需要从头至尾遍历整个字段，而可以快速找到该姓名，从而查找出与其对应的信息。地址姓名姓名索引查询式:姓名 = “张三”张三哈尔滨工业大学张三倒排文件组成n词汇表(vocabulary)+记录表(posting list)n词汇表n文档或文档集合中所包含的所有不同单词不同单词的集合n占用的空间V=cn，c是常数，n是文档集合的大小，是一个0到1之间的常数，一般在0.4到0.6之间 n记录表n对于词汇表中的每一个单词在文档中出现的位置位置或者其出现的文文档编号档编号构成的列表n占用的空间P=cn，其中c是常数，随着记录

5、表中存储的信息丰富程度而变化 n记录表既可以存储文本中单词的编号位置，也可以指向单词首字母的字符位置，还可以是其所在的文档编号，即可以根据不同的应用需求，使用不同的寻址粒度(addressing granularity)对单文档的倒排文件 对文档集合的倒排文件倒排索引主要内容n倒排索引简介n倒排文件的使用倒排文件的使用n倒排文件的建立n倒排文件的维护n倒排文件的压缩n倒排文件的性能分析n词汇表的存取倒排文件的使用 n三个步骤n词汇表检索n将出现在查询（Query）中的单词分离出来，并在词汇表中进行检索。n记录表检索n检索出所有找到的单词对应的记录表。n记录表操作n对检索出的记录表进行后处理，以

6、实现短语查询、相邻查询或者布尔查询。词汇表检索n规模相对较小的独立文件，全部调入内存n常用数据结构n树状结构，如：B树和Trie树n前缀查询和范围查询n散列n检索速度快，但是不支持前缀查询和范围查询等n需要根据实际需求情况，决定采用什么样的数据结构。记录表操作n如果查询中仅包含一个单词，则在词汇表中找到该单词，并取出其对应的记录表即完成了检索操作n如果查询中包含多个单词，则需将各个单词检索出的记录表进行合并n同步遍历记录表，实现合并过程倒排索引主要内容n倒排索引简介n倒排文件的使用n倒排文件的建立倒排文件的建立n倒排文件的维护n倒排文件的压缩n倒排文件的性能分析n词汇表的存取倒排文件的建立 n

7、建立倒排文件的最关键问题最关键问题是由于需要索引的文档数量过大，有可能导致不能在内存中存储整个倒排文件。n根据索引文档的大小，介绍三种倒排文件的建立方法。n基于内存的方法 n基于排序的方法 n基于归并的方法 倒排文件的建立 n建立倒排文件的最关键问题最关键问题是由于需要索引的文档数量过大，有可能导致不能在内存中存储整个倒排文件。n根据索引文档的大小，介绍三种倒排文件的建立方法。n基于内存的方法基于内存的方法 n基于排序的方法 n基于归并的方法 基于内存的方法输入：输入：文档集合输出：输出：基于文档集合的倒排文件算法：算法：(1) 初始遍历文档集合。对于每一个单词w，统计包含该单词的文档数fw；

8、(2) 在内存中建立长度为w词表fw的数组，并且对于每一个单词w，生成指向其记录表块首的指针pw。(3) 第二次遍历文档集合，对每个文档d中的每一个单词w，在pw中追加文档d的序号，pw后移。基于内存的方法 n核心思想是经过两次遍历n第一次遍历首先获得每个单词出现的文档的个数，从而获得所需内存的大小；n第二次遍历充分利用内存的随机访问功能，快速更新每个单词的记录表；n优点：n只要内存比最终生成的倒排文件（包括词汇表和记录表）大一些，该算法是可行的；n可以很方便地扩展该方法，在记录表中增加更多的信息，如单词的位置等；倒排文件的建立 n建立倒排文件的最关键问题是由于需要索引的文档数量过大，有可能导

9、致不能在内存中存储整个倒排文件。n根据索引文档的大小，介绍三种倒排文件的建立方法。n基于内存的方法 n基于排序的方法基于排序的方法 n基于归并的方法 基于排序的方法 n基于内存方法的不足n从磁盘读取和分析文档的操作需要花费较多时间，如果反复调用，必将成为倒排文件建立的一个瓶颈n解决方法n方法一：存储分析好的文本。n潜在的代价是将会带来大量的磁盘开销，有时甚至要花费比第二步更多的时间。n方法二：基于排序的方法；n该方法将用二元组构成数组或文件，从由原来的按照文档编号排序，变为由单词排序，然后产生最终的倒排文件。 基于排序的方法通过使用多路归并算法，排序过程可以在硬盘上完成另外一个好处是不必在内存

10、中存储整个词表，从而大大增加了在单台机器上索引的数据量倒排文件的建立 n建立倒排文件的最关键问题是由于需要索引的文档数量过大，有可能导致不能在内存中存储整个倒排文件。n根据索引文档的大小，介绍三种倒排文件的建立方法。n基于内存的方法 n基于排序的方法 n基于归并的方法基于归并的方法 基于归并的方法 n提出背景n随着文档集合的增加，将所有词汇表置于内存中的花费也越来越大n必须一部分一部分地生成索引，其中每一部分索引都可使用上面的方法生成；n最后，将各个子索引进行归并，形成最终的索引。基于归并的方法输入：输入：文档集合输出：输出：基于文档集合的倒排文件算法：算法：(1) 初始生成一个基于内存的临时

11、索引结构，其中词汇表和记录表均使用动态数据结构存储，如动态数组，链表等。(2) 读取一个文档，并在其中出现的单词的记录表中，加入文档编号。直到占用的内存大小超过一定的阈值。(3) 将生成的包括词汇表和其记录表的临时索引结构转存到磁盘，并清空内存。(4) 如果所有文档处理完毕，则转到(5)，否则转到(1)。(5) 归并以上生成的子索引，生成单一索引。基于归并的方法 n优点：n适用于各种大小的文档集合，即使对于内存不大的机器也同样有效和实用；n该方法仅需一次扫描和分析文档，效率较高。倒排索引主要内容n倒排索引简介n倒排文件的使用n倒排文件的建立n倒排文件的维护倒排文件的维护n倒排文件的压缩n倒排文

12、件的性能分析n词汇表的存取倒排文件的维护 n维护倒排文件通常需要三种维护操作n插入、删除和更新文档或文档集合 n通常的更新操作需要较高的代价n例如，要在存储了单词位置信息的倒排文件中进行一篇文档的更新，即使该文档仅仅改动很小的部分，文档中出现的大部分单词的记录表都需要做出改动。n原因：单词的位置很可能发生变化，这就需要频繁地读取和修改记录表，这种代价是相当高的。n因此，在维护倒排文件时，一般不进行更新操作，而是使用删除+插入操作代替插入操作的维护 n在已有的倒排文件中插入一篇文档相当于在该文档包含的单词所对应的记录表后面插入此文档的编号或者每个单词的位置信息n对于一般的文当，这种插入需要调用获

13、取记录表并在其末尾添加该文档或者单词位置信息的操作多次，以目前的硬件水平，这种操作需要较长的时间。 n如果使用批量插入，效率将大大的提高 n类似归并操作,首先为待插入的多个文档建立临时内存索引结构,然后一次性地将此索引结构插入到原索引中;n在生成批的时候新插入的文档不能马上被检索，会造成索引内容滞后的问题，可以通过对临时内存索引进行检索解决n除使用批量插入方法外,还可以在新文档中包含单词被用户检索的时候进行该单词词表的更新,或者使用后台进程在机器空闲的时候进行插入操作;n效率都不如批量插入效率高删除操作 n文档的删除操作与插入操作类似,其瓶颈也是记录表从磁盘读取和写回的过程;n也可使用批量删除

14、的方法n为了保持删除的及时性,需要维护一张删除文件列表n在检索时如果结果包含列表中的文件，则将其从结果中删除n总之,在维护倒排文件的时候,无率是插入操作还是删除操作,为了提高效率,必须想办法减少读写磁盘的操作,即提高磁盘I/O的效率倒排索引主要内容n倒排索引简介n倒排文件的使用n倒排文件的建立n倒排文件的维护n倒排文件的压缩倒排文件的压缩n倒排文件的性能分析n词汇表的存取倒排文件的压缩 n优点n减少内存和磁盘的空间占用n提高磁盘的吞吐量，提高索引维护和查找的效率n压缩分类n有损压缩n去停用词、词干提取等技术n使用这些技术会损失一些原文中的信息；n无损压缩 n在压缩倒排文件的同时，其原始信息完全

15、被保留，不会缺损。n分词汇表词汇表的压缩和记录表记录表的压缩词汇表的压缩 n在检索的时候，需要经常查询词汇表，在理想情况下，应将词汇表始终置于内存之中。n实际情况：n随着文档数的增多，词汇表也将逐渐增大；n存在一些对内存使用有限制的应用n必须对词汇表进行压缩；n压缩常用方法：n使用一个长字符串连续存储词汇表n见下页图词汇表的压缩 n使用长字符串连续存储单词表 n这样的存储方式紧凑，且不会出现溢出问题；n通过该种简单的压缩方式，可以很容易地将词汇表压缩为原来大小的50%左右 记录表的压缩 n文档和单词的位置使用16位或32位整数表示n16位太小，32位太大，浪费空间n解决方法：仅记录相邻文档编号

16、或词位置之间的差异n用比较少的字节表示编号的相对变化databaseD345, 25, 34, 98, 120 D348, 37, 71, 85database345, 25, 9, 64, 223, 37, 34, 14Word positions记录表的压缩 (2)n整数的定长表示不是特别的节省空间n对于常用词相对变化不多，使用16位编码，浪费空间n对于非常用词，有可能仅存在于少数的文档之中，16位表示会溢出n解决方案：变长整数表示n基本原理n使用较少位数表示较小，出现次数较多的整数n使用较多位数表示较大，出现次数较少的整数倒排表压缩总结n优点：n1、降代了索引在内存和磁盘中占用的空间，经

17、过适当的压缩，索引的大小可以降为原始文档的25%左右；n2、由于索引被压缩，提高了磁盘的传输效率，使得查询的速度加快；n3、由于磁盘传输效率的提高，使得索引的构造和维护的效率也得到提高；n4、另外一个隐含的好处是，这样提高了倒排文件的缓存能力；进而提高了检索的速度倒排表压缩总结n负面影响：n1、在搜索时必须花时间对压缩的数据进行解码;n2、在维护时,特别是进行删除操作时,由于某些文档被删除,不得不对剩余的文档编号进行重新编码;n总体上：利大于弊倒排索引主要内容n倒排索引简介n倒排文件的使用n倒排文件的建立n倒排文件的维护n倒排文件的压缩n倒排文件的性能分析倒排文件的性能分析n词汇表的存取倒排文

18、件性能分析 n可以证明,使用倒排文件,检索查询的开销与文档集合大小成次线性关系次线性关系,其时间复杂性nO(na)，其中0 a 1，与查询有关,一般在0.40.8之间n在实际应用中,倒排文件的时间和空间复杂性接近O(n0.85), n在使用压缩技术之后，在时间复杂性损失不多的条件下，空间的复杂性会进一步降低到原来的25%左右n-其它索引方法很难实现倒排索引主要内容n倒排索引简介n倒排文件的使用n倒排文件的建立n倒排文件的维护n倒排文件的压缩n倒排文件的性能分析n词汇表的存取词汇表的存取词汇表的存取 n词汇表的存取是实现倒排文件查询的第一个步骤,需要非常高的存取效率n高效的词汇表存取方法也被应用

19、于信息检索的其他步骤或者其他信息技术应用领域n要实现高效的词汇表搜索,往往需要设计特殊的数据结构数据结构n排序数组 n树状结构nB树，Trie树 n散列都是基于字符串比较的方法,需要事先将待查找的字符串排序1、不需要预先排序、检索速度快2、很难处理前缀查找(如查找以“沈阳“开始的词)、区域查找(如查找所有“技术”到“检索”之间的单词)3、要减少散列冲突，需要相对较大的存储空间排序数组n最简单的词汇表搜索方法n是由一系列元素组成的数组，其中的元素一般包括三个域：关键词、记录表的大小以及指向其记录表的指针n数组中的元素根据关键词排序n可以采用二分查找的方法，在O(log(n) 的时间复杂性内，查找

20、给定的关键词n缺点n维护代价较高，无论插入还是删除，都需要移动较多的元素 n可能造成内存不足 引入树状结构引入树状结构!B树 nB树的定义：B树是一种平衡的多叉树，一棵m阶的B树满足下列条件：l树中每个节点至多有m个孩子；l除根节点和叶子节点外，其它每个节点至少有m/2个孩子；l若根节点不是叶子节点，则至少有2个孩子；l所有叶子节点都出现在同一层，叶子节点不包含任何关键字信息；有k个孩子的非终端节点恰好包含有k-1个关键词。 在B树中，每个节点中的关键词从小到大排列，并且当该结点的孩子是非叶子节点时，该k-1个关键词正好是k个孩子包含的关键字的值域的划分。B树示例 nB树中的一个包含n个关键词

21、、n+1个指针的节点的一般形式为(P0,K1,P1, K2,P2,Kn,Pn)n其中，Ki为关键词，K1K2Kn,Pi是指向包括Ki到Ki+1之间的关键词的子树的指针B树操作n查找n在每个节点进行沿着指针查找节点和在节点内的关键词中查找交叉的过程n从根结点开始，在节点包含的关键词中查找给定的关键词，找到则查找成功，否则确定给定关键词可能在哪个子树，重复上面的操作，直到查找成功或者指针为空为止 如何查找20？如何查找21？如何查找22？B树操作n插入n在恰当的叶子节点中添加关键词，如果该节点中关键词超过m-1个，要把这个节点分裂为两个，并把中间的一个关键词拿出来插到节点的父节点里去。如果父节点也

22、是满的，就需要再分裂，再往上插，以此类推，直到根节点如何插入22？如何插入38？B树操作n删除n删除操作与插入操作类似，但要稍微复杂些。从一个节点中删除关键词时，需要重新安排一些节点，防止因删除操作而导致树的结构违反B树的性质B树的扩展：B+、B*树等Trie树 n又称作前缀树，其名字来源于英文词reTrieval(检索)n当关键词的长度变化较大时，Trie树是一种特别有效的查找数据结构；n另外，Trie树还适合用于查找单词前缀，如果找所有以”comput”开头的词，如”computing”、”computer”等nTrie树的每一层分支不是靠整个单词的值来确定，而是由单词中的一个字符来确定n

23、例如存储：information、retrieval、system、introduction的Trie树nTrie树包括两种类型的节点：元素节点和分支节点。n元素节点包含整个单词，在图中用表示，分支节点用表示。n如要查找单词”information”，则顺次查找字母”i”、”n”和”f”，进入元素节点”information”，它与查询单词”information”相同，故查找成功；n如要查找”inference”，也会进入元素节点”information”，但在比较两个单词的时候会发现它们不同，故查找失败。Patricia树nTrie树在最坏的情况下搜索的时间代价为O(l),其中l是Trie

24、树的层数;nTrie树的改进n压缩一元节点(即只有一个子节点的节点)，提高空间利用率nPatricia(Practical Algorithm To Retrieve Information Coded in Alphanumeric)树Patricia树n除了不含有一元节点外，Patricia树与Trie树的不同之处还在于其分支节点内包含待比较的字节编号。n如要查询单词”information”,Patricia树只需查找第一个字母”i”，然后查找第3个字母”r”,即可进入元素节点”information”.与Trie树查找相比,减少了一次对字母n的判断n一般情况下，Patricia树的性能

25、要优于Trie树大纲n索引和搜索的概念n倒排文件索引n后缀数组索引后缀数组索引n签名文件索引n文本搜索技术后缀数组n在倒排文档中，文本被看作是由单词组成的序列限制了倒排文件的应用n情况1：词组查询在使用倒排文件查询时就比较困难，因为不但需要记录每个单词在文档中的位置，还要在合并时判断其是否相邻并构成词组；n情况2：在某些应用中，如基因数据库，不存在词的概念。n解决方案：使用后缀数组后缀数组n在后缀数组中，可以将文本看作是一个长的字符串，文本中的每个位置都被认为是文本的一个后缀，即一个从当前文本位置到文本末尾的字符串。n索引的位置可以是每个字符的位置、单词的位置或者汉字的位置等。n后缀数组后缀数

26、组(suffix array)就是对文本中的所有后缀按照词典序存放每个后缀对应的起始位置的一个列表原始文本，按字的顺序位置索引文本中的部分后缀，按位置索引相同的部分后缀，按字典序索引后缀数组的构造 024681012141618202224262830323436384042444648这是一本关于信息检索的教材。介绍了检索的基本技术。021216223444这是是一信息检索教材检索技术441634222120技术检索检索教材是一信息这是首先截取每个后缀的前n个字节，作为类似倒排文件中的“词汇表”(此处n=4)后缀数组的使用 n在使用后缀数组进行检索的时候，将每个查询同样截取前n个字节，并于索

27、引中进行查找n如果没有找到，则表明不包含所需查询n如果查找成功，则需要在相应的文本位置上，进行进一步的字符串比较，以确定文本中是否包含查询 n实例n查找“信息检索”，首先截取4个字节“信息”，并于后缀数组中查找到了位置12，接着在原文中的12号位置，找到“信息检索”字符串，则查找成功；n查找“信息过滤”，则原文中的12号位置不能找到“信息过滤”字符串，则查找失败；n更一般的例子，如果输入的查询为“数据库”，在索引结构中不能找到“数据”，则查找直接失败返回；441634222120技术检索检索教材是一信息这是后缀数组的分析 n对于需要大数据量的检索问题，后缀数组并不适用 n因为构造出的后缀数组需

28、要占用大量的空间，通常是原文本的1.7倍 n和倒排文档相比，后缀数组里面储存了较多的重复信息 n同时，由于每个后缀位置的编号不能存储相对位置的变化，所以很难被压缩，需要较多的存储空间；n后缀数组的另外一个缺点是不容易对检索结果进行排序，因为计算查询单词的词频比较耗时；n实际上实际上,后缀数组的大部分功能可以通过倒排文档来实现后缀数组的大部分功能可以通过倒排文档来实现!n例如可以倒排索引文本中的二字串或者三字串，从而提高召回率 大纲n索引和搜索的概念n倒排文件索引n后缀数组索引n签名文件索引签名文件索引n文本搜索技术签名文件 n签名文件签名文件(signature file)是基于散列技术的面向

29、单词的索引结构n索引占用的空间大约为原始文档集的3040%n在检索时需要顺序比较，适用于小规模的文本n在大多数应用中，其性能不如倒排文件词的Signatures词“签名”单词这 是 一本 关于 信息 检索 的 教材 。 介绍 了 检索 的 基本 技术 。文本技术教材检索信息001 000 110 010000 010 101 001000 000 011 110101 000 100 001n一个单词的“签名”是一个位向量位向量,由F位组成,其中有m位置1;n如下图给出了一段文本，以及文本中部分单词的“签名”示例，其中F=12,m=4;词Signature的生成算法输入：词W，参数F和m输出：

30、词W的F位“签名”S算法：(1) 将W转换为ASCII值，然后转换为32位整数i例如：free = 66726565 (hex)(2) 初始化：a) S的F位全置0;b) srandom(i);/初始化随机种子c) j = 0;(3) while (j m。在文本T中找出模式P出现的位置。n三种常用的精确匹配算法 nBF算法nKMP算法nBM算法文本搜索技术 n精确的字符串匹配问题可以如下描述:n结定一个长度为m的模式P(p1p2pm)，以及一个长度为n的长文本T(t1t2tn)，其中nm。在文本T中找出模式P出现的位置。n三种常用的精确匹配算法 nBF算法算法nKMP算法nBM算法BF算法算

31、法nBF算法是Brute-Force(蛮力)算法的简称n是一种简单、直接、容易实现的字符串匹配算法n基本思想：n将模式P和文本T中的m个字符的子串tktk+1tk+m-1进行匹配，1k m) return 匹配位置j;else return “匹配不成功”;BF算法分析算法分析n在BF算法中，可以更改循环条件为jn-m+1,使得循环可以更早地终止；n因为存在O(n)个文本位置，在最坏的情况下，验证每个位置需要花费的时间为O(m),所以BF算法的最长时间为O(mn)nBF算法的平均时间为O(n)，因为对于一个随机文本，一般在进行O(l)次比较之后，就可以发现错误的匹配。nBF算法无需进行任何形式

32、的预处理，实现简单，被大多数程序设计语言所采用n如C语言中的字符串查找函数strstr()使用的就是BF算法nBF算法的时间复杂性与其他算法比较还是比较高的，在对效率要求较高的系统中，应该避免大量使用文本搜索技术 n精确的字符串匹配问题可以如下描述:n结定一个长度为m的模式P(p1p2pm)，以及一个长度为n的长文本T(t1t2tn)，其中nm。在文本T中找出模式P出现的位置。n三种常用的精确匹配算法 nBF算法nKMP算法算法nBM算法KMP算法 nD.E.Knuth、J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法n该算法是第一个可以在O(n+m)的时间内完成串模式匹配

33、的算法，但平均来说，它的效率并不比BF算法快很多。n基本思想n每当匹配过程中出现字符串比较不等时，不像BF算法那样仅将模式向右“滑动”一个位置，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。n可以避免对那些能够推断出不匹配的位置进行徒劳的操作KMP算法 nKMP算法原则n从匹配成功匹配成功的子模式子模式中找出“能够相互匹配的最长的前缀最长的前缀和后缀后缀”n在使用KMP算法进行模式匹配时，需要根据模式事先构造一个shift跳转表，用来决定在某个位置匹配失败时应该移动多少个字符nShift表的构造方法n如果当前不匹配的位置为j,重复字串的长度为k,则跳过的字符个数为j-k-1KMP算法的shift表n模式P=“abcabcacab”的shift表如果当前不匹配的位置为j,重复字串的长度为k,则跳过的字符个数为j-k-1nKMP算法的shift表可以在O(m)的时间复杂度下，通过对关键词的分析而获得,m是模式的长度 nKMP算法花费O(m+n)的时间来解决模式匹配问题文本搜索技术 n精确的字符串匹配问题可以如下描述:n结定一个长度为m的模式P(p1p2pm)，以及一个长度为n的长文本T(t1t2tn)，其中nm。在文本T中找出模式P出现的位置。n三种常用的精确匹配算法 nBF算法nKMP算法nBM算法算法BM算法 nBo