論文の概要: Efficient Lempel-Ziv Prediction with the Run-Length BWT

• arxiv url: http://arxiv.org/abs/2611.01874v1
• Date: Sun, 01 Nov 2026 13:10:50 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 20:05:26.012704
• Title: Efficient Lempel-Ziv Prediction with the Run-Length BWT
• Title（参考訳）: ラン長BWTを用いた効率的なLmbpel-Ziv予測
• Abstract要約: Lempel-Ziv Plurality (LZP) は、弦の次の記号を予測するアルゴリズムである。 我々は、LZPの効率的なオンライン実装と、その新しいバリエーションを提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Lempel-Ziv Plurality (LZP) is an algorithm of Kosoy that predicts the next symbol of a string by using its Lempel-Ziv factorization, and makes at most $O(z\log n)$ mistakes on every string of length $n$ with $z$ LZ77 phrases. We give efficient online implementations of LZP and of a new variant of it. Our first implementation maintains a run-length encoded Burrows-Wheeler transform (RLBWT) of the reversed history. It implements LZP, uses $O(z\log z\log^2 n)$ bits, and has worst-case update and prediction times $O(\log z+\log\log n)$ and $O(σ(\log z+\log\log n))$, respectively, where $σ$ is the size of the alphabet. This is an exponential improvement over Kosoy's implementation, whose update time is $O(z\log^7 n)$. We then introduce the Lempel-Ziv Majority (LZM) predictor, which has the same mistake bound and update time, and predicts in $O(1)$ time independently of $σ$. These two predictors accept new symbols at any time, without knowing the alphabet in advance. For an alphabet known in advance, a different data structure gives $O(σ(1+\log z/\log\log n))$ time per symbol, which is constant when $σ=O(1)$ and $z=\mathrm{polylog}(n)$.
• Abstract（参考訳）: Lempel-Ziv Plurality (LZP) は、Lempel-Ziv因子化を用いて文字列の次のシンボルを予測するKosoyのアルゴリズムである。 我々は、LZPの効率的なオンライン実装と、その新しいバリエーションを提供する。 最初の実装では、逆履歴のバーロウス・ウィーラー変換(RLBWT)をラン長符号化している。 LZPを実装し、$O(z\log z\log^2 n)$ bitsを使用し、最悪の更新時間と予測時間を持つ$O(\log z+\log n)$と$O(σ(\log z+\log n))$である。 これはKosoyの実装よりも指数関数的に改善され、更新時間は$O(z\log^7 n)$である。 次に、同じ誤り境界と更新時間を持つLempel-Ziv Majority (LZM)予測器を導入し、$σ$とは独立に$O(1)$時間で予測する。 これら2つの予測子は、前もってアルファベットを知ることなく、いつでも新しいシンボルを受け入れる。 前述したアルファベットに対して、別のデータ構造は$O(σ(1+\log z/\log\log n))$time per symbolを与え、これは$σ=O(1)$と$z=\mathrm{polylog}(n)$のとき定数である。

関連論文リスト

• Component-Weighted Centroid Search for Exact Incremental BPE [22.892102324405826]
  特別な増分BPEは付加バイト毎に標準トークン化状態を維持する。 固定アルファベット上で正規化された適切なBPEファミリーを構築する。 Rustの実装は、テストされたインスタンス毎に予測されたプローブ数と一致します。
  論文  参考訳（メタデータ） (2026-09-30T15:55:09Z)
• Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation [17.156227790252526]
  q = Oleft(T + fraclog (1/varepsilon)logleft(e + log (1/varepsilon)/(T) right) 最適なクエリ複雑性を保ち、$Oleft[q left(a + logleft (1 + fracT(+ T)varepsilonを使用する同じアルゴリズムの実装を提供する。
  論文  参考訳（メタデータ） (2026-08-31T11:39:55Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• Differentially Private Kernel Density Estimation [11.526850085349155]
  我々は、カーネル密度推定(KDE)のための洗練された微分プライベート(DP)データ構造を導入する。 類似関数 $f$ とプライベートデータセット $X サブセット mathbbRd$ が与えられた場合、我々のゴールは、任意のクエリ $yinmathbbRd$ に対して、X f(x, y)$ の $sum_x を微分プライベートな方法で近似するように$X$ を前処理することである。
  論文  参考訳（メタデータ） (2024-09-03T08:01:19Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。