竹田 正幸 (九州大学)
  

  

    
題名: 圧縮テキスト上の効率的な文字列処理アルゴリズム 
  

  

    
アブストラクト: 大規模データが利用可能となった今日、データ圧縮はそれらを扱うための不可欠 な技術となっている。従来、データ圧縮を行う目的はストレージの節約や通信コ ストの削減にあり、それと引き換えに、圧縮データを実際に利用する際には大き な計算資源を費やす伸張処理を行う必要があった。だが、圧縮文字列処理アルゴ リズムにおける近年の研究の進展により、新たな展望がもたらされた。すなわ ち、データ圧縮を、データ容量低減の手段としてではなく、文字列処理効率化の ための前処理として捉えようというものである。具体的には、圧縮パターン照 合、文字列索引、編集距離およびその変種など、さまざまな文字列処理に関する アルゴリズムが開発されている。これらのアルゴリズムは、入力テキストが圧縮 形式で与えられることを前提とし、それを陽には伸張しないままに処理を行う。 興味深いことに、これらのアルゴリズムは、理論的に（そして時には実用的に も）非圧縮形式で与えられた同じテキスト上で動作するアルゴリズムよりも高速 に動作する。本講演では、この分野における最近の研究を概観する。 



  
  

    

  


     
Masayuki Takeda (Kyushu Univeristy)
  

  

    
Title: Efficient String processing Algorithms over Compressed text 

  

  

    
Abstract: Data compression is an indispensable technology for the handling of large-scale data available today. The traditional objective of compression has been to save storage and communication costs, whereas actually using the data normally requires a decompression step which can require enormous computational resources. However, recent advances in compressed string processing algorithms give us an intriguing new perspective in which compression can be regarded as a form of pre-processing which not only reduces space requirements for storage, but allows efficient processing of the strings, including compressed pattern matching, string indices, edit distance and its variants, and various other applications. These methods assume a compressed representation of the text as input, and process them without explicit decompression. An interesting property of these methods is that they can be theoretically – and sometimes even practically – faster than algorithms which work on an uncompressed representation of the same data. In this talk we give an overview of recent progress in this area. 

  
    

[Back ]