Directed Acyclic Word Graph C#

UPDATED WIKI: Home

smallenucd — Mon, 21 Jul 2008 00:19:00 GMT

Anagram Program

The DAWG is used in my anagram program. See my article http://dotnetperls.com/Content/Anagram-Windows.aspx.

Big Update

The DawgKit program was cleaned up substantially and is in better shape. Not a lot of real algorithm changes. The code is better
and more factored. It uses more interfaces and some of the supporting code is much better.

Introduction

I have written code in C# that implements the Directed Acyclic Word Graph algorithm and data structure. This sort of data structure is used to design word games such as Scrabble or anagrams and also has usage in scientific pursuits in biology and genetics.

This code page is meant to serve as an outpost for this code. I have a complete implementation in C#. The DAWG algorithms have a dramatic performance advantage over hash tables, sometimes occupying 25% of the memory and also having faster performance. I think these source files can find utility in a broader range of projects, such as a spell-checker, or other string analysis or pattern matching tools.

Important Resources

UPDATED WIKI: Home

smallenucd — Mon, 21 Jul 2008 00:16:56 GMT

Big Update

Introduction

Important Resources

UPDATED WIKI: Home

smallenucd — Thu, 12 Jun 2008 03:30:13 GMT

New Application for DAWG

I have developed an anagram finder program called Anagram Free Finder that uses this code. It contains about 400 lines of code and has a useful GUI. It will find all anagrams of equal or lesser length to the word you type in. It displays results instantly when you type a key.
Please visit it at http://code.msdn.microsoft.com/anagrams. It is the best way to actually see a demonstration of this 1985 technology.

Big Update May 2008!

Introduction

I have written code in C# that implements the Directed Acyclic Word Graph algorithm and data stucture. This sort of data structure is used to design word games such as Scrabble or anagrams and also has usage in scientific pursuits in biology and genetics.

This code page is meant to serve as an outpost for this code. I have a complete implementation in C#. The DAWG algorithms have a dramatic performance advantage over hash tables, sometimes occupying 25% of the memory and also having faster performance. I think these source files can find utility in a broader range of projects, such as a spell-checker, or other string analysis or pattern matching tools.

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx.

I will be optimizing/enhancing this software in a series. Read the series by looking at the first link to Directed-Acyclic-Word-Graph.aspx. There is a series you can continue reading from there. Finally there is a page with benchmarks and a conclusion. Here are a couple of the results graphs. The DAWG and the Dictionary are the two on the left. The Bloom filter is another structure but it doesn't store all the same data, which is why it is smaller.

My series also includes a list of things I have learned about writing fast C# code. I hope to add more to this page and organize this stuff better. Other methods I used in implementing DawgKit include Enumerable.Range in LINQ

http://dotnetperls.com/Content/LINQ-Enumerable-Range.aspx

and also a TextBox trick to improve the UI.

http://dotnetperls.com/Content/TextBox-AppendText-Tip.aspx

It is my goal to keep improving this software occasionally, as well as the articles I have written about it. It is fairly complex but I believe it can greatly benefit some software out there.

UPDATED WIKI: Home

smallenucd — Sat, 17 May 2008 03:09:37 GMT

Big Update May 2008!

Introduction

Important Resources

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:53:24 GMT

Big Update May 2008!

Introduction

Important Resources

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:53:04 GMT

Big Update May 2008!

Introduction

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx.

I will be optimizing/enhancing this software in a series. Read the series by looking at the first link to Directed-Acyclic-Word-Graph.aspx. There is a series you can continue reading from there. Finally there is a page with benchmarks and a conclusion. Here are a couple of the results graphs. The DAWG and the Dictionary are the two on the left. The Bloom filter is another structure but it doesn't store all the same data, which is why it is smaller.

img:TimeChart1.png

img:MemoryChart1.png

My series also includes a list of things I have learned about writing fast C# code. I hope to add more to this page and organize this stuff better. Other methods I used in implementing DawgKit include Enumerable.Range in LINQ

http://dotnetperls.com/Content/LINQ-Enumerable-Range.aspx

and also a TextBox trick to improve the UI.

http://dotnetperls.com/Content/TextBox-AppendText-Tip.aspx

It is my goal to keep improving this software occasionally, as well as the articles I have written about it. It is fairly complex but I believe it can greatly benefit some software out there.

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:50:06 GMT

Big Update May 2008!

Introduction

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx.

I will be optimizing/enhancing this software in a series. Read the series by looking at the first link to Directed-Acyclic-Word-Graph.aspx. There is a series you can continue reading from there. Finally there is a page with benchmarks and a conclusion.

It also includes a list of things I have learned about writing fast C# code. I hope to add more to this page and organize this stuff better. Other methods I used in implementing DawgKit include Enumerable.Range in LINQ

http://dotnetperls.com/Content/LINQ-Enumerable-Range.aspx

and also a TextBox trick to improve the UI.

http://dotnetperls.com/Content/TextBox-AppendText-Tip.aspx

It is my goal to keep improving this software occasionally, as well as the articles I have written about it. It is fairly complex but I believe it can greatly benefit some software out there.

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:49:29 GMT

Big Update May 2008!

Introduction

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx.

I will be optimizing/enhancing this software in a series. Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list.

Read the series by looking at the first link to Directed-Acyclic-Word-Graph.aspx. There is a series you can continue reading from there.
Finally there is a page with benchmarks and a conclusion. It also includes a list of things I have learned about writing fast C# code. I hope to add more to this page and organize this stuff better.

Other methods I used in implementing DawgKit include Enumerable.Range in LINQ

http://dotnetperls.com/Content/LINQ-Enumerable-Range.aspx

and also a TextBox trick to improve the UI.

http://dotnetperls.com/Content/TextBox-AppendText-Tip.aspx

It is my goal to keep improving this software occasionally, as well as the articles I have written about it. It is fairly complex but I believe it can greatly benefit some software out there.

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:48:53 GMT

Big Update

Introduction

Important Resources

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:47:53 GMT

Big Update

Introduction

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx. My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series. Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list.

Read the series by looking at the first link to Directed-Acyclic-Word-Graph.aspx. There is a series you can continue reading from there.
Finally there is a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

Other methods I used in implementing DawgKit include Enumerable.Range in LINQ

http://dotnetperls.com/Content/LINQ-Enumerable-Range.aspx

and also a TextBox trick to improve the UI.

http://dotnetperls.com/Content/TextBox-AppendText-Tip.aspx

It is my goal to keep improving this software occasionally, as well as the articles I have written about it. It is fairly complex but I believe it can greatly benefit some software out there.

CREATED RELEASE: DawgKit May 2008 (May 14, 2008)

Thu, 15 May 2008 04:42:05 GMT

Lots of cleanups and improvements. It uses interfaces in the code, and has more logical and clear supporting code. Some complexity was removed in many parts, including critical parts. No big performance improvements, but a worthwhile update. Also uses LINQ for simplicity in some non-critical code.

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:38:43 GMT

Big Update

Introduction

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx. My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series. Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list. Here are the articles I write about DawgKit in:

http://dotnetperls.com/Content/Word-Algorithm-1.aspx
http://dotnetperls.com/Content/Word-Algorithm-2.aspx
http://dotnetperls.com/Content/Word-Algorithm-3.aspx
http://dotnetperls.com/Content/Word-Algorithm-4.aspx
http://dotnetperls.com/Content/Word-Algorithm-5.aspx

Finally, a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:37:18 GMT

Introduction

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx. My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series. Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list. Here are the articles I write about DawgKit in:

http://dotnetperls.com/Content/Word-Algorithm-1.aspx
http://dotnetperls.com/Content/Word-Algorithm-2.aspx
http://dotnetperls.com/Content/Word-Algorithm-3.aspx
http://dotnetperls.com/Content/Word-Algorithm-4.aspx
http://dotnetperls.com/Content/Word-Algorithm-5.aspx

Finally, a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:37:01 GMT

Introduction

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx. My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series. Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list. Here are the articles I write about DawgKit in:

http://dotnetperls.com/Content/Word-Algorithm-1.aspx
http://dotnetperls.com/Content/Word-Algorithm-2.aspx
http://dotnetperls.com/Content/Word-Algorithm-3.aspx
http://dotnetperls.com/Content/Word-Algorithm-4.aspx
http://dotnetperls.com/Content/Word-Algorithm-5.aspx

Finally, a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

UPDATED WIKI: Home

smallenucd — Thu, 15 May 2008 04:36:39 GMT

Introduction

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx. My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series. Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list. Here are the articles I write about DawgKit in:

http://dotnetperls.com/Content/Word-Algorithm-1.aspx
http://dotnetperls.com/Content/Word-Algorithm-2.aspx
http://dotnetperls.com/Content/Word-Algorithm-3.aspx
http://dotnetperls.com/Content/Word-Algorithm-4.aspx
http://dotnetperls.com/Content/Word-Algorithm-5.aspx

Finally, a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

UPDATED WIKI: Home

smallenucd — Sat, 03 May 2008 22:53:06 GMT

Introduction

I have written code in C# that implements the Directed Acyclic Word Graph algorithm and data stucture. This sort of data structure is used to design word games such as Scrabble or anagrams and also has usage in scientific pursuits in biology and genetics.

This code page is meant to serve as an outpost for this code. I have a complete implementation in C#. The DAWG algorithms have a dramatic performance advantage over hash tables, sometimes occupying 25% of the memory and also having faster performance. I think these source files can find utility in a broader range of projects, such as a spell-checker, or other string analysis or pattern matching tools.

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx. My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series. Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list. Here are the articles I write about DawgKit in:

http://dotnetperls.com/Content/Word-Algorithm-1.aspx
http://dotnetperls.com/Content/Word-Algorithm-2.aspx
http://dotnetperls.com/Content/Word-Algorithm-3.aspx
http://dotnetperls.com/Content/Word-Algorithm-4.aspx
http://dotnetperls.com/Content/Word-Algorithm-5.aspx

Finally, a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

UPDATED WIKI: Home

smallenucd — Sat, 03 May 2008 22:52:50 GMT

Introduction

I have written code in C# that implements the Directed Acyclic Word Graph algorithm and data stucture. This sort of data structure is used to design word games such as Scrabble or anagrams and also has usage in scientific pursuits in biology and genetics.

This code page is meant to serve as an outpost for this code. I have a complete implementation in C#. The DAWG algorithms have a dramatic performance advantage over hash tables, sometimes occupying 25% of the memory and also having faster performance. I think these source files can find utility in a broader range of projects, such as a spell-checker, or other string analysis or pattern matching tools.

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx.

My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series.

Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list. Here are the articles I write about DawgKit in:

http://dotnetperls.com/Content/Word-Algorithm-1.aspx
http://dotnetperls.com/Content/Word-Algorithm-2.aspx
http://dotnetperls.com/Content/Word-Algorithm-3.aspx
http://dotnetperls.com/Content/Word-Algorithm-4.aspx
http://dotnetperls.com/Content/Word-Algorithm-5.aspx

Finally, a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

UPDATED WIKI: Home

smallenucd — Sat, 03 May 2008 22:52:07 GMT

Introduction

I have written code in C# that implements the Directed Acyclic Word Graph algorithm and data stucture. This sort of data structure is used to design word games such as Scrabble or anagrams and also has usage in scientific pursuits in biology and genetics.

This code page is meant to serve as an outpost for this code. I have a complete implementation in C# and C+, in Visual Studio for both and GCC for the C/C+.

The DAWG algorithms have a dramatic performance advantage over hash tables, sometimes occupying 25% of the memory and also having faster performance. I think these source files can find utility in a broader range of projects, such as a spell-checker, or other string analysis or pattern matching tools.

Important Resources

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx.

My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series.

Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list. Here are the articles I write about DawgKit in:

http://dotnetperls.com/Content/Word-Algorithm-1.aspx
http://dotnetperls.com/Content/Word-Algorithm-2.aspx
http://dotnetperls.com/Content/Word-Algorithm-3.aspx
http://dotnetperls.com/Content/Word-Algorithm-4.aspx
http://dotnetperls.com/Content/Word-Algorithm-5.aspx

Finally, a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

UPDATED WIKI: Home

smallenucd — Sat, 22 Mar 2008 22:39:30 GMT

I have written code in C#, C, C++, and Perl that implements various string/word-storage algorithms, such as Directed Acyclic Word Graphs. These algorithms are used to design word games such as Scrabble or anagrams and also have usage in scientific pursuits in biology and genetics.

This code page is meant to serve as an outpost for this code. I have a complete implementation in C# and C+, in Visual Studio for both and GCC for the C/C+.

The DAWG algorithms have a dramatic performance advantage over hash tables, sometimes occupying 25% of the memory and also having faster performance.

I think these source files can find utility in a broader range of projects, such as a spell-checker, or other string analysis or pattern matching tools.

Implementation details can be found at http://dotnetperls.com/Content/Directed-Acyclic-Word-Graph.aspx.

My website is at http://dotnetperls.com/ and I will be optimizing/enhancing this software in a series.

Additional sources are available at Google Code http://code.google.com/p/dotnetperls-controls/downloads/list.

Here are the articles I write about DawgKit in:

http://dotnetperls.com/Content/Word-Algorithm-1.aspx
http://dotnetperls.com/Content/Word-Algorithm-2.aspx
http://dotnetperls.com/Content/Word-Algorithm-3.aspx
http://dotnetperls.com/Content/Word-Algorithm-4.aspx
http://dotnetperls.com/Content/Word-Algorithm-5.aspx

Finally, a page with benchmarks and a conclusion:

http://dotnetperls.com/Content/Word-Algorithm-Results.aspx

CREATED RELEASE: Dawg Kit Optimized (Mar 22, 2008)

Sat, 22 Mar 2008 22:37:37 GMT

This version includes many optimizations, improving many benchmarks up to 30%. Includes UI enhancements, cleaner code, more comments (XML), and also release and debug binaries for .NET 3.5. No installer. Also on Google Code.