Search Wiki:

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.

DawgKitScreen.png

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.
Last edited Jul 21 2008 at 12:19 AM  by smallenucd, version 25
Comments
smallenucd wrote  May 3 2008 at 10:53 PM  
Big update to page.

smallenucd wrote  May 15 2008 at 4:54 AM  
Finally, made the page decent. This is #1 home of this software now. I also store the 7z on Google Code, but this is the home.

smallenucd wrote  May 17 2008 at 3:09 AM  
Better formatting

smallenucd wrote  Jun 12 2008 at 3:30 AM  
Added link to new application--try it out, you'll like it :)

smallenucd wrote  Jul 21 2008 at 12:17 AM  
Removed dead links, sorry about that. Also fixed spelling.

Jourbon wrote  Jan 26 2012 at 3:22 PM  

Thanks, I've used your DAWG implementation for a multiplayer word game (http://fundox.free.fr).

I needed to rebuild the original list of words from a DAWG tree downloaded by the client, here is the code :

In SharpDawg.cs :

private Dictionary<char, int> _translator;
private List<string> dico;
private StringBuilder Word;

public SharpDawg(DawgMetadata metadataIn, int DawgLines)
{
_translator = metadataIn.Translator;
// and so on............
}

public List<string> GenDic()
{
dico = new List<string>();
Word = new StringBuilder();
GenDicNode(0);
return dico;
}

private void GenDicNode(int Line)
{
int super = _supers[Line];
if ((super & _fullWordBit) != 0) dico.Add(Word.ToString());
for (int i = 0; i < _fullWordBit; i++)
{
if ((super & (1 << i)) != 0)
{
Word.Append (_translator.ElementAt(i).Key);
GenDicNode(_nodes[Line][FastBitcount(super & _bitmasks[i]) - 1]);
}
}
if (Word.Length > 0) Word.Remove(Word.Length - 1, 1);
}

Updating...
Page view tracker