Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!rpi!uupsi!nynexst.com!mohan From: mohan@nynexst.com (Mohan Arkalgud) Newsgroups: comp.compression Subject: Re: What is a trie ?? (was Re: fast string compr.?) Keywords: trie Message-ID: <1991Jun5.140117.16510@nynexst.com> Date: 5 Jun 91 14:01:17 GMT References: <6228@ns-mx.uiowa.edu> Sender: news@nynexst.com (For News purposes) Reply-To: mohan@nynexst.com (Mohan Arkalgud) Organization: Nynex Science and Technology Lines: 28 Originator: mohan@diamond In article <6228@ns-mx.uiowa.edu>, jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes: |> From article , |> by d88-jwa@byse.nada.kth.se (Jon W{tte): |> > |> > What is a trie? |> |> A trie is any tree where branches are labeled with the letters of some |> alphabet and where the path label, treated as a string of these letters, |> is used to encode or decode the use of that path. Thus, the tree used |> in a Huffman code is a trie, and the hash table used by the LZW compression |> algorithm is also a funny but very useful representation of a trie. |> |> I've never seen any reason to use the word -- it's a cute pun on the word |> tree, but the problem is, too many people don't understand what you mean |> when you say it. Rather than take the time to tell them what I meant, I |> prefer to avoid the problem by avoiding the word. |> Doug Jones |> jones@cs.uiowa.edu The term 'trie' originated as letters extracted from the word 'retrieval'. I agree with you that there is no overwhelming reason for the choice of the word trie. --- Mohan Arkalgud mohan@nynexst.com