【正文】 act it as a cross array problem， set up a optimization model to get maximum matching degree between fragment edges． Next， in order to seek the best path， the different greedy algorithms are designed according to different problems， and get the original document． Eventually， the splicing recovery method based on text characteristics and structure features proved to be effective through a experiment． (小 四號 Times New Roman 體不加粗 ) Key words(小 四號 Times New Roman 體加粗 )： text characteristics； document structure；內江師范學院本科畢業(yè)論文 II patibility； optimization model； greedy algorith（小 四號 Times New Roman 體不加粗，每個關鍵詞開頭字母均不大寫，結尾處無標點符號 )內江師范學院本科畢業(yè)論文 1 1 引言 （一級標題四號黑體不加粗，段前斷后空 行．） 小四號黑體不加粗 （二級標題小四號黑體不加粗，段前斷后不空行．） 小四號仿宋體加粗 （三級標題小四號仿宋體加粗，段前斷后不空行．） 說明 ：（ 1）全文要求：文字：小四號，宋體；行距： 最小值 22 磅 ；頁邊距：上 、左 、右 、下 、頁眉 、頁腳 ；頁眉中，若是論文就刪去“設計”二字，若是設計就刪去“論文”二字． （ 2）各級標題一律頂格，標題末尾不加標點符號． （ 3）正文中所引用的文獻應加尾注，以文獻在文中出現(xiàn)的先后順序依次編號為：[1]， [2]，?，某種文獻中的內容被多次引用時以第一次出現(xiàn)時的序號為準，即一種文獻只有一個序號，可以重復出現(xiàn)．添加尾注的格式如下： 愛因斯坦說：提出一個問題往往比解決一個 問題更重要 [1]． 愛因斯坦說：“提出一個問題往往比解決一個問題更重要” [1]． 愛因斯坦說：“提出一個問題往往比解決一個問題更重要．” [1] （ 4）正文中出現(xiàn)的圖象與表格以編號（依出現(xiàn)的先后順序編號）的方式分別加以命名． 圖象：圖 1，圖 2，? (圖要加圖注，在圖的下面，文字為宋體五號加粗 ) 表格：表 1，表 2，? (表要加表頭，在表的上面，文字為宋體五號加粗 ) （ 5）行文要符合文法格式，每段開頭應空兩個漢字的位置．若一行中只有符號表達式，則可以居中或居中偏左． （ 6）正文中所有的標點符號，一律用全角；句號用 “．” （ 7）公式自動編號，公式字體大小為 10. （ 8）圖、表里面的字體為五號，必須看得清楚。） 注：本模版中紅色字體是說明部分，在具體操作時應將其刪除． 未盡事宜按《內江師范學院畢業(yè)論文（設計 ） 指導手冊》實施． 。 (2) 算法 步驟及算法框圖 Step1：確定初始碎片 x ，并從初始集 U 中剔除 x ； Step2：確定與 x 匹配度最高的碎片 y ； 內江師范學院本科畢業(yè)論文 8 Step3：判斷點 y 的個數(shù)是否 大于 1， 若滿足，進入Step4，若不滿足，進入 Step5； Step4：根據人工干預方式確定 y ； Step5：直接將 x 、 y 左右拼接； Step6：將 y 作為新的初始點，并從 U 中剔除 y ； Step7：判斷 U 中剩余點的個數(shù)是否 大于 0 ，若 大于 0 ，返回 Step2；若不滿足 大于 0 ，進入 Step8； Step8：輸出結果，結束． 從 初 始 點 集 U 中 選 擇 初 始點 x ， 并 從 U 中 去 除 x找 出 與 x 匹 配 度 最 高 的 點 y人 工 干 預y 的 個 數(shù) 1否拼 接 x y ,并 從 集合 U 中 去 除 點 y將 y 作 為 新 的 初 始 點 xU 中 點 的 個 數(shù) = 0是是否開 始結 束 圖 9 算法 框圖 (3) 拼接復原結果 在主頻 ， 內存， Windows XP 的硬件環(huán)境下，在 的軟件中編寫程序 ， 得到拼接結果見表 一，復原圖見圖 10． 表 1 縱切碎片中、英文拼接結果 08 14 12 15 03 10 02 16 01 04 05 09 13 18 11 07 17 00 06 03 06 02 07 15 18 11 00 05 01 09 13 10 08 12 14 17 16 04 以下內容省略 ?? 橫縱切碎片的擴散拼接 模型求解 (1) 多元貪心算法 設計思想 針對橫縱切碎片，漢字或英文單詞可能既被橫向切割又被縱向切割，因此僅從單一方向上進行拼接復原極有可能造成誤差，多元貪心算法的基本思想是隨機選擇一張碎片因而我們以某一碎片為起始點利用多元擴散的方式進行拼接． (2) 數(shù)據結構的選擇 隊列 [8]：存儲已拼接紙片部分的邊緣紙片，通過進隊出隊的方式刻畫多元貪心算法的復原擴算過程，如圖 8 所示； 111 21 2 1 2 31 231 2 3 41 2341 2 3 4 51 23452 3 4 5 61 2453162 3 4 5 6 71 245367 圖 11 多元貪心拼接復原過程 內江師范學院本科畢業(yè)論文 9 矩陣 [8]：儲存碎片的位置，便于計算與多個碎片相接的該碎片與其他碎片的匹配度總和（如圖 10，在碎 片 7 所屬位置的碎片時，不僅應計算該碎片與 2 的匹配度，同時需通過矩陣找到碎片 3，并計算其匹配度，），且在計算機求解困難時有利于人工的參與． (3) 算法 步驟 在多元貪心算法 [9]的過程中，首先應隨機選取一張碎片作為起始碎片點，并以此為中心，依次向右、上、左、下四個方向擴算拼接，其具體算法步驟 [10]如下： Step1:隨機選取碎片 集合 C中的碎片 A 作為起始碎片 ,將該碎片入隊并放入位置矩陣的中心位置； Step2:讀取隊頭元素，并找到在位置矩陣中的位置； Step3:檢 查該元素所在位置的右方是否已有碎片放入，若無，進入 Step4，若有，則按 Step4 的方法依次判斷上、左、下的方向； Step4:取出待拼接位置上下左右四個方向的碎片編號 (若無，則將編號置為 0)，同時考慮待拼接碎片與四個方向碎片（編號不為 0）的匹配度之和，選擇匹配度之和最大的碎片進行拼接，將所選碎片入隊，并記錄位置坐標； Step5:如果隊列 和碎片集合 C 都非空 則轉 Step2， 否則結束． (4) 人工干預原則 由于利用算法程序進行自動化拼接的隨機性，在紙片復原過程中有可能造成錯誤拼接，為提高算法的時間復雜及其求解精度， 制定如下的人工干預原則： 在拼接的工程中，在選擇下一張拼接碎片時，若出現(xiàn)兩張與其匹配度最高的碎片，進行人工干預，這時根據字符特點和句子含義選擇更為合適的碎片進行拼接． 在利用算法求解后得到了一些局部拼接較準確的大碎片，這 些大 碎片計算機不能確定拼接， 需 要進行人工干預． 進行人工干預首先通過肉眼識別把很明顯的拼接，然后將剩下的通過文件特征，句意以及句子連貫性進行再次拼接，最后將一些零散的填入到正確的位置以得到一個完整的文件．