《有限和無限階後綴排序關鍵算法研究》是依託中山大學，由農革擔任項目負責人的面上項目。
基本介紹
- 中文名：有限和無限階後綴排序關鍵算法研究
- 項目類別：面上項目
- 項目負責人：農革
- 依託單位：中山大學
- 批准號：60873056
- 申請代碼：F0201
- 負責人職稱：教授
- 研究期限：2009-01-01 至 2011-12-31
- 支持經費：31（萬元）
中文摘要
信息科技和套用的發展，對信息處理系統的存儲和處理能力的要求越來越高。後綴排序相關算法在數據壓縮和字串匹配領域裡有重要套用。結合項目組近年在後綴排序相關問題上的研究積累，本項目書提出對有限及無限階後綴排序的關鍵算法圍繞以下幾個問題作進一步深入研究：（i）直接計算有限階後綴排序的線性算法。（ii）具有理論線性複雜度，而且在實踐中有良好性能的後綴排序算法。（iii）後綴排序算法在網路環境中的實時套用關鍵算法。實現以下目標：（1）研究時空複雜度均為線性O(n)的逆ST新算法，突破逆ST算法的複雜度瓶頸。（2）研究新的切分-合併方法，設計時空複雜度均優於現存無限階後綴排序線性算法的新算法。（3）基於（1）和（2）的成果，研究直接計算有限階後綴排序的快速線性算法以及索引查找算法。（4）用C++實現一個包括以上研究成果的函式館。
