系列二分決定グラフを操作するための豊富な演算体系の構築 Rich Operations for Manipulating Sequence Binary Decision Diagrams

この論文をさがす

著者

    • 伝住 周平 DENZUMI Shuhei
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University
    • 有村 博紀 ARIMURA Hiroki
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University
    • 湊 真一 MINATO Shin-ichi
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University

抄録

大規模な文字列データを操作することは文字列処理の分野において重要な課題である.本稿では2009年にLoekitoらによって提案された系列二分決定グラフ(Sequence Binary Decision Diagram)と呼ばれるデータ構造を取り扱う.このデータ構造は多数の文字列を要素として含む文字列集合をコンパクトかつ一意に表現し,演算処理を効率良く行える.しかし,今まで提案された処理系では最小限の基本的な集合演算しか用意されていなかった.本稿では系列二分決定グラフの基本的な構造を示した上で,多様かつ高機能な文字列集合の演算体系を定義し,それらを実現する効率の良いアルゴリズムを提案する.

Manipulating large sequence data is important problem in string processing field. In this paper, we deal with sequence binary decision diagrams proposed by Loekito et al. in 2009. This data structure compactly and uniquely represents large set of many strings, and executes set operaitions efficiently. However, we have only basic set operations on processing systems already proposed. In this paper, we show fundamental structure of sequence binary decision diagrams, define various and advanced operations for string sets, and propose efficient algorithms to execute the operations.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 112(93), 9-16, 2012-06-14

    一般社団法人電子情報通信学会

参考文献:  22件中 1-22件 を表示

各種コード

  • NII論文ID(NAID)
    110009588446
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    0913-5685
  • NDL 記事登録ID
    023811054
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ