#!/usr/bin/env ruby

# このプログラムは、
#   人工知能学会 知識ベースシステム研究会(第73回)
#   「時系列データ中の頻出部分系列を高速抽出するオンライン近似計算法」
#   石原他(SIG-KBS-A504-04, 研究会資料 p.21)
# で提案されているアルゴリズムの実装を試みたものです。
#
# 参考 http://www.nesugi.net/diary/20060406.html
#
# プログラムの作者は一切の権利を主張しませんが、
# 論文のアルゴリズムと異なる場合、バグを含む場合等、
# 一切の責任を負いません。
# (プログラムの作者は論文の著者と無関係です)

# プログラムの目的:
#  オンライン処理(データスキャンが1度だけ)で、頻出部分系列を抽出する
#  ただし、
#    ・窓幅内に入る部分系列のみが対象
#    ・系列の全長n、最小頻度の閾値σに対し、nσ以上の系列を全て抽出
#    ・完全だけれど冗長(全ての正解が含まれるが、ゴミも含まれる)
#    ・頻度の正確な数字は数えない
#  という特徴だったような・・・忘れました。

# 使い方:
#  定数DATAに適当な配列をいれると、その中で頻出な部分系列を返します。
#  その際、窓幅変数Wと相対頻度SIGMAの値によって挙動が変わります。
#  引数などはないので、とりあえず実行すると結果が得られます。


$KCODE = 'e' 

DATA = ['A', 'B', 'B', 'A', 'C', 'B', 'C', 'A', 'C', 'B', 'A', 'C']

W = 3		# 窓幅
SIGMA = 0.25	# 最小頻度の閾値


# initialize

d = Hash.new
k = Array.new
W.times do |i|
  k[i] = Hash.new
end


# substr_sequence
def substr_sequence(seq)
  return [[]] if seq.nil? or seq.empty?

  result = []
  lists = substr_sequence(seq[1..-1])
  lists.each do |list|
    result << list.dup
    result << list.unshift(seq[0])
  end

  return result
end


(0..DATA.size - W).each do |t|		# DATAの処理ループ
  alpha = DATA[t...t+W]			# 対象ウィンドウ

  # 先頭頻度表の更新
  (W-1).times do |i|			# k[i]の中身をずらす
    k[i] = k[i+1]
  end
  k[W-1] = Hash.new

  lists = substr_sequence(alpha[1..-1])		# alphaの(最初の要素を除いた)全ての部分系列を返す
  lists.uniq!					# (これが必要)
  lists.each do |list|				# 各部分系列を登録
    list.unshift(alpha[0])
    if (data = k[list.size-1].fetch(list, false))	# 既に登録されているかどうか
      data[0] += 1
    else
      k[list.size-1][list] = [1, t]
    end
  end

  # 全体頻度表の更新
  k[0].keys.each do |list|
    if (data = d.fetch(list, false))			# 既に登録されているかどうか
      data[0] += k[0][list][0]
    else
      d[list] = k[0][list]
    end
  end
  
  # 有効期限チェック
  d.keys.each do |key|
    if d[key][0] <= (SIGMA * (t - d[key][1]))		# 時間切れ
      d.delete(key) if k.each do |hash|			# この部分は必要??
        break false if hash.keys.include?(key)		# (kのなかに含まれるならdeleteしない)
      end
    end
  end
end

# 出力
d.keys.sort.each do |key|
  if d[key][0] > (SIGMA * ((DATA.size - W) - d[key][1]))
    puts key.inspect + "\t" + d[key][0].to_s		# 頻度の数字は正確ではない
  end
end