當前位置:成語大全網 - 成語詞典 - 如果要對10w個英文單詞進行前綴匹配搜索,下面哪種數據結構最合適

如果要對10w個英文單詞進行前綴匹配搜索,下面哪種數據結構最合適

Trie,又稱單詞查找樹或鍵樹,是壹種樹形結構,是壹種哈希樹的變種。典型應用是用於統計和排序大量的字符串(但不僅限於字符串),所以經常被搜索引擎系統用於文本詞頻統計。它的優點是:最大限度地減少無謂的字符串比較,查詢效率比哈希表高。

散列是壹種常見的高效查找方法,它根據數組下標查詢,所以速度快。首先根據詞表構造散列表,具體來說就是用給定的哈希函數構造詞典到數組下標的映射,如果存在沖突,則根據選擇的沖突處理方法解決地址沖突。然後可以在哈希表的基礎上執行哈希查找。

沖突導致散列性能降低。不存在沖突的散列表叫做完美散列(perfect hash)。整詞散列不適合分詞的最長匹配查找方式。