不確定ストリング上の実用的KMP/BMスタイルパターンマッチング【JST・京大機械翻訳】

Dehghani Hossein; Mhaskar Neerja; Smyth W. F.

プレプリント

J-GLOBAL ID：202202212166671533 整理番号：22P0333619

不確定ストリング上の実用的KMP/BMスタイルパターンマッチング【JST・京大機械翻訳】

Practical KMP/BM Style Pattern-Matching on Indeterminate Strings

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2022年04月18日プレプリントサーバーでの情報更新日： 2024年02月16日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本論文では,pとxが「小さい」規則化アルファベットΣ-すなわちσ=ε≦9で定義される,非決定性ストリングx=x[1.n]における不確定パターンp=p[1.m]の全ての整合を見つけるための2つの単純,高速,空間効率の良いアルゴリズムを記述した。両アルゴリズムは,Σ_I=σの整数アルファベットΣ_IによりΣを置換する前処理段階に依存し,その最大(無限)レターは,32ビット単語(すなわち,DNA配列,8-ビット表現サフス)で表現できるΣ_I上で,それぞれxとpを等価正規ストリングyとqに写像する。最初に,y(xにおけるp)におけるqの全ての発生を見つけるため,また,変換されたストリングyに沿った変換パターンqのシフトを制御するために,境界アレイよりもプレフィックスアレイを用いて,必要ならば,venable Knuth-Morris-Prattアルゴリズムの効率的なバージョンKMP Indetを記述した。広範囲のテストケースにわたってKMPインデットよりも著しく高速に実行するために,Boyer-Mooreアルゴリズムの類似の効率的なバージョンBM Indetを記述する。注目すべき特徴は,両方のアルゴリズムが非常に少ない付加的空間:Θ(m)単語を必要とすることである。著者らは,類似のアプローチが,他のよく知られたパターンマッチングアルゴリズム,特にBoyer-Mooreのいくつかの変異体に対して,実用的で効率的な不確定な等価物を生成するかもしれないと推測した。【JST・京大機械翻訳】

, , , , , , ,
, , , , 【Automatic Indexing@JST】

パターン認識 , 記号処理

, , ,

前のページに戻る