文献

J-GLOBAL ID：201702256096154416   整理番号：17A1424504

厳密解と近似最短ユニークな部分文字列問題のための現場アルゴリズム【Powered by NICT】

In-place algorithms for exact and approximate shortest unique substring problems

著者 (3件)： Hon Wing-Kai (Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan) ,  Thankachan Sharma V. (Department of Computer Science, University of Central Florida, FL 32816, USA) ,  Xu Bojian (Department of Computer Science, Eastern Washington University, WA 99004, USA)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 690  ページ： 12-25  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 厳密な最短ユニークな部分文字列(SUS)発見問題を再検討し,ミスマッチが許されるようにその近似版を提案し,計算生物学のような分野への応用に起因していた。厳密および近似K ミスマッチSUS発見,最小2N記憶語,[log2(n)]ビットのプラスnバイト空間を解くために適合する一般的な現場フレームワークを設計し,ここでnは入力文字列サイズである。現場フレームワークを用いて,O(n)とO(n 2)時間を用いて各ストリング位置のための厳密および近似K ミスマッチSUSを見出し,それぞれ,kの値にかかわらず。筆者らのフレームワークは,圧縮または簡潔なデータ構造を必要とせず,それにより実用的で実装が容易である。実験的研究を行い,提案方式のピークメモリ使用量は,サイズnのストリングに対する一貫して9Nバイトことを示した,このソリューションは,現場との主張を検証した。,著者らの提案は,はるかに少ないメモリを使用し,正確なSUS発見のための実装を持っていることを現在最良の研究よりも遥かに高速である。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *文字列 ,  バイト ,  高速度 ,  *アルゴリズム ,  データ構造 ,  *厳密解 ,  不整合 ,  *近似法 ,  記憶装置
準シソーラス用語： 実験研究 ,  計算生物学 , 【Automatic Indexing@JST】

著者キーワード (3件)： ストリングパターンマッチング ,  最短ユニークな部分文字列 ,  現場アルゴリズム

分類 (2件)： AD・DA変換回路  (NC05080M) ,  計算理論  (JB02000A)

タイトルに関連する用語 (6件)： 厳密解 ,  近似 ,  文字列 ,  問題 ,  現場 ,  アルゴリズム