[發(fā)明專利]快速特征碼掃描

有效

• 申請?zhí)枺?/td>: 201410055830.4
• 申請日: 2008-10-20
• 公開（公告）號: CN103793522B
• 公開（公告）日: 2018-01-12
• 發(fā)明（設計）人: 王強
• 申請（專利權）人: 王英
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同恒源知識產(chǎn)權代理有限公司11275
• 代理人: 王維綺

技術領域

本發(fā)明涉及掃描字符串字段中的特征碼。

背景技術

數(shù)字內(nèi)容的物件（如文件，程序，網(wǎng)頁，電子郵件，互聯(lián)網(wǎng)數(shù)據(jù)包，或數(shù)字圖像）可以包含一個或多個字符串字段。一個字符串字段是一個通常代表文字或可執(zhí)行代碼的數(shù)據(jù)值串。例如，一個互聯(lián)網(wǎng)數(shù)據(jù)包可以包含網(wǎng)址，主機名，超文本傳輸協(xié)定(HTTP)報頭，超文本傳輸協(xié)定報文，電子郵件附件，電子郵件標題和電子郵件內(nèi)容。一個字符串字段的大小可從幾個字節(jié)到數(shù)百萬以上個字節(jié)。一個字符串特征碼可以是一串特定的完全指明的數(shù)據(jù)值或是特定的數(shù)據(jù)值的表達式（如特定的正則表達式），其目的是用來識別一個字符串物件（如特定的計算機病毒或特定的基因序列）。特征碼可以被存儲在一個征碼數(shù)據(jù)庫中。一個字征碼數(shù)據(jù)庫可以包含多個特征碼。一個字符串特征碼的大小可從幾個字節(jié)到幾千個字節(jié)。

字符串特征碼和字符串字段都是包含很多基本單元的比特字符串。一個基本單元是最小的有語義的單位，因此通常在特征碼掃描技術中作為掃描單元。一個基本單元的大小由應用而定。例如，英文字符串的基本單位通常是8比特位（即一個字節(jié)），而一個電腦病毒特征碼的基本單位通常是一個字節(jié)或半個字節(jié)。

每一個特征碼的基本單元可以被指定為等于或不等于某個特定值，或在某個特定范圍內(nèi)（如在數(shù)字范圍0至9內(nèi)或英文字母范圍a至z內(nèi)）。每個基本單元可以為不區(qū)分大小寫或區(qū)分大小寫。每個基本單元可以支持簡單的邏輯運算（如“非”）。此外，每個特征碼可以包括通配符，例如，“*”（一個不定長通配符）或“？”（一個定長通配符），其中“*”表示零個或任意多個任意基本單元和“？”表示一個任意基本單元。對于每一個不定長特征碼符號，可進一步指明其任意長度范圍。當一個特征碼包括不定長字符，特征碼的長度不定。如果一個特征碼不包括不定長字符，其長度是固定的。

一個典型的特征碼掃描過程可包括在一字符串字段內(nèi)的所有可能的位置上，比較所述字符串字段和特征碼數(shù)據(jù)庫中所對應的特征碼。掃描速度通常被特征碼的大小和復雜性限制。此外，掃描速度還受特征碼逐個更新的能力限制。

發(fā)明內(nèi)容

本發(fā)明實施例提供了在字符串字段上掃描特征碼的方法和系統(tǒng)。一般來說，本發(fā)明一個方面的實施例提供了字符串特征碼掃描方法，所述方法包括把一個或多個特征碼處理成一個或多個格式，所述格式包括每個定長特征碼或不定長特征碼的每個定長特征子碼的一個或多個指紋和一個或多個后續(xù)查找數(shù)據(jù)結構，所述一個或多個指紋包括特定定長特征碼或特征子碼的第J個指紋，所述第J個指紋的第一基本單元在所述特定定長特征碼或特征子碼中的在掃描方向上的位置除以特征碼掃描操作的步長的余數(shù)等于J，從而使得所述指紋的數(shù)目等于特征碼掃描的步長，并且使得所述特定定長特征碼或特征子碼在任何被掃描的字符串字段中的任何位置上都能被識別，其中每個所述指紋包括特定定長特征碼或特征子碼的一個或多個片段，所述一個或多個片段具有在所述特定定長特征碼或特征子碼中的任何地方的特定位置，接收一個由數(shù)據(jù)值組成的特定字符串字段，識別所述特定字符串字段所包括的任何特征碼，包括在每個以掃描步長為間距的位置上，掃描所述特定字符串字段，以查找一個或多個特征碼的一個或多個所述指紋，和在有一個或多個匹配的所述指紋的位置上，查找所述特定字符串字段，以查找一個或多個后續(xù)查找數(shù)據(jù)結構，和輸出所述特定字符串字段中的任何已識別的特征碼。本發(fā)明的所述方面的其它實施例包括所述方法所對應的系統(tǒng)，裝置，和計算機軟件產(chǎn)品。

這些和其它實施例可選地包括一個或多個以下特性。每個定長特征碼或特征子碼有多個指紋，和所述掃描包括在每個以掃描步長為間距的位置上，掃描所述字符串字段，以查找一個或多個特征碼的多個指紋，包括并行查找兩個或兩個以上指紋。特定特征碼的一個或多個指紋中的每個指紋在原空間或在被投影到一個或多個影子空間之后是完全指明的，所述影子空間是比所述原空間格式更廣的空間，所述影子空間通過引入一些模糊性到所述原空間，從而使得一個在特定影子空間的指紋影子對應于一個或多個在所述原空間的指紋。