圧縮テキスト上の近似文字列照合問題北海道大学.ppt

《圧縮テキスト上の近似文字列照合問題北海道大学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、圧縮テキスト上の近似文字列照合問題喜田拓也，竹田正幸，篠原歩九州大学大学院システム情報科学府情報理学専攻発表者：竹田研究室博士課程３年　喜田拓也文字列照合問題テキストT中に含まれるパタンの出現を求める問題KMP法[Knuthら(1974)]，BM法[BoyerとMoore(1977)]ビットパラレル手法[Abrahamson(1987)][Baeza-YatesとGonnet(1992)]日本経済新聞　１１月１６日　朝刊（ジュネーブ発　西山　章宏）スイスの保養地、ダヴォス・プラッツで１１月１０日から１１月１４まで、

2、行われた、世界知覚認識学会（ミシェル・ポーター会長）で、北海道大学医学部の斉藤信（まこと）教授が提唱した、痛みを表す「hanage」と言う単位を、世界で共通の単位とする事が承認された。本来、痛みは、個人差が大きく、同じ刺激でも主観によって感じ方が異なるため、客観的に数値で表すことは、不可能であると思われていた。しかし、斉藤教授は、「鼻の粘膜は、人体の中で一番個人差が小さい。」事に注目し研究を進めた結果、１センチの鼻毛を、１Ｎ（ニュートン）の力で、引っ張る時に生じる痛みを、１hanageと定義出来ることを発見し、そして

3、今学会で単位として承認された。テキストTパタンhanage文字列照合アルゴリズム圧縮テキストに対する文字列照合問題主記憶装置上文字列照合アルゴリズム圧縮文字列照合アルゴリズム主記憶装置上復号二次記憶装置上テキストデータ主記憶装置上主記憶装置上転送転送転送目標２二次記憶装置上圧縮テキスト目標１二次記憶装置上圧縮テキスト本分野における研究圧縮方法照合アルゴリズムRun-lengthEilam-Tzoreff&Vishkin(1988)Run-length(twodim)Amiretal.(1992,1997);

4、Amir&Benson(1992)LZ77familyFarach&Thorup(1995);Gąsieniec,etal.(1996);Klein&Shapira(2000)LZ78familyAmiretal.(1996);Kidaetal.(1998,1999);Navarro&Tarhio(2000);Kärkkäinenetal.(2000);LZfamilyNavarroetal.(1999)Straight-lineprogramsKarpinskietal.(1997);Miyazakietal.

5、(1997);Hiraoetal.(2000)HuffmanFukamachietal.(1998);Klein&Shapira(2001);Miyazakietal.(1998)FinitestateencodingTakeda(1997)WordbasedencodingMouraetal.(1998)PatternsubstitutionManber(1994);Shibataetal.(1998)AntidictionarybasedShibataetal.(1999)実験結果（非圧縮テキスト上のアルゴリズム

6、との対比）AlphaStationXP1000(Alpha21264:667MHz)Tru64UNIXV4.0FMedline（英文テキスト）60.3Mbyte51015202530パタンの長さ0.00.30.40.50.80.10.20.60.7CPU時間（秒）非圧縮テキストをKMPで照合非圧縮テキストをAgrepで照合BPE圧縮テキストに対する照合*AgrepはWu&Manberが開発した検索ツール*KMPはKnuth-Morris-Pratt法*BPEはBytePairEncoding圧縮法BPE圧縮テキストに

7、対するBoyer-Moore型のアルゴリズムを用いた照合（Shibataら[2000]）世界最高速近似文字列照合問題MARRIAGEMASSAGECARRIAGE近似文字列照合問題テキスト中のパタンとの編集距離がk以内の文字列の出現を求める問題編集距離文字列xに文字の挿入・削除・置換の操作を施して文字列yへ変換するために要する最小操作回数dMARRIAGEMASSAGECARRIAGEk=2d=1d=3MARRIAGEMASSAGE削除置換近似文字列照合アルゴリズム動的計画法Sellers(1980)O(mN)時

8、間O(m)領域Ukkonen(1985)平均O(kN)時間O(m)領域オートマトンに基づく手法Ukkonen(1985)O(min(3m,m(2m

9、

10、)k))個の状態数ビットパラレル手法Wu&Manber(1992)O(km/LN)時間領域Baeza-Yates&Navarro(1996)O(k(m-k)/LN)時間領域Myers(1