[發明專利]一種基于樹結構的語言庫壓縮方法和系統

無效

• 申請號: 201010164636.1
• 申請日: 2010-04-15
• 公開（公告）號: CN102222075A
• 公開（公告）日: 2011-10-19
• 發明（設計）人: 李朝中
• 申請（專利權）人: 李朝中
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海新天專利代理有限公司 31213
• 代理人: 王敏杰

技術領域

本發明涉及數據壓縮方法和系統，特別是一種基于樹結構的語言庫壓縮方法和系統。

背景技術

樹結構在載體上的實現有賴于一般樹與二叉樹的等價轉換和在存儲器中按深度搜索存放樹節點。前者被用來設定節點的數據結構而后者對該結構優化并使之走向實際應用。例如從詞匯add，adding，added，adds組成的一般樹轉換為二叉樹可得出節點的數據結構。從一般樹(圖1)到對應的二叉樹(圖2)可得節點的數據結構為：<KP><BP><EOW><L>。將該二叉樹按深度搜索存放(圖3)，可優化節點數據結構為：<K><B><EOW><L>，省去了指針開銷。但從某節點到其兄弟節點要越過該節點的所有子輩節點，比如從節點(i)到兄弟節點(e)要經過(i)所有子輩節點(n)，(g)。當然也可以從詞庫直接生成二叉樹。由于語言庫樹結構的深度與該庫中最長的詞匯有關而寬度與詞庫中詞的總量有關，因此語言庫樹結構的特點是深度有限寬度很大。隨著詞匯量的加大更是如此。最后，在載體上引擎實現的方法是用一些數組或向量當作堆棧作為工作平臺，從樹的指定地點進入，按深度優先搜索掃描樹節點，存入匹配的節點或指針信息入棧并找出滿足指定條件的字或詞匯。

定義：

<K>是子輩節點標志位，意為Kid；

<B>是兄弟節點標志位，意為Brother；

<EOW>是詞標志位，意為End?of?Word；

<L>是字母，意為Letter；

<ST>是子樹標志位，意為Sub?Tree；

<pK>是子輩指針標志位；

<pB>是兄弟指針標志位；

[]表示該括號里的內容不出現或最多出現1次；

{}表示該括號里的內容不出現或出現多次；

<Pointer>＝{<1，×××××××>，}<0，×××××××>，是由1個或多個字節組成的指針定義。<0/1，×××××××>表示字節(Byte)，×表示二進制位(bit)。其中當首位為1時表示后面的字節仍為該指針部分，直到最后一個字節首位為0時為止；所有的×組成了該指針值。

<KP>是子輩節點指針；<Pointer>結構。

<BP>是兄弟節點指針；<Pointer>結構。

現有的基于樹結構的DAWG壓縮法被Zi?Corp應用在其文本輸入法產品eZiText上。其節點數據結構是<K><B><EOW><L><pK>[<KP>]<pB>[<BP>]。其基本生成原理為從樹的底層葉子節點或從葉子節點的父節點開始從左到右，從下到上逐步歸約：尋找子樹范例(first?sub?tree)，然后將其后發現的同類去掉其所有節點并用指針指向該范例，從而達到數據庫壓縮的目的。

通過如下(表1)一組詞匯舉例說明有向無環圖壓縮法(DAWG)的壓縮過程：