圧縮を用いた類似度判定 のための計算実験 谷研究室 新井 秀 森田 岳史.

Slides:



Advertisements
Similar presentations
ゲームプログラミング講習 第2章 関数の使い方
Advertisements

サービス管理責任者等研修テキスト 分野別講義    「アセスメントと        支援提供の基本姿勢」 <児童発達支援管理責任者> 平成27年10月1日.
ヒトの思考プロセスの解明を目的とするワーキングメモリの研究
第27講 オームの法則 電気抵抗の役割について知る オームの法則を使えるようにする 抵抗の温度変化を理解する 教科書P.223~226
コラッツ予想の変形について 東邦大学 理学部 情報科 白柳研究室 山中 陽子.
コンパイラ 第3回 字句解析 ― 決定性有限オートマトンの導出 ―
第5章 家計に関する統計 ー 経済統計 ー.
公共財 公共経済論 II no.3 麻生良文.
VTX alignment D2 浅野秀光 2011年12月15日  放射線研ミーティング.
冷却フランシウム原子を用いた 電子の永久電気双極子能率探索のための ルビジウム磁力計の研究
生命情報学 (8) スケールフリーネットワーク
前半戦 「史上最強」風 札上げクイズ.

認知症を理解し 環境の重要性について考える
フッ化ナトリウムによる洗口 2010・9・13 宮崎市郡東諸県郡薬剤師会 学校薬剤師  日高 華代子.
食品の安全性に関わる社会システム:総括 健康弱者 ハイリスク集団 HACCP (食肉処理場・食品工場) 農場でのQAP 一般的衛生管理
規制改革とは? ○規制改革の目的は、経済の活性化と雇用の創出によって、   活力ある経済社会の実現を図ることにあります。
地域保健対策検討会 に関する私見(保健所のあり方)
公共政策大学院 鈴木一人 第8回 専門化する政治 公共政策大学院 鈴木一人
医薬品ネット販売規制について 2012年5月31日 ケンコーコム株式会社.
平成26年8月27日(水) 大阪府 健康医療部 薬務課 医療機器グループ
平成26年度 呼吸器学会からの提案結果 (オレンジ色の部分が承認された提案) 新規提案 既収載の変更 免疫組織化学染色、免疫細胞化学染色
エナジードリンクの危険性 2015年6月23日 経営学部市場戦略学科MR3195稲沢珠依.
自動吸引は 在宅を変えるか 大分協和病院 院長         山本 真.
毎月レポート ビジネスの情報 (2016年7月号).
医療の歴史と将来 医療と医薬品産業 個人的経験 3. 「これからの医療を考える」 (1)医薬品の研究開発 -タクロリムスの歴史-
社会福祉調査論 第4講 2.社会調査の概要 11月2日.
2015年12月28日-2016年3月28日 掲載分.
2010度 民事訴訟法講義 補論 関西大学法学部教授 栗田 隆.
腫瘍学概論 埼玉医科大学国際医療センター 包括的がんセンター 緩和医療科/緩和ケアチーム 奈良林 至
“企業リスクへの考え方に変化を求められています。 トータルなリスクマネジメント・サービスをプロデュースします。“
情報漏えい 経済情報学科 E  西村 諭 E  釣 洋平.
金融班(ミクロ).
第11回 2009年12月16日 今日の資料=A4・4枚+解答用紙 期末試験:2月3日(水)N2教室
【ABL用語集】(あいうえお順) No 用語 解説 12 公正市場価格 13 債権 14 指名債権 15 事業収益資産 16 集合動産 17
基礎理論(3) 情報の非対称性と逆選択 公共政策論II No.3 麻生良文.
浜中 健児 昭和42年3月27日生まれ 東京都在住 株式会社ピー・アール・エフ 代表取締役 (学歴) 高 校:千葉県立東葛飾高校 卒業
COPYRIGHT(C) 2011 KYUSHU UNIVERSITY. ALL RIGHTS RESERVED
Blosxom による CMS 構築と SEO テクニック
記入例 JAWS DAYS 2015 – JOB BOARD 会社名 採用職種 営業職/技術職/その他( ) 仕事内容 待遇 募集数
ネットビジネスの 企業と特性 MR1127 まさ.
Future Technology活用による業務改革
ネットビジネス論(杉浦) 第8回 ネットビジネスと情報技術.
g741001 長谷川 嵩 g740796 迫村 光秋 g741000 西田 健太郎 g741147 小井出 真聡
自然独占 公共経済論 II no.5 麻生良文.
Autonomic Resource Provisioning for Cloud-Based Software
Webショップにおける webデザイン 12/6 08A1022 甲斐 広大.
物理的な位置情報を活用した仮想クラウドの構築
ハイブリッドクラウドを実現させるポイントと SCSKのOSSへの取組み
寺尾 敦 青山学院大学社会情報学部 第12回 情報デザイン(4) 情報の構造化と表現 寺尾 敦 青山学院大学社会情報学部
【1−1.開発計画 – 設計・開発計画】 システム開発計画にはシステム開発を効率的、効果的に実行する根拠(人員と経験、開発手順、開発・導入するシステム・アプリケーション・サービス等)を記述すること。 システム開発の開始から終了までの全体スケジュールを記載すること。 アプリケーション機能配置、ソフトウェア、インフラ構成、ネットワーク構成について概要を示すこと。
6 日本のコーポレート・ガバナンス 2008年度「企業論」 川端 望.
急成長する中国ソフトウェア産業 中国ソフトウェアと情報サービス産業の規模 総売上高は5年間で約5.3倍の成長
米国ユタ州LDS病院胸部心臓外科フェローの経験
公益社団法人日本青年会議所 関東地区埼玉ブロック協議会 JCの情熱(おもい)育成委員会 2011年度第1回全体委員会
次世代大学教育研究会のこれまでの活動 2005年度次世代大学教育研究大会 明治大学駿河台校舎リバティタワー9階1096教室
子どもの本の情報 大阪府内の協力書店の情報 こちらをクリック 大阪府内の公立図書館・図書室の情報
第2回産業調査 小島浩道.
〈起点〉を示す格助詞「を」と「から」の選択について
広東省民弁本科高校日語専業骨幹教師研修会 ①日本語の格助詞の使い分け ②動詞の自他受身の選択について   -日本語教育と中日カルチャーショックの観点から- 名古屋大学 杉村 泰.
■5Ahバッテリー使用報告 事例紹介/東【その1】 ■iphon4S(晴れの昼間/AM8-PM3) ◆約1時間で68%⇒100%
『ワタシが!!』『地域の仲間で!!』 市民が始める自然エネルギー!!
ポイントカードの未来形を形にした「MUJI Passport」
SAP NetWeaver を支える Microsoft テクノロジーの全貌 (Appendix)
ガイダンス(内業) 測量学実習 第1回.
Python超入門 久保 幹雄 東京海洋大学.
熱力学の基礎 丸山 茂夫 東京大学大学院 工学系研究科 機械工学専攻
京都民医連中央病院 CHDF学習推進委員会
資料2-④ ④下水道.
Accessによる SQLの操作 ~実際にテーブルを操作してみよう!~.
Presentation transcript:

圧縮を用いた類似度判定 のための計算実験 谷研究室 新井 秀 森田 岳史

目次 はじめに 類似度の判定方法 圧縮アルゴリズム 実験 今後の課題

目次 はじめに 類似度の判定方法 圧縮アルゴリズム 実験 今後の課題

類似度判定とは? 2つの対象が相互に 似ているか、似ていないか判定すること 図1ヒト 図2 サル 例えば・・ 似ている? 図2 サル 例えば・・ 似ている? ※図1  http://ja.wikipedia.org/wiki/%E7%94%BB%E5%83%8F:Human.svg ※図2   http://ja.wikipedia.org/wiki/%E7%94%BB%E5%83%8F:Jigokudani_hotspring_in_Nagano_Japan_001.jpg

類似度判定 Ming Liらが、対象を選ばず 機械的に行える類似度判定法を提案! 専門的な知識が必要。 方言などの場合、専門家の知識・経験に頼るとこ ろがある。 Ming Liらが、対象を選ばず 機械的に行える類似度判定法を提案!

Ming Liらが提案 した類似度の特徴 パラメータを特定しない 対象を選ばない(万能性) 前提や専門知識を必要としない 人の感情が介入しないため、新たな発見も する 場合もある

Ming Liらの提案 した類似度 Kolmogorov記述量 を利用 Kolmogorov記述量 は計算不可能 データを圧縮したサイズ によって代用!

事例1 ミトコンドリアDNAからの哺乳類進化系統樹自動生成 rudiらの論文より抜粋

事例2 ロシア小説の類似度による系統樹自動生成 rudiらの論文より抜粋

谷研究室での事例1 音楽の自動分類 三井氏の論文より抜粋

谷研究室での事例2 方言の自動分類 堀中氏らの論文より抜粋

本研究の目的 以前の類似度判定では、 圧縮率の高さからbzip2を採用 Kolmogorov記述量を代用する 圧縮ソフトについて どれが適したものか あまり考えてこなかった

本研究の目的 いくつかの圧縮ソフト を用いた計算実験を行う。 類似度を算出する際に 適した圧縮ソフトを 検証する。

目次 はじめに 類似度の判定方法 圧縮アルゴリズム 実験 今後の課題

Kolmogorov記述量とは 規則性を表す 指標

規則性・ランダム性 サイコロを5回振る 出た目 パターン1 同確率 確率では 測れない 1 1 1 1 1 パターン2 3 5 1 3 2

規則性・ランダム性 #include <stdio.h> #include <stdlib.h> int main(void) { int i; for(j=0;j<100;j++){ for (i = 0;i <100;i++) { printf("%d\n", (int)(rand()*100/(1+RAND_MAX)); } return 0; 84 39 78 79 91 19 33 76 27 55 47 62 36 51 95 91 63 71 14 60 1 24 13 80 15 40 12 10 99 21 51 83 61 29 63 52 49 97 29 77 52 76 40 89 28 35 80 91 6 94 52 8 19 66 89 34 6 2 45 6 23 97 90 85 26 53 37 76 51 66 53 3 43 93 93 72 28 73 63 35 68 16 44 88 82 33 22 89 35 68 95 58 65 85 43 92 39 81 68 91 ある疑似乱数生成プログラム で作られた1以上99以下の 整数 規則性があれば プログラムで短く 表現できる可能性がある プログラムやアルゴリズムも 規則表現の一つかもしれない

Kolmogorov記述量 あるプログラム言語でデータxを生成する最小の プログラムサイズのこと。K(x)と表す。 データの規則性やランダム性などのデータに含 まれる情報量をデータを作る      プログラム サイズで評価する方法。 Kolmogorov記述量は圧縮の限界。

Kolmogorov記述量 あるプログラム言語でデータを生成する最小の プログラムサイズのこと。K(x)と表す。 データの規則性やランダム性などのデータに含 まれる情報量をデータを作る      プログラム サイズで評価する方法。 Kolmogorov記述量は圧縮の限界。

なぜ圧縮の限界? 圧縮はKolmogorov記述量の 近似! 圧縮 xの圧縮ファイル データx 解凍 解凍プログラム データx

条件付Kolmogorov記述量とは? 補助情報yを利用したKolmogorov記述量。K(x|y)とあらわす。 いちからデータx を作ると必然と Kolmogorov記述量 は大きい。 補助情報 を使うと Kolmogorov 記述量は 小さくなる データx 補助情報 データy

𝑥に含まれる𝑦の情報量 𝐼(𝑥:𝑦) 𝐼𝑦:𝑥=𝐾𝑥−𝐾(𝑥|𝑦) 𝐼𝑥:𝑦≒𝐼𝑦:𝑥であることが知られている

正規化する Xの中にyの情報が これだけ入ってる とみなす ことも出来る I(x:y) 𝑥に含まれる𝑦の情報量 𝐼(𝑥:𝑦)=𝐾𝑥−𝐾𝑥|𝑦 𝐾𝑥 I(x:y) 𝐾𝑥|𝑦 正規化する Xの中にyの情報が これだけ入ってる とみなす ことも出来る

NID (Normalized Information Distance) この値が 類似度 となる!! Ming Liらの研究では、情報に関する距離を正規化した。 その距離をNIDと呼ぶ。 𝐾を𝐾𝑜𝑙𝑚𝑜𝑔𝑜𝑟𝑜𝑣記述量、𝐾𝑥|𝑦を補助情報つき𝐾𝑜𝑙𝑚𝑜𝑔𝑜𝑟𝑜𝑣記述量 として任意のデータ𝑥,𝑦について、𝑥,𝑦間の情報に関する距離 𝑁𝐼𝐷は以下と提案される。 𝑁𝐼𝐷𝑥,𝑦= 𝑚𝑎𝑥{𝐾𝑥|𝑦,𝐾𝑦|𝑥} 𝑚𝑎𝑥{𝐾𝑥,𝐾𝑦}

NID (Normalized Information Distance) 2つのデータ間の距離 パラメーターを特定しない 対象を選ばない(万能性) Kolmogorov記述量は帰納的でない        数学的に定義できるが、有限の時間で計算でき ると限らない 実用的な圧縮した サイズで代用する

NCD (Normalized Compression Distance) 𝑁𝐼𝐷𝑥,𝑦= 𝑚𝑎𝑥{𝐾𝑥|𝑦,𝐾𝑦|𝑥} 𝑚𝑎𝑥{𝐾𝑥,𝐾𝑦} 𝑁𝐶𝐷𝑥,𝑦= 𝐶𝑥𝑦−𝑚𝑖𝑛{𝐶𝑥,𝐶𝑦} 𝑚𝑎𝑥{𝐶𝑥,𝐶𝑦} 𝑥𝑦を𝑥とyの連接とする 𝑥,𝑦:あるデータ 𝐶:ある圧縮アルゴリズム 𝐶(𝑥):𝑥を圧縮した後のサイズ

Normal Compressor NCDで用いる。圧縮ソフトは万能性を保つためいくつかの制約がある。以下の定義を満たしていること望ましい。 𝐶𝜆=0⇔𝜆が空のファイル 𝐶𝑥𝑥=𝐶𝑥 𝐶𝑥𝑦≥𝐶𝑥 𝐶𝑦𝑥=𝐶𝑥𝑦 𝐶𝑥𝑦≤𝐶𝑥𝐶𝑦 𝐶𝑥𝑦𝐶𝑧≤𝐶𝑥𝑧𝐶𝑦𝑧 ファイルxと ファイルyを 連接させたモノ と その逆をして、 圧縮した結果は ファイルサイズが 等しい。 あるファイルx を2つ連続させて 圧縮させた場合 とファイルxを 圧縮した場合の ファイルサイズ は等しい 空のファイル を 圧縮した場合 ファイルサイズ は0になる。 𝑥,𝑦,𝑧:あるファイル 𝐶:ある圧縮ソフト 𝐶𝑥:ファイル𝑥を圧縮した後のサイズ 𝑥𝑦:𝑥と𝑦の連接 𝑂 log 𝑛 の差は無視𝑛:最長の文字列

NCD (Normalized Compression Distance) 類似度が高いとき 𝑁𝐶𝐷𝑥,𝑦= 𝐶𝑥𝑦−𝑚𝑖𝑛{𝐶𝑥,𝐶𝑦} 𝑚𝑎𝑥{𝐶𝑥,𝐶𝑦} = 𝐶𝑥𝑥−𝐶𝑥 𝐶𝑥 (𝑥≒𝑦) =0

NCD (Normalized Compression Distance) 類似度が低いとき 𝑁𝐶𝐷𝑥,𝑦= 𝐶𝑥𝑦−𝑚𝑖𝑛{𝐶𝑥,𝐶𝑦} 𝑚𝑎𝑥{𝐶𝑥,𝐶𝑦} = 𝐶𝑥𝐶𝑦−𝐶𝑥 𝐶𝑦 =1

NCD (Normalized Compression Distance) 2つのデータ間の距離 パラメーターを特定しない 対象を選ばない(万能性) 実験が 容易に出来る!

目次 はじめに 類似度の判定方法 圧縮 実験 今後の課題

圧縮とは? 音声や文章などのデータを より小さな量のデータに 変換する処理のこと。

圧縮のしくみ なぜ圧縮が出来るのか →データにはパターンや無駄が存在し、その無 駄を省くことによってデータ量を小さく できる。

圧縮のしくみ ランレングス符号化

ランレングス符号化 入力データ 1 1 1 1 1 1 1 1 2 2 2 圧縮データ 4 1 1 1 2 1 4 1 1 1 3 1 2 1

圧縮ソフト いくつかのアルゴリズム 組み合わせる 例えば…bzip2 ブロックソート法 Move-to-Front法 ハフマン符号化

bzip2 1996年にジュリアン・セワード (Julian Seward) に より開発。 gzipやZIPより高い圧縮率を誇っている ブロックソート法、Move-To-Front法、ハフマン 符号化法を組み合わせた圧縮アルゴリズム。 Wikipedia(http://ja.wikipedia.org/wiki/Bzip2) より

bzip2 1996年にジュリアン・セワード (Julian Seward) に より開発。 gzipやZIPより高い圧縮率を誇っている ブロックソート法、Move-To-Front法、ハフマン 符号化法を組み合わせた圧縮アルゴリズム。 Wikipedia(http://ja.wikipedia.org/wiki/Bzip2) より

ブロックソート法 圧縮アルゴリズムの前処理 文字が偏り(同じ文字が連続)やすくなるため、圧 縮の効率がよくなる

入力:Eababadb 入力された文字を 全ての文字列を ローテーションする ソートする。 E a b a b a d b a b a b

出力 Ebbaadab “0” 入力:Eababadb ソートした後の 文字列の末尾の 文字列を出力。 a b a b a d b E a

gzip GNU ZIPの略。gzipコマンドにより用いられる LZ77符号化とハフマン符号化を組み合わせて 圧縮 拡張子は「.gz」とする 辞書式の圧縮方法 Wikipedia(http://ja.wikipedia.org/wiki/Gzip) より

gzip GNU ZIPの略。gzipコマンドにより用いられる LZ77符号化とハフマン符号化を組み合わせて 圧縮 拡張子は「.gz」とする 辞書式の圧縮方法 Wikipedia(http://ja.wikipedia.org/wiki/Gzip) より

1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ

1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 1 2 3 空の辞書を 用意

一文字 読み込む 処理したいデータ 1 2 3 4 5 6 7 8 A B A A A B A B C 辞書 処理するデータパターン 1 2 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 1 2 3 A 一文字 読み込む

辞書にないとき 0,0,'データ'を 出力 処理したいデータ 0,0 'A' 1 2 3 4 5 6 7 8 A B A A A B A B 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 辞書にないとき 0,0,'データ'を 出力

処理した データパターン を追加 処理したいデータ 0,0 'A' 1 2 3 4 5 6 7 8 A B A A A B A B C 辞書 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 1 2 3 A 処理した データパターン を追加

処理したいデータ 0,0 'A' 0,0 'B' 1 2 3 4 5 6 7 8 A B A A A B A B C 辞書 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 1 2 3 0,0 'B' A B

処理したいデータ 0,0 'A' 0,0 'B' 1 2 3 4 5 6 7 8 A B A A A B A B C 辞書 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 1 2 3 A B 0,0 'B' 1 2 3 A B

読み込んだ データパターンが 辞書に存在! 処理したいデータ 0,0 'A' 0,0 'B' 1 2 3 4 5 6 7 8 A B A A 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 1 2 3 B 0,0 'B' A 1 2 3 A B A A 読み込んだ データパターンが 辞書に存在!

辞書の一致したポインタ 一致したパターンの長さ 一致しなくなったときの文字を出力 処理したいデータ 0,0 'A' 0,0 'B' 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書の一致したポインタ 一致したパターンの長さ 一致しなくなったときの文字を出力 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 1 2 3 A B 0,0 'B' 1 2 3 A B A A 2,1 'A'

処理したいデータ 0,0 'A' 0,0 'B' 2,1 'A' 1 2 3 4 5 6 7 8 A B A A A B A B C 辞書 1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 1 2 3 B 0,0 'B' A 1 2 3 A B A A 2,1 'A' 1 2 3 A B A A

1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 1 2 3 0,0 'B' A B 1 2 3 A B A A 2,1 'A' 1 2 3 A B A A A B A B 0,3 'B'

1 2 3 4 5 6 7 8 A B A A A B A B C 処理したいデータ 辞書 処理するデータパターン 出力値 1 2 3 A 0,0 'A' 1 2 3 A B 0,0 'B' 1 2 3 A B A A 2,1 'A' 1 2 3 A B A A A B A B 0,3 'B' 1 2 3 0,0 'C' A B A B C

目次 はじめに 類似度の判定方法 圧縮 実験 今後の課題

実験1 (Normal Compressorの適合度実験) Bzip2 gzip 方言桃太郎のひらがなテキストファイル 前処理後のファイル

Normal Compressor NCDで用いる。圧縮ソフトは万能性を保つためいくつかの制約がある。以下の定義を満たしていること望ましい。 𝐶𝜆=0⇔𝜆が空のファイル 𝐶𝑥𝑥=𝐶𝑥 𝐶𝑥𝑦≥𝐶𝑥 𝐶𝑦𝑥=𝐶𝑥𝑦 𝐶𝑥𝑦≤𝐶𝑥𝐶𝑦 𝐶𝑥𝑦𝐶𝑧≤𝐶𝑥𝑧𝐶𝑦𝑧 𝑥,𝑦,𝑧:あるファイル 𝐶:ある圧縮ソフト 𝐶𝑥:ファイル𝑥を圧縮した後のサイズ 𝑥𝑦:𝑥と𝑦の連接

方言桃太郎ひらがな テキストファイル 値は全て平均 単位:byte C(x)=C(xx) bzip2 231.982 : 280.785 gzip 282.178 : 300.464 C(xy)>=C(x) bzip2 370.133928571429 : 231.982 gzip 467.472077922078 : 282.690 C(xy)=C(yx) bzip2 371.758 : 371.758 gzip 467.472 : 467.567 C(xy)<=C(x)+C(y) bzip2 370.133 : 232.34+231.61 gzip 467.472 : 282.69+281.66 C(xy)=C(yx) bzip2 370.714 + 232 : 385.60+385.14 gzip 444.7+282.266 : 458.33+461.03 値は全て平均 単位:byte

方言桃太郎前処理後ファイル 値は全て平均 単位:byte C(x)=C(xx) bzip2 202.839 : 243.57 gzip 188.696 : 200.5 C(xy)>=C(x) bzip2 342.12 : 203.650 gzip 316.86 : 189.246 C(xy)=C(yx) bzip2 342.125 : 342.125 gzip 316.863 : 316.676 C(xy)<=C(x)+C(y) bzip2 342.125 : 203.650 + 202.027 gzip 316.863 : 189.246 + 188.146 C(xy)=C(yx) bzip2 334.3 +196.6 : 333.03 +338.53 gzip 315.6 +192.8 : 308.66 +314.3 値は全て平均 単位:byte

実験1考察 bzip2はC(xy)=C(yx)を完全に満たす。よって bzip2は対称性が存在する。

C(xy)=C(yx)が 正確に成り立つ! bzip2内でブロックソート 文字列を全体を疑似的にソート 入力:Eababadb 入力された文字を ローテーションする 全ての文字列を ソートする。 文字列を全体を疑似的にソート a b a d b E a b b a d b E a b a a d b E a b a b d b E a b a b a b E a b a b a d

実験1考察 bzip2はC(xy)=C(yx)を完全に満たす。よって bzip2は対称性が存在する。 gzipはC(xx)=C(x)が精度が高い

gzip 辞書式 C(xx)=C(x)の精度が高い C(x) : C(xx) : 文字列xx : 文字列X 文字列X xの情報がある 辞書の中 C(x) : C(xx) : C(x)

実験1考察 bzip2はC(xy)=C(yx)を完全に満たす。よって bzip2は対称性が存在する。 bzip2はC(xx)=C(x)において、大きな誤差を生 ずる。 bzip2はひらがなファイルにおいて、圧縮率が高 く。gzipは前処理後のファイルにおいて圧縮率が 高い

実験2 gzipの辞書の限界 gzipは辞書式の圧縮ソフト NCD(x,x)=0が高い精度で成り立つ 𝑁𝐶𝐷𝑥,𝑥= 𝐶𝑥𝑥−𝐶𝑥 𝐶𝑥 =0 参考:manuel cebrian氏の論文参考

NCD(x,x)=0が成り立たなくなるのでは? 実験2 gzipの辞書の限界 Xのファイルサイズが大きくなると NCD(x,x)=0が成り立たなくなるのでは? 参考:manuel cebrian氏の論文参考

実験2 gzipの辞書の限界 40Kbyteのランダム文字列 ファイルを400byteずつ読み込み、 そのつど、NCD(x,x)を計算。 参考:manuel cebrian氏の論文参考

実験2考察 Gzipの辞書サイズはグラフよりおおよそ、 30Kbyte前後。あまり大きいファイルの類似度を はかる場合は適さない。

目次 はじめに 類似度の測定方法 圧縮 実験 今後の課題

今後の課題 bzip2、gzipがどちらが類似度判定 にふさわしい圧縮か実験によりさらに 調べていく。 ppmzという高圧縮アルゴリズムが存在 するらしい。調べてみる必要がある。

LZ77法(スライド辞書)

スライド辞書へのデータの追加 元の辞書データ 追加後の 辞書データ 先頭のデータを消去して 追加分を末尾に加える 1 2 3 4 A B C 1 2 3 4 A B C D E 追加 F G 元の辞書データ 1 2 3 4 追加後の 辞書データ C D E F G 先頭のデータを消去して 追加分を末尾に加える

スライド辞書による符号化 (A)辞書データ (B)符号化する データパターン 1 2 3 4 5 6 7 8 A B C D E F G H 1 2 3 4 5 6 7 8 A B C D E F G H I (A)辞書データ (B)符号化する データパターン コード値 B B C D E 1,4 1番目から4つが一致する

4,4'X' LZ77符号化での出力 辞書データ 符号化する データパターン 一致するデータパターン 1 2 3 4 5 6 7 8 A B 1 2 3 4 5 6 7 8 A B C D E F G H I 辞書データ 符号化する データパターン E F G H X コード値 “4,4” 次に続く1データは そのまま出力 出力 4,4'X'

Distance 距離空間とは・・・任意の2点間で距離が定められた空 間のこと。 距離空間とは・・・任意の2点間で距離が定められた空 間のこと。 ある集合𝑋上の距離とは、実数値関数𝑑:𝑋×𝑋→𝑅 で任意の𝑥,𝑦,𝑧∈𝑋に対して次のような性質を満たす。 𝑑𝑥,𝑦≥0 𝑑𝑥,𝑦=0⇔𝑥=𝑦 𝑑𝑥,𝑦=𝑑𝑦,𝑥:対称性 𝑑𝑥,𝑦≤𝑑𝑥,𝑧𝑑𝑧,𝑦:三角不等式

Kolmogorov記述量 データ𝑥を生成するプログラム言語を𝑆とすると、 𝑆によるデータ𝑥の𝐾𝑜𝑙𝑚𝑜𝑔𝑜𝑟𝑜𝑣記述量 𝐾 𝑠 𝑥を 以下と定義する。 𝐾 𝑠 𝑥=𝑚𝑖𝑛 |𝑝|:𝑆𝑝=𝑥

Admissible Distance 類似度の距離について、密度条件を満たすものだけを考えるという提案がなされている。条件を満たした距離のことを Admissible Distance(適切な距離)という。 𝛺を有限の文字列として,非負実数への距離関数 𝐷:𝛺×𝛺→𝑅が“𝑎𝑑𝑚𝑖𝑠𝑠𝑖𝑏𝑙𝑒𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒” であるとは、ある𝑥∈𝛺と任意の𝑦∈𝛺に対して, 次のような密度条件を満たすとき. 𝑦 2 −𝐷𝑥,𝑦 ≦1