文字列パターン照合のための損失のあるデータ圧縮

スポンサーリンク

概要

• 論文の詳細を見る

• もとのアルファベットからより小さなサイズkのアルファベットへの写像は,k-indexingと呼ばれ,損失のある圧縮符号とみなすことができる.損失のある符号を用いて圧縮されたテキスト上での文字列パターン照合は,圧縮率が高くなるために高速化が期待できるが,誤検出の可能性がある.2^n-indexingを用いると,nビットの固定長符号で,長さlのパターンの誤検出の期待値がほぼ<1/2>^<nl>となるような圧縮を行うことができる.文字ごとの照合に対する最適化,さらに2-gram,3-gramに対する最適化を行い,実際の英文テキストを用いて実験を行った.

• 社団法人電子情報通信学会の論文
• 1995-05-12

著者

• 篠原 武

  九州工大 情報工

• 有村 博紀

  九州工業大学

• 下薗 真一

  九州工業大学 情報工学部

• 篠原 武

  九州工業大学情報工学部

• 深町 修一

  九州工業大学情報工学部知能情報工学科

• 下薗 真一

  九州工業大学知能情報工学科

• 下薗 真一

  九州工業大学

関連論文

• BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム
• 第2回マシンインテリジェンスに関する国際ワークショップ(International Workshop on Machine Intelligence 1993)の報告
• 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
• 極小多重汎化によるパタン和推論アルゴリズムの実験的評価
• 圧縮テキストに対するパターン照合機械の高速化
• 極小多重汎化による正則パタン推論アルゴリズムの実験的評価
• 正則パターン言語和の包含に関する強コンパクト性(計算モデルと計算の複雑さに関する研究)
• 圧縮された日本語テキストのためのパターン照合機械の設計
• 帰納論理プログラムにおける背景知識を用いた多項式時間一般化アルゴリズム
• 複数文字列パターンによるアミノ酸配列からのタンパク質モティーフの発見
• 複数文字列パターンによる正例からのタンパク質モチーフの発見
• 木パターン言語の和の質問による学習
• 文字列パターン照合のための損失のあるデータ圧縮
• 内部変数をもつPROLOGプログラムの正事実からの極限同定
• BONSAI : 決定木とインデックス化による文字列からの機械発見システム
• 極小多重汎化を用いた正事実からの論理プログラムの帰納的学習
• COLT '92(the Fifth Annual ACM Workshop on Computational Learning Theory)に参加して
• 形式言語の学習 : 正の例からの学習を中心に (計算的学習理論とその応用)
• 文字列パターン照合アルゴリズム
• SIGHAシステムにおけるパタン・マッチングの機能について
• Complexity of Finding Alphabet Indexing(Fundamental Studies on Computational Complexity)
• 表面実相ロボットの実相シーケンスの決定に対する巡回セールスマン問題のアルゴリズムの適用
• 楽譜検索のための幾何点列の近似パタン照合(文字列アルゴリズム)
• テキストデータからの高速データマイニング : 探索的文書ブラウジングとウェブデータへの応用(発見科学)
• 生物配列の局所マルチプルアラインメントの計算困難性
• 大規模幾何データからの高速な極大部分グラフ発見 (特集 「ウェブマイニング」および一般)
• Efficient Discovery of Maximal Two-Dimensional Patterns with Don't-Cares(extended abstract) (テーマ:特集「ウェブデータの知的処理」および一般)
• K語近接相関パタンの高速発見アルゴリズム
• On Approximation Algorithms for Local Multiple Alignment (合同研究会"AIシンポジウム'99"(第10回))
• 文字列相関パタンの分類精度最大化問題について
• 省スペースな線形時間文法圧縮アルゴリズム
• DS-1-9 二次元点集合近似照合によるグラフの格子状配置アルゴリズム(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
• Minimum Multiset Covering 問題の近似アルゴリズムについて
• 平面巡回セールスマン問題の高速な近似アルゴリズム
• 無矛盾最小OBDD問題の近似困難性について
• 4Q-7 空間索引を用いた近傍点検索に対する近似アルゴリズムによる高速化(ストリーム・空間検索,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
• 九州工業大学情報工学部知能情報工学科大槻研究室
• 4Q-8 縮小型構造データSketchを用いた空間検索法に関する研究 : GHPを用いたSketch作成関数のためのピボット選択法(ストリーム・空間検索,学生セッション,データベースとメディア,情報処理学会創立50周年記念)

もっと見る 閉じる

スポンサーリンク