文字列探索 2011/5/30.

Slides:



Advertisements
Similar presentations
逐次ソート 2011/05/16. ソート(sort) 順序集合の要素a 1 … a n の上下関係を整 える 一般的には、整数の集合 N を考えればよ い ソートの計算量が問題となる どのような入力に対し、どのようなアル ゴリズムが最適か?
Advertisements

PowerPoint による プレゼンテーションの作成 2005 年 7 月 19 日 牧野真也 最初のスライドは通常表紙となる.
情報生命科学特別講義III (1) 文字列マッチング
離散システム特論 整列(sorting)アルゴリズム 2.
4.ソート 4-1.ソート問題について 4-2.簡単なソートアルゴリズム 4-3.高度なソートアルゴリズム
コンパイラ 2011年10月17日
2分探索.
ファイルやフォルダを検索する ①「スタート」→「検索」→「ファイルとフォルダ」とクリックする。
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
アルゴリズムとデータ構造 2012年7月19日
アルゴリズムとデータ構造 第9回演習解答.
担当: 遠藤 美純 情報教育 初級講座 担当: 遠藤 美純
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
今回学ぶこと ちょっとした復習 基本的な編集機能 一歩進んだ編集機能 画面のロック ウィンドウを並べる フォントについて 文字列の切り貼り
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
コンパイラ 2012年10月15日
3次元剛体運動の理論と シミュレーション技法
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
データ構造とアルゴリズム論 第7章 探索のアルゴリズム
日本語解析済みコーパス管理ツール 「茶器」
文字列照合アルゴリズム 情報知識ネットワーク特論 喜田拓也 参考文献:
アルゴリズムとデータ構造 2013年7月18日
データ構造とプログラミング技法 (第10回) ー文字列照合(KMP法、BM法)ー.
情報管理論 2018/11/9 情報分析の道具 2018/11/9 情報分析の道具 情報分析の道具.
生物情報ソフトウェア特論 (1) 文字列マッチング・データ構造
k 個のミスマッチを許した点集合マッチング・アルゴリズム
輪講 第3回 Chapter 3 Exact Matching: A Deeper Look at Classical Methods
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
Fast Pattern Matching Algorithms in Compressed Texts
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
独習XML 第2章 XML文書の構成要素 2.1 XMLの文字と文字列 2.2 コメント
Proceedings of the Third South American Workshop on String Processing.
データ構造とアルゴリズム 第14回 文字列の照合.
Coloured Katakana Jumble Animals
Q q 情報通信システムのしくみ 村川 猛彦 第2回:2007年4月18日(水) q q.
データ構造とアルゴリズム 担当:和田俊和 居室:A603 講義資料等は下記を参照してください.
情報処理技法(リテラシI) 第14回:最終課題作成 産業技術大学院大学 情報アーキテクチャ専攻 助教  柴田 淳司 2017/7/20.
わんくま同盟茶藝部顧問 Microsoft MVP for VC episthmh
ネットワークプログラミング (5回目) 05A1302 円田 優輝.
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造 2011年7月12日
半構造化テキストに対する 文字列照合アルゴリズム
分子生物情報学(2) 配列のマルチプルアライメント法
シューティングゲームにおける 弾道予測アルゴリズムの作成
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミングⅠ 平成30年10月15日 森田 彦.
データ圧縮技術による文字列照合処理の高速化に関する研究
プログラミング 4 探索と計算量.
アルゴリズム論 (第12回) 佐々木研(情報システム構築学講座) 講師 山田敬三
長さの制限付きギャップと 文字クラスを含むパタンに対する 照合アルゴリズムの改善
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
Introduction to Soft Computing
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
第9回 優先度つき待ち行列,ヒープ,二分探索木
構造的類似性を持つ半構造化文書における頻度分析
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
情報の授業 小論文の作成(2) ・ファイルでの提出方法 ・はやく終わった人の課題 Go.Ota.
LZW 圧縮テキストに対する 高速文字列照合アルゴリズム 喜田 拓也 竹田 正幸 篠原 歩 九州大学大学院システム情報科学研究科
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
4.プッシュダウンオートマトンと 文脈自由文法の等価性
ファイル操作について (1).
オートマトンって? (Turing machine).
新人研修発表 平成13年5月14日(月) 探索アルゴリズム ハッシュ法について 株式会社 エーアイネット・テクノロジ          須田 哲生.
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
データ構造とアルゴリズム 第14回 文字列の照合.
8.文字列処理 8.1 C#の文字列 C#では, “ABCD”のように文字列を2重引用符で挟んで指定します。ASCIIコード体系のとき,以下のような内部形式となります。 1 1 文字 ‘A’ ナル文字 1 1 文字 ‘B’ A B C D \ 文字 ‘C’ 1 1 文字 ‘D’ ナル文字‘\0’
JSONの概要, Cloud FireStore で JSON を扱う
ns-3. Cloud FireStore で JSON を扱う (NoSQL データベースを学ぶシリーズ)
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
Presentation transcript:

文字列探索 2011/5/30

テキスト中で指定されたパターンが出現する 探索する文字列を「パターン」 探索する対象分を「テキスト」と呼ぶ テキスト中で指定されたパターンが出現する 場所を見つける操作

力任せのアルゴリズム

力任せ法の計算量 テキストをm字、パターンをn字とすると      (m-n+1)xn 計算量  O(mn) 実質的計算量 O(n)

KMP法 1970年、Cookが理論的に示唆   計算量O(m+n) D.E.KnuthとV.R.Pratt,Morrisが開発  計算量O(n)

KMP法の動き(1)

KMP法の動き(2)

KMP法の動き(3)

KMP法における前準備 ずらし表の作成 パターン “tartar” 「パターンの i 文字目で失敗した時に、何文字ずらして再開するか」 NEXT(0)=1 NEXT(3)=3 NEXT(1)=1 NEXT(4)=3 NEXT(2)=2 NEXT(5)=3

KMP法の能力 O(n) しかしながら、実際的に力任せ法と大して変わらない。

BM法 1977年にR.S.BoyerとJ.S.Moore 計算量 最悪の場合でも O(n), 平均的な場合(文字の種類が多く,パター ンがあまり長くない)にはO (n/m) 効率的

BM法

BM法

BM法

BM法

bad-character-shift

Bad-character-shift ANPANMANに対するbad character shift の計算 N 0 A 1 M 2 他のあらゆる文字 8

good-suffix-shift

good-suffix-shift ANPANMAN n 1 aN 8 mAN 3 nMAN 6 aNMAN 6 pANMAN 6 nPANMAN 6 aNPANMAN 6

bad-character-shiftとgood-suffix-shift ANMKODSAZANPANMOPOP    ANPANMAN good-suffix shift の場合 shift=3 i=+2 ↓

bad-character-shiftとgood-suffix-shift ANMKODSAZANPANMOPOP    ANPANMAN bad-character-shiftの場合 shift=6 i=+8                    ↓        ANPANMAN

参考文献 Wikipedia /english http://www-igm.univ-mlv.fr/~lecroq/string/node14.html