圧縮テキストに対するパターン照合機械の高速化
スポンサーリンク
概要
- 論文の詳細を見る
本稿では, テキストの圧縮による文字列パターン照合の高速化を扱う.通常, テキストは二次記憶装置に格納されるため, パターン照合の処理時間の大半はテキストのデータ転送に費やされる.深町ら(1992)はHuffman符号を用いてテキストを圧縮し, データ転送量を減少させることによって処理時間を短縮する方式を提案した.その際, 圧縮テキストを一度復号したうえで照合したのでは高速化されない.そこで, 深町らはAho-Corasick法をもとに, 圧縮テキストをそのまま走査するパターン照合機械の構成法を開発した.しかし, この方法では1ビットごとに状態遷移を行う必要がある.深町らは符号単位を4ビットとした符号化によって状態遷移回数を減らすことにより高速化を図っているが, 圧縮率が低下するという問題がある.そこで本稿では, Huffman符号用パターン照合機械の複数ビット分の状態遷移を1回の状態遷移で置き換えることにより, 圧縮されたテキストを高速に走査可能なパターン照合機械の実現法を提案する.これにより, Huffman符号による圧縮の効果を十分に引き出すことができる.英文テキストを用いた実験では, まとめ読みの単位を4ビット(8ビット)とした場合の走査時間は, 非圧縮テキストを4ビット(8ビット)ずつ走査した場合の63%(69%)に短縮できた.
- 一般社団法人情報処理学会の論文
- 1998-09-15
著者
-
竹田 正幸
九州大学大学院システム情報科学研究科
-
篠原 武
九州工大 情報工
-
篠原 武
九州工業大学情報工学部
-
宮崎 正路
九州大学大学院システム情報科学研究科情報理学専攻
-
深町 修一
九州工業大学情報工学部知能情報工学科
-
竹田 正幸
九州大学大学院システム情報科学府情報学専攻
-
竹田 正幸
九州大学大学院システム情報科学府
関連論文
- オンラインランク統合問題 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 九州大学における一般情報処理教育支援システムについて
- 古典和歌からの知識発見 : モビルスーツを着た国文学者(失われゆく情報の復元・保存技術 : 人文科学における情報処理(文献学・データベース共有・史科編纂))
- 質問学習における学習可能性の統一的特徴づけ
- WindowsマシンにおけるSeepの実装
- 国文学の研究教育における機械学習応用(機械学習の科学研究への応用)
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- 漸増的なパストライ構築に基づく高速・軽量XML文書フィルタリング(夏のデータベースワークショップ2007(データ工学,一般))
- 漸増的なパストライ構築に基づく高速・軽量XML文書フィルタリング(テキスト検索,夏のデータベースワークショップ2007(データ工学,一般))
- 文字列の圧縮とパターンの照合・発見(「自動化:推論,発見,学習,データマイニング」及び一般)
- 接尾辞配列による効率的な文字列上の同値類計算
- 物名十干部試注
- 医薬品の取り違えミスを防止するための薬名類似度の定量的指標の構築
- 浅香山恋部試注
- 浅香山秋冬部試注
- 秋部試注
- BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム
- 日本産昆虫総目録のデータベース化について
- 和歌データベースからの類似歌の自動抽出
- 九州大学自己点検・評価関連情報システム(セッション2:XML応用システム)
- ストリーム指向のXQuery処理システムについて(セッション4 : XML・構造化文書の蓄積とアクセス)
- ストリーム指向のXQuery処理システムについて(セッション4 : XML・構造化文書の蓄積とアクセス)
- ストリーム指向の XQuery 処理システムについて
- 長さ優先置換による文字列圧縮の線形時間アルゴリズム(文字列アルゴリズム)
- 高速一方向逐字処理技術に基づくXML文書の検索と変換(セッション3:デジタルコンテンツ管理技術)
- D-28 文字列照合技術に基づくXMLデータ処理(XMLデータ処理,D.データベース)
- 圧縮されたテキスト上のパターン照合 : データ圧縮とパターン照合の新展開
- 極大共通生垣を用いた情報抽出手法の提案
- 極大共通生垣を用いた情報抽出手法の提案
- 古典和歌における反復表現の諸相
- 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
- 古典和歌集からのテキストマイニング
- 英文科学技術文における単純名詞句決定法の比較
- 英文科学技術文における単純名詞句決定法の比較
- TD-1-5 文学作品からのテキストマイニング : 文学における発見を支援する
- 平衡直線的プログラムに対するパターン照合アルゴリズム
- 類似歌抽出に基づく歌集の成立年代推定
- 2000-CH-47-6 歌集間における表現特徴の自動抽出 : 部分文字列の生起頻度にみる
- 単語の頻度情報の偏りを用いた文書の自動分類手法の提案
- 科学技術文における共起情報を用いた関連語の抽出
- 2000-CH-46-3 / 2000-MUS-35-3 主旋律の類似性について
- 2000-CH-46-3 / 2000-MUS-35-3 主旋律の類似性について
- 和歌データからの類似歌発見のための類似性指標について
- 2G-2 圧縮テキストに対する文字列照合のための統一的枠組み
- 2G-1 データ圧縮による文字列照合の高速化
- 5G-2 音符列比較における類似性指標の評価
- 英文科学技術文における動詞の意味的分類
- 英文CISGの格構造化手続きの開発
- 英文科学技術文における前置詞を伴う動詞句の決定
- 英文科学技術文における単純名詞句の範囲決定
- 極小多重汎化によるパタン和推論アルゴリズムの実験的評価
- 圧縮テキストに対するパターン照合機械の高速化
- 極小多重汎化による正則パタン推論アルゴリズムの実験的評価
- 正則パターン言語和の包含に関する強コンパクト性(計算モデルと計算の複雑さに関する研究)
- 圧縮された日本語テキストのためのパターン照合機械の設計
- 帰納論理プログラムにおける背景知識を用いた多項式時間一般化アルゴリズム
- 複数文字列パターンによるアミノ酸配列からのタンパク質モティーフの発見
- 複数文字列パターンによる正例からのタンパク質モチーフの発見
- 木パターン言語の和の質問による学習
- 文字列パターン照合のための損失のあるデータ圧縮
- 内部変数をもつPROLOGプログラムの正事実からの極限同定
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- 極小多重汎化を用いた正事実からの論理プログラムの帰納的学習
- COLT '92(the Fifth Annual ACM Workshop on Computational Learning Theory)に参加して
- 形式言語の学習 : 正の例からの学習を中心に (計算的学習理論とその応用)
- 文字列パターン照合アルゴリズム
- SIGHAシステムにおけるパタン・マッチングの機能について
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習(IBIS2010(情報論的学習理論ワークショップ))
- コンピュータは文学研究を変えるか?
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- 1Q-4 図書目録イメージデータの検索システム
- ピクチャ・パターン照合アルゴリズム(計算アルゴリズムと計算量の基礎理論)
- 人文科学と情報科学の学際的研究のために
- 人文科学とコンピュータの学際的研究とは
- 情報検索システムAIRの実現
- 情報検索システムにおける高頻度キーワードの文書参照ファイルの圧縮について
- 情報検索システムにおける文書参照ファイル
- 和歌データベースにおける特徴パターンの発見 (人文科学とコンピュータ)
- 和歌データベースにおける類似歌の発見
- MDL 原理を用いた和歌データからのパターン抽出
- 固定文字と文字種の混在するパターンを対象としたAho-Corasick型パターン照合機械の構成法
- LZW圧縮テキストに対する高速文字列照合アルゴリズム
- イメージデータ化された図書目録カードの検索システム
- 4Q-7 空間索引を用いた近傍点検索に対する近似アルゴリズムによる高速化(ストリーム・空間検索,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 圧縮文字列上での $q$-gram 頻度の高速な計算方法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 確率的評価値をもつゲーム木における最善手探索 (計算機科学とアルゴリズムの数理的基礎とその応用)
- DS-1-10 文字列パターン上の同値関係と飽和パターンの列挙(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 英文科学技術文における高頻度名詞の分類について
- 単語の品詞とその被修飾度および前方修飾度との関係について
- 英文科学技術文における前方修飾語の決定について
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習
- 4Q-8 縮小型構造データSketchを用いた空間検索法に関する研究 : GHPを用いたSketch作成関数のためのピボット選択法(ストリーム・空間検索,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 非線形コラージュシステムにおける文字列パターン照合
- 2単語科学技術用語の英日翻訳について
- 科学技術用語における2単語句の英日翻訳規則
- 非線形テキストにおける最長共通部分文字列・部分列アルゴリズム
- 英文科学技術抄録文における高頻度動詞の格フレームに関する調査
- EDR概念体系辞書における上位-下位関係の推移的閉包の効率的検索
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- 類似度に基づくポリフォニックな楽曲の分類