データ構造とアルゴリズム 第14回 文字列の照合.

Slides:



Advertisements
Similar presentations
復習 配列変数の要素 5は配列の要素数 これらの変数をそれぞれ配列の要素と呼ぶ この数字を配列の添え字,またはインデックスと呼ぶ
Advertisements

復習 配列変数の要素 5は配列の要素数 これらの変数をそれぞれ配列の要素と呼ぶ この数字を配列の添え字,またはインデックスと呼ぶ
【事例演習5】  字句解析     解 説  “ハッシュを用いた字句解析の方法”.
情報生命科学特別講義III (1) 文字列マッチング
データ構造とアルゴリズム 平成20年度 前期 2年生必修  水曜日 3-4時限.
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
徳山豪 東北大学情報科学研究科 システム情報科学専攻 情報システム評価学分野
コンパイラ 2011年10月17日
第11回 整列 ~ シェルソート,クイックソート ~
ファーストイヤー・セミナーⅡ 第8回 データの入力.
情報リテラシー(1) ガイダンス 情報リテラシ2003 野村松信・須藤秀紹.
システムプログラミング 第5回 情報工学科 篠埜 功 ヒアドキュメント レポート課題 main関数の引数 usageメッセージ
プログラミング演習Ⅱ 第12回 文字列とポインタ(1)
最終回 総合演習 第13回目 [7月17日、H.15(‘03)] 本日のメニュー 1)総合演習課題 2)過去の試験問題 3)試験について
アルゴリズムとデータ構造 2012年7月19日
アルゴリズムとデータ構造 第9回演習解答.
第10回 ソート(1):単純なソートアルゴリズム
IT入門B2 (木曜日1限) 第一回 講義概要 2004年月9日30日.
12: コマンドライン引数 C プログラミング入門 総機1 (月1) Linux にログインし、以下の講義ページ を開いておくこと
情報工学概論 (アルゴリズムとデータ構造)
データ構造とアルゴリズム論 第9章 木構造 平成16年12月21日 森田 彦.
第8回 プログラミングⅡ 第8回
情報科学1(G1) 2016年度.
文字列探索 2011/5/30.
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
データ構造とアルゴリズム論 第2章 配列(構造)を使った処理
コンパイラ 2012年10月15日
コンピュータと情報 第15回 Excelの使い方 その4.
学習管理ファイル画面 P-1 ・学習機能の仕組み 「OF9X」の検索例(メイン画面での検索時)の流れ
第11回 整列 ~ シェルソート,クイックソート ~
アルゴリズムとデータ構造 2013年7月18日
コンピュータと情報 第14回 Excelの使い方 その4.
データ構造とプログラミング技法 (第10回) ー文字列照合(KMP法、BM法)ー.
情報工学科 3年生対象 専門科目 システムプログラミング 第5回、第6回 ヒアドキュメント レポート課題 情報工学科 篠埜 功.
シミュレーション論 Ⅱ 第14回 まとめ.
生物情報ソフトウェア特論 (1) 文字列マッチング・データ構造
アルゴリズムとプログラミング (Algorithms and Programming)
第7回 プログラミングⅡ 第7回
データ構造とアルゴリズム論 第1章 アルゴリズムの表現-流れ図
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造 2011年7月12日
アルゴリズムとデータ構造1 2005年6月24日
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
情報処理Ⅱ 第2回:2003年10月14日(火).
プログラミング 4 探索と計算量.
アルゴリズム論 (第12回) 佐々木研(情報システム構築学講座) 講師 山田敬三
(別紙1) プレゼンテーション の実施方法 ・期末試験期間の後,1組,2組, 夜間主の全グループが一会場で行う.
情報処理基礎A・B 坂口利裕 横浜市立大学・商学部
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
アルゴリズムとデータ構造1 2006年7月11日
プログラミング基礎a 第6回 C言語によるプログラミング入門 配列と文字列(その2)
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
岡村耕二 情報ネットワーク 岡村耕二 情報ネットワーク.
シミュレーション論Ⅰ 第7回 シミュレーションの構築と実施.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
プログラミング演習I 2003年7月2日(第11回) 木村巌.
プログラミング入門2 第13回、14回 総合演習 情報工学科 篠埜 功.
岡村耕二 情報ネットワーク 岡村耕二 情報ネットワーク.
情報処理Ⅱ 2006年11月24日(金).
第2章 統計データの記述 データについての理解 度数分布表の作成.
プログラミング入門2 第5回 配列 for文 変数宣言 初期化
情報処理Ⅱ 第7回 2004年11月16日(火).
プログラミング 4 文字列.
データ構造とアルゴリズム 第14回 文字列の照合.
情報処理Ⅱ 2005年11月25日(金).
8.文字列処理 8.1 C#の文字列 C#では, “ABCD”のように文字列を2重引用符で挟んで指定します。ASCIIコード体系のとき,以下のような内部形式となります。 1 1 文字 ‘A’ ナル文字 1 1 文字 ‘B’ A B C D \ 文字 ‘C’ 1 1 文字 ‘D’ ナル文字‘\0’
プログラミング入門2 第5回 配列 変数宣言、初期化について
12: コマンドライン引数 C プログラミング入門 基幹2 (月4) Linux にログインし、以下の講義ページ を開いておくこと
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
情報処理3 第4回目講義         担当 鶴貝 達政 12/17/2019.
Presentation transcript:

データ構造とアルゴリズム 第14回 文字列の照合

本日の内容 文字列の照合(p.161) 演習 アンケート

C言語の文字列 文字列とは 文字列 hello はプログラム中では以下のように表現されている 文字型の配列 ナル文字(NULL文字)で終端 char str[6] = { ‘h’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’ }; char str[6] = “hello”; ← このようにも書ける 5文字格納するのに、配列の要素は6個必要なことに注意 ナル文字 h e l l o \0

文字列の照合(検索) 文字列中の一部分を部分文字列と呼ぶ 特定のパターンをもった部分文字列がどこにあるかを調べる テキスト:babcabaabaacaabaa パターン:abaa

文字列照合の例 n文字のテキスト(src[0]~src[n-1])から、m文字のパターン(pat[0]~pat[m-1])が最初に現れる位置を検索 src h y p o c h o n d r i a \0 pat c h o \0

力まかせ法 src の0文字目~m-1文字目が、patと一致するか調べる src の1文字目~m文字目が、patと一致するか調べる h o y p c n d a r i \0 pat src の1文字目~m文字目が、patと一致するか調べる src h y p o c h o n d r i a \0 pat c h o \0 すべて一致するまで pat を1ずらしながら調べていく src h y p o c h o n d r i a \0 pat c h o \0

力まかせ法の計算量 テキスト長 n、パターン長 m 計算量 O(mn) テキスト長 n、パターン長 m 計算量 O(mn) 実際には、パターン先頭の数文字で一致判定できる(mはほぼ定数cとみなせる)ので O(cn) = O(n)

BM(Boyer-Moore)法 パターンを、右端の文字から照合していく パターンをずらせる量をあらかじめ計算しておき、可能な限りずらすことにより高速化 ⇒ 2つの方法で表をあらかじめ作成 テキストに現れるすべての文字について、それらがパターン中のどこに現れるかを示した表(表d) パターン中のそれぞれの位置について、そこで不一致が発生した場合にパターンをどれだけずらせるかを計算した表(表e)

BM法の文字照合 パターンpの右はしの文字から、文字列と一致するか調べる p[j] に対して j = m-1, m-2 の順に比較 (mはpの文字数) i t e p k o g e h o g e j (= 7) i t g e p k o g e h o g e j (= 6)

BM法のストラテジ1 あらかじめ、すべての文字について、パターン中のどこに現れるかの表 d を作成しておく (教科書 6.22式) a b 同じ文字が複数個ある場合には、もっとも右側の位置 文字がパターン中に存在しない場合には -1 パターンが kogehoge の場合 p k o g e h o g e a b c d e f g h i j k ・ o -1 7 6 4 5

BM法のストラテジ1 照合文字に応じて、max{1, j-d(t[i])} だけスキップ d(‘a’) = -1 (パターンに’a’は含まれない) s = max{1, 5 – (-1)} = 6 t a g e p k o g e h o g e j (= 5) t a g e p k o g e h o g e

BM法のストラテジ2 e( j ) = min{ s | p[l] = p[l – s], l = m–1, m–2,..., max{ j+1, s }, さらに j – s ≧ 0 の場合は p[j] ≠ p[j – s] } となる表を作成しておく (教科書 6.23式) e(j)とは、後方から照合していって、この位置で不一致が起きた場合、これだけずらさないと一致しない!という値 j 1 2 3 4 5 6 7 p k o g e h o g e e(j) 8 8 8 8 4 8 8 1

BM法のストラテジ2(例1) ここで不一致! 確認済み ? g e k o g e h o g e j (= 5) k o g e h o 1 2 3 4 5 6 7 p k o g e h o g e e(j) 8 8 8 8 4 8 8 1

BM法のストラテジ2 (例2) ここで不一致! 確認済み ? o g e k o g e h o g e j (= 4) k o g e h 1 2 3 4 5 6 7 p k o g e h o g e e(j) 8 8 8 8 4 8 8 1

いくつかのパターンに対する e(j) の例 j 1 2 3 4 5 6 7 j 1 2 3 a b c d e a b c a b a a 1 2 3 4 5 6 7 j 1 2 3 a b c d e a b c a b a a e(j) 5 5 5 5 5 8 8 1 e(j) 3 3 1 2 j j 1 2 3 4 5 6 7 1 2 3 4 5 6 7 a b c d e c d e a a a a a a a a e(j) e(j) 8 8 8 8 3 8 8 1 1 2 3 4 5 6 7 8

Boyer-Moore法 (まとめ) パターンの右端から照合 不一致がおきたときに、2つの表からパターンをずらす量を決定 s = max{ j –d(t[i]), e(j)} d(t[i]) は、不一致を起こしたsrc文字の種類によって決まる値 e(j) は、不一致を起こしたパターン中の位置によって決まる値 Boyer-Moore法の計算量 最悪ケース O(n) 平均ケース O(n/m)

期末試験について 日時:7/25(水) 10時30分~12時 場所:特別講義室Ⅱ 教科書,配布資料等の持ち込み不可 学生証を必ず提示すること 日時:7/25(水)  10時30分~12時 場所:特別講義室Ⅱ 教科書,配布資料等の持ち込み不可 学生証を必ず提示すること 机上に置けるものは,鉛筆またはシャープペン,消しゴム,定規,学生証のみ 座席は当日指定する 不正行為には厳正に対処する

成績評価について 全講義回数の2/3回(9回)以上の出席を満たさない場合は単位を取得できない(履修規定) レポートおよび期末試験を総合評価(比率 3:7) レポートと試験の合計得点を100点満点に換算 優:80点以上 良:70点以上~80点未満 可:60点以上~70点未満