読者です 読者をやめる 読者になる 読者になる

文法圧縮(4)

Java

前回、紹介した論文で、かなりざっくりとRe-Pairを実装してみた。

An Online Algorithm for Lightweight Grammar-Based Compression.
Shirou Maruyama, Algorithms 2012, 2012.

バグもいっぱいあると思うし、後処理もさぼってはいるが、それなりに動く。

class RePair {
    
    RePair() { }
    
    int lca( final int i, final int j ) {
        return SBVUtility.getMSB(i ^ j);
    }
    
    boolean replacedPair(
            final Queue<Integer> pQueue,
            final int pLeaveNum,
            final int pIndex
            ) {
        
        Iterator<Integer> itr = pQueue.iterator();
        
        // pIndexまで読み飛ばす。
        int prevElem0 = 0;
        for ( int i = 0; i < pIndex; i++ ) {
            prevElem0 = itr.next();
        }
        
        // index iの要素を取得する。
        Integer elem0 = itr.next();
        // index i + 1の要素を取得する。
        Integer elem1 = itr.next();
        
        // Is w[i, i+1] repetitive pair ?
        if ( elem0 == elem1 ) {
            return true;
        }
        
        // index i + 2の要素を取得する。
        Integer elem2 = itr.next();
        
        // Is w[i+1, i+2] repetitive pair ?
        if ( elem1 == elem2 ) {
            return false;
        }
        
        // index i + 3の要素を取得する。
        Integer elem3 = itr.next();
        
        // Is w[i+2, i+3] repetitive pair ?
        if ( elem2 == elem3 ) {
            return true;
        }
        
        int prevLeaveNum = (pLeaveNum << 1) | 1;
        int leaveNum0 = ((pLeaveNum + 1) << 1) | 1;
        int leaveNum1 = ((pLeaveNum + 2) << 1) | 1;
        int leaveNum2 = ((pLeaveNum + 3) << 1) | 1;
        int leaveNum3 = ((pLeaveNum + 4) << 1) | 1;
        if ( -1 == prevElem0 ) { // dummyである。
            leaveNum0 = (pLeaveNum << 1) | 1;
            leaveNum1 = ((pLeaveNum + 1) << 1) | 1;
            leaveNum2 = ((pLeaveNum + 2) << 1) | 1;
            leaveNum3 = ((pLeaveNum + 3) << 1) | 1;
        }
        
        // Is w[i, i+1] is minimal pair or maximal pair ?
        if ( -1 != prevElem0 ) { // dummyではない。
            if ( elem0 < prevElem0 && elem0 < elem1 ) { // minimal pair ?
                return true;
            } else if ( lca(leaveNum0, leaveNum1) > lca(prevLeaveNum, leaveNum0)
                    && lca(leaveNum0, leaveNum1) > lca(leaveNum1, leaveNum2) ) { // maximal pair ?
                return true;
            }
        }
        
        // Is w[i+1, i+2] is minimal pair or maximal pair ?
        if ( elem1 < elem0 && elem1 < elem2 ) { // minimal pair ?
            return false;
        } else if ( lca(leaveNum1, leaveNum2) > lca(leaveNum0, leaveNum1)
                && lca(leaveNum1, leaveNum2) > lca(leaveNum2, leaveNum3) ) { // maximal pair ?
            return false;
        }
        
        return true;
        
    }
    
    void insertSymbol(
            final Map<String, Integer> pDictionary,
            final int pMaxCodePoint,
            final List<Queue<Integer>> pQueueList,
            final List<Integer> pLeavesList,
            final int pQueueIndex,
            final int pCodePoint
            ) {
        
        // 対象となるキューを取得する。
        Queue<Integer> queue = pQueueList.get(pQueueIndex);
        
        Integer leaveNum = pLeavesList.get(pQueueIndex);
        
        // キューに文字を格納する。
        queue.offer(Integer.valueOf(pCodePoint));
        
        // 5文字以上格納されているか?
        if ( 5 <= queue.size() ) {
            if ( replacedPair(queue, leaveNum.intValue(), 1) ) {
                Integer y0 = queue.poll();
                Integer y1 = queue.poll();
                Integer y2 = queue.peek();
                
                StringBuffer keyBuffer = new StringBuffer(8);
                keyBuffer.appendCodePoint(y1.intValue());
                keyBuffer.appendCodePoint(y2.intValue());
                String key = keyBuffer.toString();
                Integer z = Integer.valueOf(pDictionary.size() + pMaxCodePoint);
                if ( pDictionary.containsKey(key) ) {
                    z = pDictionary.get(key);
                    insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, z.intValue());
                } else {
                    pDictionary.put(key, z);
                    insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, z.intValue());
                }
                
                if ( -1 == y0.intValue() ) {
                    // dummy
                    leaveNum++;
                } else {
                    leaveNum += 2;
                }
            } else {
                Integer y0 = queue.poll();
                Integer y1 = queue.poll();
                insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, y1.intValue());
                Integer y2 = queue.poll();
                Integer y3 = queue.peek();
                
                StringBuffer keyBuffer = new StringBuffer(8);
                keyBuffer.appendCodePoint(y2.intValue());
                keyBuffer.appendCodePoint(y3.intValue());
                String key = keyBuffer.toString();
                Integer z = Integer.valueOf(pDictionary.size() + pMaxCodePoint);
                if ( pDictionary.containsKey(key) ) {
                    z = pDictionary.get(key);
                    insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, z.intValue());
                } else {
                    pDictionary.put(key, z);
                    insertSymbol(pDictionary, pMaxCodePoint, pQueueList, pLeavesList, pQueueIndex + 1, z.intValue());
                }
                if ( -1 == y0.intValue() ) {
                    // dummy
                    leaveNum += 2;
                } else {
                    leaveNum += 3;
                }
            }
        }
        
        pLeavesList.set(pQueueIndex, Integer.valueOf(leaveNum));
        
        return;
        
    }
    
    void compress(final String pStr) {
        
        // 文字数を取得する。
        int codePointCount = pStr.codePointCount(0, pStr.length());
        
        // 辞書
        Map<String, Integer> dictionary = new HashMap<String, Integer>();
        
        // 取得した文字数からparse treeの高さを計算する。
        int height = SBVUtility.getMSB(codePointCount);
        
        // キューを高さ分用意して、初期化する。
        List<Queue<Integer>> queueList = new ArrayList<Queue<Integer>>(height);
        // 完全二分木のin-orderでの葉の番号のリスト
        List<Integer> leavesList = new ArrayList<Integer>(height);
        for ( int i = 0; i < height; i++ ) {
            Queue<Integer> queue = new LinkedList<Integer>();
            // dummyを格納する。
            queue.add(Integer.valueOf(-1));
            queueList.add(queue);
            leavesList.add(Integer.valueOf(0));
        }
        
        // 最大のコードポイントを取得する。
        CodePointIterator itr = new CodePointIterator(pStr);
        int maxCodePoint = 0;
        for ( ; itr.hasNext(); ) {
            int codePoint = itr.next();
            if ( maxCodePoint < codePoint ) {
                maxCodePoint = codePoint + 1;
            }
        }
        
        // Algorithm2 LCA-online
        itr = new CodePointIterator(pStr);
        int queueIndex = 0;
        for ( ; itr.hasNext(); ) {
            
            // コードポイントを取得する。
            int codePoint = itr.next();
            
            // キューに文字を挿入する。
            insertSymbol(dictionary, maxCodePoint, queueList, leavesList, queueIndex, codePoint);
            
        }
        
        // post-process
        for ( int i = 0; i < height - 1; i++ ) {
            Queue<Integer> targetQueue = queueList.get(i);
            Queue<Integer> nextQueue = queueList.get(i + 1);
            if ( 0 != targetQueue.size() ) {
                targetQueue.poll();
            }
            while ( 0 != targetQueue.size() ) {
                Integer elem = targetQueue.poll();
                nextQueue.add(elem);
            }
        }
        
        // 残った文字列を出力する。
        Queue<Integer> queue = queueList.get(height - 1);
        StringBuffer resultBuffer = new StringBuffer();
        queue.poll();
        while ( 0 != queue.size() ) {
            resultBuffer.appendCodePoint(queue.poll().intValue());
        }
        
        System.out.println( "入力文字列:" + pStr );
        System.out.println( "結果文字列:" + resultBuffer.toString() );
        
        System.out.println();
        
        System.out.println( "辞書定義:" );
        
        // 辞書
        for ( String key : dictionary.keySet() ) {
            System.out.println( key + " ---> " + new String(Character.toChars(dictionary.get(key).intValue())) );
        }
        
        // 最大文字は、サロゲートペアの範囲に気を付ける。
        
        return;
        
    }

}

実行は、以下です。

String str = "abababcccccc";
RePair rePair = new RePair();
rePair.compress( str );

実行結果は、以下です。

入力文字列:abababcccccc
結果文字列:aebffcc

辞書定義:
dd ---> e
ba ---> d
cc ---> f

かなり怪しいが、それなりには動く。これをビットベクトルに適用して、辞書を簡潔データ構造で表現して、ランダムアクセス可能な補助データ構造を作成すると、Re-Pairを利用した簡潔ビットベクトルができるはず。

ここまで来るのに半年かかってしまった。

広告を非表示にする