資料結構 -- PatTree

資料結構

簡介

陣列

排序與搜尋

鍊節串列

雜湊表

二元樹

紅黑樹

派氏樹

多元樹

訊息

相關網站

參考文獻

最新修改

簡體版

English

 
package ccc;
import java.util.*;
import java.io.*;
 
/*
1. 讓 trie 長大, 當 trie 太大時, 就選定一大區塊, 將之存入硬碟, 
   並將整棵 subtree 縮為一個 prefix node, 並記錄存檔資訊
  a. 選定大區塊
    i.  記錄在 insert 過程中, 一個node 被走過的次數, 就是該 node 的大小.
 
  b. subTree 縮為一個node
    if back_link in LTREE then lChild = back_link else rChild = back_link.
 
2. 若一個save block 太大時, 將此 block 分為兩個 block, 並將較深的 prefix node 插入trie 中.
*/
 
public class PatTree {
  static   int SHRINK_SIZE=10;
  PatNode  root = null;
 
  public static void main(String[] args) {
    PatTree patTree = new PatTree();
    patTree.insert("23456");
    patTree.insert("333");
    patTree.insert("987");
    patTree.insert("abc");
    patTree.insert("glx");
    patTree.insert("pjb8");
    patTree.insert("dkdl8");
    patTree.insert("eodd4");
    patTree.insert("iemc1");
    patTree.insert("lsd");
    System.out.println(patTree.root.toSortLines());
  }
 
  public PatTree() {}
 
  boolean search(BitData item, Ptr nowPtr) {
    PatNode parent, now;
    if (root==null) return false;
    now = root.lChild;
    parent = root;
    while (now.bitNumber > parent.bitNumber) {
      parent = now;
      if (item.getBit(now.bitNumber-1)==1)
        now = now.rChild;
      else
        now = now.lChild;
    }
    nowPtr.obj = now;
    if (now.equals(item)) return true; else return false;
  }
 
  boolean insert(String itemStr) {
    BitData item = new BitData(itemStr.getBytes());
    // empty tree, new root.
    if (root == null)  {
      root = new PatNode();
      root.setData(item, (short)0);
      root.lChild = root;
      root.rChild = null;
      return true;
    }
    // search until leaf node !
    Ptr nowPtr = new Ptr(null);
    boolean isFound = search(item, nowPtr);
    PatNode now = (PatNode) nowPtr.obj;
    if (isFound) { // data duplication
      System.out.println(item+" = "+now+" bitNumber="+now.bitNumber
                            +" Insert fail : data duplicate error ! ");
      return false;
    }
    short sameBits = now.getSameBits(item);
    PatNode searchNode = root.lChild;
    PatNode parent = root;
    root.size++;
    while (searchNode.bitNumber > parent.bitNumber && searchNode.bitNumber <= sameBits) {
      parent = searchNode;
      if (item.getBit(searchNode.bitNumber-1)==1)
        searchNode = searchNode.rChild;
      else
        searchNode = searchNode.lChild;
      parent.size++;
    }
    PatNode newNode = new PatNode();
    newNode.setData(item, (short)(sameBits+1));
    if (sameBits < item.length() && item.getBit(sameBits)==1) {
      // bit(sameBits) == 1 表示 newNode 比 searchNode 大，使 searchNode 成為 newNode 的左子。
      newNode.lChild=searchNode;
      newNode.rChild=newNode;
    }
    else {
      // bit(sameBits) == 0 表示 newNode 比 searchNode 小，使 searchNode 成為 newNode 的右子。
      newNode.lChild=newNode;
      newNode.rChild=searchNode;
    }
    if (searchNode.bitNumber > parent.bitNumber) // it's not a back link.
      newNode.size = (short) (searchNode.size+1);
    if (searchNode == parent.lChild)
      parent.lChild = newNode;
    else
      parent.rChild = newNode;
    return true;
  }
 
  PatNode selectShrinkNode() {
    return selectDeep(root.lChild, SHRINK_SIZE);
  }
 
  PatNode selectDeep(PatNode node, int maxSize) {
    if (node.size <= maxSize)
      return node;
    else if (!node.isLEnd() && !node.isREnd()) {
      if (node.lChild.size > node.rChild.size)
        return selectDeep(node.lChild, maxSize);
      else
        return selectDeep(node.rChild, maxSize);
    }
    else if (!node.isLEnd() && node.isREnd())
      return selectDeep(node.lChild, maxSize);
    else if (node.isLEnd() && !node.isREnd())
      return selectDeep(node.rChild, maxSize);
    else return null; // LEnd && REnd
  }
 
  // 每個 SubTree(node) 都只有一個往上連的 back_link, 找出該 link 在 LTREE 或 RTREE,
  // if back_link in LTREE, then node.lChild = back_link else node.rChild = back_link
  void treeShrink(PatNode node) {
    if (node == root) return;
    PatNode backNode = null;
    if (backNode == null && node.lChild.bitNumber < node.bitNumber) {
      backNode = node.lChild;
      node.rChild = node;
    }
    if (backNode == null && node.rChild.bitNumber < node.bitNumber) {
      backNode = node.rChild;
      node.lChild = node;
    }
    if (backNode == null) {
      backNode = findBackLink(node.lChild, node.bitNumber);
      if (backNode != null) {
        node.lChild = backNode;
        node.rChild = node;
      }
    }
    if (backNode == null) {
      backNode = findBackLink(node.rChild, node.bitNumber);
      if (backNode != null) {
        node.rChild = backNode;
        node.lChild = node;
      }
    }
    if (backNode == null) return;
    if (node.lChild.toString().compareTo(node.toString())>0)
      System.out.println("error : lChild "+node.lChild+" > node "+node);
    if (node.toString().compareTo(node.rChild.toString())>0)
      System.out.println("error : node "+node+" > rChild "+node.rChild);
    PatNode searchNode = root.lChild;
    PatNode parent = root;
    root.size -= (node.size-1);
    while (searchNode.bitNumber > parent.bitNumber && searchNode.bitNumber <= node.bitNumber) {
      parent = searchNode;
      if (node.getBit(searchNode.bitNumber-1)==1)
        searchNode = searchNode.rChild;
      else
        searchNode = searchNode.lChild;
      parent.size -= (node.size-1);
    }
    searchNode.bitNumber = searchNode.getSameBits(backNode); // backLink 重指, 須調整 bitNumber !
  }
 
  PatNode findBackLink(PatNode node, int baseBitNumber) {
    if (node.lChild.bitNumber < baseBitNumber)
      return node.lChild;
    else if (!node.isLEnd()) {
      PatNode lFind = findBackLink(node.lChild, baseBitNumber);
      if (lFind != null) return lFind;
    }
    if (node.rChild.bitNumber < baseBitNumber)
      return node.rChild;
    else if (!node.isREnd()) {
      PatNode rFind = findBackLink(node.rChild, baseBitNumber);
      if (rFind != null) return rFind;
    }
    return null;
  }
 
  public String toString() {
    if (root == null) return "";
    return root.toString();
  }
}
 
class PatNode extends BitData {
  short   bitNumber=0, size = 1;
  PatNode lChild = null, rChild = null;
 
  public static void main(String[] args) {
    PatNode node = new PatNode();
    BitData bitData = new BitData("0123");
    for (short i=0; i<100; i++) {
      node.setData(bitData, i);
      if (!node.data.equals(bitData))
        System.out.println(node.data);
    }
  }
 
  public PatNode() { super(""); }
 
  void setData(BitData pData, short pBitNumber) {
    data = pData.data;
    bitNumber = pBitNumber;
  }
 
  public String dataString() {
    String rzString = new String(data);
    return rzString;
  }
 
  public String toBinary() {
    StringBuffer rzString = new StringBuffer();
    for (int i=0; i<length(); i++)
      if (getBit(i)==1) rzString.append('1'); else rzString.append('0');
    return rzString.toString();
  }
 
  public boolean equals(byte pData[]) {
    if (pData.length!=data.length) return false;
    for (int i=0; i<data.length; i++)
      if (pData[i] != data[i])
        return false;
    return true;
  }
 
  boolean isLEnd() {
    if (lChild == null) return true;
    if (lChild.bitNumber > bitNumber)
      return false;
    else
      return true;
  }
 
  boolean isREnd() {
    if (rChild == null) return true;
    if (rChild.bitNumber > bitNumber)
       return false;
    else
       return true;
  }
 
  public String toSortLines() {
    StringBuffer rzStr = new StringBuffer();
    toSortLines(rzStr);
    return rzStr.toString();
  }
 
  public void toSortLines(StringBuffer sortStr) {
    if (isLEnd()) {
      if (lChild != null) sortStr.append(lChild+"("+lChild.size+")\n");
    } else
      lChild.toSortLines(sortStr);
    if (isREnd()) {
      if (rChild != null) sortStr.append(rChild+"("+rChild.size+")\n");
    } else
      rChild.toSortLines(sortStr);
  }
 
  public String dump() {
    StringBuffer rzXml = new StringBuffer(bitNumber+":"+data.toString());
    if (!isLEnd())
      rzXml.append("<L>"+lChild.dump()+"</L>");
    else if (lChild!=null)
      rzXml.append("<l>"+lChild.data+"</l>");
    if (!isREnd())
      rzXml.append("<R>"+rChild.dump()+"</R>");
    else if (rChild != null)
      rzXml.append("<r>"+rChild.data+"</r>");
    return rzXml.toString();
  }
}
 
class BitData {
  byte  data[];
 
  public static void main(String[] args) {
    BitData bitData = new BitData("XXXX");
    System.out.println(bitData.equals(new BitData("XXXX")));
    BitData v1 = new BitData("1"), v0= new BitData("0");
    System.out.println("1="+v1.toBinary()+" 0="+v0.toBinary());
    for (int i=0; i<8; i++) {
      System.out.println("mask("+i+")="+mask(i));
    }
  }
 
  public BitData(String pStr) {
    data = pStr.getBytes();
  }
 
  public BitData(byte pBuf[]) {
    data = pBuf;
  }
 
  byte getBit(int bitIdx) {
     if (bitIdx >= length()) return 0;
     byte sigByte = data[bitIdx/8];
     if ((sigByte & mask(bitIdx%8)) == 0)
       return 0;
     else
       return 1;
  }
 
  void setBit(int bitIdx) {
    setBit(bitIdx, (byte) 1);
  }
 
  void clearBit(int bitIdx) {
    setBit(bitIdx, (byte) 0);
  }
 
  void setBit(int bitIdx, byte value) {
    byte sigByte = data[bitIdx/8];
    if (value == 0)
      sigByte = (byte) (sigByte & (~mask(bitIdx%8)));
    else
      sigByte = (byte) (sigByte | mask(bitIdx%8));
    data[bitIdx/8] = sigByte;
  }
 
  static byte mask(int i) {
    return (byte) (0x80>>i);
  }
 
  public int length() { return data.length*8; }
 
  public short getSameBits(BitData toBitData) {
    short sameBytes, sameBits;
    int minBytes = Math.min(data.length, toBitData.data.length);
    int minLen = minBytes*8;
    for (sameBytes=0; sameBytes<minBytes
         &&data[sameBytes]==toBitData.data[sameBytes]; sameBytes++);
    for (sameBits=(short)(sameBytes*8); sameBits<minLen
         &&getBit(sameBits)==toBitData.getBit(sameBits); sameBits++);
    return sameBits;
  }
 
  public String toString() {
    String rzString = new String(data);
    return rzString;
  }
 
  public String toBinary() {
    StringBuffer rzString = new StringBuffer();
    for (int i=0; i<length(); i++)
      if (getBit(i)==1) rzString.append('1'); else rzString.append('0');
    return rzString.toString();
  }
 
  public boolean equals(BitData pData) {
    if (pData.data.length!=data.length) return false;
    for (int i=0; i<data.length; i++)
      if (pData.data[i] != data[i])
        return false;
    return true;
  }
}
 
class Ptr {
  Object obj;
  public Ptr(Object pObj) {
    obj = pObj;
  }
}

Facebook
page revision: 2, last edited: 04 Nov 2010 02:18
Edit Rate (0) Tags Discuss (0) History Files Print Site tools + Options
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License