A DAWG (directed acyclic word graph) is a data structure for storing a set of strings. It can be thought of as a compressed trie, or as a minimum-state finite automaton for the given set of strings.
Questions tagged [dawg]
18 questions
162
votes
16 answers
How to create a trie in Python
I'm interested in tries and DAWGs (direct acyclic word graph) and I've been reading a lot about them but I don't understand what should the output trie or DAWG file look like.
Should a trie be an object of nested dictionaries? Where each letter is…
Phil
- 13,875
- 21
- 81
- 126
5
votes
1 answer
Best way to construct a Directed Acyclic Word Graph (DAWG)
I am currently looking into DAWGs and I haven't been able to find one good way of constructing an acyclic automaton.
So basically, what I want to do is this :
It is basically a tree, where the number of states are reduced. I would use it with…
Anoracx
- 438
- 7
- 24
3
votes
1 answer
Meta-information in DAWG/DAFSA
I would like to implement a string look-up data structure, for dynamic strings, that will support efficient search and insertion. Currently, I am using a trie but I would like to reduce the memory footprint if possible. This Wikipedia article…
Schemer
- 1,635
- 4
- 19
- 39
3
votes
3 answers
Updateable DAWG library or DAWG construction from non-sorted data
dawgdic is a great DAWG library, but it has a significant drawback because it is static (not updateable) and has to be constructed form strings sorted in alphabetical order. If the raw data from which the DAWG is constructed is big (several…
lizarisk
- 7,562
- 10
- 46
- 70
3
votes
1 answer
How to construct a DAWG from a trie?
i just construct a trie for a vocabulary, and then I found that there are many branches shared the same struct. i want to combine them together result to be a DAWG.
What algorithm would I use to convert a trie to a DAWG?
user1540043
- 163
- 5
2
votes
1 answer
Using Aho-Corasick on a DAWG rather than a Trie
does anybody know if it's possible to modify the Aho-Corasick string matching algorithm to be used on a DAWG (Directed Acyclic Word Graph) rather than a Trie?
parsa
- 2,628
- 3
- 34
- 44
2
votes
3 answers
Can a DAWG be used to store word related information?
Can a DAWG be used to store auxiliary information relating to each path, e.g. a word's frequency in the English language? If yes, then how can i do that?
Usman Amjed
- 89
- 1
- 7
1
vote
1 answer
Import Error from binary dependency file
I am attempting to run a package after installing it, but am getting this error:
ImportError: /home/brownc/anaconda3/lib/python3.5/site-packages/dawg.cpython-35m-x86_64-linux-gnu.so: undefined symbol:…
chase
- 3,592
- 8
- 37
- 58
1
vote
2 answers
Android DAWG implementation
In my application I need to work with dictionary, what have a lot of words(110 000), so I decided to use trie, but loading of trie cost 9 seconds every time. And this is much a lot even for my emulator. Recently I have read about DAWG(Direct…
Mike Herasimov
- 1,319
- 3
- 14
- 31
1
vote
2 answers
Set vs DAWG for checking membership in dictionary in Python
I need to be able to quickly check if a given word is in my dictionary (English wordlist). I'm only concerned with speed of checking membership (not adding or removing elements), and memory use isn't really a problem.
Originally I was using a set…
Dave White
- 321
- 1
- 3
- 13
0
votes
0 answers
Failed to build DAWG issue
Im trying to install a package, but one of its dependencies is DAWG and it just cant install it correctly. The only solution ive found is downgrading to python 3.8 where it works, but I dont want to depend on that.
The error in mention is:
Running…
Jorge M
- 11
- 2
0
votes
2 answers
Seeking suggestions on a Word Game implementation using DAWG
I am trying to implement a little game with the following rules:
Given a set of random letters (e.g. 10), I want to find all possible words one can form out of these letters. I am using a standard dictionary for this.
Letters are allowed to be used…
Nimo
- 61
- 6
0
votes
0 answers
how to build a DAWG graphique in Java
I need to create a DAWG graphic for my scrabble IA.
After multi search I found two or three sites that explain how to create a DAWG:
https://progaide.com/question/12331755-algorithme-de-cr-ation-de-dawg-facile
How to create a…
nicolas
- 1
- 1
0
votes
0 answers
best way to store DAWG(Directed Acyclic Word-Graph) and findout if word exist
so i wrote a code to construct a dawg. i want to findout if a word exist in a language or not? after a lot of search i findout best way is to use dawg. here
public class DawgNode
{
public DawgNode(int id)
{
Id = id;
}
public…
shahrooz.bazrafshan
- 61
- 4
0
votes
0 answers
DAWG implementation in Javascript
What are the first steps for implementing a DAWG or GADDAG in browser in Javascript (without overloading memory)? Specifically, I want to port this data structure into an interactive Scrabble game in browser so that humans can play against a…
Daniel
- 1
- 1
- 1