リードコード-PatternとFrequentPatternMaxHeap

5535 ワード
Pattern
package org.apache.mahout.fpm.pfpgrowth.fpgrowth;
public class Pattern implements Comparable
patternはitemのセットをカプセル化し、各itemのsupport値、全体のsupport値

  private int[] pattern;
  
  private long support = Long.MAX_VALUE;
  
  private long[] supportValues;

patternが含まれているかどうかを判断します.patternは既に昇順配列であるため,2つの配列を比較して推進すればよい.
いくつかの条件が含まれています.1.本配列の長さは小外来2である.外来配列が本配列の現在値より大きい場合は不可能である.どちらの配列も末尾に達するか、外来配列が末尾に達していないか

  public final boolean isSubPatternOf(Pattern frequentPattern) {
    int[] otherPattern = frequentPattern.getPattern();
    int otherLength = frequentPattern.length();
    if (this.length() > frequentPattern.length()) {
      return false;
    }
    int i = 0;
    int otherI = 0;
    while (i < length && otherI < otherLength) {
      if (otherPattern[otherI] == pattern[i]) {
        otherI++;
        i++;
      } else if (otherPattern[otherI] < pattern[i]) {
        otherI++;
      } else {
        return false;
      }
    }
    return otherI != otherLength || i == length;
  }

容量拡張1.5倍に拡大して再コピーする前の.

  private void resize() {
    int size = (int) (GROWTH_RATE * length);
    if (size < DEFAULT_INITIAL_SIZE) {
      size = DEFAULT_INITIAL_SIZE;
    }
    int[] oldpattern = pattern;
    long[] oldSupport = supportValues;
    this.pattern = new int[size];
    this.supportValues = new long[size];
    System.arraycopy(oldpattern, 0, this.pattern, 0, length);
    System.arraycopy(oldSupport, 0, this.supportValues, 0, length);
  }

itemを1つ追加し、合計supportはすべてのitemの最小値を取ります.

  public final void add(int id, long supportCount) {
    dirty = true;
    if (length >= pattern.length) {
      resize();
    }
    this.pattern[length] = id;
    this.supportValues[length++] = supportCount;
    this.support = supportCount > this.support ? this.support : supportCount;
  }

package org.apache.mahout.fpm.pfpgrowth.fpgrowth;
public final class FrequentPatternMaxHeap
スタックにtop k個のpatternを保存する
コア構造

  private final PriorityQueue<Pattern> queue;

同じsupport値のpatternはsetを構成します

  private final OpenLongObjectHashMap<Set<Pattern>> patternIndex;

追加可能かどうかを判断
容量が満たされていない場合は直接追加できますが、満たされている場合はsupport値が現在の最小値より大きい場合も追加できます.

  public boolean addable(long support) {
    return count < maxSize || least.support() <= support;
  }

新しいpatternを挿入し、積み上げられている場合は置換プロセスがあり、サブpatternチェックがある場合はsupportとの集合を維持します.Insert関数は主に挿入前の条件フィルタリング,主な論理を行う.

  public void insert(Pattern frequentPattern) {
    if (frequentPattern.length() == 0) {
      return;
    }
    
    if (count == maxSize) {
      if (frequentPattern.compareTo(least) > 0 && addPattern(frequentPattern)) {
        Pattern evictedItem = queue.poll();
        least = queue.peek();
        if (subPatternCheck) {
          patternIndex.get(evictedItem.support()).remove(evictedItem);
        }
      }
    } else {
      if (addPattern(frequentPattern)) {
        count++;
        if (least == null) {
          least = frequentPattern;
        } else {
          if (least.compareTo(frequentPattern) < 0) {
            least = frequentPattern;
          }
        }
      }
    }
  }

具体的な挿入プロセス.サブセットをチェックし、スタックにスーパーセットがある場合は挿入しません.

  private boolean addPattern(Pattern frequentPattern) {
    if (subPatternCheck) {
      Long index = frequentPattern.support();
      if (patternIndex.containsKey(index)) {
        Set<Pattern> indexSet = patternIndex.get(index);
        boolean replace = false;
        Pattern replacablePattern = null;
        for (Pattern p : indexSet) {
          if (frequentPattern.isSubPatternOf(p)) {
            return false;
          } else if (p.isSubPatternOf(frequentPattern)) {
            replace = true;
            replacablePattern = p;
            break;
          }
        }
        if (replace) {
          indexSet.remove(replacablePattern);
          if (!indexSet.contains(frequentPattern) && queue.add(frequentPattern)) {
            indexSet.add(frequentPattern);
          }
          return false;
        }
        queue.add(frequentPattern);
        indexSet.add(frequentPattern);
      } else {
        queue.add(frequentPattern);
        Set<Pattern> patternList;
        if (!patternIndex.containsKey(index)) {
          patternList = new HashSet<Pattern>();
          patternIndex.put(index, patternList);
        }
        patternList = patternIndex.get(index);
        patternList.add(frequentPattern);
      }
    } else {
      queue.add(frequentPattern);
    }
    return true;
  }
ファイル圧縮解凍のコードを送りましょう.
Grid Garden