Trie

「トライ」と読む

GPT-4.icon

文字列や配列の集合を効率的に管理するためのデータ構造

特徴

各Nodeは1つの文字を持つ

各Edgeは文字を表す

文字列は、rootからedgeを辿ることで表現される

文字列の終端には終端Nodeという特別なNodeが置かれる

同じ接頭辞を持つ文字列は、共通のルートノードから分岐する

メモリ使用量を効率化し、検索や挿入の高速化が図れる

主な操作

挿入

新しい文字列をトライ木に追加する

Lは文字列の長さ

つまり、文字列の長さに依存する

検索

文字列がトライ木に存在するかどうかを確認する操作

O(L)

削除

トライ木から文字列を削除する操作。

O(L)

用途

辞書作成

多くの単語を効率的に管理・検索するための辞書として使用される

文字列検索

特定の接頭辞を持つ文字列の検索や、部分一致検索を高速に行うために使用される

パス検索

file systemやURLの管理において、パスの共通部分を共有することで効率的に管理できる

連想配列を表す木

(上記の説明と若干Nodeの扱いが異なる)

こういう連想配列があるとする

table:_

key to tea ted ten A i in inn

value 7 3 4 12 15 11 5 9

これをTrieで表現すると以下のようになる

https://gyazo.com/17075b35fec4c53df6956abc54de1ea5 https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)

亜種

Haskellでの実装例

トライ木のデータ構造

code:hs

import Data.Map (Map)

import qualified Data.Map as Map

data TrieNode a = TrieNode

{ value :: Maybe a

, children :: Map Char (TrieNode a)

} deriving (Show)

type Trie a = TrieNode a

code:hs

-- 空のトライ木の生成

emptyTrie :: Trie a

emptyTrie = TrieNode Nothing Map.empty

-- 挿入

insert :: String -> a -> Trie a -> Trie a

insert [] v (TrieNode _ children) = TrieNode (Just v) children

insert (c:cs) v (TrieNode val children) =

let childTrie = Map.findWithDefault emptyTrie c children

newChildTrie = insert cs v childTrie

in TrieNode val (Map.insert c newChildTrie children)

-- 検索

search :: String -> Trie a -> Maybe a

search [] (TrieNode val _) = val

search (c:cs) (TrieNode _ children) =

case Map.lookup c children of

Nothing -> Nothing

Just childTrie -> search cs childTrie

-- 削除

delete :: String -> Trie a -> Trie a

delete [] (TrieNode _ children) = TrieNode Nothing children

delete (c:cs) (TrieNode val children) =

case Map.lookup c children of

Nothing -> TrieNode val children

Just childTrie ->

let newChildTrie = delete cs childTrie

newChildren = if isEmpty newChildTrie

then Map.delete c children

else Map.insert c newChildTrie children

in TrieNode val newChildren

isEmpty :: Trie a -> Bool

isEmpty (TrieNode Nothing children) = Map.null children

isEmpty _ = False

使用例

code:hs

main :: IO ()

main = do

let trie = insert "hello" "world" $ insert "hell" "fire" $ insert "he" "wave" emptyTrie

print $ search "hello" trie -- Just "world"

print $ search "hell" trie -- Just "fire"

print $ search "he" trie -- Just "wave"

print $ search "hel" trie -- Nothing

let trie' = insert "hel" "lo" trie

print $ search "hel" trie' -- Just "lo"

let trie'' = delete "hell" trie'

print $ search "hello" trie'' -- Just "world"

print $ search "hell" trie'' -- Nothing

print $ search "he" trie'' -- Just "wave"

print $ search "hel" trie'' -- Just "lo"