抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本研究では,サブシーケンスフリーネスをテストする問題を研究した。与えられたサブシーケンス(語)w=w_1...w_kに対して,配列(テキスト)T=t_1...t_nは,指数1≦i_1<...<i_k≦n(例えば,t_ij=w_jが1≦j≦k)が存在するならば,wを含むと言われている。さもなければ,Tはwフリーである。特性試験における研究の大多数は,質問を実行するアルゴリズムを扱うが,ここでは,サンプルベース試験(片側誤差による)を考察した。「標準」サンプルベースモデル(即ち,均一分布の下で)では,このアルゴリズムは,iがランダムで独立に分布するサンプル(i,t_i)を与える。このアルゴリズムは,Tがwフリーである場合と,Tがwフリー(すなわち,そのシンボルのε-分数以上)がε-farである場合を区別するべきである。Freitag,Price,およびSwartworth(RANDOM,2017年)は,O((k2logk)ε)試料がこの試験作業に forしいことを示した。次の結果を得る:片側誤差サンプルベース試験(均一分布下)に対する十分なサンプル数はO(kε)である。この上限は,Tにおけるwのコピーの最大数に関してwフリーネスからテキストTの距離に対して存在する特徴に関して構築され,そこでは,これらのコピーは特定の制約に従うべきであり,ここでは,あらゆる単語wに対して保持するマッチング下界を証明した。これは,上記の上限が,より一般的な分布のないサンプルベースのモデルにおいて,同じ上限が保持されていることを意味した。このモデルでは,このアルゴリズムは,任意の分布p(そして,wフリーから距離がpに関して測定される)に従って,iが分布するサンプル(i,t_i)を受信する。著者らは,試験アルゴリズムがあらゆる分布に対して動作し,サンプルだけを提供するとき,この複雑性が,均一分布の下で1側面の誤差で,また質問(Canonne et al.,コンピューティングの理論,2019)で,一面誤差を有するテストのより容易な問題の特殊ケースに対して,既知の下限に整合するという事実を強調する。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
