（基础数学专业论文）基于马尔科夫链的算法复杂度分析.pdf

大连理工大学硕士学位论文 摘要 字符串查找是计算机科学中基础的问题，涉及到文本编辑、数据检索、符号操作、 搜索引擎等算法复杂度是衡量算法运行效率的一把尺子，对算法的复杂度的分析是研 究算法的重要课题本文利用了马尔科夫链理论对经典字符串搜索算法k m p 算法和初 等算法的复杂度做了精确的刻画 文章安排如下： 1 第一章主要介绍了字符串匹配算法和算法复杂度的一些知识 2 第二章描述了k m p 算法和初等算法 3 第三章对我们要使用的工具马尔科夫链理论做了相关的说明 4 第四章给出了分析的过程和得到的主要结果 关键词：算法复杂度；马尔科夫链；字符串匹配；k m p 算法 基于马尔科夫链的算法复杂度分析 a n a l y s i so fa l g o r i t h m sb a s e do nm a r k o vc h i n sm o d e l a b s t r a c t s t r i n gm a t c h i n gi saf u n d a m e n t a lc o m p o n e n to fc o m p u t e rs c i e n c e ，i n c l u d i n gt e x t e d i t i n g ，d a t ar e t r i e v a l ，s y m b o lm a n i p u l a t i o n ，s e a r c h i n ge n g i n ea n ds oo n a l g o r i t h mc o i n - p l e 五t yi sar u l e rt om e a s u r er u n n i n ge f f i c i e n c yo fp r o g r a m s om a n yc o m p u t e rs c i e n t i s t s a r ei n t e r e s t e di nt h i st o p i c i nt h i sp a p e r ，w es t u d yt h em a r k o vc h a i nm o d e lo nt h e a u t o m a t o nt a i l o r e dt ot e x t ，a n dd e r i v ee x a c t a n a l y s i sf o rt h ea v e r a g ec a s ep e r f o r m a n c eo f t h eb r u t e - f o r c ea n dk m p a l g o r i t h m t h eo r g a n i z a t i o no ft h i sp a p e ri sa sf o l l o w s ： 1 i nt h ef i r s tc h a p t e r ，w er e v i e wt h eb a c k g r o u n da n ds o m er e l a t e dd e f i n i t i o n so fs t r i n g m a t c h i n ga n da l g o r i t h mc o m p l e x i t y 2 i nt h es e c o n dc h a p t e r ，t h et w oc l a s s i ca l g o r i t h m sa r ed e s c r i b e d 3 t h et h i r dc h a p t e rm a i n l yd i s c u s s e ss o m et h e o r yr e l a t e dt om a r k o vc h a i n s 4 t h el a s tc h a p t e rt h e nc o n s i d e r sa n a l y s i so fa l g o r i t h m sp r e s e n t e d ，i nw h i c ht w om a i n t h e o r e m sa r ed e r i v e d k e y w o r d s ：a n a l y s i so fa l g o r i t h m s ；m a r k o vc h a i n s ；s t r i n gm a t c h i n g ；k m p i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：立堕照日期：玉掣 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名； 导师签名： 叫耳日 大连理工大学硕士学位论文 1 绪论 1 1 字符串匹配算法 字符串匹配算法是处理在一段文本t i t 2 k 中搜索一个子串p i p 2 p 。的一类算 法它是计算机科学中最常用的算法之一常用的匹配算法有： 1 初等算法最原始的算法，利用穷举完成搜索匹配，时间复杂度为o ( n 2 ) 2 k m p 算法由d e k n u t h 与v r p r a t t 和j h m o r r i s 【9 】这三个人于1 9 7 7 年共同发 现，因此称之为k m p 算法这是第一个在线性时间o ( n + m ) 内完成匹配的算法 3 b m 算法和b m h 算法同样在1 9 7 7 年，由b o y e r 和m o o r e 2 提出了b m 算法 通过对b m 算法的改进，h o r s p o o l | 8 1 在1 9 8 0 年得到了b m h 算法，这种算法更加 简单，效率却不逊色于b m 算法 4 其它算法如利用了h a s h 技巧f 7 】的k a r p - r a b i n 算法 1 0 等与本文无关，在此不 做详细介绍 本文只对初始算法和k m p 算法的复杂度进行分析。 1 2算法分析 同一问题可用不同算法解决，而个算法的质量优劣将影响到算法乃至程序的效率 算法分析的目的在于选择合适算法和改进算法一个算法的评价主要从时间复杂度和空 间复杂度来考虑 1 2 1 时间复杂度 时间频度个算法执行所耗费的时间从理论上是不能算出来的，必须上机运行测试 才能知道但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的 时间多，哪个算法花费的时间少就可以了并且一个算法花费的时间与算法中语句的执 行次数成正比例，哪个算法中语句执行次数多，它花费时间就多一个算法中的语句执 行次数称为语句频度或时间频度记为t ( n ) 1 基于马尔科夫链的算法复杂度分析 时间复杂度在刚才提到的时问频度中，n 称为问题的规模，当n 不断变化时，时间 频度t ( n ) 也会不断变化但有时我们想知道它变化时呈现什么规律为此，我们引入时 间复杂度概念 般情况下，算法中基本操作重复执行的次数是问题规模n 的某个函数，用t ( n ) 表 示，若有某个辅助函数，( 仃) ，使得当n 趋近于无穷大时，? ( n ) ，( n ) 的极限值为不等于 零的常数，则称，( n ) 是t ( n ) 的同数量级函数。记作罗( 他) = 0 ( ，( 挖) ) ，称0 ( 歹( 死) ) 为算 法的渐进时间复杂度，简称时间复杂度 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为0 ( 1 ) ，另 外，在时间频度不相同时，时间复杂度有可能相同，如t ( n ) = 扎2 + 3 n + 4 与t ( n ) = 4 舻+ 2 n + i 它们的频度不同，但时间复杂度相同，都为o ( 舻) 按数量级递增排列，常见的时间复杂度有：常数阶d ( 1 ) ，对数阶o ( 1 0 醪) ，线性阶 0 ( n ) ，线性对数阶o ( n l 0 9 2 ) ，平方阶p ( 舰2 ) ，立方阶0 ( 舻) ，k 次方阶o ( n ) ，指数阶 0 ( 2 n ) 随着问题规模n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低 1 2 2 空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空闻的度量 本文讨论的两种算法空间复杂度相差不大，我们仅对时间复杂度进行研究以下所 说的复杂度都是指时间复杂度，用0 表示复杂度的平均性能 1 3 研究概况 g b a r t h 1 】提出用马尔科夫链分析算法的复杂度，通过构造子串的自动机来实现， 假设字母表的大小为c ，得到的结果； 艮一c m + 蓦一南c c 一上一l 而且k m p 算法和初等算法效率之比； n a i v e21 一：+ - j p 1 1 k m 但是因为k m p 算法并非与内存无关，所以b a r t h 的模型无效【4 1 b a e z a - y a t e s 3 】改进了模型，并且获得了关于k m p 的复杂度近似结果： 当c f l o 岛m 1 时， 了c k m p s2 一：+ 。( ：) ， 礼c几 2 大连理工大学硕士学位论文 当c 1 0 懿m l 时 挈1 + ：1 + 丁 1 0 9 m i - 1 + o ( 字)nc 其中= 学 以上都是对子串进行建模分析本文对通过建立文本的马尔科夫链模型对算法的复 杂度进行了精确的分析，而且即使不是在独立同分布概率的情况下，这种方法也能对复 杂度有很好的刻画 3 大连理工大学硕士学位论文 2k m p 和初等算法简介 以下将用类c 的伪码描述算法 2 1 初等算法 p t = 1 ；p 以秕e rt ot e x t p p = l ：t x 咖t e r 幻p a t t e r n w h i l e ( p t n ) a n d ( p p r e ) d o i f ( s t r i n g 却 = = t e x t 州) p p = p p + 1 ： p t = p t + 1 ： 。 e 8 e t p p = 1 ： p t = p t p p + 2 ： ) i f ( p p m 1 p r i n t ( 7 ，饥dp a t t e r na tp o s i t i o np t m 7 ) e l s e p r i n t ( 7 n oo c c u r r e n c ef o u n d ) ； 5 基于马尔科夫链的算法复杂度分析 举例2 2 从一个基因d n a 序列中匹配形如a g c a t 的子序列 如上图。假设比较到第五个字( 指针指向的位置) 发现不相等那么下一次，指针精 移向下图中的位置重新开始下一次的比较t 这种方法没有充分利用已经比较时候的信息，因而效率低 2 3 k m p 算法 d e s e r i p t i o nl = 1 ；p o i n t e rt ot e x t p p = l ：p o n t e rt op a t t e r n w h i l e sn ) a n d ( p p r e ) d o w h i l e ( s t r i n g 陆v p t 耐矧) n 倒 0 ) p p = n e x t ( p p ) ； ) p p = p p + l ；p t = p 十1 ； i f e w m 1 p r i n t ( 7 f i n dp a t t e r n 面p o s i t i o n 彤一m 7 ) e l s e p r 讥t ( 7 n oo c c u r r e n c e ，伽凡d ，) ； 6 大连理工大学硕士学位论文 举例2 4 跟上个例子类似，比较到指针所指位置的时候发现不相等； 查表知n e x t f 砂指向g ，文本的指针不发生移动，而只需要把子串向前移动，使得g 能对齐到文本指针的位置： 这种算法考虑了字串的结构信息，当出现不匹配的时候可以利用已知信息提高检索 的效率因而比初等算法的效率更高实质上，在最坏的情况下，k m p 算法退化为初 等算法 7 大连理工大学硕士学位论文 3 马尔科夫链介绍 本章只对马尔科夫链做简单介绍，更多知识可以参考其它有关理论专著，如【5 ，1 2 ， 2 2 ，2 1 】 马尔科夫链是一个随机过程在任一时刻处于某个有限状态集s = s l ，8 2 ，s r 的随机过程被称作有限马尔科夫链【1 5 】，本文中所讨论的都是有限马尔科夫链，关于无 限马尔科夫链可参考【1 3 ，1 4 定义3 1 一个状态被称作是稳定的，如果到达后不会再离开 定义3 2 马尔科夫链是稳定的当且仅当它至少包含一个稳定状态而且从任一个非稳定 状态出发都会最终达到稳定状态 设表示从状态最转换到岛的概率，由此得转换矩阵r 。= ( 吩) 。此矩阵 任一行的元素之和为l ，即 = 1 ，i = l 2 n j = l 重新标记这些状态的序号，把对角线是1 的元素调整到右下角，也就是变成 r x n _ 其中丑，) 恤一埘是一) m 一七) 阶的单位矩阵，0 ( ，k ) ( ) 是一k ) xk 阶 的零矩阵这样就分离出q 拈矩阵，这个矩阵的逆一定存在 定义3 3 矩阵f = ( 一q k x k ) - 1 称作基础矩阵 有以下性质； 定理3 1 矩阵f 的元素厶等于从状态& 出发到达稳定时经过易的次数的期望值 由此定理得 推论3 1 马尔科夫过程中，从非稳定状态s 出发，到达稳定状态时的步数期望值等于 矩阵f 第t 行元素的和 9 基于马尔科夫链的算法复杂度分析 举例3 1 ( 赌徒问题【6 】) 一个赌徒，假设拿两元钱，一次赌一美元，赢的概率是p ，输 的概率是1 - p ，当赢够4 元，或者全部输光就不赌了 状态转换图t 状态转换矩阵t p = 10 oo0 、 1 p 0 p 00 0 1 p 0 p 0 00 1 p 0p 0o o0 1 ( 一 于是， 1 一 0 、 j q = l 一l 一 i 0 一；1 f ：( ，一q ，一：( 盏7 31 l 喜1 1 ， 、 2 ；，警 ，j-f-一 o p o p p 0 一 p 0 0 ，jiiii、 1 2 3 = q 阵 簪 觯 褂 q 列 出 南 离 v 分 = 而 p 因 设 大连理工大学硕士学位论文 即可看出从各种状态出发达到稳定所需要的步数比如，由于f 第二行元素之和为 警，所以从匏出发达到稳定状态期望的步数是警 更多的例子可以参考【1 6 ，1 7 ，1 8 ，1 9 ，2 0 】 1 l 大连理工大学硕士学位论文 4 分析过程 这一节中，我们将利用马尔科夫链理论分析这两个算法的复杂度，为了简单起见， 约定文本的长度为礼+ 1 ( 第+ 1 ) 个状态代表达到稳定状态) 4 1 k m p 算法复杂度 设文本指针不发生移动的概率为p 状态转换图： q 秽 k m p 的状态转换矩阵； k m p 的q 矩阵 因而， 只1 ) ( 叶1 ) = i t q k m 尸= q n n = 1 1 一p l p ) 一”矿，击f 1 - p 1 誓 因为从初始状态考察，由定理3 1 ，只需要注意矩阵f 的第一行元素，于是得到 1 3 p一 1 1 p 基于马尔科夫链的算法复杂度分析 定理4 1 k m p 算法的平均比较次数为 尸是文本指针不发生移动的概率 4 2 初等算法复杂度 e k m p 1 了2r 了n 1 一， 定理4 2 基础矩阵f n a i v e 的第一行第n i + 1 列元素为h i ( 1 i n ) ，满足： 其中 证明状态转换图 1 ( 1 0 l 0 、 i = 1 i - - 1 ( 1 + o k 以一k ) ( 1 一q o )2 i m 跟k m p 算法类似，我们得到： q n a i v e = 0l 0 p o1 一昂 0 p 1蜀1 一r k = o 0 p 2b 0 p m 一2p m 一3 0 0 o o r p m 一2 0 2 n 1 一p 4 u 缸= ：0 m 一2 p o1 一r 1 4 4 = 0 p 仇一3 岛 焉一2 n 一 一 m q 一 七一坟k a 鹄三 +l r 脚腩 = 叱 r 譬脚昂 一l 查垄里三查堂堡圭兰垡丝茎 ： j q n a i v e = 11 01 一t o 一1 + r 1 0 一p 11 一r 一1 + 尼 k = o 0 一恳 一只 0 一f m 一2一p 竹；一3 o o 0 o 1 一p 0 一只。一2 o 一1 + 最 k = 0 l t t - - 2 1 一r一1 + r p 竹，一3 一p 竹。一2 0 m - 2 1 一岛一1 + 屁 k = 0 1 一晶 接下来求f n a l y e = u q n 刖v e ) 为此，写出i q n a i v e 的增广矩阵为口一 q a f y e i l q ，以下通过初等列变换求出 i i ( z q a t v e ) 1 】 把矩阵i - q 的第一列加到第二列，第二列加到第三列，第n 一1 列加到第礼 列，于是； 1 q n 舡v e 。 1 01 一岛 1 0 一p 11 一r k = 0 0 一恳 2 一p 2 一p l1 一r k = 0 0 一一2 一p m 一2 一岛一3 0 0 相应地， o o 一只。一2 0 t n 一2 1 一r k = - - 0 一只。一2 一只，一3 一p 竹。一2 ，11 1 、 l 1 1l h l + ij 1 5 0 m - 2 1 一r k - - - - 0 m - 2 m 一2 一p k1 一最 k = lk = 0 基于马尔科夫链的算法复杂度分析 把，一q 卅y e 最后一列除以1 一q o ，相应的有， i _ 把，一q n a r w 最后一列乘以昂，2 加到第佗一m + 2 列，乘以p 一2 + f ，m 一1 加到 第n m + 3 列，依次把最后一行除了对角线外其余变为0 那么， i - q n a i v e - 对应的有， j _ 1 01 p o 1 0 一p 11 一鼠 知= 0 2 0 一p 2一岛一只1 一r jjj 0 一p m 一2 一尸m 一2 一一3 0 00 一p m 一2 一岛一2 一p m 一3 1 一 o o0o 11 1 1 + 篱1 + 皱1 - - o 。0 1 + 瓮 1 + 等1 + 业l - - a o 1 + 丑1 - - 。0 1 + 而a m - 3 1 + 篱 当2 墨曼曼= 墨 j 兰i 一l 1 一n 0l n 0l 一口0l 一口0 m - 2 最 七= 0 01 于是得到b l = i 去，而且j q a n ，e 最后一行化为了标准形式依照类似以上的 步骤进行下去最终会得到【- r l ( z q a e ) q 】，即 1 ( 1 一o o ) 坟： ( ，+ 茎咄_ ( 1 咱) 【( 1 + k = l q k ( 1 一n 。) i = 1 2 i m m t 竹 、， 。一h，一h ，一h。一h r 譬脚 一1 。一h，一：。一h。一h； 品品 + + 1 1 妻f - - 大连理工大学硕士学位论文 引理4 1 b i 是随着i 的增大而单调增的 证明由定理4 2 ， b i + l h ti - - 1 n k 魄一女+ 1 一口曲i 一 七= l k = l 1 c t 0 m - 2 女( 坟一t + 1 一阮一女) 南= 1 1 一口o 1 i m m i 仇 i - 1 q 6 1 + a k ( b , 一 + 1 一b i k ) 知= 1 1 一o m - - 2 ( 瓯一k + 1 一玩一e ) k = l 1 q o 1 t b 1 ，所以由数学归纳法可证，如随着i 的增大单调增 口 推论4 1 当i m 时，玩满足 m - 2 l + n 玩一m + 2 毛= 1 1 一a o 证明由引理4 1 得 m - - 2 1 + d k 蚨一1 机 玩一t ，l + 2 b i tsb i 一1 1 k m 一2 所以。 也就是 m - - 2 m - - 2m 一2 1 + q k 也一m + 21 + o k 一t1 + n k 魄1 1 一a o 1 一o o 一 1 一q 0 由此得证 引理4 2 当i 趋于d - 。时。兢的极限存在， 证明设存在2 0 满足 m - - 2 1 + 1 0 j 兰_ 一l o 1 一n o 一 1 7 口 ( 4 1 ) ，i_fii，(1llii，iill_-(1t-l k 一鼬 一 k 脚眦 i o 时，由推论4 1 和( 4 1 ) ， r n - - 2 1 + d f o 良丝ls 坛 1 一a 0 即 坟) 有界，由此得出矛盾 当i 趋于+ o 。时，由推论4 1 得 定理4 3 一 c n a l v b 1 1 _ 2 。矿 “ 1 一a 女 4 3 简单应用 在文本和子串满足独立同分布的前提下，初等算法的转换概率为 口 最= p p l p 2 p k + l = 如一一1 t 一女t i 一1a n dp k + 2 岛， = 击( 1 一：1 ) ( o 老m 一2 ) 从而 哟：m - 2 r ；而一万1 1 ( o j s m 一2 ) ， 哟= r = 万一万( o j s m 一2 ) ， 所以，由定理4 3 ， 推论4 2 tcnafve=j干i1弓霹=1i 1 1 - - ， n - - i j t 。= 吾了吾丐i 丐r 4 = j 。 至于k m p 算法，设p 是文本指针不移动的概率，这只有当文本和子串的前老( 1s k s m 一1 ) 个字符匹配而第( 七+ 1 ) 个字符不匹配的时候出现故 p k = p p * p 2 p k = 缸一k 岛一k + l t i 一1a n dp k + 1 岛) = 壶( 1 一三1 ) ( 1 k m 一1 ) 1 8 大连理工大学硕士学位论文 我们得到 由定理4 1 ， 推论4 3 m p - - 1 11 p = r = ：一土c o n k = l 挈= 忐连 2 f 孺一 cc c 即得到两种算法的复杂度结果 1 9 基于马尔科夫链的算法复杂度分析 结论 本文所取得的主要工作归纳如下： 1 在独立同分布的条件下k m p 和初等算法的效率之比为 一致 这跟r e g n i e r 【1 1 的结果： 瓦c k 赢m p 卜石1c n a i v e 一 乎 2 对于其他的概率分布，这种方法也很容易得出结论比如在g o o g l e 中搜索。我爱我 家”，那么可能出现很多类似“我爱数学”“我爱北京天安门。这样有较多重复的词 的时候，显然字符串的分布不再满足独立同分布，但是此种方法也很适用对于别的 匹配算法，比如b m ，b m h 算法，用这种方法也能分析，不过其中的计算过程比较 繁琐 南一苷器 大连理工大学硕士学位论文 参考文献 【1 】g b a r t h ，a na n a l y t i c a lc o m p a r i s o no ft w os t r i n gs e a r c h i n ga l g o r i t h m s ，i n f o r n m t i o n p r o c e s s i n gl e t t e r s ，1 8 ：2 4 9 - 2 5 6 ，1 9 8 4 【2 】r b o y e ra n ds m o o r e ，af a s ts t r i n gs e a r c h i n ga l g o r i t h m ，c a c m ，2 0 ：7 6 2 - 7 7 2 ，1 9 7 7 3 】i la b a e z a - y a t e s ，s t r i n gs e a r c h i n ga l g o r i t h mr e v i s i t e d ，i nw o r k s h o pi na l g o r i t h m sa n d d a t as t n l c 饥嬲o t t a w a , c a n a d a , a u g u s t1 9 8 9 【4 】ra b a e z a - y a t e s ，a l g o r i t h m sf o rs t r i n gs e a r c h i n g ：as u r v e y , s i g i rf o r u m ，1 9 8 9 2 3 ( 3 - 4 ) ：3 4 - 5 8 ( 5 】d ，r c o xa n dh d 施 j l e r ，t h et h e o r yo fs t o c h a s t i cp r o c e s s e s ，c h a p m a na n dh a l l ， l o n d o n ，1 9 6 5 6 】f r r o b e r t s ，d i s c r e t em a t h e m a t i c a lm o d e l s ，p r e n t i c e - h a l l ，n e wj e r s e y , 1 9 7 6 ，p p 2 6 8 - 2 8 4 用m c h a r r i s o n ，i m p l e m e n t a t i o no ft h es u b s t r i n gt e s tb yh a s h i n g c a c m ，1 4 ：7 7 7 7 7 9 1 9 7 1 f 8 】n h o r s p o o l ，p r a c t i c a lf a s ts e a r c h i n gi ns t r i n g s s o f t w a r e p r a c t i c ea n de x p e r i e n c e ， 1 0 ：5 0 1 5 0 6 1 9 8 0 【9 】d e k n u t h ，j m o r r i sa n dv p r a t t ，f a s tp a t t e r nm a t c h i n gi ns t r i n g s ，s i a mjo n c o m p u t i n g ，6 ：3 2 3 - 3 5 0 ，1 9 7 7 f 10 】r k a r pa n dm r a b i n ，e 矗i c i e n tr a n d o m i z e dp a t t e r n - m a t h i n ga l g o r i t h m s ，m mjr e s d e v e l o p m e n t ，3 1 ：2 4 9 - 2 6 0 ，1 9 8 7 【1 l 】m r e g n i e r ，k n u t h - m o r r i s - p r a t ta l g o r i t h m ：a na n a l y s i s ，i n i t i a ，r o c q u e n c o t t r t ，f r a n c e ( u n p u b l i s h e d ) ，1 9 8 8 【1 2 j s h e l l ，i n t r o d u c t i o nt 0p r o b a b i l i t yt h e o r yw i t hc o m p u t i n g ，p r e n t i c e - h a l l ，1 9 7 5 f 1 3 】a t b h a m c h a - r e i d ，e l e m e n t so ft h et h e o r yo fm a r k o vp r o c e s s e sa n dt h e i ra p p l i c a t i o n s ，m c g r a w - h i l lb o o kc o m p a n y , n e wy o r k ，1 9 6 0 基于马尔科夫链的算法复杂度分析 【1 4 】r a h o w a r d ，d y n a m i cp r o b a b i l i s t i cs y s t e m si ：m a r k o vm o d e l s ，j o h nw i l e y & s o n s ， i n c ，n e wy o r k , 1 9 7 1 【1 5 】j g k e m e n y , a n dj l s n e l l ，f i n i t em a r k o vc h a i n s ，d v a nn o s t r a n dc o ，i n c ，p r i n c e - t o n ，n ，j ，1 9 6 0 【1 6 】w j e w e n s ，p o p u l a t i o ng e n e t i c s ，m e t h u e n ，l o n d o n ，1 9 6 9 【1 7 b c e l a u d t - j o h n s o n ，p r o b a b i l l s t i cm o d e l sa n ds t a t i s t i c a lm e t h o d si ng e n e t i c s ，