論文の概要: Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem
- arxiv url: http://arxiv.org/abs/2005.14335v1
- Date: Thu, 28 May 2020 22:44:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-18 02:41:43.824577
- Title: Classical and Quantum Algorithms for Constructing Text from Dictionary
Problem
- Title（参考訳）: 辞書問題からのテキスト構築のための古典的および量子的アルゴリズム
- Authors: Kamil Khadiev and Vladislav Remidovskii
- Abstract要約: 辞書(小文字列列)からテキストを構築する際の問題の解法について検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study algorithms for solving the problem of constructing a text (long
string) from a dictionary (sequence of small strings). The problem has an
application in bioinformatics and has a connection with the Sequence assembly
method for reconstructing a long DNA sequence from small fragments. The problem
is constructing a string $t$ of length $n$ from strings $s^1,\dots, s^m$ with
possible intersections. We provide a classical algorithm with running time
$O\left(n+L +m(\log n)^2\right)=\tilde{O}(n+L)$ where $L$ is the sum of lengths
of $s^1,\dots,s^m$. We provide a quantum algorithm with running time $O\left(n
+\log n\cdot(\log m+\log\log n)\cdot \sqrt{m\cdot L}\right)=\tilde{O}\left(n
+\sqrt{m\cdot L}\right)$. Additionally, we show that the lower bound for the
classical algorithm is $\Omega(n+L)$. Thus, our classical algorithm is optimal
up to a log factor, and our quantum algorithm shows speed-up comparing to any
classical algorithm in a case of non-constant length of strings in the
dictionary.
- Abstract（参考訳）: 辞書(小文字列列)からテキスト(長文字列)を構築する際の問題を解決するアルゴリズムについて検討する。
この問題はバイオインフォマティクスに応用され、小さな断片から長いDNA配列を再構築するSequenceアセンブリー法と関係がある。
問題は、文字列 $s^1,\dots, s^m$ から長さ$n$ の文字列を構成することである。
ランニングタイム $O\left(n+L + m(\log n)^2\right)=\tilde{O}(n+L)$ ここで$L$は$s^1,\dots,s^m$の長さの和である。
実行時間 $O\left(n +\log n\cdot(\log m+\log n)\cdot \sqrt{m\cdot L}\right)=\tilde{O}\left(n +\sqrt{m\cdot L}\right)$ の量子アルゴリズムを提供する。
さらに、古典的アルゴリズムの下位境界は$\Omega(n+L)$であることを示す。
したがって、我々の古典アルゴリズムはログ係数まで最適であり、我々の量子アルゴリズムは、辞書における文字列の非定数長の場合、任意の古典アルゴリズムと比較するスピードアップを示す。
関連論文リスト
- Quantum Algorithm for the Multiple String Matching Problem [0.0]
我々は$m$文字列のシーケンスを$S$と表現し、それを辞書と呼ぶ。
目的は、テキスト内の辞書から文字列のすべてのインスタンスを特定することである。
我々は,$O(n+sqrtmLlog nlog n)$クエリ複雑性と$O(n+sqrtmLlog n)=O*(n+sqrtmL)$タイム複雑性を持つ量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-22T10:50:43Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Quantum Algorithms for the Shortest Common Superstring and Text
Assembling Problems [11.048346250166073]
テキスト集合問題の2つのバージョンについて考察する。
文字列のシーケンスは$s1,dots,sn$ of total length $L$ that is a dictionary, string $t$ of length $m$ that is textsです。
どちらの問題に対しても、従来の量子アルゴリズムよりもうまく動作する新しい量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-18T14:16:49Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Near-Optimal Quantum Algorithms for String Problems [0.5736353542430439]
ほぼ最適なクエリ複雑度と時間複雑度を持つ基本文字列問題に対する量子アルゴリズムを提案する。
これらの問題には、Longest Common Substring、Lexicographically Minimal String Rotation、Longest Square Substringが含まれる。
我々の手法は、Longest Repeated Substring、Longest Lyndon Substring、Minimmal Suffixといった他の関連する文字列問題に自然に拡張する。
論文 参考訳（メタデータ） (2021-10-19T02:32:18Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Quantum Algorithms for the Most Frequently String Search, Intersection
of Two String Sequences and Sorting of Strings Problems [0.0]
弦の3つの問題を解くアルゴリズムについて研究する。
1つ目は、最も頻度の高い文字列検索問題である。
2つ目は、2つの弦列の交叉である。
第三の問題は長さ$k$の$n$文字列をソートすることだ。
論文 参考訳（メタデータ） (2020-01-07T07:22:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。