The best way to store dictionary from file

Question

I'm working on a translator in C++. Basically I want to parse the file with translations and store it in my program, so I can perform search through the words and simply access the corresponding word. My file will look like that:

word|translation
second word|second translation

etc. It doesn't have to be | as delimiter and the word can contain spaces. So after I store it in my program I want to search for a word and get the corresponding word easily.

The question is, what is 'the best' way to store this dictionary? Should I use dynamic structures and link them? Maybe vectors? Or should I use two-dimensional array to store the 2 strings? Could you please propose to me how the structure will look like?

Answer 1

Since you're going to search by the first word, I'd suggest using a Hashmap.

A Hashmap is designed to solve exactly this issue: Search for a complicated key; It's also sometimes referred to as "Dictionary," so you know it's about this. It works by defining a function (Which is called "hash function") from the key-domain ("word" in your dictionary) to int, and then use these ints as the position in an array, where it stores both original key and value ("word" and "translation"). If your input is identical to some key, then the result of the hash function will give you the right int key, and you can complete your search very fast.

For more information: http://en.wikipedia.org/wiki/Hashmap

Good luck :)

Answer 2

One solution to consider is a SQLite database. SQLite, in contrast to most other databases, works well as a self-contained database within an application. It gives you immediate support for serializing your dictionary to disk, querying your dictionary in many ways, etc.

SQLite is a higher level construct than a Hashmap; it comes with more of the functionality your application will need, thus reducing the amount of implementation work in your application.

If you are already familiar with SQL, SQLite is generally an immediate win as an alternative to ad-hoc file formats.

Answer 3

The three main approaches to this have fundamentally different approaches and it really depends upon what your requirements are.

You've got a dictionary of some sort. In many languages, dictionary is synonymous with Map and that will lead us down the different paths.

The first approach is to use a database of some sort. You could store this in an actual database external to the system - Oracle, MSSQL, MySQL, PostgreSQL just being the big names that come to mind. With this approach, the database engine does all the work looking up things and completely external to your application. This has the benefit that it is possible to work with it with external tools, but has the side bit that it itself is an external tool.

Next is the simpler embedded databases. Berkley Database, optionally through SQLLite as a layer to make accessing the data a bit more familiar to the SQL family. The Berkley Database itself will fill the role of key value pairs (its a simple hash map behind the scenes). This means getting other libraries (but not tools) to store your data.

Realizing that this is a dictionary of text there are specific data structures that are optimized to processing text structures. The trie is a specialized tree for working with text. This is just one of many data structures - the specifics of it really depend on what you are doing with your data once you have it. The hash map is another way to store the data after it has been read (and there are many forms of the hash map too).

You may find that something else works better - it depends on what you are doing, how much data you have, the ratio of reads to writes (are there any writes at all?), knowing the size of the data before hand or not, if you want to be able to search on partial data, etc... All of these things should come into play in choosing the correct data structure.