Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

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 :)

share|improve this answer
    
I took the time and read about it a little and it works like associative array in php, which is awesome. This project is for my college, so using any external libraries would be not good in my case, hence i used <unordered_map>. I would certainly use some sort of SQL if I was doing a bigger and more serious project. Thank you very much for your help, you will all get +1 (when I can), but I will accept this answer since it became handy in my case. :) –  sobol6803 Apr 1 '13 at 13:35
    
SQLite would not require external libraries; support for it is built into PHP. However, I agree that it is overkill for a college assignment. Even so, I would not be surprised if some of your classmates used SQLite for such an assignment. –  Brian Apr 2 '13 at 17:27
    
@Brian, I said, that the <unordered_map> works like associative array in php. I'm not using php, I'm using C++. :) –  sobol6803 Apr 2 '13 at 19:34
add comment

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.

share|improve this answer
    
If you're going to use a DB, consider using more than two columns. For example, adding support for bi-directional soundex matching might make things much more usable. –  Donal Fellows Mar 31 '13 at 20:27
    
Adding support for soundex matching is something the OP would potentially want whether using a DB or not. –  Brian Mar 31 '13 at 21:13
add comment

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.

share|improve this answer
    
I don't think the first approach really makes sense for the OP's purposes. You can still use external tools even with a simple database like SQLite. However, based on the OP's question, none of the major benefits of an external database are needed. The bottom half of SQLite: When To Use enumerates these benefits. I do agree with you that a HashMap is not necessarily the optimal choice for a data structure. –  Brian Mar 31 '13 at 20:49
    
Using a full database depends on what the requirements really are and how the application will grow. Will "part of speech" become part of the data set for the application? Or the plural/singular nature? Is there already a database in the vicinity (a CRM for which this is the front end with the field translations)? These questions come into play. The full shape of the problem hasn't yet been defined. I will certainly admit to adding a full on mysql database is probably overkill, unless there are other things that need to be done too or it is already there. –  MichaelT Apr 1 '13 at 0:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.