文字列集合における識別文字列を求めるための多項式時間手続き

伊藤 実  清水 邦保  中西 通雄  橋本 昭洋  

誌名
電子情報通信学会論文誌 D   Vol.J77-D1   No.8   pp.531-538
発行日: 1994/08/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 
識別文字列,  近似文字列照合,  DNAプローブ,  

本文: PDF(614.2KB)>>
論文を購入




あらまし: 
文字列a1a2anに対して,ai+1ai+2ajと表される文字列をa1a2anの部分文字列と言う.二つの文字列pqの距離とは,(1)任意の位置への1文字の挿入,(2)任意の位置の1文字の削除,(3)任意の位置の1文字の異なる1文字への置換の3種類の操作をpに適用してqを求めるために必要な操作の最小回数である.Sを文字列の有限集合とし,S Sの部分集合とする.ある距離δに対して,SにおけるS δ-識別文字列とは,S に属するすべての文字列の部分文字列で,かつ,SS に属するどの文字列のどの部分文字列とも距離がδ以上の文字列を言う.本論文では,SS ,および,1以上の距離δが任意に与えられたとき,SにおけるS δ-識別文字列が存在するかどうかを判定し,もし存在するならば,そのうちの最短のものをすべて求めるOδl・∥S∥)時間の手続きを示す.但し,lS に属する最短の文字列の長さで,∥S∥はSの記述長である.