抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
本論文では,ミスマッチと差異によるテキストインデクシングの基本問題に対する下限を研究した。この問題において,長さn,”テキスト”の長いストリングを与え,タスクはクエリストリングQを与えられたデータ構造に前処理し,1つはQからほとんどのkでHammingまたは編集距離内にあるサブストリングを迅速に同定できる。この問題は生物学とテキスト処理で生じる様々な問題のコアにある。正確なテキストインデクシングは線形クエリ時間を有する線形サイズデータ構造を可能にするが,kミスマッチ(またはk差)によるテキストインデクシングははるかに硬く見える:全ての既知データ構造は空間または時間境界のいずれかでkに指数関数的依存性を持つ。この現象を説明するためのステップを作る条件付きおよびポインタマシン下限を提供した。k=Θ(logn)の下限を示すことで開始する。強い指数関数時間仮説を仮定すると,多項式時間で構築できるテキストインデクシングのための任意のデータ構造は,任意のΔΨ0に対してO(n1-δ)クエリ時間を持たないことを示した。また,この境界は,テキストインデクシングのための(1+O)近似解に対してのみ,著者らは,設定に拡張する。しかし,多くの応用において,kの値はむしろ小さく,1つは,小さなkに対して,より効率的な解を開発できると期待する。これは,現在の方法を使用すると,空間内のkへの指数関数的依存性を回避できないか,または,全ての[MATH HERE]に対して結合した時間において,ラジカル的に新しいアプローチを必要とすることを示した。この下限は辞書ルックアップ問題にも適用され,テキストの代りは文字列の集合を与える。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
