Hot answers tagged

15

When seeing a class with a constructor signature like EnglishWordsListGenerator(const std::string &wordFileName) I think it is pretty obvious that this constructor will read the given file (and so need some time), and it should not be to hard to understand that the caller has to care for possible exceptions from this (because file IO can fail). So ...


15

Aguri is a traffic profiler that uses prefix trees. The complete article is on that page. In short there is no such data structure as an "Aguri Tree" unless you count the prefix trees used in that system to be their own unique subtype.


9

Very little really dies on the internet. Archive.org just happens to have one single snapshot of that blog post from when it was live. Copied here: Some remedial computer science, for the PCI auditors in my audience. I hand you an array of random integers. How can you tell if the number three is in it? Well, there’s the obvious way: check ...


7

If you are new to C++, it may be desirable to shy away from doing big work in a constructor. Constructors are wedded tightly to the way the language behaves, and you really don't want the constructor getting called unexpectedly (explicit is your friend!). Constructors are also rather unique in that they cannot return a value. This can make error handling ...


5

By Wikipedia, it looks like your tree is specified by the two properties arborescence and ordered tree (scroll down to find the definition "ordered tree or plane tree.")


5

It's not a good practice to load an object from a file in the constructor. Beyond the good C++ arguments in the other answers, I'd add a clean code principle: a function should do only one thing. Ok, the constructor is not a normal function, but the principle still applies. I suggest the following: keep the Trie as general as possible to aim at reuse. ...


4

A hashtable is an array of buckets, where the bucket index corresponds to the hash values of the keys (modulo the array length). As collisions do happen (two different keys mapping to the same bucket), you need a strategy to deal with that. Here are two popular strategies. Using a list: you design a bucket data structure that supports multiple key/value ...


4

A trie is a data structure where: nodes represent strings that are matched, edges represent transitions of one node to the next based on a given additional character, and the root node corresponds to the empty string that is always a matched when no characters are yet processed . Based on this understanding, and from a theoretical point of view: ...


4

if you encode up the strings into UTF8 you can use the standard 256 branching trie and still be unicode compatible also you should note that only 70 or so characters out of the possible 128 ascii characters (which all encode to 1 byte in UTF8) will be found most heavily you can optimize for that (like include the common digraphs in place of the unused ...


4

The classic answer would be a trie which stores all rotations of words (in scrabble there is a very similar need and a very similar datastructure called a gaddag). It turns out you can do much better (B-tree of words where the lowest level is delta encoded), but the simplest thing you can do is store a sorted list of all rotations of all words in your ...


4

It seems you're searching for a standard Information Retrieval algorithm. Instead of giving you the answer (which depends on factors such as frequency and cardinality of terms and the number of documents, the type of queries asked), I forward you to the excellent introductory treatise on the topic called: Introduction to Information Retrieval: http://nlp....


4

You're almost certainly overthinking this. Your quest for an ideal data structure is a solution in search of a problem. Look carefully at the example you gave. All three of those dropdowns have a different data source, and they imply a relational structure. Just by looking at the names of your dropdowns, I know that you have three tables: Groups, Events ...


3

This is very close to a Radix tree. The primary differences are that a normal radix tree wouldn't split on words, so the 'c' in both "cat" and "cow" would be the same node, and it only splits when necessary: The +-------------------------+ | | c dog barks +---------------+ | ...


3

You want to store strings in compressed form (to save space, I guess), but you want fast lookup, is this right? If I were you, I would go for the speed and use a trie (for the first few characters). It has O(log n) lookup, and it will automatically condense common prefixes. A lot depends on the statistics of the strings, like how many there are, and their ...


3

Use a tree, where each node will be a subdomain. The top level will be the start symbol. Then it would branch into k nodes, where k is the number of top level domains you have. For instance, if your entire database was two entities: foo.bar.example.com and boo.car.ample.net, k will be 2 (net and com). Each of net and com nodes will have one children each: ...


2

What are you using this trie for? What is the total number of words that you plan to hold, and what is the sparseness of their constituent characters? And most important, is a trie even appropriate (versus a simple map of prefix to list of words)? Your idea of an intermediate table and replacing pointers with indexes will work, provided that you have a ...


2

Quick Short Answer Pick a regular Tree Structure first, later look for a similar optimized version Long Boring Extended Answer Use a regular Tree Structure first. I read that it seems you try to store the entire path in each node element, and that's one of the reasons your structure may requiere unnecesarily optimization. Note: The following examples ...


2

This is called sharding in MongoDB and partitioning in SQL Server. If the website actually uses “huge amounts of data”, sharding/partitioning is already implemented. You may probably want to rethink what data you actually need to retrieve, how is it used and how do you store it. If you do auto-completion on product names, you probably don't need to retrieve ...


2

A trie itself is a generic term for a data structure that stores keys implicitly as a path. If you google tries, you will see that there are multiple different implementations for a searching data structure where the keys are stored in this way, and thus, there will be different space complexities for each. One that comes to mind from my personal studies ...


2

Data Stores Have two responsibilities: storing data efficiently performing queries/updates efficiently. Hashmaps do not make for a particularly elegant solution to these two problems. HashMaps become less efficient the more dense they become, so an hashmap optimal for retrieval is more than sub-optimal for storage. Conversely a dense hashmap is also ...


2

A B-Tree is a balanced tree structure that ensures a search in logarithmic time and efficient ordered traversal. Each node has more than two children. This helps to achieve a higher performance than binary trees, because it reduces the number of disk accesses and their storage layout can take advantage of block devices. A trie on the other hand is a ...


1

Let w be the amount of words in the trie. Then the boundary O(w*m) is much more useful, since it simply represents the max amount of characters in the trie, which is obviously also it's space boundary. In a way, yes, O(n**m) is a correct boundary too. It's just pretty useless in most cases. For example, w = 200 words with an average length of m = 100 in an ...


1

I don't think I would read a file in the constructor for a couple of reasons: it will significantly slow down object creation and potentially the startup of your program. as you mentioned, there are limited options for error handling. You would have to either put the entire program in a try...catch block or set some sort of flag if something ...


1

You could maintain a separate (or as a part of the NoSQL record) store of hashes of the searchable data. The nature of a hash being non-reversible makes it leak far less information than encrypted strings when you have various amounts of the strings available. Then as queries come in, you just hash the query request information and match on hashes. This ...


Only top voted, non community-wiki answers of a minimum length are eligible