論文の概要: Imagined-Trailing-Whitespace-Agnostic Levenshtein Distance For Plaintext Table Detection

• arxiv url: http://arxiv.org/abs/2103.06942v1
• Date: Thu, 11 Mar 2021 20:39:40 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-16 02:29:47.424504
• Title: Imagined-Trailing-Whitespace-Agnostic Levenshtein Distance For Plaintext Table Detection
• Title（参考訳）: 平文テーブル検出のためのホワイトスペース非依存レベンシュテイン距離の想像
• Authors: Kartik Vempala (Bloomberg LP)
• Abstract要約: Levenshtein 距離は後続の空白を他の文字や記号と同じ扱います。 人間が2つの文字列を比較するとき、両方の文字列は無限の後続の空白でパッドされていると暗黙的に仮定する。 この期待に反すると、直感的な編集距離値が得られません。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The standard algorithm for Levenshtein distance, treats trailing whitespace the same as any other letter or symbol. However, when humans compare 2 strings, we implicitly assume that both strings are padded by infinite trailing whitespace. This informs our expectations for what the costs for insertion, deletion and replacement, should be. This violation of our expectations results in non-intuitive edit distance values. To account for this specific human intuition, a naive approach which considers "all possible" substrings of trailing whitespace would yield an $O(n^3)$ algorithm. In this work, we provide an efficient $O(n^2)$ algorithm to compute the same. Keywords: Imagined Infinite Trailing Whitespace, Human Friendly, Intuitive Edit Distance, Table Detection, Table Alignment
• Abstract（参考訳）: Levenshtein距離の標準アルゴリズムは、後続の空白を他の文字や記号と同じ扱います。 しかし、人間が2つの文字列を比較するとき、両方の文字列は無限の後続の空白でパッドされていると暗黙的に仮定する。 これにより、挿入、削除、および交換のコストがどうあるべきかが予想されます。 この期待に反すると、直感的な編集距離値が得られません。 この特定の人間の直観を考慮すれば、後続する空白空間の「すべての可能な」部分文字列を考えるナイーブなアプローチは、$o(n^3)$アルゴリズムをもたらす。 本研究では,効率の良い$O(n^2)$アルゴリズムを用いて計算を行う。 キーワード:無限の後続ホワイトスペース、人間フレンドリー、直感的な編集距離、テーブル検出、テーブルアライメント

関連論文リスト

• On Differentially Private String Distances [12.852131074558057]
  基本的なデータ構造タスクは、データベース内のすべての文字列で、与えられたクエリのBin 0,1n$間の距離を見積もることである。 本稿では,このようなタスクに対して,ハミングと編集距離に着目した差分プライベート(DP)データ構造を提案する。 そこで我々は,ビットフリップ法としてランダム化応答手法の新たな適応により,これらの結果を得た。
  論文  参考訳（メタデータ） (2024-11-08T18:10:07Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Differentially Private Approximate Pattern Matching [0.0]
  我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。 目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。 1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
  論文  参考訳（メタデータ） (2023-11-13T15:53:45Z)
• 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 Near-Linear Time Algorithm for the Chamfer Distance [21.018781726524946]
  チャンファー距離は点雲間の相似性の一般的な尺度である。 1+epsilon)$-approximate アルゴリズムは,Chamfer 距離をほぼ直線走行時間で推定する。 我々の実験は、大規模な高次元データセット上では正確かつ高速であることを示した。
  論文  参考訳（メタデータ） (2023-07-06T15:07:48Z)
• Breaking the cubic barrier in the Solovay-Kitaev algorithm [0.0]
  我々は、一般有限で逆閉生成集合がクーディットに作用するようなソロヴィ・キタエフの定理とアルゴリズムを改善する。 我々の結果はより一般的に、連結半単純実リー群を密に生成する任意の有限集合に対して成り立つ。
  論文  参考訳（メタデータ） (2023-06-22T18:35:06Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。 このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
  論文  参考訳（メタデータ） (2023-03-16T15:24:29Z)
• Supervised Training of Conditional Monge Maps [107.78770597815242]
  最適輸送(OT)理論は、多くの可能な選択の中から確率測度を他のものにマッピングする最も効率的な方法を定義し、選択する一般的な原理を記述している。 本研究では,コンテキスト変数に条件付きOTマップの族を推定するマルチタスク手法であるCondOTを紹介する。 本研究では,CondOTの遺伝的・治療的摂動の任意の組み合わせが単一細胞に与える影響を推測する能力を示す。
  論文  参考訳（メタデータ） (2022-06-28T19:34:44Z)
• 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)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear Bandits [16.103685478563072]
  本稿では,一般制約付き線形帯域について考察する。 目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。 本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-10T07:30:37Z)

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

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