論文の概要: 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)$アルゴリズムを用いて計算を行う。
キーワード:無限の後続ホワイトスペース、人間フレンドリー、直感的な編集距離、テーブル検出、テーブルアライメント
関連論文リスト
- 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) - Can You Solve Closest String Faster than Exhaustive Search? [4.963483138661772]
与えられた集合を表すのに最適な文字列を見つけるという根本的な問題を研究する。
本稿では,最も近い文字列問題は,自明な網羅的探索アルゴリズムよりも高速なアルゴリズムを許容するかどうかを考察する。
論文 参考訳(メタデータ) (2023-05-26T12:30:16Z) - On the Interplay Between Misspecification and Sub-optimality Gap in
Linear Contextual Bandits [76.2262680277608]
本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。
このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
論文 参考訳(メタデータ) (2023-03-16T15:24:29Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳(メタデータ) (2023-02-03T03:19:14Z) - 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) - Algorithme de recherche approximative dans un dictionnaire fond\'e sur
une distance d'\'edition d\'efinie par blocs [0.0]
そこで本研究では,修正文字列が参照形式にマッチする近似辞書検索アルゴリズムを提案する。
このアルゴリズムは、文字列間の分岐関数を利用する。
検索文字列までの距離が一定の閾値以下である辞書エントリを見つける。
論文 参考訳(メタデータ) (2021-09-01T21:36:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。