文献

J-GLOBAL ID：202002284731296952   整理番号：20A0529227

圧縮範囲最小クエリー【JST・京大機械翻訳】

Compressed range minimum queries

著者 (4件)： Gawrychowski Pawel (University of Wroclaw, Poland) ,  Jo Seungbum (University of Haifa, Israel) ,  Mozes Shay (Interdisciplinary Center Herzliya, Israel) ,  Weimann Oren (University of Haifa, Israel)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 812  ページ： 39-48  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： [0,σ]におけるn整数のストリングSを与えると,S[i...j]における最小整数の指数に対する範囲最小質問RMQ(i,j)が求められる。この問題は,サイズ2n+o(n)と一定の質問時間の簡潔なデータ構造で解くことができることが良く知られている。本論文では,高速範囲最小質問を可能にする圧縮表現にSを前処理する方法を示した。これにより,対数質問時間を持つサブ線形サイズデータ構造が可能になる。最も自然なアプローチは,ストリング圧縮を用いて,圧縮されたストリング上で直接的に範囲最小質問を応答させるためのデータ構造を構築することである。文法圧縮の文脈でこのアプローチを調べた。次に,代替アプローチを考察した。ストリング圧縮を用いてSを圧縮する代わりに,ツリー圧縮を用いてSのデカルトツリーを圧縮した。このアプローチは前者よりも指数関数的に優れており,O(σ)因子(すなわち,一定アルファベットに対しては漸近的に悪い)によっては決して悪くならず,Ω(σ)因子により実際には悪いことを示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 指数関数 ,  *対数 ,  線形性 ,  データ構造 ,  前処理
準シソーラス用語： *クエリー , 【Automatic Indexing@JST】

著者キーワード (5件)： RMQ ,  文法圧縮 ,  SLP ,  木の圧縮 ,  デカルトツリー

分類 (3件)： 図形・画像処理一般  (JE04010I) ,  人工知能  (JE08000Z) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (1件)： クエリー