中科院計算所智能安全(編輯修改稿)
2025-03-31 07:32 本頁面
【文章內(nèi)容簡介】 a Sets ?插入 1%的匹配數(shù)據(jù) ?正則表達(dá)式測試集（文中沒說明） 最好情況比較差 Deterministic and Robust Mapping ?主要目標(biāo) ? 同時執(zhí)行的自動機應(yīng)當(dāng)位于不同的內(nèi)存模塊中 避免內(nèi)存沖突 可以通過使內(nèi)存數(shù)目大于自動機個數(shù)來解決 ? default path中的狀態(tài)結(jié)點應(yīng)當(dāng)位于不同的內(nèi)存模塊中 避免 default path中所有狀態(tài)位于一個內(nèi)存模塊中 需要通過一定算法來解決的目標(biāo) ?問題形式化 ?問題可以 形式化成 graph coloring problem ?顏色代表內(nèi)存模塊， default path代表圖 問題轉(zhuǎn)化成：將圖中的結(jié)點涂顏色，使得每條從葉子到根結(jié)點的路 徑都涂上不同的顏色 maxmin algorithm – 介紹 ? 具體算法 ? 使用三個堆：樹堆、層次堆、顏色堆 ? 每次選樹堆中結(jié)點對多的一棵樹 ? 對數(shù)構(gòu)建層次堆（層數(shù)：每層的節(jié)點數(shù)） 選擇顏色堆中顏色使用數(shù)目的最多的顏色 分給層次堆中最少層的所有該層結(jié)點 更新顏色堆中該分配顏色的使用數(shù)目 直至所有層均分配顏色 ?直至所有樹均分配到顏色 即：每次選擇樹堆中最大的樹，在該樹中選層次堆中結(jié)點最少的一 層，配顏色堆中最多使用的顏色 maxmin algorithm 示例 ?缺陷 ?導(dǎo)致顏色不均勻 （下圖所示） Adaptive coloring algorithm ?主要思路 ?maxmin算法沒有考慮當(dāng)結(jié)點可以涂多種顏色選擇哪種顏色的情況 ?主要思想 ?對每個結(jié)點賦予全部的顏色集合 ?當(dāng)結(jié)點賦予某個顏色時，將其它顏色去除（僅余一種顏色） ?使用兩個變量 used 每種顏色使用的次數(shù) deproved 不能使用這種顏色的節(jié)點個數(shù)， 當(dāng)某一結(jié)點選定某一顏色，則其子結(jié)點均不能使用該顏色 ?選擇最長深度的節(jié)點 ?根據(jù)其默認(rèn)路徑逐一將路徑上的點涂顏色 顏色選 used中最小的并且 deprived中最大的 ?更新 used和 deproved變量。直至全部路徑都涂完顏色。 Adaptive coloring algorithm—示例 實驗結(jié)果 ?實驗數(shù)據(jù) ?測試數(shù)據(jù)同隨機測試 ?實驗結(jié)果 最好情況已較好 小結(jié) ? 提出新自動機表示方法 ? 用時間來換空間 ?平均減少 95%的 transition
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1