文献

J-GLOBAL ID：202002284694036652   整理番号：20A1555180

重み付きスコアへのマッチカウント問題のためのFFTベースアルゴリズムの拡張【JST・京大機械翻訳】

An extension of the FFT-based algorithm for the match-count problem to weighted scores

著者 (1件)： Baba Kensuke (Artificial Intelligence Laboratory, Fujitsu Laboratories Ltd, Kawasaki, 211-8588, Japan)
資料名： IEEJ Transactions on Electrical and Electronic Engineering  (IEEJ Transactions on Electrical and Electronic Engineering)
巻： 12 Suppl S2  ページ： S97-S100  発行年： 2017年 
JST資料番号： W1854A  ISSN： 1931-4973  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ストリングに関するマッチカウント問題は,あらゆる可能なアラインメントのために2つのストリングの間の特性の一致を計数する基本的問題である。この問題は,サイズσのアルファベット上の長さmとn(m≦n)の2つのストリングに対して高速Fourier変換(FFT)を用いてO(σ_nlogm)時間で古典的に計算される。本論文は,このFFTベースのアルゴリズムの目標を問題の重みづけバージョンに拡張し,それは,マッチの数の代わりに文字間の類似性の合計を計算する。本論文に拡張されたアルゴリズムは,次元dの数値的ベクトルに文字を写像することによって,O(dnlog m)時間で加重マッチカウント問題を解決することができる。また,本論文は,文書における斜長石検出に適用することによって,拡張アルゴリズムの有用性を評価した。実験結果は,提案アルゴリズムが単語の一般的ベクトル表現に適用可能であり,得られた斜長石検出法が,通常のマッチカウント問題に基づく方式からの精度のわずかな減少で処理時間を著しく減少できることを示した。Copyright 2020 Wiley Publishing Japan K.K. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アラインメント ,  *アルゴリズム ,  畳込み ,  ベクトル ,  斜長石 ,  加工時間 ,  検出法 ,  重みづけ ,  類似性 ,  高速Fourier変換 ,  単語
準シソーラス用語： ストリングマッチング , 【Automatic Indexing@JST】

著者キーワード (5件)： ストリングマッチング ,  マッチカウント問題 ,  畳込み ,  単語のベクトル表現 ,  盗作検出

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (6件)： スコア ,  カウント ,  問題 ,  FFT ,  アルゴリズム ,  拡張