作者
Fredrik Svahn <Fredrik(dot)Svahn(at)gmail>
狀態
最終版/R-34 已被 EEP-11 和 EEP-31 取代,除了 `binary_string`,它是新的 `string` 實作的一部分
類型
標準追蹤
建立時間
2007-12-28
Erlang 版本
OTP_R12B-2

EEP 9:用於處理二進位的函式庫 #

摘要 #

此 EEP 建議新增兩個二進位輔助函式庫,其中包含用於時間關鍵活動(例如搜尋和分割 Erlang 二進位)的內建函式,以及用於二進位常見操作的函式庫函式。此 EEP 也建議新增使用內建函式的正規表示式函式庫。

理由 #

對於列表資料類型,有一個輔助函式庫提供用於常見操作(例如搜尋和分割列表)的函式。此 EEP 建議應為二進位建立類似的函式庫函式集。許多建議的函式都是基於在 erlang-questions 郵件清單上關於二進位的問題的答案,例如「如何將數字轉換為二進位?」

動機 #

由於二進位通常用於對大量資料進行時間關鍵的活動,因此建議將二進位的一些操作實作為內建函式 (BIF)。

具體而言,社群似乎對有效率的正規表示式實作以搜尋二進位有很大的興趣。此外,為了在搜尋和分割二進位時獲得最大效能,建議使用高效能函式來補充正規表示式搜尋函式,以便進行簡單的搜尋,例如定位和分割換行符號的二進位。測試表明,例如,Boyer-Moore 演算法對於此類目的可能比正規表示式演算法快得多。

在審閱 EEP 時,很明顯對二進位進行字串操作以獲得更好的效能也有強烈的需求。

單獨發送給 OTP 團隊的參考實作指示了與當前用於搜尋列表的正規表示式模組相比,預期的效能提升。一些結果可在本 EEP 的末尾找到。

建議的變更 #

此 EEP 建議新增兩個新模組;一個名為 binary 的模組和一個名為 binary_string 的模組。

此 EEP 也建議使用基於 Perl 相容正規表示式 (PCRE) 的新正規表示式函式庫。該函式庫應能夠在 binary_strings 和字串上操作。

最後,應將以下函式新增至 erlang 模組

binary_to_atom(Binary) -> Atom
atom_to_binary(Atom) -> Binary
binary_to_existing_atom(Binary) -> Atom

未包含 #

目前,以下內容未包含在 EEP 中

  • 支援不同的編碼,例如 UTF-8
  • 對字串模組的變更

「binary_string」模組 #

binary_string 模組應以目前的字串模組為基礎,但應在由二進位表示的字串上操作,而不是目前在由列表表示的字串上操作的字串模組。

除了在二進位上操作外,binary_string 的介面應與字串相同,但有以下例外

  1. 應修改 str/2 和 rstr/2,以選擇性地接收二進位列表或 MatchSpec,例如 binary:match_compile/2 所傳回的 MatchSpec 作為第二個引數。如果 Keys 引數對應到多個鍵,則該函式應傳回一個元組,指示匹配的鍵和匹配的索引,即

     str(Binary, Keys) -> Return
     rstr(Binary, Keys) -> Return
    
       Binary = binary()
       Keys = Key | [ Key ] | MatchSpec
       Key = string() | binary()
       MatchSpec = tuple() as returned by binary:match_compile/1
       Return = Index | {NeedleNumber, Index}
       Index = integer()
    

    應使用高效的演算法(例如 Boyer-Moore、Aho-Corasick 或類似演算法)將 str/rstr 實作為內建函式。通常,該函式可以在 binary:match/2 的基礎上建立。

  2. 應新增新的 split 函式。它的行為應與 tokens/2 相同,但應接收分隔符號二進位/字串列表,而不是分隔符號字元列表。

     split(Binary, SplitKeys) -> List
    
       Binary = binary()
       SplitKeys = Key | [ Key ] | MatchSpec
       Key = string() | binary()
       MatchSpec = tuple() as returned by binary:match_compile/1
       List = [ binary() ]
    

    根據 SplitKeys 二進位中指定的模式,將二進位分割為二進位列表。

    範例

     > binary_string:split(<<"cat and dog">>, <<"and">>).
     [<<"cat ">>, <<" dog">>]
    
     > binary_string:split(<<"cat and dog">>, "and").
     [<<"cat ">>, <<" dog">>]
    
     > binary_string:split(<<"cat and dog">>,["a","n",<<"d">>]).
     [<<"c">>,<<"t ">>,<<" ">>,<<"og">>]
    

    產生的列表應與 regexp:split/2 的列表相同(明顯例外的是「*」、「.」、「^」等特殊字元)。

    請注意,第三個範例應產生與 binary_string:tokens(«“cat and dog”», “and”) 相同的結果。

  3. 應新增新的 substitute 和 globally_substitute 函式。

    3.1. substitute/3

     substitute(OldBinary, Key, Replacement)-> NewBinary
    
       OldBinary, NewBinary, Replacement = binary()
       Keys = binary() | [ binary() ] | MatchSpec
       MatchSpec = tuple() as returned by binary:match_compile/1
    

    透過以 Replacement 二進位替換 OldBinary 中 Keys 中的任何二進位第一次出現的位置,從 OldBinary 建立 NewBinary 二進位。

    Replacement 二進位的大小不必與匹配的鍵相同。

    範例

       > binary_string:substitute(<<"cat anf dog">>,<<"anf">>,<<"and">>).
       [<<"cat and dog">>]
    

    3.2. globally_substitute/3

     globally_substitute(OldBinary, Key, Replacement)-> NewBinary
    
       OldBinary, NewBinary, Replacement = binary()
       Keys = binary() | [ binary() ] | MatchSpec
       MatchSpec = tuple() as returned by binary:match_compile/1
    

    與 substitute 相同,只是 OldBinary 中子二進位的所有非重疊出現位置都將被 Replacement 二進位取代。

建議將相同的函式也新增到字串模組,但這超出本 EEP 的範圍。

「binary」模組 #

binary 模組的介面應具有以下匯出函式(請注意,由於相信某些函式對於字串和二進位資料操作都很有用,因此某些函式刻意與 binary_string 中的函式相同)

match(Binary, Keys) -> Return
match(Binary, Keys, {StartIndex, EndIndex}) -> Return

  Binary = binary()
  Keys = binary() | [ binary() ] | MatchSpec
  MatchSpec = tuple() as returned by binary:match_compile/1
  StartIndex = EndIndex = integer()

  Return = Index | {KeyNumber, Index}
  Index = KeyNumber = integer()

傳回 Keys 中第一個匹配的二進位在 Binary 中第一次出現的位置,如果沒有匹配則傳回 0。如果給定鍵列表,則該函式將傳回一個元組,其中包含匹配鍵的 KeyNumber 和在 Binary 中找到它的位置。

有人討論過該函式是否應傳回匹配的 Key,而不是 KeyNumber。傳回 KeyNumber 應該稍微有效率,並且由於如果需要,可以透過 lists:nth(KeyNumber, Keys) 輕鬆擷取匹配的鍵,因此建議該函式傳回 KeyNumber。

Binary 從 StartIndex 搜尋到 EndIndex。如果未指定 StartIndex 和 EndIndex,則預設是從頭到尾搜尋 Binary。

範例

> binary:match(<<1,2,3,0,0,0,4>>, <<0,0,0>>).
4

> binary:match(<<1,2,255,0,0,0,4,255>>, [<<0,0,0>>, <<255>>]).
{2, 3}

實作建議:應使用例如 Boyer-Moore、Aho-Corasick 或類似的高效演算法實作為一個或多個 BIF。

matches(Binary, Keys) -> Return
matches(Binary, Keys, {StartIndex, EndIndex}) -> Return

  Binary = binary()
  Keys = binary() | [ binary() ] | MatchSpec
  MatchSpec = tuple() as returned by binary:match_compile/1
  StartIndex = EndIndex = integer()

  Return = [ Index ] | [ {KeyNumber, Index} ]
  Index = KeyNumber = integer()

在 Haystack 中尋找 Keys 的所有匹配項。傳回所有鍵的非重疊出現位置的索引列表。

split(Binary, SplitKeys) -> List
split(Binary, SplitKeys, {StartIndex, EndIndex}) -> List

  Binary = binary()
  SplitKeys = binary() | [ binary() ] | MatchSpec
  MatchSpec = tuple() as returned by binary:match_compile/1
  StartIndex = EndIndex = integer()

  List = [ binary() ]

根據 SplitKeys 中指定的模式,將二進位分割為二進位列表。

範例

> binary:split(<<1,255,4,0,0,0,2,3>>, <<0,0,0>>).
[<<1,255,4>>, <<2,3>>]

> binary:split(<<0,1,0,0,4,255,255,9>>, [<<0,0>>, <<255,255>>]).
[<<0,1>>,<<4>>,<<9>>]

產生的列表基本上應與 regexp:split/2 的列表相同(明顯例外的是「*」、「.」、「^」等特殊字元)。

List 中的二進位都是 Binary 的子二進位,表示 Binary 中的資料實際上不會複製到新的二進位。

substitute(OldBinary, Key, Replacement)-> NewBinary

  OldBinary, NewBinary, Replacement = binary()
  Keys = binary() | [ binary() ] | MatchSpec
  MatchSpec = tuple() as returned by binary:match_compile/1

透過以 Replacement 二進位替換 OldBinary 中 Keys 中的任何二進位第一次出現的位置,從 OldBinary 建立 NewBinary 二進位。

Replacement 二進位的大小不必與匹配的鍵相同。

globally_substitute(OldBinary, Key, Replacement)-> NewBinary

  OldBinary, NewBinary, Replacement = binary()
  Keys = binary() | [ binary() ] | MatchSpec
  MatchSpec = tuple() as returned by binary:match_compile/1

與 substitute 相同,只是 OldBinary 中子二進位的所有非重疊出現位置都將被 Replacement 二進位取代。

match_compile(Keys) -> MatchSpec

  Keys = binary() | [ binary() ]
  MatchSpec = tuple()

建構一個內部結構,表示一個或多個搜尋鍵。如果使用相同的搜尋關鍵字執行 binary:match/2 或 binary_string:str/2 的多次搜尋,則可以使用 MatchSpec 結構來加速搜尋。

binary:from_unsigned(Integer)-> Binary
binary:to_unsigned(Binary)-> Integer

將正整數轉換為二進位資料類型格式中最小的可能表示形式,反之亦然。

範例

> binary:from_unsigned(11111111).
<<169,138,199>>

> binary:to_unsigned(<<169,138,199>>).
11111111

first(Binary1)-> Binary2
first(SizeBytes, Binary1)-> Binary2

傳回 Binary1 中第一個位元組或 SizeBytes 個位元組的子二進位。

範例

> binary:first(2, <<"abc">>).
<<"ab">>

last(Binary1)-> Binary2.
last(SizeBytes, Binary1)-> Binary2

傳回 Binary1 中最後一個位元組或 SizeBytes 個位元組的子二進位。

範例

> binary:last(2, <<"abc">>).
<<"bc">>

nth(N, Binary) -> Value

  N = integer(), 1 =< N =< size(Binary)
  Value = integer()

從 Binary 中位置 N 擷取位元組。與

T = N-1,
<<_:T/binary, Value:Size/binary, _/binary>> = Binary,
Value.

雖然此函式較短且易於撰寫。

extract(N, Size, Binary) -> SubBinary

  N = integer(), 1 =< N =< size(Binary)
  Size = integer()
  SubBinary = subbinary()

從 Binary 的位置 N 開始,傳回大小為 Size 的子二進位。此操作中不會複製任何資料。

有人討論過是否應該有一個函式來複製二進位的一部分,而不是取得子二進位。這會讓您可以取得二進位的一小部分,並讓其餘部分進行垃圾收集。由於可以透過將擷取的部分轉換為列表,然後再轉換回二進位來達到相同的結果,而且這是一個非常特殊的操作,可能會讓新使用者感到困惑,因此在此階段已將其排除。

與設計人員交談時,許多人似乎更喜歡此函式的名稱 extract 而不是 subbinary。

duplicate(N, Byte)-> Binary

lists:duplicate/2 類似。建立一個由重複 N 次的 Byte 組成的新二進位。

範例

> binary:duplicate(5, $a).
<<"aaaaa">>

正規表示式函式庫 #

建議新增基於內建函式的新正規表示式函式庫。它應具有以下介面函式(要決定的模組名稱,出於向後相容性的原因,它可能應該與舊的 regexp 模組平行存在)

在第一輪回饋中,有人建議最終的實作應是基於 Perl 相容正規表示式 (PCRE) 函式庫的內建函式。它經過最佳化、支援良好,並且或多或少被視為今天的標準。它在許多著名的產品和專案中使用,例如 Apple 的 Safari、Apache、KDE、PHP、Postfix 和 Nmap。

建議模組具有以下匯出函式

compile(Regex) -> MatchSpec

  Regex = string()
  MatchSpec = tuple()

建構一個內部結構,表示一個或多個搜尋鍵。如果要使用相同的搜尋關鍵字執行多次搜尋,則可以使用 MatchSpec 結構來加速搜尋。

match(BinOrString, RegExp)-> Return
match(BinOrString, RegExp, {StartIndex, EndIndex})-> Return

  BinOrString = binary() | string()
  RegExp = string() | MatchSpec
  MatchSpec = tuple() as returned by match_compile/1
  StartIndex = EndIndex = integer()
  Return = 0 | {Start, Length, [CapturedPatterns]}

在 BinOrString 中尋找正規表示式 RegExp 的第一個最長匹配項。此函式會搜尋最長的可能匹配項,如果存在多個相同長度的表示式,則傳回找到的第一個表示式。

該函式支援模式擷取。擷取的模式(如果有的話)將在 Return 元組中的列表中傳回。

範例

> binary:regex_match(<<"abcde">>, "b?cd").
{2,3,[]}

> binary:regex_match(<<"127.0.0.1">>, "(\d*)\.(\d*)\.").
{1,6,[<<"127">>, <<"0">>]}

開放問題

  • 新增 Options 參數(當然是可選的)可能是個好主意,例如,指定應啟用部分匹配功能
  • 編碼的處理。

    matches(BinOrString, RegExp)-> Replacementeturn matches(BinOrString, RegExp, {StartIndex, EndIndex})-> Return

    BinOrString = binary() | string()
    RegExp = string() | MatchSpec
    MatchSpec = tuple() as returned by match_compile/1
    StartIndex = EndIndex = integer()
    
    Return = 0 | [ {Start, Length, [CapturedPatterns]} ]
    

在 BinOrString 中尋找正規表示式 RegExp 的所有匹配項。

範例

> binary:regex_matches(<<"aaa">>, "a").
[{1,1,[]},{2,1,[]},{3,1,[]}]
sub(BinOrString, RegExp, Replacement)-> NewStringOrBinary

  BinOrString = NewStringOrBinary = binary() | string()
  RegExp = string() | MatchSpec
  MatchSpec = tuple() as returned by match_compile/1
  Replacement = string()

使用 Replacement 取代 BinOrString 中與 RegExp 匹配的子字串或子二進位的第一次出現位置。Replacement 字串中的 & 將被 BinOrString 的匹配子字串或子二進位取代。\& 將文字 & 放入取代字串或二進位中。NewStringOrBinary 的類型將與 BinOrString 的類型相同。

gsub(BinOrString, RegExp, Replacement)-> Binary2

與 sub 相同,只是 BinOrString 中與 RegExp 匹配的子字串或子二進位的所有非重疊出現位置都將被字串 Replacement 取代。

split(BinOrString, RegExp) -> List
split(BinOrString, RegExp, {StartIndex, EndIndex}) -> List

  BinOrString = binary() | string()
  RegExp = string() | MatchSpec
  MatchSpec = tuple() as returned by match_compile/1
  StartIndex = EndIndex = integer()

  List = [ binary() ]

根據 RegExp 中指定的模式,將二進位分割為二進位列表。

產生的列表基本上應與 regexp:split/2 的列表相同。

效能 #

使用參考實作測量了認為最重要的函式的效能。一些範例

  1. 在約 1 Mb 的二進位中搜尋不存在的 1 和 3 位元組二進位。請注意,由於 O(n/m) 演算法,binary:match/2 的速度會隨著搜尋目標越長而變得更快。所有時間均以微秒為單位。

         Search for:        1 byte   3 bytes
     ---------------------------------------
     binary:match/2:        17598      6045
     binary:regex_first/2:  47299     46701
     string:str/2:          68969     69637
     regexp:first_match/2: 460858    887485
    
  2. 在換行符號上分割約 1 Mb 的二進位。此特定二進位平均每 60 個字元包含一個換行符號。

     binary:split/2:  89142 microseconds
     regexp:split/2: 564911 microseconds
    
  3. 來自電腦語言對決的 Regex-DNA 基準測試

     prototype regexp bif:    1.9 seconds
     regexp module in R12B:  99.1 seconds
    

在電腦語言對決的範例中,與參考實作中的或其他演算法(特別是 TCL 中的演算法)相比,PCRE 的效能略低。這不一定表示這適用於所有類型的模式。

參考實作 #

已向 OTP 團隊提供參考實作。

著作權 #

本文檔根據創用 CC 授權條款授權。