hat trie下載 - hat trie原始碼下載

快速且記憶體高效的 HAT-trie 的 C++ 實現

基於「HAT-trie：一種基於快取的基於 Trie 的字串資料結構」的 Trie 實作。（Askitis Nikolas 和 Sinha Ranjan，2007 年）論文。目前，僅實現了純 HAT-trie，混合版本可能會稍後推出。有關 HAT-trie 資料結構的詳細資訊可以在此處找到。

該程式庫透過壓縮公共前綴提供了一種高效且緊湊的方式來儲存字串集或字串映射。它還允許搜尋與前綴匹配的鍵。請注意，雖然該結構的預設參數旨在優化精確搜索，但如果您進行大量前綴搜索，您可能希望透過burst_threshold方法降低突發閾值。

這是一個非常適合儲存大量字串的結構。

對於數組哈希部分，使用 array-hash 專案並將其包含在儲存庫中。

該函式庫提供了兩個類別： tsl::htrie_map和tsl::htrie_set 。

概述

僅標頭庫，只需將包含目錄新增至包含路徑即可開始使用。如果您使用 CMake，也可以使用 CMakeLists.txt 中匯出的tsl::hat_trie目標。
記憶體使用率低，同時保持合理的效能（請參閱基準測試）。
支援透過equal_prefix_range進行前綴搜尋（例如，對於自動完成很有用），並透過erase_prefix支援前綴擦除。
透過longest_prefix支援最長匹配前綴搜尋。
支援高效的序列化和反序列化（有關詳細信息，請參閱範例以及 API 中的serialize/deserialize方法）。
鍵沒有排序，因為它們部分儲存在哈希圖中。
所有修改資料結構的操作（插入、放置、擦除…）都會使迭代器失效。
支援鍵中的空字元（因此您可以在 trie 中儲存二進位資料）。
支援任何類型的值，只要它是可複製構造的，或者既可構造無拋出移動又可分配無拋出移動。
速度和記憶體使用之間的平衡可以透過max_load_factor方法修改。較低的最大負載因子將提高速度，較高的最大負載因子將減少記憶體使用量。其預設值設定為 8.0。
預設突發閾值（突發發生前數組哈希節點的最大大小）設定為 16 384，這為精確搜尋提供了良好的效能。如果您主要使用前綴搜索，您可能希望將其減少到 1024 或更低，以便透過burst_threshold方法更快地迭代結果。
預設情況下，密鑰允許的最大KeySizeT設定為 65 535。

線程安全和異常保證與 STL 容器類似。

哈希函數

此結構使用的預設雜湊函數取決於std::string_view的存在。如果可用，則使用std::hash<std::string_view> ，否則使用簡單的 FNV-1a 雜湊函數來避免任何依賴性。

如果您無法使用 C++17 或更高版本，我們建議將雜湊函數替換為 CityHash、MurmurHash、FarmHash 等，以獲得更好的效能。在我們所做的測試中，與 FNV-1a 相比，CityHash64 的讀取速度提高了約 20%。

# include < city.h >

struct str_hash {
    std:: size_t operator ()( const char * key, std:: size_t key_size) const {
        return CityHash64 (key, key_size);
    }
};

tsl::htrie_map< char , int , str_hash> map;

std::hash<std::string>無法有效使用，因為該結構不儲存任何std::string 。任何時候需要哈希時，都必須建立一個暫時的std::string 。

基準

維基百科資料集

基準測試包括將維基百科檔案主命名空間中的所有標題插入到資料結構中，檢查插入後使用的記憶體空間（包括潛在的記憶體碎片），並在資料結構中再次搜尋所有標題。插入過程中的峰值記憶體使用量也用 time(1) 來衡量。

資料集：enwiki-20170320-all-titles-in-ns0.gz
大小：262.7 MiB
鑰匙數量：13 099 148
平均密鑰長度：19.90
中位數密鑰長度：17
最大密鑰長度：251

每個標題都與一個 int（32 位元）相關聯。所有基於哈希的結構都使用 CityHash64 作為哈希函數。對於標有 Reserve 的測試，會提前調用reserve函數以避免任何重新哈希。

請注意， tsl::hopscotch_map 、 std::unordered_map 、 google::dense_hash_map和spp::sparse_hash_map使用std::string作為鍵，即使鍵只有一個字元長，它也強制規定最小大小為32 位元組（在x64上）。其他結構可能能夠儲存具有 1 位元組 + 8 位元組指標的單字元鍵（在 x64 上）。

此基準測試使用 GCC 6.3 編譯，並在配備 Intel i5-5200u 和 8Go RAM 的 Debian Stretch x64 上執行。採取了 20 次運行中的最佳成績。

基準測試的程式碼可以在 Gist 上找到。

未分類

enwiki-20170320-all-titles-in-ns0.gz資料集依字母順序排序。對於此基準測試，我們首先透過 shuf(1) 對資料集進行混洗，以避免出現偏差的排序資料集。

圖書館	資料結構	峰值內存 (MiB)	內存 (MiB)	插入（奈秒/鍵）	讀取（奈秒/鍵）
tsl::htrie_map	HAT特里樹	405.22	402.25	643.10	250.87
tsl::htrie_map 最大負載係數=4	HAT特里樹	471.85	468.50	638.66	212.90
tsl::htrie_map 最大負載係數=2	HAT特里樹	569.76	566.52	630.61	201.10
tsl::htrie_map 最大負載係數=1	HAT特里樹	713.44	709.81	645.76	190.87
雪松::達	雙數組 trie	1269.68	1254.41	1102.93	557.20
雪松::da ORDERED=false	雙數組 trie	1269.80	1254.41	1089.78	570.13
雪松::達	雙數組精簡特里樹	1183.07	1167.79	1076.68	645.79
雪松::da ORDERED=false	雙數組精簡特里樹	1183.14	1167.85	1065.43	641.98
雪松::達	雙數組前綴特里樹	498.69	496.54	1096.90	628.01
雪松::da ORDERED=false	雙數組前綴特里樹	498.65	496.60	1048.40	628.94
帽子特里¹ (C)	HAT特里樹	504.07	501.50	917.49	261.00
qp 特里樹 (C)	QP特里樹	941.23	938.17	1349.25	1281.46
暴擊位特里樹 (C)	Crit-bit trie	1074.96	1071.98	2930.42	2869.74
朱迪 (C)	朱迪陣列	631.09	628.37	884.29	803.58
朱迪 (C)	朱迪陣列	723.44	719.47	476.79	417.15
tsl::數組映射	數組哈希表	823.54	678.73	603.94	138.24
tsl::數組映射有保留	數組哈希表	564.26	555.91	249.52	128.28
tsl::跳房子地圖	哈希表	1325.83	1077.99	368.26	119.49
tsl::跳房子地圖有保留	哈希表	1080.51	1077.98	240.58	119.91
Google::dense_hash_map	哈希表	2319.40	1677.11	466.60	138.87
Google::dense_hash_map 有保留	哈希表	1592.51	1589.99	259.56	120.40
spp::sparse_hash_map	稀疏哈希表	918.67	917.10	769.00	175.59
spp::sparse_hash_map 有保留	稀疏哈希表	913.35	910.65	427.22	159.08
std::unordered_map	哈希表	1249.05	1246.60	590.88	173.58
std::unordered_map 有保留	哈希表	1212.23	1209.71	350.33	178.70

由於雜湊函數不能傳入參數，所以修改了函式庫本身的程式碼以使用CityHash64。

已排序

密鑰按字母順序插入和讀取。

圖書館	資料結構	峰值內存 (MiB)	內存 (MiB)	插入（奈秒/鍵）	讀取（奈秒/鍵）
tsl::htrie_map	HAT特里樹	396.10	393.22	255.76	68.08
tsl::htrie_map 最大負載係數=4	HAT特里樹	465.02	461.80	248.88	59.23
tsl::htrie_map 最大負載係數=2	HAT特里樹	543.99	541.21	230.13	53.50
tsl::htrie_map 最大負載係數=1	HAT特里樹	692.29	689.70	243.84	49.22
雪松::達	雙數組 trie	1269.58	1254.41	278.51	54.72
雪松::da ORDERED=false	雙數組 trie	1269.66	1254.41	264.43	56.02
雪松::達	雙數組精簡特里樹	1183.01	1167.78	254.60	69.18
雪松::da ORDERED=false	雙數組精簡特里樹	1183.03	1167.78	241.45	69.67
雪松::達	雙數組前綴特里樹	621.59	619.38	246.88	57.83
雪松::da ORDERED=false	雙數組前綴特里樹	621.59	619.38	187.98	58.56
帽子特里² (C)	HAT特里樹	521.25	518.52	503.01	86.40
qp 特里樹 (C)	QP特里樹	940.65	937.66	392.86	190.19
暴擊位特里樹 (C)	Crit-bit trie	1074.87	1071.98	430.04	347.60
朱迪 (C)	朱迪陣列	616.95	614.27	279.07	114.47
朱迪 (C)	朱迪陣列	722.29	719.47	439.66	372.25
tsl::數組映射	數組哈希表	826.98	682.99	612.31	139.16
tsl::數組映射有保留	數組哈希表	565.37	555.35	246.55	126.32
tsl::跳房子地圖	哈希表	1331.87	1078.02	375.19	118.08
tsl::跳房子地圖有保留	哈希表	1080.51	1077.97	238.93	117.20
Google::dense_hash_map	哈希表	2325.27	1683.07	483.95	137.09
Google::dense_hash_map 有保留	哈希表	1592.54	1589.99	257.22	113.71
spp::sparse_hash_map	稀疏哈希表	920.96	918.70	772.03	176.64
spp::sparse_hash_map 有保留	稀疏哈希表	914.84	912.47	422.85	158.73
std::unordered_map	哈希表	1249.09	1246.65	594.85	173.54
std::unordered_map 有保留	哈希表	1212.21	1209.71	347.40	176.49

由於雜湊函數不能傳入參數，所以修改了函式庫本身的程式碼以使用CityHash64。

Dr. Askitis 資料集

基準測試包括將 Dr. Askitis 的「Distinct Strings」資料集中的所有單字插入資料結構中，檢查已使用的記憶體空間並蒐索「Skew String Set 1」資料集中的所有單字（其中字串可以是出現多次）在資料結構中。請注意，此資料集中的字串具有相當短的平均和中位數密鑰長度（與上面使用的維基百科資料集相比，這可能不是一個現實的用例）。和cedar首頁上的差不多。

資料集：distinct_1（寫入）/skew1_1（讀取）
大小：290.45 MiB / 1 029.46 MiB
按鍵數量：28 772 169 / 177 999 203
平均密鑰長度：9.59 / 5.06
中位數密鑰長度：8 / 4
最大金鑰長度：126 / 62

基準協定與維基百科資料集相同。

圖書館	資料結構	峰值內存 (MiB)	內存 (MiB)	插入（奈秒/鍵）	讀取（奈秒/鍵）
tsl::htrie_map	HAT特里樹	604.76	601.79	485.45	77.80
tsl::htrie_map 最大負載係數=4	HAT特里樹	768.10	764.98	491.78	75.48
tsl::htrie_map 最大負載係數=2	HAT特里樹	1002.42	999.34	496.78	72.53
tsl::htrie_map 最大負載係數=1	HAT特里樹	1344.98	1341.97	520.66	72.45
雪松::達	雙數組 trie	1105.45	1100.05	682.25	71.98
雪松::da ORDERED=false	雙數組 trie	1105.47	1100.05	668.75	71.95
雪松::達	雙數組精簡特里樹	941.16	926.04	684.38	79.11
雪松::da ORDERED=false	雙數組精簡特里樹	941.16	925.98	672.14	79.02
雪松::達	雙數組前綴特里樹	714.58	712.59	831.71	75.83
雪松::da ORDERED=false	雙數組前綴特里樹	714.66	712.31	786.93	75.89
帽子特里³ (C)	HAT特里樹	786.93	784.32	743.34	93.58
qp 特里樹 (C)	QP特里樹	1800.02	1797.21	987.95	428.51
暴擊位特里樹 (C)	Crit-bit trie	2210.52	2207.64	1986.19	1109.88
朱迪 (C)	朱迪陣列	1025.59	1023.11	535.02	202.36
朱迪 (C)	朱迪陣列	1002.50	999.97	456.09	148.36
tsl::數組映射	數組哈希表	1308.08	1031.67	545.82	46.41
tsl::數組映射有保留	數組哈希表	979.44	921.363	244.19	45.74
tsl::跳房子地圖	哈希表	2336.39	1611.54	288.70	47.05
tsl::跳房子地圖有保留	哈希表	1614.22	1611.64	220.67	46.39
Google::dense_hash_map	哈希表	3913.64	2636.31	317.66	43.62
Google::dense_hash_map 有保留	哈希表	2638.19	2635.68	227.58	43.09
spp::sparse_hash_map	稀疏哈希表	1419.69	1417.61	586.26	56.00
spp::sparse_hash_map 有保留	稀疏哈希表	1424.21	1421.69	392.76	55.73
std::unordered_map	哈希表	2112.66	2110.19	554.02	105.05
std::unordered_map 有保留	哈希表	2053.95	2051.67	309.06	109.89

由於雜湊函數不能傳入參數，所以修改了函式庫本身的程式碼以使用CityHash64。

安裝

要使用該庫，只需將包含目錄新增至包含路徑即可。它是一個僅包含頭檔的庫。

如果您使用 CMake，也可以將 CMakeLists.txt 中的tsl::hat_trie匯出目標與target_link_libraries結合。

 # Example where the hat-trie project is stored in a third-party directory
add_subdirectory (third-party/hat-trie)
target_link_libraries (your_target PRIVATE tsl::hat_trie)

程式碼應適用於任何符合 C++11 標準的編譯器，並已使用 GCC 4.8.4、Clang 3.5.0 和 Visual Studio 2015 進行了測試。

要執行測試，您將需要 Boost Test 程式庫和 CMake。

git clone https://github.com/Tessil/hat-trie.git
cd hat-trie/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hat_trie_tests

用法

該 API 可以在這裡找到。如果std::string_view可用，API 會略有變化，可在此處找到。

例子

# include < iostream >
# include < string >
# include < tsl/htrie_map.h >
# include < tsl/htrie_set.h >


int main () {
    /*
     * Map of strings to int having char as character type. 
     * There is no support for wchar_t, char16_t or char32_t yet, 
     * but UTF-8 strings will work fine.
     */
    tsl::htrie_map< char , int > map = {{ " one " , 1 }, { " two " , 2 }};
    map[ " three " ] = 3 ;
    map[ " four " ] = 4 ;
    
    map. insert ( " five " , 5 );
    map. insert_ks ( " six_with_extra_chars_we_ignore " , 3 , 6 );
    
    map. erase ( " two " );
    
    /*
     * Due to the compression on the common prefixes, the letters of the string 
     * are not always stored contiguously. When we retrieve the key, we have to 
     * construct it.
     * 
     * To avoid a heap-allocation at each iteration (when SSO doesn't occur), 
     * we reuse the key_buffer to construct the key.
     */
    std::string key_buffer;
    for ( auto it = map. begin (); it != map. end (); ++it) {
        it. key (key_buffer);
        std::cout << " { " << key_buffer << " , " << it. value () << " } " << std::endl;
    }
    
    /*
     * If you don't care about the allocation.
     */
    for ( auto it = map. begin (); it != map. end (); ++it) {
        std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
    }
    
    
    
    
    tsl::htrie_map< char , int > map2 = {{ " apple " , 1 }, { " mango " , 2 }, { " apricot " , 3 },
                                      { " mandarin " , 4 }, { " melon " , 5 }, { " macadamia " , 6 }};
    
    // Prefix search
    auto prefix_range = map2. equal_prefix_range ( " ma " );
    
    // {mandarin, 4} {mango, 2} {macadamia, 6}
    for ( auto it = prefix_range. first ; it != prefix_range. second ; ++it) {
        std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
    }
    
    // Find longest match prefix.
    auto longest_prefix = map2. longest_prefix ( " apple juice " );
    if (longest_prefix != map2. end ()) {
        // {apple, 1}
        std::cout << " { " << longest_prefix. key () << " , " 
                  << *longest_prefix << " } " << std::endl;
    }
    
    // Prefix erase
    map2. erase_prefix ( " ma " );
    
    // {apricot, 3} {melon, 5} {apple, 1}
    for ( auto it = map2. begin (); it != map2. end (); ++it) {
        std::cout << " { " << it. key () << " , " << *it << " } " << std::endl;
    }
    
    
    
    
    tsl::htrie_set< char > set = { " one " , " two " , " three " };
    set. insert ({ " four " , " five " });
    
    // {one} {two} {five} {four} {three}
    for ( auto it = set. begin (); it != set. end (); ++it) {
        it. key (key_buffer);
        std::cout << " { " << key_buffer << " } " << std::endl;
    }
}

序列化

該庫提供了一種有效的方法來序列化和反序列化映射或集合，以便將其保存到文件或透過網路發送。為此，它要求使用者提供用於序列化和反序列化的函數物件。

 struct serializer {
    // Must support the following types for U: std::uint64_t, float and T if a map is used.
    template < typename U>
    void operator ()( const U& value);
    void operator ()( const CharT* value, std:: size_t value_size);
};

 struct deserializer {
    // Must support the following types for U: std::uint64_t, float and T if a map is used.
    template < typename U>
    U operator ()();
    void operator ()(CharT* value_out, std:: size_t value_size);
};

請注意，如果需要相容性，則實作會將其序列化/反序列化類型的二進位相容性（位元組序、浮點二進位表示、int 大小等）保留在所提供的函數物件手中。

有關serialize和deserialize方法的更多詳細資訊可以在 API 中找到。

# include < cassert >
# include < cstdint >
# include < fstream >
# include < type_traits >
# include < tsl/htrie_map.h >


class serializer {
public:
    serializer ( const char * file_name) {
        m_ostream. exceptions (m_ostream. badbit | m_ostream. failbit );
        m_ostream. open (file_name);
    }
    
    template < class T ,
             typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr >
    void operator ()( const T& value) {
        m_ostream. write ( reinterpret_cast < const char *>(&value), sizeof (T));
    }
    
    void operator ()( const char * value, std:: size_t value_size) {
        m_ostream. write (value, value_size);
    }

private:
    std::ofstream m_ostream;
};

class deserializer {
public:
    deserializer ( const char * file_name) {
        m_istream. exceptions (m_istream. badbit | m_istream. failbit | m_istream. eofbit );
        m_istream. open (file_name);
    }
    
    template < class T ,
             typename std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr >
    T operator ()() {
        T value;
        m_istream. read ( reinterpret_cast < char *>(&value), sizeof (T));
        
        return value;
    }
    
    void operator ()( char * value_out, std:: size_t value_size) {
        m_istream. read (value_out, value_size);
    }

private:
    std::ifstream m_istream;
};


int main () {
    const tsl::htrie_map< char , std:: int64_t > map = {{ " one " , 1 }, { " two " , 2 }, 
                                                    { " three " , 3 }, { " four " , 4 }};
    
    
    const char * file_name = " htrie_map.data " ;
    {
        serializer serial (file_name);
        map. serialize (serial);
    }
    
    {
        deserializer dserial (file_name);
        auto map_deserialized = tsl::htrie_map< char , std:: int64_t >:: deserialize (dserial);
        
        assert (map == map_deserialized);
    }
    
    {
        deserializer dserial (file_name);
        
        /* *
         * If the serialized and deserialized map are hash compatibles (see conditions in API), 
         * setting the argument to true speed-up the deserialization process as we don't have 
         * to recalculate the hash of each key. We also know how much space each bucket needs.
         */
        const bool hash_compatible = true ;
        auto map_deserialized = 
            tsl::htrie_map< char , std:: int64_t >:: deserialize (dserial, hash_compatible);
        
        assert (map == map_deserialized);
    }
}

使用 Boost 進行序列化使用 zlib 進行序列化和壓縮

如果要序列化的類型更複雜，可以使用序列化庫來避免一些樣板檔案。

以下範例使用 Boost Serialization 和 Boost zlib 壓縮流來減少產生的序列化檔案的大小。

# include < boost/archive/binary_iarchive.hpp >
# include < boost/archive/binary_oarchive.hpp >
# include < boost/iostreams/filter/zlib.hpp >
# include < boost/iostreams/filtering_stream.hpp >
# include < boost/serialization/split_free.hpp >
# include < boost/serialization/utility.hpp >
# include < cassert >
# include < cstdint >
# include < fstream >
# include < tsl/htrie_map.h >


template < typename Archive>
struct serializer {
    Archive& ar;
    
    template < typename T>
    void operator ()( const T& val) { ar & val; }
    
    template < typename CharT>
    void operator ()( const CharT* val, std:: size_t val_size) {
        ar. save_binary ( reinterpret_cast < const void *>(val), val_size* sizeof (CharT));
    }   
};

template < typename Archive>
struct deserializer {
    Archive& ar;
    
    template < typename T>
    T operator ()() { T val; ar & val; return val; }
    
    template < typename CharT>
    void operator ()(CharT* val_out, std:: size_t val_size) {
        ar. load_binary ( reinterpret_cast < void *>(val_out), val_size* sizeof (CharT));
    }  
};

namespace boost { namespace serialization {
template < class Archive , class CharT , class T >
void serialize (Archive & ar, tsl::htrie_map<CharT, T>& map, const unsigned int version) {
    split_free (ar, map, version); 
}

template < class Archive , class CharT , class T >
void save (Archive & ar, const tsl::htrie_map<CharT, T>& map, const unsigned int version) {
    serializer<Archive> serial{ar};
    map. serialize (serial);
}


template < class Archive , class CharT , class T >
void load (Archive & ar, tsl::htrie_map<CharT, T>& map, const unsigned int version) {
    deserializer<Archive> deserial{ar};
    map = tsl::htrie_map<CharT, T>:: deserialize (deserial);
}
}}


int main () {
    const tsl::htrie_map< char , std:: int64_t > map = {{ " one " , 1 }, { " two " , 2 }, 
                                                    { " three " , 3 }, { " four " , 4 }};
    
    
    const char * file_name = " htrie_map.data " ;
    {
        std::ofstream ofs;
        ofs. exceptions (ofs. badbit | ofs. failbit );
        ofs. open (file_name, std::ios::binary);
        
        boost::iostreams::filtering_ostream fo;
        fo. push ( boost::iostreams::zlib_compressor ());
        fo. push (ofs);
        
        boost::archive::binary_oarchive oa (fo);
        
        oa << map;
    }
    
    {
        std::ifstream ifs;
        ifs. exceptions (ifs. badbit | ifs. failbit | ifs. eofbit );
        ifs. open (file_name, std::ios::binary);
        
        boost::iostreams::filtering_istream fi;
        fi. push ( boost::iostreams::zlib_decompressor ());
        fi. push (ifs);
        
        boost::archive::binary_iarchive ia (fi);
     
        tsl::htrie_map< char , std:: int64_t > map_deserialized;   
        ia >> map_deserialized;
        
        assert (map == map_deserialized);
    }
}