1

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?
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”.

  • Really appreciate your.detailed explanation. I learn a lot from the description of your thought process. – McBear Holden Nov 10 '18 at 19:49
  • You've mentioned effecicient to load binary file format. What makes a binary file efficient to load? Do you mean the parsing complexity? – McBear Holden Nov 10 '18 at 19:54
  • 1
    @McBearHolden Usually the program has to first parse the complete file into a data structure before performing any queries. With a suitable binary format, the on-disc format is identical to the in-memory data structure. I can skip the parsing step. That means I also don't have to load the complete file first, but it's sufficient to only load relevant pages of the file. This is much more complicated than ordinary parsing and there can be important portability and security concerns, but when done correctly (as is the case for most databases) then we get significant performance improvements. – amon Nov 10 '18 at 20:24
  • what programming books discuss stuff like.this? System programming? – McBear Holden Nov 10 '18 at 20:41
  • 1
    @McBearHolden I'm not much of a book-learning person so I don't have any recommendations. System programming might include efficient I/O or low-level tricks to avoid parsing, but it's a very broad term that also includes lots of boring stuff. Learning a bit of C is useful, I guess – if only to understand POSIX APIs or to read source code of systems-level software. While writing my discussion of file formats in the answer, I had the Textuality chapter from ESR's The Art of Unix Programming (2003) in mind. – amon Nov 10 '18 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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