一種基于STR算法的新表壓縮方法

董愛迪 李占山 于海鴻

(吉林大學計算機科學與技術學院 長春 130012) (符號計算與知識工程教育部重點實驗室(吉林大學) 長春 130012)

在約束編程中,由于表約束算法可以對任何種類的約束編碼,并且表達方式簡潔,所以近些年來基于表約束過濾算法被廣泛研究和使用,其中STR2[1]和STR3[2]算法是當前主流的表縮減算法.關于表約束的研究,國內學者關注于約束可滿足問題中二元問題,其中文獻[3]的算法將約束求解與優化技術相結合,提高約束求解效率;李占山等人[4]提出新啟發式用于回溯搜索過程.同時為了在表約束上維持高階相容性,王瑞偉等人[5]提出一種對eSTR算法的優化算法.而由于表約束將關系用表的方式顯示出來,內存空間的需求可能會由于參數的增加而出現指數型爆炸,所以為了優化表縮減算法性能,降低約束表的空間消耗并提高廣義弧相容(generalised arc consistent, GAC)算法的運行速度,許多用于約束表壓縮的算法相繼被提出.例如用MDD圖來表示約束關系的MDD4R[6]算法,當子圖十分復雜且壓縮率很高時,在其上維持GAC效果十分顯著.同時運用c-tuple在笛卡兒積壓縮表上維持GAC的STR2-C算法及STR3-C[7]算法,同樣在壓縮率較大的benchmark實例上,能取得顯著的效果提升.而STR-slice[8]算法則是在分割表上維持GAC的算法,這些改進算法都是用一種更加緊湊的方式來表示約束表,從而提高過濾性能.

在眾多成功的表壓縮方法中,我們發現:約束表中完全長度集合大小嚴重大于短支持集合,因此運用短支持方法,利用元組的特性,將原有約束表壓縮成短表[9],減少約束元組個數,更加節省空間,同時可以比原始STR算法傳播更多的約束,甚至由于內存問題,原始STR算法都不能將這些約束放入內存中.但是當壓縮率比較小時(即原約束表中元組很少能被壓縮成短約束元組),應用短支持方法的ShortSTR2與STR2算法相比運行速度并沒有顯著提升.而位操作[10]允許在位向量上并行操作來提高算法運行速度,因此文中提出一種新的表壓縮算法STRO(simple tabular reduction optimizaton),結合短支持方法和位操作,保留了短支持方法中可以傳播更多結點的優點,輔以位操作并行的優勢,與主流算法STR2,ShortSTR2相比,約束表空間壓縮程度更好,且運行速度有顯著提高;與目前維持GAC效果較好的STRbit算法相比,表壓縮率更大,可明顯降低空間消耗.

1 背景知識

定義1. 約束網絡(constraint network, CN)[11].約束網絡CN由一個包含n個變量的集合和一個包含e個約束的集合構成.每個變量x都有一個相關的論域dom(x),其中包含了一個變量x的有限賦值集合.每個約束c都有一個集合scp(c)和一個集合rel(c),其中scp(c)是X的子集,集合內元素是約束c涉及的變量.r表示約束c的元數,在正表約束中,rel(c)是滿足約束c的元組的集合.若a∈dom(x)則(x,a)是有效的；若a?dom(x)則(x,a)是無效的.一個元組τ是(x,a)的支持當且僅當 (x,a)∈τ.τ是有效的當且僅當?x∈scp(c),都有(x,τ(x))是有效的.

定義2. 短支持(short support)[9].短支持S是一個文字的集合S=(y→2,z→1),其中x∈scp(c),且文字x→v是關于Ds有效的,x在S中僅僅出現一次,并且S的每一個超集都包含一個有效的文字,關于scp(c)中每個變量來說都是一個完全長度支持.

在本文中,我們用完全長度元組來表示短支持,*表示一個不被短支持包含的變量.假設有一個約束c涉及3個變量x,y,z,短支持S=(y→2,z→1),S用完全長度表示為{*,2,1}.壓縮算法Greedy-Compress是由Jefferson等人[9]于2013年提出,描述如何將大小為r的完全長度元組,逐步迭代壓縮直到不能壓縮為止.算法用UsedTuples存儲可以被壓縮的元組,并用CompTuples存儲壓縮后的元組,最終將所有可能大小的元組收集起來,完成短支持壓縮.

定義3. 廣義弧相容GAC[12].一個約束c是弧相容的,當且僅當對每一個x∈scp(c)，每個值a∈dom(x)在c中至少存在一個支持.

定義4. 位操作(bit-wise operation)[10].位操作將約束表中元組集構造成位表,用數組來表示約束和域,用數組bit_dom[x]表示變量的域,將變量X域中的每一個值對號入座,但是存放的不是變量值而是0或1.0表示與這個位置對應的值不在變量X的值域中,反之則為1.同時用位向量support來表示約束表中的支持,如果元組τ對值對(x,a)關于約束C是有支持的,那么位向量在位置i的值為1,否則為0.

例1. 一個簡單原始約束表如表1所示,其中dom(x)={a,b,c},dom(y)={a,b,c},dom(x)={a,b,c}.每個變量值對應的位向量support值如表2所示.

Table 1 Constraint Table 表1 約束表

Table 2 Value of Bit Support 表2 位支持的對應值

2 STRO算法的思想

STRO算法是結合短支持和位操作得到的簡表壓縮優化方法,其中位操作受到STRbit算法的啟發,沿用了STR的算法框架.主要思想是先將約束表壓縮為短表,再將其轉化為位表,并在位表上維持GAC.整個算法可以分為3個部分:1)將原約束表壓縮成短表;2)在搜索過程中動態刪除無效的元組;3)為每個變量值對在當前有效的約束表中尋找支持.

為了實現STRO算法,需用到5種數據結構.

1)support(C,X,a).表示值對(x,a)關于約束c的位支持.

2)support*(C,X,a).表示值對(x,a)關于約束c的位短支持.

3)LAST(C,X,a).記錄的是最后一個有效位支持的位置,初始化為support.size-1.

4)DEL(C,X).集合中存放所有從值域中刪除但還未更新位表的變量值.

5)VAL(C,X).表示的是元組的有效性,初始時每個位的值均為1.

對于表1的約束表,經過STRO算法的第1步短表壓縮后將轉變為表3,相應的位短支持support*的計算可以看作2部分,首先計算出原有的位支持support,而當任何一個變量x被壓縮后,該變量的值對(x,*)的位支持support等于包含*的元組位置的位值為0,其余為1.在表4中,對于壓縮后的(y,*)值對的位支持support=(011111),將相應值對的位支持support和(y,*)值對的位支持support進行按位與計算,從而得到位短支持support*.例如變量值(y,a)的support(y,a)=(110100),與support(y,*)=(011111)進行按位與計算后,得到support*(y,a)=(010100).

Table 3 Constraint Table After Short Table Compression表3 短支持壓縮后的約束表

Table 4 Value of Bit Support* After Short Table Compression表4 短支持壓縮后的位短支持的對應值

算法1. STRO算法.

Algorithm STRO()

①S←{x|(x→a)∈shorttable∧|dom(x)|>1}；

②deleteInvalidTuple();

③ returnsearchSupport();

FunctiondeleteInvalidTuple()

① FOR all variables∈Sdo

② FORa∈DEL(C,X) do

③ FORi≤LAST(C,X,a) do

④u=support*(C,X,a)[i].

mask&VAL(C,X);

⑤ IFu≠0

⑥ save(C,VAL(C,X),restoreV);

⑦VAL(C,X)=(u) &

VAL(C,X);

⑧ ENDIF

⑨ ENDFOR

⑩ ENDFOR

FunctionsearchSupport()

① FOR all variablex∈Sanda∈dom(x) do

②now=LAST(C,X,a);

③ IFsupport(C,X,a)[now].mask&VAL(C,X)=0

④now=now-1;

⑤ IFnow<0

⑥dom(x)←dom(x){a};

⑦ AddatoDEL(C,X);

⑧ IFdom(x)=?

⑨ return false;

⑩ ENDIF

Functionsave(key,newdata,store)

① IF(key,olddata)?top(store) for any

olddata

② Addnewdatatotop(store);

③ ENDIF

STRO算法是在回溯搜索過程中維持GAC的,所以需要在初始化時就使得約束表中的元組滿足GAC.在初始化階段,VAL(C,X)中每個位值都設置為1,LAST(C,X,a)等于最后一個位支持的位置,DEL(C,X)初始為空.

STRO算法首先經過第1步短表壓縮后,開始動態刪除無效的元組(調用deleteInvalidTuple方法),遍歷DEL中所有的變量,將變量的所有支持刪除,并清空DEL(C,X)數據結構,同時記錄VAL(C,X)的值.在STRO算法中support和support*的值只在創建時計算,不會有更改,動態變化的是VAL(C,X)的值,用于記錄當前約束表中元組的有效性.由于在DEL(C,X)中存儲的是確定的已被刪除的值,所以在刪除無效元組階段驗證短支持有效性時,我們嚴格要求提τi[x]=a,即用support*輔助刪除無效元組.

在搜索支持階段(調用searchSupport方法),STRO將為約束范圍內的每一個變量的每一個變量值進行位支持的有效性檢查.若support(C,X,a)[now].mask&VAL(C,X)=0,則表明在位支持中沒有包含有效元祖.now是當前操作的位支持,當now<0表明變量值沒有有效的位支持,將該變量值刪除并加入到DEL數據結構中.算法中函數save中保存的數據將用于算法回溯時恢復現場使用.其中restoreV中保存的是VAL(C,X)的值,restoreL中記錄的是LAST(C,X,a)數據結構的值.STRO算法在搜索支持后,由于為當前約束表中的每個變量值都維持了至少一個支持,所以約束是滿足GAC的.

Jefferson等人[9]已詳細分析了STR2與Short-STR2算法的復雜度:對于一個值域大小為d且有t個元祖的變量集合U,STR2算法的復雜度為O(|U|d+|Sval|+|U|t),ShortSTR2算法的復雜度為O(rd+|Sval|+|U|t).其中Sval是STR2及ShortSTR2算法中用于保存相對于前一次的調用，論域發生改變的未賦值的變量,r為ShortSTR2算法中變量在主循環的時間消耗.

定理1. 對于r元約束,d為變量的最大值域,sn為表中各個變量值的位短支持總數,在一條長度為m的搜索路徑上,STRO算法的最壞時間復雜度為O(sn+r2d2+m).

證明. STRO算法維持GAC雖然有3個階段的操作,但主要的時間消耗在刪除無效元組和尋找支持2個階段.其中在刪除無效元組時,若DEL(C,X)≠?,則DEL(C,X)中變量的每個變量值都要被處理一次,所以最壞時間復雜度為O(sn).尋找支持階段,LAST(C,X,a)值不變時,時間復雜度為O(r2d2);LAST(C,X,a)值改變時,遍歷了所有的位支持,所以STRO算法總的最壞時間復雜度為O(sn+r2d2+m).

證畢.

3 實驗結果與分析

為了展示新表壓縮算法STRO的優化效果,本文實驗對比了STRO,STR2,ShortSTR2,STRbit算法的性能.文中實驗環境為Intel?CoreTMi7-3770 CPU@ 3.40 GHz,8.00 GB的RAM,Java語言,所有算法采用的變量啟發式為dom/ddeg,變量值啟發式為字典序[13],實驗中的經典測試用例來自XCSP2數據庫[14],其中MDD0.7和MDD0.9以及rand-5-2x實例來自STR2-C論文中提出的benchmark實例[15].

表5中的數據是3種算法對于每類benchmark實例進行測試,各個算法消耗的平均時間、運行時間單位為s,實例的最高運行時間設置為600 s,大于600 s則為timeout.實驗測試了19個系列,共861組實例,表5中黑體為該系列3個算法中最短平均時間.實驗結果表明,在90%以上的benchmark實例上,STRO算法的時間都是最優的.尤其在MDD0.9實例上,STRO算法的運行速度為STR2算法的20倍左右,是ShortSTR2算法的3倍左右;在MDD0.7實例中,STRO算法的運行速度也可達到STR2算法的10倍左右.這是由于在這2組實例上,STRO算法的壓縮率非常大,所以提升效果特別明顯.而由于rand-8,tsp和aim-50系列實例的約束表在回溯搜索中的平均大小特別小(<0.004),而STRO算法相較于STR2算法需要有壓縮表的過程,所以STR2算法消耗時間要比STRO算法更少一些.在jnh實例中,由于短支持位表較小,所以STRO算法與ShortSTR2算法的CPU時間接近.

Table 5 Running Time of STR2,ShortSTR2 and STRO表5 STR2,ShortSTR2,STRO運行時間比較

Note: The minimum average time of each row is in bold.

圖1中的矩形代表的是用STR2及STRO算法分別測試benchmark實例中經常出現的時間結點區間.在圖1中可以清楚看到STRO算法中絕大部分的時間是集中在10 s以下,STRO算法整體運行時間大多都小于STR2算法.

Fig. 1 Comparison of running time between STR2 and STRO圖1 STR2 與STRO時間對比盒圖

在圖2中用散點圖的方式更加清晰地比較STRO與STR2,ShortSTR2算法的時間性能.圖2中每個點都代表一個具體的實例,圖2中斜線代表2個對比算法在測試實例上消耗時間相同.在圖2(a)和圖2(b)中大部分的點都集中在右下角,所以STRO算法相對于ShortSTR2和STR2算法,都耗時更少、性能更好.對比圖2(a)和圖2(b)發現:圖2(b)中的結點更遠離紅線,因此，STRO算法相對于STR2算法的速度提升效果比STRO算法相對于ShortSTR2算法要更為明顯.并且ShortSTR2算法和STR2算法運行超時(>600 s)時,STRO算法都能夠在600 s內完成實例的測試.

Fig. 2 Running time of STRO, STR2 and ShortSTR2圖2 STRO與STR2及ShortSTR2時間性能對比

STRO和STRbit算法的性能對比結果展示在表6中,在表6中將壓縮率和每秒處理的結點數作為衡量算法性能的參數.可以看到,STRO與STRbit算法相比,STRO算法整體的壓縮率都比STRbit算法壓縮率要大,尤其對于實例MDD0.7,STRO算法壓縮率是STRbit算法的4倍左右,每秒處理的結點數是2倍以上.對于MDD0.9實例,STRO算法壓縮率是STRbit算法的20倍以上,每秒處理的結點數也達到了10倍以上.在實驗中,在少數實例上STRO算法速度提升效果并不大,這是由于STRO算法需要將原約束表轉化為短表,維持了額外的數據結構,有額外的時間開銷,但總體來講在時間上可以替代STRbit算法.

Table 6 Performance Comparison Between STRbit and STRO表6 STRbit與STRO算法的性能對比

Note: The minimum average time of each row is in bold.

4 總 結

表縮減算法STR在表約束上求解效率非常高,對于STR算法的改進算法,近些年來也相繼被提出.其中通過表壓縮的方式,將約束表的空間壓縮從而提高效率,是STR算法的一種優化方式.而其中的ShortSTR2算法,在壓縮率較低的情況下對于STR2算法的優化效果并不明顯.這是由于目前沒有直接的短表,需要短支持方法維護額外的數據結構,將原有的約束表轉化為短表,所以消耗了一部分時間.但是相比STR算法,ShortSTR2算法節約了空間,可以傳播更多的結點.基于此本文將短支持方法輔以位操作,保留短支持方法的優勢,并結合位操作提出STRO算法.實驗結果表明:除了在約束表規模特別小的情況下,效果與STR2算法及ShortSTR2算法差別不大,STRO算法在大多數情況下優于STR2算法及ShortSTR2算法；與STRbit算法相比,在CPU處理時間上可以替代STRbit算法,但是表壓縮率更大,更加節省空間.