パラメータワード

単語の組合せ論における数学的研究において、パラメータワードとは、与えられたアルファベット上の文字列で、いくつかのワイルドカード文字を含むものである。^[1]与えられたパラメータワードに一致する文字列の集合は、パラメータセットまたは組合せキューブと呼ばれる。パラメータワードは、与えられた組合せキューブのより小さなサブキューブを生成するように合成することができる。これらは、ラムゼー理論やコンピュータサイエンスにおける重複コードの検出に応用されている。

定義と表記

正式には、長さ の-パラメータ語は、与えられたアルファベット 上において、文字の並びであり、その一部は から抽出され、その他は とは異なるワイルドカード文字である。各ワイルドカード文字は少なくとも 1 回出現する必要があるが、複数回出現しても構わない。また、ワイルドカード文字は、そのインデックスで指定された順序で出現する必要がある。つまり、単語の最初のワイルドカード文字は でなければならず、 と異なる次のワイルドカード文字は でなければならない、などとなる。特別な場合として、与えられたアルファベット 上の、ワイルドカード文字を含まない単語は、0-パラメータ語と呼ばれる。1-パラメータ語の場合、異なるワイルドカード文字間に曖昧さがないため、添え字は省略できる。長さ のすべての-パラメータ語の集合は と表記される。^[1]${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle *_{1},*_{2},\ldots ,*_{k}}$ ${\displaystyle *_{1}}$ ${\displaystyle *_{1}}$ ${\displaystyle *_{2}}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle A{\tbinom {n}{k}}}$

-パラメータワードは、各ワイルドカード文字を のシンボルに置き換えることで得られる文字列（0パラメータワード）の集合を表します。この文字列の集合は、組み合わせキューブのパラメータ集合と呼ばれ、 はその次元と呼ばれます。1次元の組み合わせキューブは、組み合わせ直線と呼ばれることもあります。^[1]${\displaystyle k}$ ${\displaystyle |A|^{k}}$ ${\displaystyle A}$ ${\displaystyle k}$

組み合わせキューブでは、特定のワイルドカード文字の各コピーは同じ置き換えを持たなければなりません。 パラメータワードの一般化により、同じワイルドカード文字の異なるコピーを、制御された方法でアルファベットの異なる文字に置き換えることができます。 がアルファベットでがに作用するグループである場合、-ラベル付きパラメータワードは、ワード内の各ワイルドカード文字にグループ要素を割り当てた-パラメータワードです。各ワイルドカード文字の最初の出現には、グループの単位元が割り当てられていなければなりません。次に、ラベル付きパラメータワードによって表される文字列は、各ワイルドカード文字に対して の文字を選択し、その文字をその文字の各コピーにラベル付けしたグループ要素と組み合わせた結果を代入することによって得られます。 上の長さ のすべての -ラベル付き-パラメータワードの集合はと表されます。[ ^1]${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle [A,G]{\tbinom {n}{k}}}$

例

三目並べゲームでは、ゲームボードのセルにアルファベット から2 つの整数座標を割り当てることができます。これらの 2 つの座標を連結すると、各セルを表す文字列が生成され、9 つの文字列またはのいずれかになります。このアルファベットには、長さ 2 の 1 パラメータ ワードが 7 つあり、それぞれ と です。対応する組み合わせラインは、三目並べボードの 1 列に 3 つのセルが並ぶ 8 行のうち 7 行を形成します。たとえば、1 パラメータ ワードは組み合わせライン に対応し、1 パラメータ ワードは組み合わせラインに対応します。^[2]${\displaystyle (x,y)}$ ${\displaystyle \{1,2,3\}}$ ${\displaystyle 11,12,13,21,22,23,31,32,}$ ${\displaystyle 33}$ ${\displaystyle 1*,2*,3*,*1,*2,*3,}$ ${\displaystyle **}$ ${\displaystyle 2*}$ ${\displaystyle \{21,22,23\}}$ ${\displaystyle **}$ ${\displaystyle \{11,22,33\}}$

しかし、この組み合わせ線のセットには、三目並べゲームの 8 つの勝ちラインのうちの 1 つ、つまり対角線が欠けています 。このラインを組み合わせ線${\displaystyle \{13,22,31\}}$ として得ることは (三目並べでは無効となる他のセルの組み合わせを含めずに)、2 つの要素を持つグループと、非単位元がアルファベットの文字とを入れ替え、要素をそのままにするアクションを使用することで可能です。このアクションには長さ 2 のラベル付き 1 パラメータ単語が 8 つあり、そのうち 7 つはラベルなしの 1 パラメータ単語から、すべてのワイルドカードに単位元ラベルを使用して取得されます。これらの 7 つは以前と同じ組み合わせ線を持ちます。8 番目のラベル付き単語は、最初のラベルが単位元でラベル付けされた単語と、2 番目のラベルが反転した非単位元でラベル付けされた単語で構成されます。その組み合わせ線が三目並べボードの最終的な勝ちライン です。^[2]${\displaystyle 1}$ ${\displaystyle 3}$ ${\displaystyle 2}$ ${\displaystyle **}$ ${\displaystyle *}$ ${\displaystyle *}$ ${\displaystyle \{13,22,31\}}$

構成

3 つの整数パラメータ に対して、2 つのパラメータワードとを組み合わせて別のパラメータワード を生成することができます。そのためには、の 番目のワイルドカード記号の各コピーを の番目の文字で置き換えるだけです。これにより、 の各ワイルドカード記号を少なくとも 1 回昇順で使用する長さ のワードが必然的に生成され、長さ の有効な-パラメータワードが生成されます。この合成の概念は、ラベル付きパラメータワード (どちらも同じアルファベットとグループアクションを使用) の合成にも拡張できます。これは、グループアクションをワイルドカードでない置換文字に適用し、ワイルドカード置換文字のグループラベルを合成することによって行います。組み合わせキューブのサブセットは、このように合成によって取得できる場合、より小さな組み合わせキューブです。^[1]${\displaystyle n\geq m\geq k}$ ${\displaystyle f\in A{\tbinom {n}{m}}}$ ${\displaystyle g\in A{\tbinom {m}{k}}}$ ${\displaystyle f\circ g\in A{\tbinom {n}{k}}}$ ${\displaystyle i}$ ${\displaystyle f}$ ${\displaystyle i}$ ${\displaystyle g}$ ${\displaystyle n}$ ${\displaystyle g}$ ${\displaystyle k}$ ${\displaystyle n}$

組み合わせ列挙

サイズ のアルファベットに対するのパラメータワードの数は、第二種-スターリング数である。これらの数は、範囲 の整数を、最初の整数が異なる部分集合に属するような空でない部分集合に分割する回数を数える。このタイプの分割は、範囲 の各整数を表す文字を持つワードを作成し、この文字値を、分割の同じ部分集合に属する の整数、または に整数を含まない分割の各部分集合を表すワイルドカード文字に設定することで、パラメータワードと全単射同値関係に置くことができる。-スターリング数は、簡単に計算できる単純な再帰関係に従う。 ^{[3] [4]}${\displaystyle A{\tbinom {n}{k}}}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle \textstyle \left\{{r+n \atop r+k}\right\}_{r}}$ ${\displaystyle [1,r+n]}$ ${\displaystyle r+k}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle [r+1,n+r]}$ ${\displaystyle [1,r]}$ ${\displaystyle [1,r]}$ ${\displaystyle r}$

アプリケーション

ラムゼー理論では、パラメータ語と組合せ立方体を用いてグラハム・ロスチャイルド定理を定式化することができる。この定理によれば、すべての有限アルファベットと群作用、およびすべての整数値、、の組み合わせに対して、長さ の文字列上の各次元組合せ立方体に 色のいずれかを割り当てると、その次元部分立方体がすべて同じ色になるような次元組合せ立方体が存在するという、十分に大きな数が存在する。この結果は構造ラムゼー理論の重要な基礎であり、特定の値の組み合わせに対するの値を推定するために使用される巨大な数であるグラハム数を定義するために使用される。^[1]${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle n}$

コンピュータサイエンスにおいて、重複コードを検索する問題では、特定のルーチンまたはモジュールのソースコードをトークンのシーケンスに変換し、各変数またはサブルーチン名について、同じ名前の各コピーを同じワイルドカード文字に置き換えることで、パラメータワードに変換できます。コードが重複している場合、一部の変数またはサブルーチンの名前が変更されても、結果として得られるパラメータワードは同じままです。より洗練された検索アルゴリズムでは、ワイルドカード文字を互いに置き換えることで、より大きなソースコードリポジトリの部分文字列を形成する長い重複コードセクションを見つけることができます。^[5]

パラメータワードの重要な特殊なケースとして、ワードの組合せ論でよく研究されている部分ワードがあります。これはワイルドカード文字を含む文字列で、置換される文字の一部が等しいかグループアクションによって制御されている必要はなく、互いに独立して置換できます。パラメータワードの言語では、部分ワードは、各ワイルドカード記号が正確に1回出現するパラメータワードとして記述できます。ただし、ワイルドカード記号は重複しないため、部分ワードはワイルドカード記号の添え字を省略することでより簡潔に記述できます。^[6]

参照

• 正規表現

参考文献

1. Prömel, Hans Jürgen (2002)、「大きな数、クヌースの矢印表記法、そしてラムゼー理論」、Synthese、133 ( 1– 2): 87– 105、doi :10.1023/A:1020879709125、JSTOR  20117296、MR  1950045
2. Prömel, Hans Jürgen (2013)、「Hales–Jewettの定理」、Ramsey Theory for Discrete Structures、Springer International Publishing、pp.  41– 51、doi :10.1007/978-3-319-01315-2_4
3. Broder, Andrei Z. (1984)、「-スターリング数」、離散数学、49 (3): 241– 259、doi : 10.1016/0012-365X(84)90161-4、MR  0743795${\displaystyle r}$
4. Benzait, A.; Voigt, B. (1989)、「組み合わせ論的解釈」、Oberwolfach会議「Kombinatorik」（1986）の議事録、離散数学、73（1-2）：27-35、doi：10.1016/0012-365X（88）90130-6、MR  0974810${\displaystyle (1/k!)\Delta ^{k}t^{n}}$
5. Baker, Brenda S. (1997)、「文字列におけるパラメータ化された複製：アルゴリズムとソフトウェアメンテナンスへの応用」、SIAM Journal on Computing、26 (5): 1343– 1362、doi :10.1137/S0097539793246707、MR  1471985
6. Blanchet-Sadri, Francine (2008)、「部分語のアルゴリズム的組合せ論」、離散数学とその応用、フロリダ州ボカラトン：Chapman & Hall/CRC、ISBN 978-1-4200-6092-8、MR  2384993