Dictionary Application: Suggestions for serialization format and data structure

Question

I want to create a dictionary application. One of the design guideline is performance in querying and showing up the definitions of words.

I would like some suggestions on two design choices:

1. Which serialization format should I choose? I'm thinking of JSON(or YAML)I checked on popular opensource dictionary applications(stardict, freedict, goldendict etc.) None of the above software choose this format. Most often they use their own specific format. Could anyone explain why this is so?
2. What data structure could I choose? Whatever dictionary format is chosen, after loading the dictionary file into memory, it should be stored in some kind of data structure. For fast searching I assume this could be hash table or tree?

Answer 1

First, consider an existing database system such as SQLite. This will get you efficient search data structures without a lot of programming effort, and can even query data without having to completely load it into memory first. The data is also stored in an efficient-to-load binary format.

If that is not an option and you have to implement everything yourself (e.g. for a study project), ask yourself how the files will be modified.

• If the files may be edited by humans, prefer an easy to edit format like YAML or XML.
• If the files will only be edited by your program, prefer an easy to manipulate format like JSON, XML, or CSV. You could also use a custom file format.

Why?

• YAML is an extremely complex format with very tricky edge cases. No parser supports the spec precisely. However, the most important parts of the syntax are very obvious for humans, and the format allows comments. But these comments are not part of the document model and will not round-trip: if your application reads a file with comments, modifies the data structure, and writes it back, then any comments are lost.
• JSON looks like a simple, friendly format, but has some gotchas. E.g. it does not allow any comments, the order of keys is not specified, and JSON's support for numbers is underspecified (e.g. it doesn't necessarily distinguish between integers and floats).
• XML is a quite complex format, but there is very good software support and it is OK as a human-editable format. XML may not be the best choice, but it won't be the wrong choice.
• A custom file format can be a great solution if you are somewhat experienced with designing file formats and parsing. But using an existing format gets you a parser for free, which also avoids many difficult topics such as Unicode characters. While many applications do specify their own format, this is not generally advisable.

Once you have the data, you will want to organize it in a way that is easy to query. What kind of queries you need to perform determines the data structure. A few examples:

• If you want to show an alphabetical list of all dictionary entries, an ordered data structure like a sorted array or a binary search tree would be appropriate. This will also help if you need to search by the prefix of an exact term.
• If you need fast lookup of a term, given that term's exact name, then a hash table or a binary search tree would be appropriate.
• Things get more difficult for fuzzy searches, for example by rough entry name or when searching the body of a dictionary entry. This is something where using existing software will be very useful.
• In the worst case you'll just have to scan all your data. This might not actually be that bad unless you need very quick responses or have huge amounts of data.

You can combine different data structures. E.g. you can keep your main records in an ordered data structure but also index them with a hash table, or precompute an index for full-text searches. One very useful data structure for some applications is a bloom filter, which is a probabilistic set data structure with a tunable error rate. Before performing an expensive query you can ask the bloom filter whether such an element even exists, and it will answer “no” or “perhaps”.