Suffix Array 構成アルゴリズムの比較

12 References

Bibliographic Information

Other Title
  • Comparison among Suffix Array Construction Algorithms

Search this article

Description

文書データベースから一致文字列を検索するためのコンパクトなデータ構造としてsuffix arrayがある。これは文字列の全ての接尾辞のポインタを辞書順に格納した配列で、木構造よりも必要なメモリが小さいため大きなデータベースに対して有効である。またsuffix arrayの構成はブロックソート圧縮法でも必要である。このsuffix arrayを構成するいくつかのアルゴリズムについて必要メモリと速度を比較し、それらを組み合わせた省メモリで高速なアルゴリズムを提案する。このアルゴリズムは文字列中に繰り返しが多い場合に有効である。
Suffix array is a compact data structure for searching matched strings from text databases. It is an array of pointers and stores all suffixes of a text in lexicographic order. Because its memory requirement is less than tree structures, it is effective for large databases. Moreover, constructing the suffix array is used in the Block Sorting compression scheme. We compare algorithms for constructing suffix arrays on speed and required memory and propose a fast and memory efficient algorithm by combining them. It is effective when the length of repeated strings in a text is large.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 59 9-16, 1997-11-28

    Information Processing Society of Japan (IPSJ)

References(12)*help

See more

Details 詳細情報について

  • CRID
    1573950401931472256
  • NII Article ID
    110002812051
  • NII Book ID
    AN1009593X
  • ISSN
    09196072
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top