Click here to Skip to main content
11,576,064 members (57,779 online)
Click here to Skip to main content

String Tree Dictionary

, 23 Sep 2008 CPOL 35.6K 575 15
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.

You may also be interested in...

Comments and Discussions

 
QuestionIs it Ternary Search Trie implementation? Pin
c-smile23-Sep-08 17:17
memberc-smile23-Sep-08 17:17 
AnswerRe: Is it Ternary Search Trie implementation? Pin
gajatko23-Sep-08 23:04
membergajatko23-Sep-08 23:04 
GeneralThoughts Pin
PIEBALDconsult23-Sep-08 10:09
memberPIEBALDconsult23-Sep-08 10:09 
GeneralRe: Thoughts Pin
gajatko23-Sep-08 10:59
membergajatko23-Sep-08 10:59 
GeneralRe: Thoughts Pin
PIEBALDconsult23-Sep-08 12:56
memberPIEBALDconsult23-Sep-08 12:56 
GeneralRe: Thoughts Pin
gajatko23-Sep-08 22:28
membergajatko23-Sep-08 22:28 
GeneralRe: Thoughts Pin
PIEBALDconsult24-Sep-08 3:47
memberPIEBALDconsult24-Sep-08 3:47 
Ah, it took several readings to figure out what you are saying and I'm still not entirely sure.
You really need to explain the problem you're trying to solve, not just explain the solution.
GeneralRe: Thoughts Pin
gajatko24-Sep-08 9:57
membergajatko24-Sep-08 9:57 
GeneralRe: Thoughts Pin
PIEBALDconsult24-Sep-08 10:20
memberPIEBALDconsult24-Sep-08 10:20 
GeneralRe: Thoughts Pin
gajatko25-Sep-08 1:00
membergajatko25-Sep-08 1: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
Web04 | 2.8.150603.1 | Last Updated 23 Sep 2008
Article Copyright 2008 by Jacek Gajek
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid