Spell Checker [OUI - 2019]

Spell Checker implementation for DSA course. (Data Structures & Algorithms)

• 🗾 Custom HashMap implementation

• 🌴 Okasaki RedBlack Trees

• ❔ Basically hashes one file as dictionary and checks other file with it

What is it you say?

This project tries to accomplish:

• 😳 Adhering to OOP programming style [~40%]
• 😌 Implementing custom HashMap [~90%]
• 😧 Implementing custom RedBlack Tree [~60%]
• 😃 Basic file I/O usability [~80%]

Implementation details:

• MajellaMap - Open adressed HashMap

  • Uses Round Robin linear probing with log2n limit
  • Uses MurMurHash3 to hash (currently can hash only strings)
  • Uses Fibbonachi Hashing to map the values to current size
  • Operates with immutable map cells
  • Doesn't know how to decrease its size after expanding

• OkasakiRBTree - Okasaki funcitonal RedBlack Tree

  • Follows Chris's original algorithms for addition
  • Sadly is NOT, fully functional (in design), uses highly mutable objects as nodes

A little insight in to some design desision in RedBlack Tree:

Resourses

Here are the most crucial acrticles, that I've used to understand the topics:

• I Wrote The Fastest Hashtable - Insiration on HashMap desing, a lot of cool info. besides that.
• Backward Shift Deletion - Helped visualize the swaps in Robin Hood hashning mechanism
• The Missing Method - Good explanation for deletion method from Okasaki RB Trees
• Algorithms Visualisation - Red Black Tree Visualisation
• Gianmarco De Francisci Morales - Author of hard hitting pic. in description : )

How to run it

Use command line to show the program location of dictionary and text file

$ java -jar spell-checker-1.0.jar text_file dictionary_file

It will then generate the output file