順序同型な部分系列を用いた数値列に対する最長共通部分列問題
電子情報通信学会コンピュテーション研究会，COMP,
信学技報 Vol.115, pp.11-20
(2016)
開催日:
2016年3月14日
Abstract / 概要
数値列の形状に着目した類似性の判断基準として順序同型がある．順序同型となる部分系列を数値列間から見つけ出す問題である順序保存照合問題に関する研究は盛んに行われているが，部分系列が完全に順序同型であるものだけを探すため，実用的には使いにくい．本論文では，順序同型を基にした数値列間の新しい類似性の判断基準として，順序同型LCSと呼ばれる指標を提案する．また，2つの系列が与えられた時，順序同型LCSを高速に計算するためのアルゴリズムを提案する．このアルゴリズムを評価するため，ランダムデータを用いた速度比較実験を行う．