部分的な単語
コンピュータサイエンスの文字列用語

コンピュータサイエンスおよび単語の組合せ論の研究において、部分単語とは、文字列中に「不明」または「無視」の記号、つまり記号の値が不明または指定されていない文字列内のプレースホルダーを複数含む文字列のことである。より正式には、部分単語とは、有限のアルファベットを持つ部分関数である。u(k)が何らかの文字に対して定義されていない場合、文字 列のk番目の位置にある未知の要素は「ホール」と呼ばれる。正規表現（POSIX標準準拠）では、ホールはメタ文字「.」で表される。例えば、aab.ab.bは、アルファベットA ={ a , b }の長さ8の部分単語であり、4番目と7番目の文字がホールである。[1] あなた : { 0 、 … 、 n − 1 } → あ {\displaystyle u:\{0,\ldots ,n-1\}\rightarrow A} あ {\displaystyle A} け ∈ { 0 、 … 、 n − 1 } {\displaystyle k\in \{0,\ldots ,n-1\}}

アルゴリズム

「don't caresを含む文字列マッチング」問題に対しては、いくつかのアルゴリズムが開発されている。このアルゴリズムでは、入力は長いテキストと短い部分単語であり、目標はテキスト内で与えられた部分単語に一致するすべての文字列を見つけることである。[2] [3] [4]

アプリケーション

部分語の適合グラフ

2つの部分単語が同じ長さであり、かつ両方でワイルドカードでないすべての位置が両方で同じ文字を持つ場合、それらの部分単語は互換性があると言われる。部分単語のコレクション内の各部分単語を頂点とし、互換性のある各ペアを辺とする無向グラフを形成すると、このグラフのクリークは、少なくとも1つの共通文字列に一致する部分単語の集合から生成される。部分単語の互換性に関するこのグラフ理論的解釈は、クリーク問題の近似の困難性の証明において重要な役割を果たしている。クリーク問題とは、確率的に検証可能な証明検証器の成功した実行を表す部分単語のコレクションが、基礎となるNP完全問題の有効な証明が存在する場合にのみ、大きなクリークを持つ問題である。[5]

次元超立方体の面（部分立方体）は、2進アルファベット上の長さの部分語で記述することができ、その記号は超立方体の頂点の直交座標（例えば、単位立方体の場合は0または1）である。この表現における部分立方体の次元は、それに含まれるdon't care記号の数に等しい。同じ表現は、ブール関数の含意を記述するためにも用いられる。[6] n {\displaystyle n} n {\displaystyle n}

部分語はパラメータ語へと一般化することができ、パラメータ語では「知らない」記号の一部が互いに等しいとマークされます。部分語はパラメータ語の特殊なケースであり、各「知らない」記号は他のすべての記号とは独立して、任意の文字に置き換えられます。[7]

参考文献

  1. ^ Blanchet-Sadri, Francine (2008)、「部分語のアルゴリズム的組合せ論」、離散数学とその応用、フロリダ州ボカラトン：Chapman & Hall/CRC、ISBN 978-1-4200-6092-8、MR  2384993
  2. ^ Pinter, Ron Y. (1985), 「ドントケアパターンによる効率的な文字列マッチング」、単語の組み合わせアルゴリズム（Maratea, 1984）、NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci.、第12巻、Springer、ベルリン、pp.  11– 29、MR  0815329
  3. ^ Manber, Udi ; Baeza-Yates, Ricardo (1991)、「don't caresのシーケンスによる文字列マッチングアルゴリズム」、Information Processing Letters、37 (3): 133– 136、doi :10.1016/0020-0190(91)90032-D、MR  1095695
  4. ^ Kalai, Adam (2002)、「don't cares による効率的なパターンマッチング」、Eppstein, David (編)、Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms、2002年1月6日～8日、サンフランシスコ、カリフォルニア州、米国、ACM and SIAM、pp.  655～ 656
  5. ^ Feige, U. ; Goldwasser, S. ; Lovász, L. ; Safra, S ; Szegedy, M. (1991)、「近似クリークはほぼNP完全である」、Proc. 32nd IEEE Symp. on Foundations of Computer Science、pp.  2– 12、doi :10.1109/SFCS.1991.185341、ISBN 0-8186-2445-0、S2CID  46605913
  6. ^ カルノー、モーリス（1953）、「組み合わせ論理回路の合成のためのマップ法」、アメリカ電気学会誌、第1部：通信と電子工学、1953（5）：593-599、doi：10.1109/TCE.1953.6371932、MR  0069032、S2CID  51636736
  7. ^ プロメル、ハンス・ユルゲン（2002）「大きな数、クヌースの矢印表記法、そしてラムゼー理論」、シンセシス、133（1-2）：87-105、doi：10.1023/A：1020879709125、JSTOR  20117296、MR  1950045、S2CID  18330949
「https://en.wikipedia.org/w/index.php?title=Partial_word&oldid=1140659391」より取得