（模式識別與智能系統(tǒng)專業(yè)論文）數(shù)學(xué)公式圖像識別的自動性能評估.pdf

摘要 數(shù)學(xué)公式圖像讓 別是個具有相當(dāng)難度的前沿課題，許多處理方法都還在探索和嘗試 中。為了小斷改進(jìn)各種處理方法，提高公式識別系統(tǒng)的整體性能，需要對公式識別的各個 階段以及整體進(jìn)行自動的測試和性能評估。然而有關(guān)性能評估的研究相當(dāng)少，在本文開始 研究之前，尚沒有對大規(guī)模圖像進(jìn)行性能評估的實驗結(jié)果，這嚴(yán)重阻礙了數(shù)學(xué)公式識別研 究的進(jìn)一步發(fā)展。 本文根據(jù)數(shù)學(xué)公式本身的二維特性，首次提出采用帶邊屬性的三叉樹結(jié)構(gòu)來表示數(shù)學(xué) 公式的以別結(jié)果，并首次提出兩科l 基于樹匹配算法( 動態(tài)規(guī)劃算法和b u t d 算法) 的公式 識別自動性能評估方法。其中基于b u t d 算法的性能評估方法是目前唯一能夠發(fā)現(xiàn)公式符 號切割、識別以及公式分析中產(chǎn)生的任意錯誤的評估方法。 關(guān)鍵詞 數(shù)學(xué)公式圖像識別數(shù)學(xué)公式分析自動性能評估 a b s t r a c t t h e1 _ e c o g n i t i o no fm a t h e m a t i c a le x p r e s s i o ni m a g ei sad i f f i c u l ts u b j e c t m a n yr e c o g n i t i o n m e t h o d sa r es t j l it e n t a t i v ei no r d e rt o i m p r o v e t h e s em e t h o d sa n de n h a n c et h e s y s t e m p e r f o r m a n c e ，i t 1 s n e c e s s a r yt oe v a l u a t et h ep e r f o r m a n c eo ft h ee n t i r er e c o g n i t i o ns y s t e m b u t a l s ot h e p m 。f o r m a n c e o fe a c h p h a s e h o w e v e r ，t h er e s e a r c h o n p e r f o r m a n c ee v a l u a t i o n o f m a t h e m a t i c a le x p r e s s i o nr e c o g n i t i o ni s v e r ys c a r c e b e ：f o r eo u rw o r k ，t h e t ei sn or e p o r ta b o u t p e r f o r m a n c e e v a l u a t i o ni na l a r g ev a r i e t y o fi m a g e s ，w h i c hh a s p r e v e n t e dt h ea d v a n c eo f m a t h e m a t i c a le x p r e s s i o nr e c o g n i t i o n ， b e c a u s eo ft h et w o d i m e n s i o n a lf o r m a t t i n go fm a t h e m a t i c a le x p r e s s i o n s ，at r i p l e t t r e e w i t h m a r k e de d g ei s p r e s e n t e dt or e p r e s e n tt h ea n a l y s i sr e s u l to fm a t h e m a t i c a le x p r e s s i o n s t w o a u t o m a t i cp e r f o r m a n c ee v a l u a t i o nm e t h o d so nt h eb a s i so ft r e em a t c h i n ga r ep r o p o s e d ，w h i c h a r e b a s e do nd y n a m i cp r o g r a m m i n g a l g o r i t h ma n db u t d ( b o t t o m - u pa n dt o p d o w n ) a l g o r i t h m ， r e s p e c t i v e l y ，b u t di st h eo n l yk n o w nm e t h o dt h a tc a nf i n da n ye r r o r so fs y m b o ls e g m e n t a t i o n s y m b o lr e c o g n i t i o na n de x p r e s s i o na n a l y s i s ， k e yw o r d s ：m a t h e m a t i c a i e x p r e s s i o ni m a g er e c o g n i t i o n m a t h e m a t i c a le x p r e s s i o na n a l y s i s a u t o m a t i cp c r f o r m a n c ee v a l u a t i o n 第一章引言 1 1 數(shù)學(xué)公式圖像識別的意義 數(shù)學(xué)是“唯一的國際科學(xué)語言”，不受種族、國家、文化和任何方言的限制，不同國 籍的科學(xué)人員都可以通過這種共通的符號溝通。這是因為“數(shù)學(xué)提供了一種有力的、簡潔 的、準(zhǔn)確無誤的交流信息的手段”，正如數(shù)學(xué)算數(shù)一書中所說，“所有數(shù)學(xué)有用性的 理由都根源于數(shù)學(xué)可用作交流信息的有利手段這個事實”。數(shù)學(xué)大師華羅庚甚至認(rèn)為可以 使用數(shù)形關(guān)系圖作為與外星人交流的媒介。這是因為在宇宙中，計數(shù)的規(guī)則應(yīng)該類似，自 然圖形所具備的數(shù)形關(guān)系也是普遍的。魏晉時期的大數(shù)學(xué)家劉徽不使用任何數(shù)學(xué)符號和文 字，不進(jìn)行任何運(yùn)算，只用涂有顏色的“青朱出入圖”就把勾股定理清晰地呈現(xiàn)在人們面 f 狩。無怪乎華羅庚會如此感慨。 數(shù)學(xué)在“宇宙之大、粒子之微、火箭之速、化工之巧、地球之變、生物之謎、日用之 繁”等各方面都有重要貢獻(xiàn)，而數(shù)學(xué)公式是數(shù)學(xué)語言的最主要表現(xiàn)形式，所以科技文獻(xiàn)中 包含大量數(shù)學(xué)公式。這些文獻(xiàn)被掃描儀掃描，作為圖像數(shù)據(jù)保存入計算機(jī)，識別其中的數(shù) 學(xué)公式圖像，就是為了獲取公式中包含的信息，使信息的儲存和使用變得容易，實現(xiàn)信息 更好的交流和共享。例如t 研究人員要求能夠輕易重用數(shù)學(xué)公式；數(shù)字圖書館要求能夠以 便于編輯、便于查找的方式儲存數(shù)學(xué)公式；遠(yuǎn)程教育要求能夠以有效的方式在網(wǎng)絡(luò)上傳輸 數(shù)學(xué)公式?，F(xiàn)有的文檔圖像處理系統(tǒng)能夠高速、準(zhǔn)確的識別文檔圖像中的普通文本，但是 不能正確處理其中的數(shù)學(xué)公式。大多數(shù)情況下，數(shù)學(xué)公式的識別結(jié)果是一些毫無意義的符 號，如圖卜1 。 = 阿 o ，o 巧 ( a ) 公式掃拙圖像 ( b ) 公式識別結(jié)果 圖l l ：一般文檔圖像處理系統(tǒng)識別數(shù)學(xué)公式的結(jié)果 不能夠正確識別數(shù)學(xué)公式圖像會帶來以下問題： 第一，驗證與重用。如果研究人員想要驗證或重用文檔中的數(shù)學(xué)公式，就只能使用專 用的數(shù)學(xué)計算軟件( 例如m a t l a b 或者m a p l e ) ，或者數(shù)學(xué)排版軟件( 例如t b x 或者l a t e x ) ， 按照各自的語法要求重新輸入。這個輸入過程既漫長又令人生厭，而且還要冒著引入新的 錯誤的風(fēng)險。即便是使用新的可視化的公式輸入軟件( 侈l j o l q s c i e n t i f i cw o r k p l a c e 或者 s c i e n c ew o r d ) ，輸入速度也不可能加快很多。 第：，編輯與查找。以圖像形式保存的數(shù)學(xué)公式，既無法編輯修改，也無法實現(xiàn)公式 的查找和檢索。 第三，存儲和傳輸。以圖像形式保存的數(shù)學(xué)公式占據(jù)的空間遠(yuǎn)遠(yuǎn)大于以其他可編輯格 式保存占據(jù)的空間。這樣既耗費(fèi)了存儲空間，又加大了傳輸量。 為什么目前的文檔圖像處理系統(tǒng)不能識別數(shù)學(xué)公式昵? 除了數(shù)學(xué)公式與普通文本反映 的內(nèi)容不同以外，排版結(jié)構(gòu)上也存在很大差別。表1 1 列舉了兩者在結(jié)構(gòu)上的一+ 些區(qū)別。 數(shù)學(xué)公式普通文本 符號間位置關(guān)系 二維( 2 - d )一維( 卜d ) 字符集英文字符、希臘字符、數(shù)字、文本所屬語言的字符集 運(yùn)算符等 字號變化頻繁同段落內(nèi)基本相同 ( 上下標(biāo)字號小) 風(fēng)格斜體居多正體居多 基線 不對齊 行內(nèi)對齊 ( 符號間二維關(guān)系) ( b a s e l i n e ) 符號問距不均勻 均勻，字問距，行間距 符號出現(xiàn)頻率 數(shù)學(xué)運(yùn)算符號出現(xiàn)頻繁遵循一般文本的統(tǒng)計規(guī)律 襲1 1 ：數(shù)學(xué)公式與普通文本的差異 因此識別數(shù)學(xué)公式圖像有著重要的現(xiàn)實意義。 1 2 數(shù)學(xué)公式圖像識別的基本步驟 i 旮動數(shù)學(xué)公式圖像識別的目的就是從包含有數(shù)學(xué)公式的掃描圖像開始，定位其中的公 式，識別公式中的符號，然后根據(jù)符號的內(nèi)容和相互間位置關(guān)系，對公式進(jìn)行分析，并將 分析結(jié)果按照某種1 格式保存，最終實現(xiàn)復(fù)用。如圖l 一2 所示，數(shù)學(xué)公式泌別的基本步驟可 以分為數(shù)學(xué)公式定位、數(shù)學(xué)公式識別、數(shù)學(xué)公式分析以及數(shù)學(xué)公式分析結(jié)果的格式轉(zhuǎn)換輸 出。 無論是數(shù)學(xué)公式定位，數(shù)學(xué)公式符號識別還是數(shù)學(xué)公式分析，都需要對其性能進(jìn)行有 效的評估，以便準(zhǔn)確地定位系統(tǒng)中出現(xiàn)的各種錯誤。 1 3 數(shù)學(xué)公式圖像識別自動性能評估的必要性 現(xiàn)實生活中，我們到處都能見到形形色色的“排行榜”，這些“排行榜”實際上就是 對乖物某些方而的性能或功能的一個評價結(jié)果，不可否認(rèn)“排行榜”對事物發(fā)展有著或多 或少的影響。同樣，對于一個軟件系統(tǒng)而言，在設(shè)計開發(fā)的整個過程中，在每個階段都需 要對各個模塊和各個功能進(jìn)行測試和性能評估。有時候測試和性能評價工具的欠缺甚至成 為系統(tǒng)性能提高和改善的制約因素。因為通常設(shè)計開發(fā)者在對其中的某一個模塊進(jìn), i j = - t 一 個很小的改動，往往就會影響系統(tǒng)性能的方方面面。他們需要花贊大量的時問來分析被修 改以后的系統(tǒng)的性能，而且有時即使花費(fèi)了很多時間對系統(tǒng)性能的評估仍然不準(zhǔn)確。因為 這些分析和評估只是在實驗的基礎(chǔ)上，對一個較小的樣本集進(jìn)行，而不可能對大的樣本集 進(jìn)行，因此這些分析的結(jié)果一般只有理論上的價值，而沒有實際的價值。 數(shù)學(xué)公式圖像識別是一個具有相當(dāng)難度的前沿課題，許多處理方法都還在探索利嘗試 中。無論是公式的定位，公式符號的識別，還是公式的分析都需襄進(jìn)行測試和性能評估。 3 有關(guān)數(shù)學(xué)公式識別系統(tǒng)性能的評測問題至今尚無公認(rèn)的標(biāo)準(zhǔn)，然而性能評估是非常重要 的。為了比較處理方法的優(yōu)劣，就必須在大規(guī)模集合上進(jìn)行測試。如果測試過程不能自動 進(jìn)行，測試規(guī)模就只能很小。 數(shù)學(xué)公式行的二維結(jié)構(gòu)決定了公式識別不僅包含符號識別，更重要的是對其結(jié)構(gòu)的分 析，因此數(shù)學(xué)公式分析的性能評估顯得尤為重要。同時，也下因為二維結(jié)構(gòu)，使數(shù)學(xué)公式 分析的性能評估變得更困難，不能像符號識別那樣僅僅用符號的識別率就能衡量其性能。 雖然已經(jīng)有很多數(shù)學(xué)公式分析的方法，然而這些方法分析得到的結(jié)果究竟如何，準(zhǔn)的 方法效果好，準(zhǔn)確性高，目前尚沒有一個公認(rèn)的評測標(biāo)準(zhǔn)。分析結(jié)果的好壞只能由人工評 判，所以目前幾乎所有的方法都只是在幾十甚至十幾個公式集上進(jìn)行測試，這嚴(yán)重阻礙了 數(shù)學(xué)公式識別研究的進(jìn)一步發(fā)展。這就迫切需要開發(fā)出一個工具，使其對數(shù)學(xué)公式分析技 術(shù)進(jìn)行自動的性能評估。只有這樣，對它們的性能評估才可能在大樣本集上進(jìn)行，得出的 評估數(shù)值才真正具有實際意義。因此對這方面的研究也變得非常有價值了。 1 。4 本文的主要內(nèi)容及結(jié)構(gòu) 數(shù)學(xué)公式圖像漢別的各個階段都需要進(jìn)行有效的測試和性能評估。目前出現(xiàn)的對手寫 體數(shù)學(xué)公式識別的性能評估都存在有片面性，性能指標(biāo)太過籠統(tǒng)以及測試規(guī)模小等缺點(diǎn)， 并不通用。而對于印刷體數(shù)學(xué)公式識別的性能評估，只有m o k a m o t o 等人在 1 1 中提出了 一種基于m a t h m l 格式比較的方法，但是他們的方法只能判斷出分析結(jié)果是否詐確，并沒 有指出錯誤的原因及修改的方法。由于公式本身的二維特點(diǎn)決定了公式關(guān)系用樹表示是非 常恰當(dāng)?shù)模砸话阕R別結(jié)果都采用有層次的樹結(jié)構(gòu)表示，因此本文提出了基于樹匹配的 公式識別自動性能評估的方法。該方法不僅能夠找出符號識別和分析中存在的錯誤，還能 指出錯誤的類型和原因，并以此指導(dǎo)識別方法的修改。作為核心，本文詳細(xì)介紹了兩種樹 匹配算法：動態(tài)規(guī)劃算法和b u t d ( b o t t o m u pa n dt o p - d o w n ，因為每一個樹節(jié)點(diǎn)都采用 先自底向上然后自定向下的比較過程) 算法。其中b u t d 算法不僅能夠評估公式分析的一陛 能，還能評估符號切割和識別的性能。最后我們給出了b u t d 算法的實驗結(jié)果。 第一章：概述了數(shù)學(xué)公式圖像處理的意義和基本步驟，以及數(shù)學(xué)公式識別的自動性能 評估在數(shù)學(xué)公式處理中的地位。 第二章：給出性能評估的概念和系統(tǒng)性能評估的一般模型。概述公式識別的結(jié)果并提 l 乜識別結(jié)果的三叉樹表示，同時總結(jié)了當(dāng)前公式識別性能評估的現(xiàn)狀。就此本文提出一個 公式識別的自動性能評估模型和兩種基于樹匹配的性能評估算法：動態(tài)規(guī)劃算法與b u t d 4 算法。 第三章：給出基于動態(tài)規(guī)劃的性能評估算法。由于我們使用帶邊屬性的三叉樹與一般 帶標(biāo)記的樹結(jié)構(gòu)有所不同，而且節(jié)點(diǎn)匹配的標(biāo)準(zhǔn)也不一樣，因此本文將傳統(tǒng)的動態(tài)規(guī)劃匹 配算法進(jìn)行了擴(kuò)充和改進(jìn)，即把傳統(tǒng)的節(jié)點(diǎn)更改，節(jié)點(diǎn)插入和節(jié)點(diǎn)刪除三種基本編輯操作 擴(kuò)充為節(jié)點(diǎn)完全替代，節(jié)點(diǎn)內(nèi)容修改，節(jié)點(diǎn)類型修改，節(jié)點(diǎn)插入，節(jié)點(diǎn)刪除，邊屬性修改 六種基本編輯操作，以滿足公式識別性能評估的特殊需要。對該算法進(jìn)行了詳細(xì)的描述利 分析，并給出一個實例。 第四章：給h _ 基于b u t d 的性能評估算法。動態(tài)規(guī)劃算法由于受到節(jié)點(diǎn)的兄弟次序不 變和祖孫次序不變的約束，在記錄錯誤的時候存在冗余，隱藏了某些錯誤的根本原因，因 此本文根據(jù)實際需要，將動態(tài)規(guī)劃中的編輯操作和錯誤類型進(jìn)一步擴(kuò)充，使錯誤類型能夠 直接反映出錯誤的本質(zhì)原因，并提出新的匹配算法( b u t d ) 。詳細(xì)介紹了該算法的流程， 同時給出相應(yīng)的實例。最后從合理性和效率兩個角度比較了b u t d 算法和動態(tài)規(guī)劃算法， 證明b u t d 算法比動態(tài)規(guī)劃算法更具優(yōu)勢。 第五章：給出了基于b u t d 算法的自動性能評估的實驗結(jié)果，并對結(jié)果進(jìn)行了分析和 總結(jié)。 第二章數(shù)學(xué)公式圖像識別的自動性能評估模型 2 1 性能評估概述 所謂性能評估是指根據(jù)一定的基準(zhǔn)數(shù)據(jù)來進(jìn)行的測試比較。性能評估在比較幾個相似 的復(fù)雜系統(tǒng)時非常重要。此外，當(dāng)一個系統(tǒng)被修改或者被更新版本時，也需要對修改后的 系統(tǒng)的性能做出評估。在這種隋況下，性能評估不僅要對整個系統(tǒng)進(jìn)行，而且需要對系統(tǒng) 的各個模塊來進(jìn)行，這樣才有機(jī)會發(fā)現(xiàn)系統(tǒng)中的薄弱環(huán)節(jié)，并且給出一個直接面向系統(tǒng)目 標(biāo)的改進(jìn)。 2 1 1 性能評估的一般目標(biāo) 性能評估基本上追求以下三個目標(biāo)： 提高系統(tǒng)性能并對系統(tǒng)進(jìn)行質(zhì)量控制： 比較多個復(fù)雜系統(tǒng)； 評估系統(tǒng)的性能，即定義一個系統(tǒng)性能的絕對值。 性能評估的第一個目標(biāo)是提高或者維護(hù)系統(tǒng)的性能。 性能評估的第二個目標(biāo)是比較多個不同的系統(tǒng)。這在要從幾個系統(tǒng)中選擇一個最好的 系統(tǒng)去完成某項任務(wù)時，是非常關(guān)鍵的。 性能評估的第三個目標(biāo)是進(jìn)行性能評估，給出評價系統(tǒng)性能的一個絕對數(shù)值，這個數(shù) 值可以說l 蟈系統(tǒng)的當(dāng)前發(fā)展水平。它描述了在不同特征的輸入數(shù)據(jù)情況下，實際系統(tǒng)和理 想系統(tǒng)之間的性能差距。 這些情況下，性能評估的執(zhí)行都是基于系統(tǒng)比較。這種比較可以是兩個系統(tǒng)之問的比 較，也可以是多個系統(tǒng)之問的比較。如果要評價系統(tǒng)性能的絕對值，可以用該系統(tǒng)與所謂 的理想系統(tǒng)進(jìn)行比較。而所有這些比較的執(zhí)行都使用參考數(shù)據(jù)或者基準(zhǔn)( g r o u n dt r u t h 簡 稱g t ) 來作為比較的依據(jù)。 下面，我們給出一個基于上述目標(biāo)的關(guān)于性能評估的更正規(guī)的描述。通常情況一f ，一 個性能評估包含輸入數(shù)據(jù)，一個或多個系統(tǒng)，一個評估函數(shù)和一個評價函數(shù)。 6 一一一。 輸入數(shù)據(jù)兩個系統(tǒng) 評估函數(shù) 評價函數(shù)l - - 一- 一一一一一- 一一一一一一一一一一一_ _ - - _ - _ - _ - - _ - - - _ _ _ - - - 一一_ 一一一一_ 一一一一一一_ 一一一- _ _ - _ _ - - _ 一- 圖2 - 1 ：兩個系統(tǒng)的性能評估模型 1 一一一一。一一一一一一。- 。一一一一一1 輸入數(shù)據(jù)一個系統(tǒng)評估函數(shù)： l 匾亟畫口魚l 墮) 笪l 圃i 圖2 - 2 ：一個系統(tǒng)的性能評估模型 圖2 1 和圖2 - 2 分別表示對兩個系統(tǒng)和一個系統(tǒng)進(jìn)行比較評估的模型，其中各模塊說明 如下： 輸入數(shù)據(jù)( i n p u t d a t a ) 的選擇對于性能評估來說是非常重要的。輸入數(shù)據(jù)對于系統(tǒng)處 理的般任務(wù)應(yīng)該具有代表性。有的系統(tǒng)本身對它所要完成的任務(wù)描述就不清楚，但是對 于一個確定的算法不會出現(xiàn)這種情況。然而這里系統(tǒng)的概念是包含理想系統(tǒng)( 見2 1 2 節(jié)) 的，這個理想系統(tǒng)是存在于設(shè)計者的腦海里的。系統(tǒng)所給出的描述可能是系統(tǒng)的理想輸出 或者是一種基準(zhǔn)( g t ) 。從實際的角度考慮，這利，方法看上去很合理，因為性能評估通常 要求系統(tǒng)的輸出滿足或者達(dá)到一定的要求。 評估函數(shù)( a s s e s s m e n tf u n c t i o n ) 是性能評估的另一個重要部分。評估函數(shù)是根據(jù)系統(tǒng) 的輸出而賦的一個值，這個值可以是基于系統(tǒng)的輸出與對應(yīng)輸入的比較所得出的值，它定 量地反映了系統(tǒng)輸出的質(zhì)量。顯然，不同的評估函數(shù)對于系統(tǒng)相同的輸出會有一i 同的結(jié)果。 而理想的評估函數(shù)總是能產(chǎn)生一個最優(yōu)的值。評估函數(shù)對于某些系統(tǒng)是比較確定的，但是 對于數(shù)學(xué)公式處理系統(tǒng)或公式分析模塊來說就不是很確定了，因此，評估函數(shù)的選擇是一 個很重要的因素。 評價函數(shù)( e v a l u a t i o nf u n c t i o n ) 用于比較幾個不同系統(tǒng)的評估函數(shù)的值。這個函數(shù)繪 出的結(jié)果是幾個系統(tǒng)中哪個好哪個壞，或者哪個更好一些。評價結(jié)果應(yīng)當(dāng)同時指出對輸入 數(shù)據(jù)的分類情況。因此，輸出結(jié)果就不應(yīng)當(dāng)是：“系統(tǒng)a 比系統(tǒng)b 好”，而是：“在輸入有 字符粘連( t o u c h i n g ) 的情況下，系統(tǒng)a 比系統(tǒng)b 好”?；蛘咻敵鼋Y(jié)果中可以包含假設(shè)的 測試過程。 如果輸入數(shù)據(jù)、系統(tǒng)、評估函數(shù)和評價函數(shù)都確定了，則性能評估也就確定了。 7 2 1 2 理想系統(tǒng)與理想評估 在此，我們給出理想系統(tǒng)與理想評估的概念。 我們所說的性能評估都隱含著：每個實際系統(tǒng)s y s 都對應(yīng)一個理想系統(tǒng)d s y s 。這個理 想系統(tǒng)以最優(yōu)的方式解決了實際系統(tǒng)所要解決的問題。由于理想系統(tǒng)是實際系統(tǒng)所希望達(dá) 到的目標(biāo)，實際系統(tǒng)就會試圖將它的輸出向基準(zhǔn)靠近。對應(yīng)于理想系統(tǒng)，也有一個理想的 評估。理想評估總是以期望的方式來評估系統(tǒng)的輸出。如果系統(tǒng)的輸出是理想輸出，則評 估結(jié)果就應(yīng)該是一個最優(yōu)值，否則評估結(jié)果就應(yīng)該差一些。由于實際應(yīng)用中也許只提供了 有限的信息，使實際的評估含有不精確的因素，因此實際的評估只是理想評估值的一個近 似。理想評估是一個沒有錯誤的評估，不同的目標(biāo)應(yīng)該由不同的評估來完成。 因此，理想系統(tǒng)和理想評估相對于實際系統(tǒng)和實際評估是一個沒有錯誤情況的系統(tǒng)模 型和評估模型。我們的目標(biāo)是要最優(yōu)地近似這些理想模型。 2 1 3 測試基準(zhǔn)( g r o u n dt r u t h ) 這里所提到的測試基準(zhǔn)就是前面所介紹的基準(zhǔn)( g r o u n dt r u t h 簡稱g t ) 。在數(shù)學(xué)公式 識別系統(tǒng)中，基準(zhǔn)代表系統(tǒng)的最優(yōu)輸出。在性能評估中我們也使用這個詞來表示評估所依 賴的標(biāo)準(zhǔn)，為了定義基準(zhǔn)，我們必須考慮這個最優(yōu)是相對于一個什么參考標(biāo)準(zhǔn)而言的，即： 相對于什么最優(yōu)? 。 例如在數(shù)學(xué)公式識別系統(tǒng)中，基準(zhǔn)主要是為系統(tǒng)的輸出定義的。對于數(shù)學(xué)公式處理系 統(tǒng)的輸出，基準(zhǔn)就是人對于數(shù)學(xué)公式圖像的識別結(jié)果。因此，在這種情況下，是人決定什 么足最優(yōu)。例如，圖2 3 所示，也許有人認(rèn)為t ，a ，c 是同一行的關(guān)系，而有入則 認(rèn)為一a 是1 t 的上標(biāo)，c 是a 的上標(biāo)，遇到這種情況，就要考慮是相對誰最優(yōu)? 。 當(dāng)我們要確定一個系統(tǒng)某些內(nèi)部模塊輸出的基準(zhǔn)，這個最優(yōu)輸出就依賴于浚模塊之后的其 它模塊，所以基準(zhǔn)可以在系統(tǒng)任何兩個模塊的接口之間定義。因此，在確定了輸入數(shù)據(jù)， 評估函數(shù)和評價函數(shù)之后，性能評估也可以在系統(tǒng)的任意兩個模塊之間進(jìn)行。如圖2 - 4 所 示。 總之，我們需要一個評估函數(shù)，這個評估函數(shù)可以出人來確定，也可以山系統(tǒng)的后續(xù) 模塊確定。 不失一般性，我們可以認(rèn)為評估函數(shù)是一個計算代價的函數(shù)。這個代價就是將系統(tǒng)的 輸出修改成為最優(yōu)輸出所需要花費(fèi)的代價。這就意味著評估函數(shù)的值總是大于或等于零。 而且系統(tǒng)的輸出結(jié)果越好，代價值就越小。對于基準(zhǔn)來說，該評價函數(shù)的值應(yīng)該等于零。 這是一個一般意義上的定義，因為其它函數(shù)都可以很容易地轉(zhuǎn)化為這種代價函數(shù)的形式。 - 一- - - - 一_ 一一一一一一_ 一_ 一一一一一一一一一一 ：性能評估1 ：基準(zhǔn)l c a c 圖2 - 3 性能評估n l性能評估n ； 圖2 - 4 ：基準(zhǔn)可以在系統(tǒng)的各個地方定義 定義2 1 ：假設(shè)給定系統(tǒng)曲s 和它的輸入數(shù)據(jù)集合i n 。跏。是輸入數(shù)據(jù)i n ( i n 脅) 在基準(zhǔn) 中的對應(yīng)結(jié)果，系統(tǒng)s y s 對應(yīng)的理想系統(tǒng)是l d s y s 理想的評估函數(shù)為l d a s s a 則： i d s y s ( i n ) = g t l , ，且i d a s s ( g t i , 。) = 0 注：一個輸入數(shù)掘可能對應(yīng)多個基準(zhǔn)。因為可能有幾種結(jié)果都被認(rèn)為是最優(yōu)的。但是通常 出現(xiàn)這種情況時，我們就給出一些特殊規(guī)定或說明，從而選定這幾種結(jié)果中的一種作為基 準(zhǔn)。 2 2 數(shù)學(xué)公式圖像識別結(jié)果及其自動性能評估現(xiàn)狀 2 2 1 數(shù)學(xué)公式圖像識別的結(jié)果 圖像i f ，的數(shù)學(xué)公式經(jīng)過定位，符號識別和分析之后以某種格式保存即得到公式的識別 結(jié)果，因此數(shù)學(xué)公式識別的結(jié)果實際上等同于公式分析之后所得的結(jié)果。 數(shù)學(xué)公式分析就是在正確識別公式的每個符號，并且得到包含該符號的最小外接矩形 的j i g ；i l l l 上，分析符號之間的關(guān)系并進(jìn)行組合，理解公式的含義，實現(xiàn)公式版式結(jié)構(gòu)的恢復(fù)， 甚至表達(dá)式的自動計算，最后將分析結(jié)果用某種數(shù)據(jù)結(jié)構(gòu)( 一般是圖或者樹) 表示出來。 根據(jù)最終分析目標(biāo)的不同，數(shù)學(xué)公式分析分為兩種層次m l ： ( 1 ) 版式以別( l a y o u tr e c o g n i t i o n ) ：版式識別要求分析結(jié)果足夠恢復(fù)該公式的排版樣式， 但是不需要理解整個公式的數(shù)學(xué)含義。版式識別結(jié)果可以使用l a t 。x 等排版語言輸出。文 獻(xiàn)電子化過程中，為了保證版面的一致，就需要識別數(shù)學(xué)公式的版式。 q ( 2 ) 語義識別( s e m a n t i cr e c o g n i t i o n ) ：語義識別要求確切理解整個數(shù)學(xué)公式的數(shù)學(xué)含 義，即明確表達(dá)式的計算順序和函數(shù)的作用域。語義識別結(jié)果可以使用m a t l a b 等數(shù)學(xué)計算 軟件包的語言輸出。實現(xiàn)數(shù)學(xué)公式的自動計算就需要識別公式的語義。 同一公式的版式識別和語義識別的結(jié)果并不相同，我們以公式( 2 - 1 ) 為例給出版式 識別結(jié)果與語義識別結(jié)果。圖2 5 是利用樹結(jié)構(gòu)表示的版式識別結(jié)果。圖2 - 6 是利用樹結(jié) 構(gòu)表示的語義識別結(jié)果。 由于語義識別的難度遠(yuǎn)大于版式識別的難度，因此目前絕大部分?jǐn)?shù)學(xué)公式分析都是以 版式識別為目的。版式識別的分析方法大致可以分為兩種：基于結(jié)構(gòu)的分析方法和基于文 法的分析方法。 基于結(jié)構(gòu)的分析方法就是直接根據(jù)各個符號的內(nèi)容、大小、相對位置以及符號間的空 t 3 等結(jié)構(gòu)信息判斷出相鄰符號的關(guān)系，生成符號組，合并子表達(dá)式，從而實現(xiàn)數(shù)學(xué)公式分 析的方法。這種分析方法既可以把握公式的整體結(jié)構(gòu)，也可以把握局部符號之間的關(guān)系， 能夠處理格式復(fù)雜，符號數(shù)目多的公式。結(jié)構(gòu)分析可以較好的識別公式版式，但語義識別 的能力較差。 基于文法的分析方法是通過定義文法來分析數(shù)學(xué)公式的含義。這種方法具有很強(qiáng)的語 義識別能力，但是只能處理格式簡單，類型單一，符號數(shù)目少的數(shù)學(xué)公式，根本不能滿足 實際需要。 工3 l n 工+ f ( 2 一1 ) i x d x 7 l a t e x 結(jié)果輸出： l nx + f r a c x “3 j x i n t _ a “b x d x 圖2 - 5 版面識別結(jié)果 m a t l a b 結(jié)果輸出： l n ( x ) + ( x “3 u a d ( x 1 ，a ，b ) 圖2 - 6 語義識別結(jié)果 得到公式的分析結(jié)果之后，我們就可以視其為基準(zhǔn)，基于它來評估整個識別系統(tǒng)的性 1 0 能。就目前來況，基于結(jié)構(gòu)的分析方法居多，所以我們后面定義的1 1 種公式關(guān)系只反歡了 結(jié)構(gòu)信息，如果定義足夠的關(guān)系，那么語義信息同樣也是可以評估的。 2 2 2 數(shù)學(xué)公式圖像識別結(jié)果的表示 l a t e x 是一種科技排版軟件，常用于數(shù)學(xué)文獻(xiàn)的排版，而且l a t e x 格式的源文件是人 可以閱讀并理解的文本格式。因此可以將數(shù)學(xué)公式識別結(jié)果保存為l a t e x 格式。以下是數(shù) 學(xué)公式及相應(yīng)的l “t b x 表達(dá)式： f m ) 如2 毛w 。，( x i ) - ) 、 i n t 一 o l “ i n f t y f f l e f t ( x u i g h t ) d x l p p r o x , s u m “ n ) 一( i = lj w 一 i c a x 一 i f q e f t ( x i h - i g h t ) 】 無論用什么樣的分析方法，公式本身的二維特點(diǎn)決定了公式關(guān)系用樹表示是非常恰當(dāng) 的，所以一般分析結(jié)果都采用有層次的樹結(jié)構(gòu)表示，另外我們很容易就能將l 4 t b x 格式轉(zhuǎn) 化為樹結(jié)構(gòu)。因此，我們提出用一種帶邊屬性的三叉樹來表示數(shù)學(xué)公式的分析結(jié)果，從這 種三叉樹結(jié)構(gòu)很容易就可以得到公式的版式結(jié)構(gòu)，給人一種直觀的感覺。 根撕人二件寫、閱讀公式的習(xí)慣，并參考l 葉e x 語言表示數(shù)學(xué)公式的方法我們將數(shù)學(xué) 公式劃分成l1 種類型，即：多行表達(dá)式( m u l t i l i n ee x p r e s s i o n ) 分式表達(dá)式( f r a c t i o n e x p r e s s i o n ) ，根式表達(dá)式( r a d i c a le x p r e s s i o n ) ，定界表達(dá)式( d e l i m i t e r e x p r e s s i o n ) ，矩陣 表達(dá)式( m a t r i xe x p r e s s i o n ) ，組表達(dá)式( g r o u p e x p r e s s i o n ) ，堆疊表達(dá)式( s t a c k e x p r e s s i o n ) ， 帽子表達(dá)式( h a te x p r e s s i o n ) ，角標(biāo)表達(dá)式( s c r i p te x p r e s s i o u ) ，普通表達(dá)式( c o m m o n e x p r e s s i o n ) 和基元表達(dá)式( p r i m a r ye x p r e s s i o n ) 。圖2 7 至2 一1 7 給出了各種表達(dá)式的示 例。 ( z + ) ( z y ) = z 2 一x y + x y y 2 = z 2 一y 2 j i a 2 一b 2 a + b 圖2 - 8 ：分式表達(dá)式示例 ( 8 2 3 + 1 2 3 ) 圖2 - 1 0 ：定界表達(dá)式示例 x l lx 1 2 x 2 1x 2 2 圖2 一1 2 ：矩陣表達(dá)式示例 圖2 7 ：多行表達(dá)式示例 1 2 3 _ _ a + b + + y + z 圖2 一1 4 ：帽子表達(dá)式示例 z = 2 0 + 3 可 圖2 一1 6 ：普通表達(dá)式示例 乒2 + y 2 + 2 z 可 圖2 9 ：根式表達(dá)式示例 n i - - - - 1 圖2 一1 1 ：組表達(dá)式示例 圖2 1 3 ：堆疊表達(dá)式示例 z y 2 圖2 - 1 5 ：角標(biāo)表達(dá)式示例 z 圖2 一1 7 ：基元表達(dá)式示例 任意類型的公式都可以用帶邊屬性的三叉樹表示，自然整個數(shù)學(xué)公式也可以表示成一 棵三叉樹。樹中每個節(jié)點(diǎn)代表一個數(shù)學(xué)符號或一個組元( 如s i n ，l o g ，m i n ，1i m 等) ，節(jié)點(diǎn) 中給出了相應(yīng)符號的識別結(jié)果，位置信息以及公式類型，并且每個節(jié)點(diǎn)至多有三個非空子 節(jié)點(diǎn)。每條邊都有一個屬性值，指出所連接的兩個節(jié)點(diǎn)之間的關(guān)系，包括：同行( n e x t ) ， 上標(biāo)( s u p e r s c r i p t ) ，下標(biāo)( s u b s c r i p t ) ，組表達(dá)式上標(biāo)( l o pu p s c r i p t ) , 組表達(dá)式下標(biāo) ( l o i d o w n s c r i p t ) ，分子( n u m e r a t o r ) ，分母( d e n o m i n a t o r ) ，帽子( h a t ) ，堆疊( s t a c k ) ， 根式開方數(shù)( r a d i c a l e x p ) ，根式被開方數(shù)( r a d i c a l m a i n ) ，矩陣起始元素( m a t r f x b e g n ) ， 矩陣結(jié)束元素( m a f r i x e n d ) 。對于多行表達(dá)式，我們把每一行表達(dá)式看成一棵獨(dú)立的三叉 樹。這種結(jié)構(gòu)類似于公式的版式結(jié)構(gòu)，但是比版式結(jié)構(gòu)包含更多的語義信息。如圖2 一1 8 所示為公式磐+ 等的三叉樹熟 圖2 1 8 ：公式口f + 蘭 的三叉樹結(jié)構(gòu)示例 l - i j 用帶有邊屬性的三叉樹表示數(shù)學(xué)公式的結(jié)構(gòu)，會使某些公式類型“消失”，如定界表達(dá) 式( d e l i m i t e r e x p r e s s i o n ) ，堆疊表達(dá)式( s t a c ke x p r e s s i o n ) 帽子表達(dá)式( c a d e x p r e s s i o n ) 以及伯標(biāo)表達(dá)式( s c r i p te x p r e s s i o n ) ，這些表達(dá)式類型信息將保存在相應(yīng) 子表達(dá)式的邊屬性中，而不必在節(jié)點(diǎn)中記錄。這種節(jié)點(diǎn)平衡的三叉樹結(jié)構(gòu)極大的方便了后 續(xù)的基于樹匹配算法的性能評估工作。 2 2 3 自動性能評估的現(xiàn)狀 1 9 6 8 年，a n d e r s o n 在他的博士論文1 1 i 中最早提出了數(shù)學(xué)公式的處理問題，在隨后的三 十多年中，有關(guān)數(shù)學(xué)公式處理的各個方面都有或多或少的研究。由于早期的研究人員主要 致力于理論方面的研究，而沒有實驗結(jié)果，因此直到后來刊。提出如何評價一個數(shù)學(xué)公式處 理系統(tǒng)的性能問題。在2 0 0 0 年之前的文獻(xiàn)中所提到的評估方法都是針對手寫體數(shù)學(xué)公式 的，大致可以歸為三類： ( 1 ) 注重于公式的結(jié)構(gòu)，通過測試只給出兩種結(jié)果，即f 確或不正確。 ( 2 ) 只考慮符號的識別率。 ( 3 ) 只對少數(shù)非常典型的公式進(jìn)行評測，這些公式由少數(shù)固定人員書寫，而且書寫整潔。 這些手寫體數(shù)學(xué)公式的評估方法都具有片面性，性能指標(biāo)太過籠統(tǒng)以及測試規(guī)模小等 缺點(diǎn)，并不通用。k a m f a ic h a n 等在 1 2 中也提到了在線手寫體數(shù)學(xué)公式處理系統(tǒng)的性能 評估問題，他們綜合了前人的方法，將錯誤類型分成兩種：公式中符號的識別錯誤和公式 本身結(jié)構(gòu)的錯誤，給出了兩種錯誤率的計算公式，即錯誤個數(shù)除以總數(shù)，但是也僅僅是如 此而已，并沒有說明如何找到那些錯誤，也未提出有效的評測步驟和過程。 對于印刷體數(shù)學(xué)公式識別的性能評估，至今只有m o k a m o t o 等人在 1 1 中提出了一種 基于m a t h m l 格式比較的方法。他們將公式的標(biāo)準(zhǔn)分析結(jié)果和實際的分析結(jié)果都用 m a t h m l 格式表示，在此基礎(chǔ)上進(jìn)行比較檢查那些典型公式結(jié)構(gòu)( 如角標(biāo)，分式，根式， 極限，矩陣等) 的分析是否正確。首先，對應(yīng)的兩個公式結(jié)構(gòu)的圖像坐標(biāo)一致時，才會比 較兩者的結(jié)構(gòu)類型是否相符臺，因此將子表達(dá)式圖像的左上角和右下角坐標(biāo)作為標(biāo)記( t a g s ) 加l 入到m a t h m l 格式中，如圖2 1 9 所示。其次，用正確或錯誤表示公式結(jié)構(gòu)比較的結(jié)果， 即如果對應(yīng)的兩個公式結(jié)構(gòu)類型一致，就認(rèn)為分析是j 下確的，否則認(rèn)為是錯誤的?？紤]到 盡管整個公式結(jié)構(gòu)可能不完全相同，但是其中某些予表達(dá)式結(jié)構(gòu)類型也許是一致的，所以 他們用一利予結(jié)構(gòu)方法來比較兩個子結(jié)構(gòu)。主要步驟如下： 1 從標(biāo)準(zhǔn)分析結(jié)果中找每個子表達(dá)式最內(nèi)部的標(biāo)記： 2 如果這個標(biāo)記( 比如 ) 在實際分析結(jié)果中存在，則 檢查標(biāo)記內(nèi)部子表達(dá)式的結(jié)構(gòu)類型是否相同。如果不相同，則記錄該子表達(dá)式結(jié)構(gòu)類型錯 誤。 4 圖2 一1 9 ：公式結(jié)構(gòu)的m a t h m l 表示 盧 餞 j ：塥i 訕耐i 誦i ；t j “ t - ， ：n 毪戇甥鱗孵州矗睫二： t 由a r t s e l “e l l l 強(qiáng) ：蘆黼鬻研憾螄嘲 o io _ ，l 1 i q h i -i _ 1 1m - i 2 2 ，帥，黧4 a i i i 釜, i j 她一蚋s 盟j i 3 1 ：n o t f o u n d - o , - jt 的r e c o g n i t i o nr e s h l f 圖2 - 2 0 ：公式結(jié)構(gòu)的比較示例 以圖2 2 0 所示的公式分析結(jié)果為例，首先，對于標(biāo)準(zhǔn)分析結(jié)果中的標(biāo)記 ，在實際分析結(jié)果中也檢測到了，因此比較標(biāo)記中兩個子表達(dá)式類型 由標(biāo)記中“m f r a c ”知道，它們具有相同的類型，都為分式，所以這個子表達(dá)式分析正確。 1 5 其次，同理可知標(biāo)i g 中的子表達(dá)式分析結(jié)果也是正確的 再次，由于標(biāo)準(zhǔn)分析結(jié)果中的標(biāo)記 在實際分析結(jié)果巾不存 在，凼此認(rèn)為該標(biāo)記中的角標(biāo)( s u b s u p ) 結(jié)構(gòu)類型分析錯誤。 對于簡單的非常典型的公式結(jié)構(gòu)，mo k a m o t o 的方法效果比較好，但是對于復(fù)雜一點(diǎn) 的結(jié)構(gòu)，其比較結(jié)果不甚理想，因此該方法沒有很好的通用性。此外，他們只是判斷出分 析結(jié)果是否正確，并沒有指出錯誤的原因，這= ；_ i l i 滿足我們評估的宗旨即為系統(tǒng)的設(shè)計開發(fā) 者指出問題所在和改進(jìn)方向。 基于目前的實際情況，實現(xiàn)數(shù)學(xué)公式識別的自動性能評估不僅是必要的而且是艱巨的。 2 3 數(shù)學(xué)公式圖像識別的自動性能評估模型 2 3 1 自動性能評估模型 為了提高整個公式處理系統(tǒng)的性能，或者比較各種公式處理方法的效果，需要在大規(guī) 模集合上進(jìn)行測試，因此我們需要構(gòu)建一個自動性能評估系統(tǒng)來定量地評估公式結(jié)果，當(dāng) 然這是相當(dāng)困難的。 從2 1 的討論，我們知道為了對數(shù)學(xué)公式識別系統(tǒng)進(jìn)行性能評估，我們需要有一個衡 量性能的尺度，還需要一些基準(zhǔn)數(shù)據(jù)，以及一個實用的算法來比較公式分析的結(jié)果與基準(zhǔn) 數(shù)據(jù)，從而得出性能評估的結(jié)果數(shù)據(jù)。對這些結(jié)果數(shù)據(jù)迸行統(tǒng)計以后，將最終結(jié)果反饋給 設(shè)計開發(fā)者，可以幫助他們很快地知道公式分析算法的效果。這些統(tǒng)計結(jié)果之中包括對錯 誤的分類，對錯誤嚴(yán)重程度的估算，以及對這些錯誤可能產(chǎn)生的原因的分析?；谏鲜隹?慮，我們提出了圖2 2 l 所示的自動性能評估模型，這實際上是將數(shù)學(xué)公式識別系統(tǒng)與一 個理想系統(tǒng)進(jìn)行比較。 下面，對性能評估模型中主要部分作一個簡要說明： 基準(zhǔn)數(shù)據(jù)是評估實際識別結(jié)果的一個參考標(biāo)準(zhǔn)。在我們的自動性能評估系統(tǒng)中，摹準(zhǔn) 數(shù)據(jù)是每個數(shù)學(xué)公式的正確的三叉樹結(jié)構(gòu)。我們構(gòu)造一個標(biāo)準(zhǔn)的數(shù)據(jù)庫。用來存放各個數(shù) 學(xué)公式的f 確的三叉樹格式文件。 公式識別的結(jié)果數(shù)據(jù)是系統(tǒng)實際識別所得的結(jié)果。 格式轉(zhuǎn)換模塊用于將實際的分析結(jié)果轉(zhuǎn)換為帶邊屬性的三叉樹結(jié)構(gòu)，該模塊可以內(nèi)嵌 于公式識別系統(tǒng)中，也可以獨(dú)立運(yùn)作。 轉(zhuǎn)換結(jié)果數(shù)掘是將實際的識別結(jié)果通過格式轉(zhuǎn)換所得，是實際識別結(jié)果的三叉樹結(jié)構(gòu)。 性能評估算法是自動性能評估系統(tǒng)的核心。一個有效而實用的性能評估算法是真正做 到自動進(jìn)行性能評估的關(guān)鍵，否則就只能紙上談兵。有關(guān)性能評估算法參見2 3 2 小節(jié)。 性能評估的結(jié)采是各種錯誤的描述文件和統(tǒng)計數(shù)字文件a 性能評估結(jié)果的表示工具是性能評估結(jié)果的表現(xiàn)形式，我們采用圖形，表格，文術(shù)棚 結(jié)合的表示方式。 圖2 2 l ：數(shù)學(xué)公式識別系統(tǒng)的自動性能評估模型 凡是能將實際以別結(jié)果通過格式轉(zhuǎn)換模塊轉(zhuǎn)化為帶邊屬性的三叉樹結(jié)構(gòu)的公式識別系 統(tǒng)，都可p j 我們基于該模型構(gòu)建的自動性能評估系統(tǒng)來評測系統(tǒng)的性能。 2 3 2 性能評估算法概述 根據(jù)2 3l 的自動性能評估模型，我們設(shè)計了兩個基于樹匹配的算法來實現(xiàn)上述的評估 方法a 一一是經(jīng)過擴(kuò)充的動態(tài)規(guī)劃算法，二是b u t d ( b o t t o m u pa n dt o p d o w n ) 算法。要 構(gòu)建這樣一個自動性能評估系統(tǒng)，關(guān)鍵的有兩點(diǎn)： - a 定義性能指標(biāo)，即從哪些方面來衡量諺! 別結(jié)采的好壞。掇據(jù)上述描述，對公式識別結(jié)梁 的評估最終是將實際分析得到結(jié)果與基準(zhǔn)數(shù)據(jù)進(jìn)行比較，因此我們采用編輯距離表示 1 7 兩棵樹之間的差異，用該距離中出現(xiàn)的各種編輯操作的個數(shù)來定景描述相應(yīng)的分析錯 誤，并且給出各種統(tǒng)計結(jié)果。具體的編輯操作將根據(jù)所使用的樹匹配算法而定，見3 1 小節(jié)。 b 設(shè)計出有效的樹匹配算法。彥算法在時間效率上應(yīng)該是比較快的，否則性能評估占去太 多的時間會給人一種本末倒置的感覺。 在動態(tài)規(guī)劃算法中，我們定義了節(jié)點(diǎn)完全替代，節(jié)點(diǎn)內(nèi)容修改，節(jié)點(diǎn)類型修改，節(jié)點(diǎn) 插入，節(jié)點(diǎn)刪除，邊屬性修改六種基本編輯操作，而在b u t d 算法中我們定義了節(jié)點(diǎn)內(nèi)容 修改，節(jié)點(diǎn)類型修改，節(jié)點(diǎn)插入，節(jié)點(diǎn)刪除，節(jié)點(diǎn)分裂，節(jié)點(diǎn)合并，節(jié)點(diǎn)轉(zhuǎn)移和邊屬性修 改八種基本編輯操作，用這些編輯操作的數(shù)目和比例來評估公式識別方法的性能。其中的 節(jié)點(diǎn)內(nèi)容修改反映了公式符號識別的性能，其它操作則主要反映了公式分析和符號切割的 性能。兩種樹匹配算法的輸入與輸出分別為： 算法的輸入 按照自動性能評估模型，算法的輸入應(yīng)該是待比較的公式實際分析結(jié)果的轉(zhuǎn)換結(jié)果與 相應(yīng)的基準(zhǔn)數(shù)據(jù)，即公式的三叉樹。 算法的輸出 輸出是比較后的結(jié)果描述文件和性能評估的統(tǒng)計數(shù)字文件。結(jié)果描述文件中包括對正 確情況的描述和對錯誤情況的描述，錯誤情況根掘不同的編輯操作錯誤進(jìn)行歸類描述。而 性能評估的統(tǒng)計數(shù)字文件則包含了公式分析的各種錯誤類型的數(shù)目和它們在整個錯誤中 所占的比例以及各種公式類型的分析錯誤率。 在后續(xù)兩章我們會給出兩種算法的詳細(xì)描述及相應(yīng)的實例。 第三章基于動態(tài)規(guī)劃算法的自動性能評估 3 - 1 預(yù)備知識 由于我們的自動性能評估系統(tǒng)主要通過樹匹配算法實現(xiàn)性能評估，因此先介紹有關(guān)樹 及樹匹配的相關(guān)基礎(chǔ)知識。 3 1 1 樹的遍歷 本文所涉及到的樹都是指帶標(biāo)記的有序樹，即樹中每個節(jié)點(diǎn)都有一個標(biāo)i , e ( 1 a b e l ) ，甚至 可能有某些附加的信息( 這種信息被稱作節(jié)點(diǎn)的內(nèi)容) ，并且如果該節(jié)點(diǎn)有子節(jié)點(diǎn)，則子 節(jié)點(diǎn)之間從左至右的順序是固定的。這里所提到的從左到右的順序是指按照某種方式對樹 進(jìn)行遍歷，得到所有節(jié)點(diǎn)的一個排序，每個節(jié)點(diǎn)在排序中的相對位置。所謂遍歷就是將樹 中每個節(jié)點(diǎn)都訪問一遍，通常有先根遍歷，后根遍歷幾種方式等。先根遍歷就是先訪問根 結(jié)點(diǎn)，再訪問它的子節(jié)點(diǎn)；反之，先訪問子節(jié)點(diǎn)再訪問根節(jié)點(diǎn)則稱之為后根遍歷。 由于本文后面介紹的兩個算法都采用后根遍歷，所以在此舉例說明。與一般樹中的節(jié) 點(diǎn)有所不同，我, f i g f i 1 每個節(jié)點(diǎn)代表一種表達(dá)式類型，節(jié)點(diǎn)本身的結(jié)構(gòu)比較復(fù)雜，而且對各 種表達(dá)式處理也有差異，因此整個遍歷過程相對復(fù)雜。但是基本的思路仍然與一般的后根 遍歷相同，只是每次訪問到某個節(jié)點(diǎn)時，必須先判斷它的表達(dá)式類型，再確定下一步的遍 nk ，3 歷方向。如圖3 - l 所示為公式以，+ 芝 的后根遍歷的結(jié)果，其中每個節(jié)點(diǎn)右側(cè)的( i ) 表 i = 1 j 示該節(jié)點(diǎn)在后根遍歷排序中的序號。 3 1 2 樹的距離度量 早在1 9 7 9 年i c t a i 就在 9 提出了有關(guān)樹與樹之間的比較( 或者稱之為匹配) 問題。 至今，已經(jīng)出現(xiàn)許多解決樹匹配的方法，其中大多數(shù)都采用動態(tài)規(guī)劃來實現(xiàn)，而動態(tài)規(guī)劃 的方法實際上是字符串匹配算法的個推廣。當(dāng)然，也有一些其他的方法。例如【l o 】中將 樹匹配問題看作一個最優(yōu)化問題，提出一個簡單的遞歸的圈溯算法，但是該算法的運(yùn)行時 問是指數(shù)級的，相較于動念規(guī)劃算法它的速度要慢。 無瞼用什么方法解決樹匹配問題，首先都必須定義樹之間的距離度量，用以定量地描 述出兩棵樹之間到底相差多少，這是前提條件。得益于字符串匹配問題的解決思路，樹之 1 9 圖3 - 1 ：公式2 產(chǎn)n 。+ 竺_ 二后根遍歷結(jié)果 百 3 間的距離也可以用編輯距離表示。因此樹之間的匹配轉(zhuǎn)化為對兩棵樹進(jìn)行比較并且找出一 個基本編輯操作( 如捅入，刪除，替代等) 的序列，該序列滿足以下兩個條件： ( 1 ) 按照該序列進(jìn)行操作能夠?qū)⒁豢脴滢D(zhuǎn)化成另棵樹； ( 2 ) 在滿足( 1 ) 的所有基本編輯操作序列中，該序列的操作代價最小。 除了編輯距離之外，諸如對齊距離、獨(dú)立子樹距離、t o p d o w n 距離以及b o t t o m u d 距離等等都可以用來表示樹之間的距離度量。事實上，這些距離度量都是在編輯距離的基 礎(chǔ)上附加一些限制條件得來的。本文采用編輯距離來度量樹之間的距離，將在后面詳細(xì)介 紹。 3 1 3 編輯操作與編輯距離 對于一般的帶標(biāo)記的有序樹，我們通常考慮三種基本的編輯操作：節(jié)點(diǎn)的替代( c h a n g e 或r e l a b e l ) ，刪除( d e l e t e