論文の概要: A Fast Randomized Algorithm for Finding the Maximal Common Subsequences
- arxiv url: http://arxiv.org/abs/2009.03352v1
- Date: Mon, 7 Sep 2020 18:12:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 02:41:13.207554
- Title: A Fast Randomized Algorithm for Finding the Maximal Common Subsequences
- Title（参考訳）: 最大共通部分列探索のための高速ランダム化アルゴリズム
- Authors: Jin Cao and Dewei Zhong
- Abstract要約: 複数の文字列の最大共通部分列(MCS$)のランダムなインスタンスを見つけるためのランダム化アルゴリズムであるem Random-MCSを開発した。
アルゴリズムの複雑さは$L$で線形であることを示し、従って大きめの$L$に適している。
- 参考スコア（独自算出の注目度）: 8.970032486260695
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding the common subsequences of $L$ multiple strings has many applications
in the area of bioinformatics, computational linguistics, and information
retrieval. A well-known result states that finding a Longest Common Subsequence
(LCS) for $L$ strings is NP-hard, e.g., the computational complexity is
exponential in $L$. In this paper, we develop a randomized algorithm, referred
to as {\em Random-MCS}, for finding a random instance of Maximal Common
Subsequence ($MCS$) of multiple strings. A common subsequence is {\em maximal}
if inserting any character into the subsequence no longer yields a common
subsequence. A special case of MCS is LCS where the length is the longest. We
show the complexity of our algorithm is linear in $L$, and therefore is
suitable for large $L$. Furthermore, we study the occurrence probability for a
single instance of MCS and demonstrate via both theoretical and experimental
studies that the longest subsequence from multiple runs of {\em Random-MCS}
often yields a solution to $LCS$.
- Abstract（参考訳）: L$多重文字列の共通部分列を見つけることは、バイオインフォマティクス、計算言語学、情報検索の分野で多くの応用がある。
良く知られた結果は、$L$文字列に対して最も長い共通部分列(LCS)を見つけることはNPハードである、例えば、計算複雑性は$L$で指数関数的である。
本稿では,複数の文字列の最大共通部分列(MCS$)のランダムなインスタンスを見つけるためのランダム化アルゴリズムである {\em Random-MCS} を開発する。
共通部分列が {\em maximal} であるとは、任意の文字を部分列に挿入しても、もはや共通部分列は得られないということである。
MCSの特殊な例は、長さが最も長いLCSである。
アルゴリズムの複雑さは$L$で線形であることを示し、従って大きめの$L$に適している。
さらに, MCS の単一インスタンスの出現確率について検討し, 理論的および実験的な研究により, 複数行の {\em Random-MCS} の最長列が$LCS$の解となる場合が多いことを示した。
関連論文リスト
- Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning [2.2083091880368855]
差分的にプライベートな$k$選択問題について検討し、$d$アイテムから最も高いスコアを持つ$k$アイテムの列を特定することを目的とした。
Gillenwaterらによる最近の研究(ICML '22)は、$d,Theta(k)$ possible length-$k$ sequencesの膨大なコレクションから直接サンプリングアプローチを採用している。
時間と空間の複雑さを持つアルゴリズムを改良し、$O(d + k2 / epsilon cdot ln d)$で、$epsilon$はプライバシーを表す。
論文 参考訳（メタデータ） (2024-11-14T16:06:13Z) - A sublinear time quantum algorithm for longest common substring problem
between run-length encoded strings [0.951828574518325]
ラン長符号化(RLE)入力に対して,最長共通(LCS)問題に対するサブ線形量子アルゴリズムを提案する。
我々のアルゴリズムは$tildeO(n5/6)cdot O(mathrmpolylog(tilden))$ timeで、$n$と$tilden$はそれぞれ入力のエンコードされた長さとデコードされた長さである。
論文 参考訳（メタデータ） (2023-10-02T08:14:34Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For
Hidden Markov Models [70.26374282390401]
ノイズの多い観測から元の信号(すなわち隠れ鎖)を復号することは、ほぼすべてのHMMに基づくデータ分析の主要な目標の1つである。
本稿では,多対数計算複雑性において隠れた列を復号化するための分法であるQuick Adaptive Ternary(QATS)を提案する。
論文 参考訳（メタデータ） (2023-05-29T19:37:48Z) - Quantum algorithm for position weight matrix matching [0.9404723842159504]
バイオインフォマティクス, 位置重み行列(PWM)マッチングにおける問題に対する2つの量子アルゴリズムを提案する。
提案した2つのアルゴリズム、ナイーブ法とモンテカルロ法は、生物学的配列のエントリへの分子アクセスを考慮し、一致したセグメントを出力する。
論文 参考訳（メタデータ） (2023-03-07T00:34:16Z) - Longest Common Substring in Longest Common Subsequence's Solution
Service: A Novel Hyper-Heuristic [0.0]
最も長い共通部分列(Longest Common Subsequence、LCS)は、すべての文字列に共通であり、最も長い2つの性質を持つ文字列の集合の列を見つける問題である。
本稿では,その類似性に基づいて文字列の集合を分類する新しい基準を用いて,最も長い共通部分列問題の解法を提案する。
論文 参考訳（メタデータ） (2022-12-03T07:52:57Z) - A Single-Timescale Analysis For Stochastic Approximation With Multiple
Coupled Sequences [21.50207156675195]
複数の結合配列を持つ非線形近似の有限時間収束について検討する。
我々の分析の核心は、多くの応用において保持される多列SAの固定点の滑らか性である。
論文 参考訳（メタデータ） (2022-06-21T14:13:20Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳（メタデータ） (2021-06-14T13:01:46Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。