平均情況下的最優(yōu)多模式近似匹配

1、平均情況下的最優(yōu)多模式近似匹配 Average-Optimal Multiple Approximate String Matching 在目標(biāo)文本中同時(shí)搜索r個(gè)模式P1P2.Pr，找到目標(biāo)文本中和這r個(gè)模式中的某一個(gè)模式最多只有k個(gè)字符不同的所有匹配結(jié)果。 最原始的多模式近似匹配算法是對(duì)r個(gè)模式分別進(jìn)行單模式近似匹配 平均情況下的最優(yōu)多模式近似匹配 基于散列方法的算法，只允許進(jìn)行k=1的近似搜索，但對(duì)模式個(gè)數(shù)r有很強(qiáng)的容忍能力 分塊精確搜索算法，基于這樣一個(gè)事實(shí)：如果將P分成k+1塊，那么目標(biāo)文本中的匹配結(jié)果中至少精確包含這k+1塊中的一塊。這個(gè)算法將所有的模式都切成k+1塊，然后使用多模式

2、精確匹配算法在目標(biāo)文本中搜索這r(k+1)個(gè)模式塊。 平均情況下的最優(yōu)多模式近似匹配 本文介紹的算法是從單模式近似匹配最優(yōu)算法Chang-Marr算法擴(kuò)展而來 Chang-Marr算法的基本思想： 每個(gè)匹配結(jié)果長(zhǎng)度至少為 m-k，如果將目標(biāo)文本切成長(zhǎng)度為b=(m-k)/2的塊，目標(biāo)文本中的任何一個(gè)匹配結(jié)果都至少包含其中的某一整塊。 判斷一個(gè)文本塊不是一個(gè)匹配結(jié)果，要比判斷它是一個(gè)匹配結(jié)果容易。(因此，目標(biāo)文本中所包含的匹配結(jié)果越多，算法處理得越慢)平均情況下的最優(yōu)多模式近似匹配 怎樣判斷一個(gè)長(zhǎng)度為(m-k)/2的文本塊不是一個(gè)匹配結(jié)果？首先選擇一個(gè)數(shù) ，滿足1 = 建立一個(gè)表D ，其中保存了任

3、何一個(gè)長(zhǎng)度為 的串(稱為 -gram)在模式中匹配的最小錯(cuò)誤數(shù)。因此D的大小為 在文本塊中只要找到若干個(gè)互不交疊的 -gram，它們的D表元素值之和大于k，則可以肯定這個(gè)文本塊不會(huì)和模式匹配k)/2-(m平均情況下的最優(yōu)多模式近似匹配 本文介紹的算法基本思想是：給定待搜索的r個(gè)模式P1.Pr，我們建立和Chang- Marr算法一樣的表D，D中保存了任何一個(gè) -gram與任何一個(gè)模式的子串匹配的最小錯(cuò)誤數(shù)。掃描目標(biāo)文本的每一塊，如果在某一個(gè)塊以內(nèi)錯(cuò)誤數(shù)就超過了k，我們就能夠確信不可能存在包含本塊的匹配結(jié)果 平均情況下的最優(yōu)多模式近似匹配 -gram的最優(yōu)選擇 最簡(jiǎn)單的辦法：依次計(jì)算塊中前部 -

4、gram的錯(cuò)誤數(shù)之和。但不是最優(yōu)其實(shí)只要是塊內(nèi)互不交疊的 -gram組成的集合，它們的錯(cuò)誤數(shù)之和超過了k，而不管這些元素出現(xiàn)的位置，都可以確信本塊不構(gòu)成匹配結(jié)果最優(yōu)選擇：掃描當(dāng)前塊，總是選擇錯(cuò)誤數(shù)之和最大的互不相交的 -gram集合平均情況下的最優(yōu)多模式近似匹配 對(duì)于不能跳過的文本塊，怎樣驗(yàn)證它確實(shí)是一個(gè)匹配結(jié)果呢？ 簡(jiǎn)單的用動(dòng)態(tài)規(guī)劃算法逐個(gè)驗(yàn)證每個(gè)模式，平均情況下效率低下 層次驗(yàn)證平均情況下的最優(yōu)多模式近似匹配 層次驗(yàn)證 (Hierarchical Verification) 構(gòu)造一棵層次驗(yàn)證樹，每個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)模式集的子集，祖先結(jié)點(diǎn)所代表的模式子集包含了后代結(jié)點(diǎn)所代表的模式子集，葉結(jié)點(diǎn)

5、代表單個(gè)模式，而根結(jié)點(diǎn)代表了整個(gè)模式集 每個(gè)結(jié)點(diǎn)建造一個(gè)D表，葉結(jié)點(diǎn)的D表構(gòu)造方法同Chang-Marr算法；而內(nèi)部結(jié)點(diǎn)的D表，每個(gè)元素取子結(jié)點(diǎn)D表中對(duì)應(yīng)元素最小的那個(gè)值 驗(yàn)證的時(shí)候從根結(jié)點(diǎn)開始，用它的D表掃描文本塊，如果驗(yàn)證沒通過，跳過本塊；否則用它的子結(jié)點(diǎn)依次驗(yàn)證。迭代這個(gè)過程直到層次驗(yàn)證樹的葉結(jié)點(diǎn)，葉結(jié)點(diǎn)采用經(jīng)典的動(dòng)態(tài)規(guī)劃算法驗(yàn)證平均情況下的最優(yōu)多模式近似匹配 層次驗(yàn)證 (Hierarchical Verification) 如果層次驗(yàn)證樹的各個(gè)子樹所代表的模式子集存在聚類特征(即子集內(nèi)的模式之間的編輯距離小于各子集間的模式的編輯距離)，那么將會(huì)加速層次驗(yàn)證過程 作者建議，在建立層次驗(yàn)證樹之前，采用層次聚類算法對(duì)模式進(jìn)行排序，然后按聚類結(jié)果建立子樹平均情況下的最優(yōu)多模式近似匹配 優(yōu)化措施 為了減少預(yù)處理時(shí)間，采用帶標(biāo)記的根樹(trie)來建造葉結(jié)點(diǎn)的D表 為了減少算法所需