Trie

Un trie és un cas especial d'autòmat finit determinista ${\displaystyle (S,\Sigma ,T,s,A)}$, que serveix per a emmagatzemar un conjunt de cadenes ${\displaystyle E}$ en el qual:

• ${\displaystyle \Sigma }$ és l'alfabet sobre el qual estan definides les cadenes;
• ${\displaystyle S}$, el conjunt d'estats, cadascun dels quals representa un prefix de E;
• la funció de transició: ${\displaystyle T:S\times \Sigma \to S}$; està definida com segueix: ${\displaystyle T(x,\sigma )=x\sigma }$ si ${\displaystyle x,x\sigma \in S}$, i indefinida altrament;
• l'estat inicial ${\displaystyle s}$ correspon a la cadena buida ${\displaystyle \lambda ;}$
• el conjunt d'estats d'acceptació ${\displaystyle A\subseteq S}$ és igual a ${\displaystyle E}$.

El seu nom procedeix del terme anglés retrieval.