# 志田君研究テーマ検討

## あらまし

## 文献

MCS（maximal common subsequence）を計算するFPTアルゴリズムの論文．

* $k$本の文字列のMCSのFPT
* $T \in MCS(S_1, \dots, S_k)$
* Bulteau, Laurent, et al. “An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions.” 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.

* 2本の文字列のMCS（の列挙）
* $T \in MCS(S_1, S_2)$
* Alessio Conte, Roberto Grossi, Giulia Punzi, and Takeaki Uno, “Polynomial-delay enumeration of maximal common subsequences.” International Symposium on String Processing and Information Retrieval (SPIRE2019), 2019.

## 準備：MCSの定義

MCS問題の元の定義を与える．$\Sigma$を文字のアルファベットとする．

$\Sigma$上の**部分系列関係**を$\preceq$で表す．ここに，$S \preceq T$ならば，$S$は$T$の**部分系列**であるという．もし $S \preceq T$ かつ $T \not\preceq S$ ならば，$S \prec T$と書き，$S$は$T$の**真部分系列**であるという．

補題: 任意の文字列 $S, T, U$ に対して，次の性質が成立する:
* (i) Reflexivity: $S \preceq S$
* (ii) Transitivity: $(S \preceq T)\land (T \preceq U) \implies (S \preceq U)$
* (iii) Anti-symmetricity: $(S \preceq T)\land (T \preceq S) \implies (S = U)$

補題: 部分系列関係 $\preceq$ は，$\Sigma^*$上の半順序関係である．

証明: 上の(i)--(iii)から直ちに成立する．

任意の文字列を$S_1, S_2 \in \Sigma^*$とおく．文字列 $T \in \Sigma^*$ が，$\{S_1, S_2\}$の**共通部分系列**（common subsequence）であるとは，$T \preceq S_i, \forall i=1,2$ が成立することを言う．

定義1（MCS問題の元の定義）: 任意の文字列 $S_1, S_2 \in \Sigma^*$ に対して，パターンの集合 $MCS(S_1, S_2)\subseteq \mathcal S$ を次のように定義する：任意の$T \in \Sigma^*$に対して，
$T \in MCS(S_1, S_2) \iff$ 次の(1)と(2)が成立する:
* (1) $T$は$\{S_1, S_2\}$の共通部分系列である．
* (2) $T \prec T'$を満たすような $\{S_1, S_2\}$の共通部分系列 $T'\in \Sigma^*$は存在しない．

$MCS(S_1, S_2)$の任意の要素$T$を，$\{S_1, S_2\}$の**極大共通部分系列**（longest common subsequences）と呼ぶ．

## MCS問題のパターン族への一般化

### パターン族

極大共通パターン問題（MCS）を，任意のパターン族$(\mathcal P, \sqsubseteq)$に対して拡張する．

定義3：パターン族とは，三つ組$\Gamma = (\Delta, \mathcal P, \sqsubseteq)$である．ここに，
* $\Delta$は，$\Sigma \subseteq \Delta$を満たす記号のアルファベットである．
* $\mathcal P \subseteq \Delta^*$は，$\Delta$上の表現の族である．$\Sigma^* \subseteq \mathcal P$ を満たすものと仮定する．$\mathcal P$の要素 $P \in \mathcal P$ を**パターン**（pattern）と呼ぶ．
* $(\sqsubseteq) \subseteq \mathcal {P}^2$ は，$\mathcal P$上の半順序関係であり，**部分パターン関係**（subpattern relation）と呼ばれる．

### 例: 部分系列パターンの族

先の部分系列の定義に基づいて，次のように定める．**部分系列パターンの族**は，三つ組$Seq = (\Sigma, \mathcal S, \preceq)$で与えられる．ここに，
* $\Sigma$ はアルファベットである．
* $\mathcal S := \Sigma^*$ は，長さ0以上の文字列の全体であり，その要素 $S \in \mathcal S$ は**部分系列パターン**（subsequence pattern）と呼ばれる．
* $(\preceq)\subseteq \mathcal S^2$ は，$\Sigma^*$上の部分系列関係である．

### 極大共通パターン問題

定義3（）: 任意のパターン族を $\Gamma = (\Delta, \mathcal P, \sqsubseteq)$ とする．任意の文字列 $S_1, S_2 \in \Sigma^*$ に対して，パターンの集合 $MCP_\Gamma(S_1, S_2)\subseteq \mathcal S$ を次のように定義する：任意の $T \in \mathcal P$に対して，
$T \in MCP_\Gamma(S_1, S_2) \iff$ 次の(1)と(2)が成立する:
* (1) $T \sqsubseteq S_i, \forall i=1,2$ が成立する．
* (2) 条件 (2.i) $T \sqsubset T'$と，条件 (2.ii) $T' \sqsubseteq S_i, \forall i=1,2$ を共に満たすようなパターン $T'\in \mathcal P$は存在しない．

MCS問題は，パターン族$Seq = (\Sigma, \mathcal S, \preceq)$に対する極大共通パターン問題（$MCP_{Seq}$）と，考えられる．

**補題**: 任意の文字列$S_1, S_2$に対して，$MCS(S_1, S_2) = MCP_{Seq}(S_1, S_2)$ が成立する．

### 別の例：VLDCパターンの族（作業中）

- VLDC, Variable-length don't-cares
- subsequenceの拡張
- $P = w_0 \Sigma^* w_1 \dots w_{m-1} \Sigma^* w_m\; (m\ge 0)$の形の正規表現
- 例：${\tt P_1 = AB .* BB .* BCA}$
- 例：${\tt P_1 = ABBBA = A.*B .* B .* B.* A}$
- 記法：

## 研究のアイディア

上のMCSの定義で，$\mathcal S$をVLSCパターンの族とする．同時に部分系列関係を，次のように定義されるVLDCパターンの包摂関係（subsumption relation）$\preceq$に拡張する．

定義：VLDCパターン上の二項関係$\preceq$を次のように定義する．任意のVLDCパターン$P, Q \in \mathcal S$ に対して，$P \preceq Q$であるとは，$P$のワイルドカードに任意の長さ0以上の文字列を代入すると$Q$が得られることをいう．もし$P \preceq Q$が成立する時，**$P$は$Q$を含む**といい，**$Q$は$P$に含まれる**という．

とすると，別のMCS問題が定義できる．

注意：包摂関係（subsumption relation）は，次の名前でも呼ばれる．
* 汎化関係（generalization/specialization relation），
* 部分パターン関係（subpattern relation）

MCSの定義で，**common subsequence**のところを，**common VLDC**　で置き換える．

## 参考文献

* Hiroki Arimura, Takeaki Uno:
Mining Maximal Flexible Patterns in a Sequence. JSAI 2007: 307-317
* Sec.2 Preliminariesと本文：論文のマイニング対象が，極大VLDCパターン

* Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura, Yoshikazu Miyanaga:
A Dynamically Reconfigurable FPGA-Based Pattern Matching Hardware for Subclasses of Regular Expressions. IEICE Trans. Inf. Syst. 95-D(7): 1847-1857 (2012)
* 論文のSec 2. Preliminariesに，VLDCパターンを含む拡張文字列パターンの定義あり

* NavaNavarro & Raffinot,Flexible Pattern Matching in Strings（黄色本）
* 一直線の正規表現のマッチングに詳しい．Bitap/Bit parallelも一番詳しい文字列照合の教科書．
* Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences (English Edition)

* 正規表現の選言にbitapを拡張したもの．
* Yusaku Kaneta, Shin-ichi Minato, Hiroki Arimura:
Fast Bit-Parallel Matching for Network and Regular Expressions. SPIRE 2010: 372-384

## EOF