圧縮された日本語テキストのためのパターン照合機械の設計
スポンサーリンク
概要
- 論文の詳細を見る
情報検索の問題の1つとして,パターン照合問題がある.パターン照合間題とは,パターンおよびテキストという2つの文字列が与えられたとき,テキスト中におけるパターンのすべての出現を見つけだす問題である.このパターン照合問題を解くアルゴリズムに,Aho-Corasick法がある.Aho-Corasick法の特長は,パターンよりパターン照合機械という一種の有限オートマトンを作り,そのパターン照合機械をテキスト上で1回走査させるだけで複数のパターンを同時に検出できることである.Aho-Corasick法を用いて実際に検索を行う際に問題になるのが,ディスクからテキストを読み込むのに要する時間である.この間題に対して,テキストをあらかじめ圧縮しておき,その圧縮されたテキストを復号せずに検索する方法が提案されている.日本語テキストには,ひらがな,カタカナ,漢字,記号といった複数の文字種が存在し,テキスト中では同じ文字種が連続して出現するという性質がある.この性質を利用して,文字種ごとに圧縮符号を割り当てることにする.このとき,異なる文字種間で同じ符号が割り当てられる可能性があるので,文字種を保持する必要がある.文字種の変わり目に文字種が変わることを示すシフトコードを用いる.この方法により,文字種を考慮に入れずに全体で圧縮符号を割り当てた場合より圧縮率はよくなる.本稿では,Aho-Corasick法のパターン照合機械を拡張し,シフトコード付き圧縮符号によって圧縮された日本語テキストのためのパターン照合機械を設計した.これを用いて日本語テキストを対象として実験を行った結果,圧縮率は69.7%,走査時間は78.3%に短縮できた.
- 一般社団法人情報処理学会の論文
- 1995-09-20
著者
-
篠原 武
九州工大 情報工
-
有村 博紀
九州工業大学
-
篠原 武
九州工業大学情報工学部
-
深町 修一
九州工業大学情報工学部知能情報工学科
-
宮崎 哲司
九州工業大学
-
平田 博明
九州工業大学
-
古賀 寿憲
寿殿
関連論文
- BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム
- 第2回マシンインテリジェンスに関する国際ワークショップ(International Workshop on Machine Intelligence 1993)の報告
- 極小多重汎化によるパタン和推論アルゴリズムの実験的評価
- 圧縮テキストに対するパターン照合機械の高速化
- 極小多重汎化による正則パタン推論アルゴリズムの実験的評価
- 正則パターン言語和の包含に関する強コンパクト性(計算モデルと計算の複雑さに関する研究)
- 圧縮された日本語テキストのためのパターン照合機械の設計
- 帰納論理プログラムにおける背景知識を用いた多項式時間一般化アルゴリズム
- 複数文字列パターンによるアミノ酸配列からのタンパク質モティーフの発見
- 複数文字列パターンによる正例からのタンパク質モチーフの発見
- 木パターン言語の和の質問による学習
- 文字列パターン照合のための損失のあるデータ圧縮
- 内部変数をもつPROLOGプログラムの正事実からの極限同定
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- 極小多重汎化を用いた正事実からの論理プログラムの帰納的学習
- COLT '92(the Fifth Annual ACM Workshop on Computational Learning Theory)に参加して
- 形式言語の学習 : 正の例からの学習を中心に (計算的学習理論とその応用)
- 文字列パターン照合アルゴリズム
- SIGHAシステムにおけるパタン・マッチングの機能について
- 4Q-7 空間索引を用いた近傍点検索に対する近似アルゴリズムによる高速化(ストリーム・空間検索,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 九州工業大学情報工学部知能情報工学科大槻研究室
- 4Q-8 縮小型構造データSketchを用いた空間検索法に関する研究 : GHPを用いたSketch作成関数のためのピボット選択法(ストリーム・空間検索,学生セッション,データベースとメディア,情報処理学会創立50周年記念)