WEKO3
アイテム
未決定文字列における欠如単語の検索の困難さ
https://ipsj.ixsq.nii.ac.jp/records/241031
https://ipsj.ixsq.nii.ac.jp/records/2410311beb47f1-a13e-4a13-88b0-e7f8c3a76df0
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]()
2026年11月19日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
非会員:¥660, IPSJ:学会員:¥330, AL:会員:¥0, DLIB:会員:¥0 |
Item type | SIG Technical Reports(1) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2024-11-19 | |||||||||
タイトル | ||||||||||
タイトル | 未決定文字列における欠如単語の検索の困難さ | |||||||||
言語 | ||||||||||
言語 | jpn | |||||||||
資源タイプ | ||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
資源タイプ | technical report | |||||||||
著者所属 | ||||||||||
山梨大学コンピュータ理工学 | ||||||||||
著者所属 | ||||||||||
University of Ulm | ||||||||||
著者所属(英) | ||||||||||
en | ||||||||||
University of Ulm | ||||||||||
著者名 |
Dominik, Köppl
× Dominik, Köppl
× Jannik, Olbrich
|
|||||||||
著者名(英) |
Dominik, Köppl
× Dominik, Köppl
× Jannik, Olbrich
|
|||||||||
論文抄録 | ||||||||||
内容記述タイプ | Other | |||||||||
内容記述 | 単純な文字列の一般化の一つは未決定文字列である.未決定文字列の中に,各位置に一つの文字が格納されているだけではなく,複数の文字の選択肢が認められている.応用として,テキスト位置ですべての可能性を列挙することをモデル化する.実用的であるためには,パターン照合や未決定文字列の類似性を測定するなど,単純な文字列に対して知られている技術を未決定文字列に応用し,さまざまなクエリの種類に答えることに注目が集まっているが,遺伝子データの解析でよく利用されている欠如単語の検索にはまだ応用されていない.単純な文字列で,最短の欠如単語の検索を既に線形時間で答えられるが,未決定文字列上での計算は NP 困難であることを示す. | |||||||||
書誌レコードID | ||||||||||
収録物識別子タイプ | NCID | |||||||||
収録物識別子 | AN1009593X | |||||||||
書誌情報 |
研究報告アルゴリズム(AL) 巻 2024-AL-200, 号 15, p. 1-5, 発行日 2024-11-19 |
|||||||||
ISSN | ||||||||||
収録物識別子タイプ | ISSN | |||||||||
収録物識別子 | 2188-8566 | |||||||||
Notice | ||||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
出版者 | ||||||||||
言語 | ja | |||||||||
出版者 | 情報処理学会 |