論文の概要: Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection

• arxiv url: http://arxiv.org/abs/2601.09577v1
• Date: Wed, 14 Jan 2026 15:46:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-15 18:59:20.456131
• Title: Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection
• Title（参考訳）: Parikh 予算下での置換マッチング:線形時間検出, パッケージング, 結合選択
• Authors: MD Nazmul Alam Shanto, Md. Tanzeem Rahat, Md. Manzurul Hasan,
• Abstract要約: 一般アルファベット$$に対して置換(ジャンブル/アベリア)パターンマッチングを研究する。 本稿では、PとTの現在の窓とのパリカーベクトル差の維持に基づく一貫したスライドウインドウ・フレームワークを提案する。 We show that MFSP can be solve in O(n + ) time through a two-pointer feasibility maintenance algorithm。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study permutation (jumbled/Abelian) pattern matching over a general alphabet $Σ$. Given a pattern P of length m and a text T of length n, the classical task is to decide whether T contains a length-m substring whose Parikh vector equals that of P . While this existence problem admits a linear-time sliding-window solution, many practical applications require optimization and packing variants beyond mere detection. We present a unified sliding-window framework based on maintaining the Parikh-vector difference between P and the current window of T , enabling permutation matching in O(n + σ) time and O(σ) space, where σ = |Σ|. Building on this foundation, we introduce a combinatorial-optimization variant that we call Maximum Feasible Substring under Pattern Supply (MFSP): find the longest substring S of T whose symbol counts are component-wise bounded by those of P . We show that MFSP can also be solved in O(n + σ) time via a two-pointer feasibility maintenance algorithm, providing an exact packing interpretation of P as a resource budget. Finally, we address non-overlapping occurrence selection by modeling each permutation match as an equal-length interval and proving that a greedy earliest-finishing strategy yields a maximum-cardinality set of disjoint matches, computable in linear time once all matches are enumerated. Our results provide concise, provably correct algorithms with tight bounds, and connect frequency-based string matching to packing-style optimization primitives.
• Abstract（参考訳）: 一般アルファベット$Σ$上での置換(ジャンブル/アベリア)パターンマッチングについて検討する。 長さ m のパターン P と長さ n のテキスト T が与えられたとき、古典的なタスクは、T がパリカーベクトルが P の値に等しい長さ m 部分弦を含むかどうかを決定することである。 この存在問題は線形時間スライディング・ウインドウの解を許容するが、多くの実用的な応用では単なる検出以上の変種を最適化しパッケージングする必要がある。 我々は、P と T の現在の窓とのパリカーベクトル差の維持に基いて、O(n + σ) 時間と O(σ) 空間における置換マッチングを可能にし、σ = |Σ| である。 この基礎の上に構築された組合せ最適化変種は、パターン供給(MFSP)の下で最大Fasible Substring(英語版)と呼ぶもので、記号数がP の成分的に有界な T の最長部分弦 S を求める。 我々は,MFSPをO(n + σ)時間で2点実現可能性維持アルゴリズムを用いて解くことができ,資源予算としてのPの正確なパッキング解釈を提供する。 最後に、各置換一致を等長間隔でモデル化し、全ての一致が列挙されたとき、線形時間で計算可能な不整合の最大心性集合が得られることを証明して、重複しない出現選択に対処する。 提案手法は,周波数に基づく文字列マッチングをパッキングスタイルの最適化プリミティブに接続する。

関連論文リスト

• Fairness in Repeated Matching: A Maximin Perspective [13.603504120117016]
  複数のラウンドで同じエージェントのセットにアイテムのセットが繰り返しマッチするシーケンシャルな意思決定モデルについて検討する。 目的は、全てのラウンドの終端(最適)または各ラウンドの終端(常に最適)において、最も有利でないエージェントの効用を最大化するマッチングの列を決定することである。
  論文  参考訳（メタデータ） (2025-10-06T09:32:40Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。 関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。 また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
  論文  参考訳（メタデータ） (2025-01-22T16:30:58Z)
• Probabilistic Permutation Graph Search: Black-Box Optimization for Fairness in Ranking [53.94413894017409]
  本稿では、置換グラフの概念に基づいて、置換分布を表現する新しい方法を提案する。 PLと同様に、PPGと呼ばれる分布表現は、公正性のブラックボックス最適化に利用できる。
  論文  参考訳（メタデータ） (2022-04-28T20:38:34Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Determinantal Beam Search [75.84501052642361]
  ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。 複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。 ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
  論文  参考訳（メタデータ） (2021-06-14T13:01:46Z)
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem [0.5584060970507505]
  グラフの最大マッチングに関するいくつかの問題に対処するための導出手法を設計する。 入力として空の状態が与えられたとき、可能なすべてのマッチングに対する重ね合わせと、入力としてW-状態が与えられたとき、すべての最大マッチングに対する重ね合わせを得る。 本研究の主な成果は,QAOA+アルゴリズムの2正規グラフ上での実行時の出力状態に対応するマッチングの期待サイズが,全てのマッチングの均一分布から得られるマッチングサイズよりも大きいことである。
  論文  参考訳（メタデータ） (2020-11-24T06:36:11Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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