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

String Tree Dictionary

, 23 Sep 2008
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)

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 17:17 
AnswerRe: Is it Ternary Search Trie implementation? Pinmembergajatko23-Sep-08 23:04 

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 | Mobile
Web01 | 2.8.140721.1 | Last Updated 23 Sep 2008
Article Copyright 2008 by Jacek Gajek
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid