文献

J-GLOBAL ID：202102258970413846   整理番号：21A0568512

マルチトラックストリング上の順列パターンマッチングアルゴリズム【JST・京大機械翻訳】

Permuted Pattern Matching Algorithms on Multi-Track Strings

著者 (5件)： Hendrian Diptarama ,  Ueki Yohei ,  Narisawa Kazuyuki ,  Yoshinaka Ryo ,  Shinohara Ayumi
資料名： Algorithms (Web)  (Algorithms (Web))
巻： 12  号： 4  ページ： 73  発行年： 2019年 
JST資料番号： U7130A  ISSN： 1999-4893  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： スイス (CHE)  言語： 英語 (EN)

抄録/ポイント： マルチトラックストリングは同じ長さのストリングのタプルである。2つのマルチトラックストリングのパターンとテキストを与えて,交換パターンマッチング問題は,テキストにおけるパターンのすべての置換の発生位置を見つけることである。本論文では,交換パターンマッチングのためのいくつかのアルゴリズムを提案した。KnuhMorrisPratt(KMP)アルゴリズムに基づく著者らの最初のアルゴリズムは,前処理時間としてO(mk)とマッチング時間としてO(nklog)を有する高速理論的計算時間を持ち,ここで,n,m,k,およびoccは,テキストの長さ,パターンの長さ,マルチトラックにおけるストリングの数,アルファベットサイズ,およびパターンの発生の数をそれぞれ示した。次に,より良い実験実行時間を持つオートマトンを用いてKMPベースのアルゴリズムを改善した。次の提案アルゴリズムは,BoyerMooreアルゴリズムおよびパターンマッチングを実行する試みであるHorsプールアルゴリズムに基づいている。これらのアルゴリズムは最速の実験アルゴリズムである。さらに,マルチトラックテキストにおける複数のマルチトラックパターンを見つけるタスクであるマルチトラック上の辞書マッチングを解決できるACオートマトンアルゴリズムの拡張を提案した。最後に,実際には,交換パターンマッチングを高速に実行できるフィルタリングアルゴリズムを提案した。Copyright 2021 The Author(s) All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  オートマトン ,  加工時間 ,  フィルタリング ,  *順列 ,  *パターンマッチング
準シソーラス用語： 実行時間 , 【Automatic Indexing@JST】

著者キーワード (3件)： マルチトラックストリング ,  順列パターンマッチング ,  ACオートマトン

分類 (2件)： 記号処理  (JE03000Q) ,  計算理論  (JB02000A)

引用文献 (14件)：

• Knuth, D.E.; Morris, J.H., Jr.; Pratt, V.R. Fast Pattern Matching in Strings. SIAM J. Comput. 1977, 6, 323-350.
• Boyer, R.S.; Moore, J.S. A fast string searching algorithm. Commun. ACM 1977, 20, 762-772.
• Horspool, R.N. Practical fast searching in strings. Softw. Pract. Exp. 1980, 10, 501-506.
• Weiner, P. Linear pattern matching algorithms. In Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT 1973), Iowa City, IA, USA, 15-17 October 1973; pp. 1-11.
• Manber, U.; Myers, G. Suffix Arrays: A New Method for On-Line String Searches. SIAM J. Comput. 1993, 22, 935-948.

タイトルに関連する用語 (3件)： 順列 ,  パターンマッチング ,  アルゴリズム