Click here to Skip to main content
Click here to Skip to main content

String Tree Dictionary

, 23 Sep 2008 CPOL
Rate this:
Please Sign up or sign in to vote.
Good for decoding a stream of characters with a finite number of predefined tokens

Introduction

A StringTreeDictionary<T> class implements a IDictionary<string, T> interface and is 57% faster than a Dictionary<string, T> at a task described below, 50% slower at adding items and much slower at accessing them. Even so it can be useful if you have to translate a sequence of characters.

Using the Code

A method, MatchKey, provided in a class tries to find a key in a dictionary which matches the beginning of a given string. If the key was found, then it returns a KeyValuePair<string, TKey> object. Otherwise a KeyNotFoundException is thrown. For example, if a dictionary would contain keys aaba, ac, ccbc and abcd, then the MatchKey("accdba") would retaurn a pair {"ac", dict["ac"]}. Note that we do not know a length of a key we are searching for. The method can be used to extract a sequence of meaningful strings (keys) from a continuous stream of characters.

How It Works

Internally, the StringTreeDictionary object represents a node of a tree structure. There are the following fields inside:

public class StringTreeDictionary<T> : IDictionary<string, T>
{
	private T value;
	private bool hasValue = false;
	private Dictionary<char, StringTreeDictionary<T>> childs = null;

A single StringTreeDictionary object contains just one value and a dictionary with child nodes as values and chars as keys. Let's see how the items are stored.

StringTreeDictionary_diagram1.jpg

Such a dictionary could be instantinated this way:

StringTreeDictionary<string> std = new StringTreeDictionary<string> {
	{"bear", "sleuth"},
	{"bee", "grist"},
	{"bird", "flock"},
	{"cat", "clowder"}
};

The diagram clearly shows that the dictionary does not like long keys.

Remarks

  • A StringTreeDictionary<T> is good only for very specific cases; do not use it instead of a standard .NET dictionary.
  • Accessing items with keys longer than 3 characters is terribly slow and is not recommended.
  • The dictionary does not support a true item removal. A faked Remove method only disallows accessing deleted items and sets value to default(TValue), but does not detach unused nodes.
  • The MatchKey method searches for the shortest key matching a string's beginning. If you would add keys acx and ac, then the acx would never be found.

History

  • 2008-09-20 - First version posted
  • 2008-09-20 - Download files updated

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jacek Gajek
Software Developer (Junior)
Poland Poland
My name is Jacek Gajek. I have graduated in computer science with a master's degree from Polibuda in Wrocław. I like C# and Monthy Python's sense of humour.

Comments and Discussions

 
QuestionIs it Ternary Search Trie implementation? Pinmemberc-smile23-Sep-08 18:17 
AnswerRe: Is it Ternary Search Trie implementation? Pinmembergajatko24-Sep-08 0:04 
GeneralThoughts PinmemberPIEBALDconsult23-Sep-08 11:09 
GeneralRe: Thoughts Pinmembergajatko23-Sep-08 11:59 
no it does not allow only two nodes. If you look at the code (in the article), you can see that sub-nodes are stored in a Dictionary<char, tree>, which obviously does not have such a limitation. The picture is just an example. Anyway it is an implentation detail as these members are private.
 
I'm sorry if I did not explain well enough how the MatchKey method works. Please ask what you find not clear and I will try to clarify the thing.
 
Greetings - Gajatko
 
Portable.NET is part of DotGNU, a project to build a complete Free Software replacement for .NET - a system that truly belongs to the developers.

GeneralRe: Thoughts PinmemberPIEBALDconsult23-Sep-08 13:56 
GeneralRe: Thoughts Pinmembergajatko23-Sep-08 23:28 
GeneralRe: Thoughts PinmemberPIEBALDconsult24-Sep-08 4:47 
GeneralRe: Thoughts Pinmembergajatko24-Sep-08 10:57 
GeneralRe: Thoughts PinmemberPIEBALDconsult24-Sep-08 11:20 
GeneralRe: Thoughts Pinmembergajatko25-Sep-08 2:00 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.1411028.1 | Last Updated 23 Sep 2008
Article Copyright 2008 by Jacek Gajek
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid